Комплект заданий по численным методам - (реферат)
p>2. В процессе решения принимать меры, уменьшающие возможность по явления новых ненулевых элементов.3. Вычисления производить только с ненулевыми элементами.
Разреженный строчный формат
Это одна из широко используемых схем для хранения разреженных матриц, которая предъявляет минимальные требования к памяти и очень удобна для выполнения основных операций с матрицами.
Значения ненулевых элементов и соответствующие столбцовые индексы хранятся по строкам в двух массивах: NA и JA. Для разметки строк в этих массивах используется массив указателей IA, отмечающих позиции массивов AN и JA, с которых начинается описание очередной строки. Пос ледняя цифра в массиве IA содержит указатель первой свободной позиции в JA и AN. Рассмотрим конкретный пример, который будет также и далее применятся для демонстрации других операций и который был использован в качестве контрольного примера для программы, выполняющей основные операции с разреженными матрицами.
- ¬
¦ 3 0 0 5 0 ¦ Позиция: 1 2 3 4 5 6 7 8 9 10
¦ 0 4 0 0 1 ¦ IA: 1 3 5 7 9 11
A = ¦ 0 0 8 2 0 ¦ JA: 1 4 2 5 3 4 1 4 2 5
¦ 5 0 0 6 0 ¦ AN: 3 5 4 1 8 2 5 6 7 9
¦ 0 7 0 0 9 ¦
L
Данный способ представления называется полным (так как представ лена вся матрица А) и упорядоченным (так как элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов). Обознача ется RR(c)O - Row-wise representation Complete and Ordered (англ. ). Массивы IA и JA представляют портрет матрицы А. Если в алгоритме разграничены этапы символической и численной обработки, то массивы IA и JA заполняются на первом этапе, а массив AN - на втором.
Транспонирование разреженной матрицы
Пусть IA, JA, AN - некоторое представление разреженной матрицы. Нужно получить IAT, JAT, ANT - разреженное представление транспониро ванной матрицы. Алгоритм рассмотрим на нашем примере:
IA = 1 3 5 7 9 11
JA = 1 4 2 5 3 4 1 4 2 5
AN = 3 5 4 1 8 2 5 6 7 9
Символический этап.
1. Заводим 5 целых списков по числу столбцов матрицы А. пронуме руем их от 1 до 6.
2. Обходим 1 строку и заносим 1 в те списки, номера которых ука заны в JA:
1: 1
2:
3:
4: 1
5:
3. Обходим вторую строку, вставляя аналогичным образом 2:
1: 1
2: 2
3:
4: 1
5: 2
В итоге получим:
1: 1 4
2: 2 5
3: 3
4: 1 3 4
5: 2 5
Массив ANT можно получить, вставляя численное значение каждого ННЭ, хранимое в AN, в вещественный список сразу после того, как соот ветствующее целое внесено в целый список. В итоге получим:
IAT = 1 3 5 6 9 11
JAT = 1 4 2 5 3 1 3 4 2 5
ANT = 3 5 4 7 8 5 2 6 1 9
Произведение разреженной матрицы и
заполненного вектора-столбца
Алгоритм рассмотрим на нашем конкретном примере:
IAT = 1 3 5 7 9 11
JAT = 1 4 2 5 3 1 3 4 2 5
ANT = 3 5 4 7 8 5 2 6 1 9
B = ( -5 4 7 2 6 )
Обработка 1 строки:
Просматриваем массив IA и обнаруживаем, что первая строка матрицы А соответствует первому и второму элементу массива JA: JA(1)=3, JA(2)=4, то есть ННЭ являются a 411 0 и a 414 0.
Просматриваем массив AN и устанавливаем, что a 411 0=3 и a 414 0=5. Обращаемся к вектору B, выбирая из него соответственно b 41 0=-5 и b 44 0=2.
Вычисляем C 41 0= 3 * (-5) + 5 * 2 = -5.
Абсолютно аналогично, вычисляя остальные строки, получим:
C = (-5 58 56 1 58).
Произведение двух разреженных матриц
Рассмотрим метод на конкретном примере. Предположим, что нам не обходимо перемножить две матрицы:
IA = 1 3 5 7 9 11
JA = 1 4 2 5 3 4 1 4 2 5
AN = 3 5 4 1 8 2 5 6 7 9
IAT = 1 3 5 7 9 11
JAT = 1 4 2 5 3 1 3 4 2 5
ANT = 3 5 4 7 8 5 2 6 1 9
Суть метода состоит в том, что используя метод переменного перек лючателя и расширенный вещественный накопитель, изменяется порядок на копления сумм для формирования элементов матрицы С. Мы будем формиро вать элементы C 4ij 0 не сразу, а постепенно накапливая, обращаясь только к строкам матрицы B.
Символический этап.
Определяем мерность IX = 5
IX = 0 0 0 0 0
1-я строка матрицы JAT: 1 4
JA(1) = 1 4 JC(1) = 1 4
IX = 1 0 0 1 0
JA(4) = 1 4
IX(1) = 1 ? Да. JC(1) - без изменений
IX(4) = 1 ? Да. JC(1) - без изменений
2-я строка матрицы JAT: 2 5
JA(2) = 2 5 JC(2) = 2 5
IX = 1 2 0 1 2
JA(5) = 2 5 -> JC(2) - без изменений
......
4-я строка матрицы JAT: 1 3 4
JA(1) = 1 4 JC(4) = 1 4
IX = 4 2 2 4 2
JA(3) = 3 4
IX(3) = 4 ? Нет. JC(4) = 1 4 3
IX(4) = 4 ? Да. JC(4) - без изменений
......
в итоге получим:
IC = 1 3 5 7 10 12
JC = 1 4 2 5 3 4 1 4 3 2 5
Численный этап.
X = 0 0 0 0 0
1-я строка: JC(1) = 1 4
AN(1) = 3 5,
AA = 3
ANT(1) = 3 5
AA * ANT = 9 15
X = 9 0 0 15 0
AA = 5
ANT(1) = 3 5
AA * ANT = 15 25
X = 24 0 0 40 0
CN(1) = 24 40
......
Аналогично проделывая действия над другими строками получим:
IC: 1 3 5 7 10 12
JC: 1 4 2 5 3 4 1 4 3 2 5
CN: 24 40 20 35 80 0 55 22 66 16 144
Все вышеприведенные операции были получены на компьютере и ре зультаты совпали для нашего контрольного примера. Описание программы на языке 2 C 0, занимающейся этими операциями не приводится, так как дан ная программа нами не разрабатывалась, однако в приложении присутству ет распечатка этой программы.
2ПРАКТИЧЕСКАЯ ЧАСТЬ. ОПИСАНИЯ ПРОГРАММ.
1. ЯВНЫЕ МЕТОДЫ.
Данная группа представлена 3 программами, реализующими методы Эй лера, Рунге-Кутта 2-го и 4-го порядков. В данной группе все программы индентичны, поэтому далее следует описание программы, реализующем ме тод Эйлера, с указанием различий для методов Рунге-Кутта 2-го и 4-го порядков.
1EILER. M
Головной модуль.
Входные и выходные данные: отсутствуют.
Язык реализации: PC MathLab
Операционная система: MS-DOS 3. 30 or higher
Пояснения к тексту модуля:
Стандартный головной модуль. Происходит очистка экрана, задание начальных значений по времени и по Y. Затем происходит вызов подпрог раммы EIL. M (RG2. M или RG4. M для методов Рунге-Кутта 2 и 4 порядков) а после получения результатов строятся графики.
1EIL. M
Вычислительный модуль.
Входные данные:
FunFcn - имя подпрограммы, написанной пользователем, которая возвращает левые части уравнения для определенного момента времени. T0, Tfinal - начальные и конечные моменты времени.
Y0 - начальные значения.
Выходные данные:
Tout - столбец времени
Yout - столбцы решений по каждой координате
Язык реализации: PC MathLab
Операционная система: MS-DOS 3. 30 or higher
Пояснения к тексту модуля:
Данный модуль и реализует собственно метод Эйлера (Рунге-Кутта 2 или 4-го порядков). В начале происходит инициализация внутренних пере менных, а также вычисление максимального шага, который затем использу ется для определения точности. Далее следует цикл While.... End внутри которого и выполняются все необходимые действия: по формуле (для каж дого метода своя! ) вычисляется значение Y на каждом шаге (при необхо димости вызывается подфункция FunFcn) а также формируются выходные значения Tout и Yout. Далее метод сам корректирует свой шаг, по форму ле описанной выше (в теоретическом разделе). Этот цикл выполняется до тех пор, пока значение Tfinal не будет достигнуто. Все выходные значе ния формируются внутри данного цикла и поэтому никаких дополнительных действий не требуется. В связи с этим с окончанием цикла заканчивается и подпрограмма EIL. M. Методы Рунге-Кутта реализованы аналогично, с учетом отличий в формулах вычислений (более сложные по сравнению с ме тодом Эйлера).
2. НЕЯВНЫЕ МЕТОДЫ.
