Неявные методы решения системы уравнений ОДУ

         Ошибка аппроксимации Е 5a 0 = k*h 4m 55 0. 
 

2. МЕТОДЫ РЕШЕНИЯ  НЕЛИНЕЙНЫХ САУ 

2.1. МЕТОД НЬЮТОНА 

     Итерационная формула метода  Ньютона имеет вид

                     X 5m+1 0=X 5m  0- 5  0J 5-1  0* 5  0(X 5m 0) 5  0* 5  0F(X 5m 0),

     где J(X)=F 4x 5| 0/ 4x=xm

     Характеристики метода:

     1. Сходимость. Покажем, что в точке  P(G 4x 5| 0(X 5* 0))=0

     Здесь G(x)=X  - J 5-1 0(x) * F(x) - изображение итерационного процес-

са. Условие  сходимости метода:  P(G 4x 5| 0(X)) < 1 должно  выполняться для всех значений  X 5m 0.  Это условие осуществляется при достаточно жестких требованиях к F(x):  функция должна быть непрерывна и дифференцируема по X, а также выпукла или вогнута вблизи X 5* 0. При этом выполняется лишь условие локальной сходимости.  Причем можно показать,  что чем ближе к X 5* 0, тем быстрее сходится метод.

     2. Выбор начального приближения  X 50 0 - выбирается достаточно близко

к точному  решению.  Как именно близко - зависит  от скорости изменения

функции F(x) вблизи X 5* 0:  чем выше скорость,  тем меньше  область,  где

соблюдается условие  сходимости и следовательно  необходимо ближе выби-

рать  X 50 0 к X 5* 0.

     3. Скорость сходимости определяется  соотношением

                  ¦E 5m+1 0¦ = C 4m 0 * ¦E 5m 0¦ 51+p 0,  0 < P < 1.

     При X -> X 5* 0 величина P -> 1. Это значит, что вблизи точного реше-

ния скорость сходимости близка к квадратичной.  Известно,  что  метода

Ньютона сходится на 6-7 итерации.

     4. Критерий окончания итераций - здесь могут использоваться  кри-

терии точности, то есть максимальная из норм изменений X и F(x). 

                 2.2.       ДИСКРЕТНЫЙ МЕТОД НЬЮТОНА 

     Трудность использования метода  Ньютона состоит в

     1. Необходимости вычисления на  каждом этапе J=F 4x 5| 0.

     Возможно несколько путей решения:

     - аналитический способ. Наиболее  эффективен, однако точные форму-

лы могут  быть слишком большими, а также  функции могут быть заданы таб-

лично.

     - конечно-разностная аппроксимация: 

       dF 4i 0   F 4i 0(x 41 0,...,x 4j 0+dx 4j 0,...,x 4n 0) - F 4i 0(x 41 0,...,x 4j 0-             dx 4j 0,...x 4n 0)

       -- = ______________________________

       dX 4j 0                           2*dX 4j 

     В этом случае мы имеем уже  дискретный метод Ньютона,  который  уже

не обладает квадратичной сходимостью. Скорость сходимости можно увели-

чить, уменьшая dX 4j 0 по мере приближения к X 5* 0.

     2. Вычисление матрицы J 5-1 0 на каждом шаге требует значительных вы-

числительных  затрат, поэтому часто решают такую  систему:

                         dX 5  0= 5  0J 5-1 0(X 5m 0) 5  0* 5  0F(X 5m 0)

     или умножая правую и левую  часть на J, получим:

                         J(X 5m 0) 5  0* 5  0dX 5m  0= 5  0F(X 5m 0)

     На каждом M-ом шаге матрицы J и F известны. Необходимо найти dX 5m 0, как решение вышеприведенной системы линейных АУ, тогда

                             X 5m+1 0=X 5m 0+dX 5m

     Основной недостаток  метода  Ньютона  - его локальная сходимость,

поэтому рассмотрим еще один метод. 

               2.3. МЕТОД ПРОДОЛЖЕНИЯ РЕШЕНИЯ ПО ПАРАМЕТРУ 

     Пусть t - параметр,  меняющийся от 0 до 1.  Введем в рассмотрение

некоторую систему

                              H(X,t)=0,

     такую, что:

     1. при t=0 система имеет решение X 50

     2. при t=1 система имеет решение X 5*

     3. вектор-функция H(X,t) непрерывна по t.

     Вектор функция может быть  выбрана несколькими способами,  например

                        H(X,t) = F(X) + (t-1)

                                 или

                          H(X,t) = t * F(X)

     Нетрудно проверить, что для  этих вектор-функций выполняются  усло-

вия 1-3.

     Идея метода состоит в следующем:

     Полагаем t 41 0= 7D 0t и решаем систему H(X,t 41 0)=0 при выбранном X 50 0. Полу-

чаем  вектор  X 5t1 0.  Далее берем его в качестве начального приближения и

решаем  при новом t 42 0=t 41 0+ 7D 0t систему H(X,t 42 0)=0,  получаем X 5t2 0 и так далее

до тех  пор, пока не будет достигнута заданная точность. 

                  2.4. ТЕХНОЛОГИЯ РАЗРЕЖЕННЫХ МАТРИЦ 

     Основные требования к этим  методам можно свести в 3 утверждения:

     1. Хранить в памяти только ненулевые  элементы.

     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.