5. Итерационные методы решения систем линейных алгебраиче-ских уравнений. Численные методы решения нелинейных уравнений (8 практических занятий с сайта кафеды 805)

Занятие 5. МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХАЛГЕБРАИЧЕСКИХ УРАВНЕНИЙПОСТАНОВКА ЗАДАЧИРассматривается проблема решения систем линейных алгебраических уравнений (СЛАУ), записываемых в видеAx  bили a11  a1n   x1   b1               ,   a n1  ann   x n   bn где A  (ai j )  R n  n – действительная матрица размеров (n  n) , i , j – переменные,соответствующие номерам строк и столбцов (целые числа); b  (b1 ,..., bn )T  R n –вектор-столбец размеров (n  1) , x  ( x1 ,..., x n )T  R n – вектор-столбец неизвестных,R n – n -мерное евклидово пространство, верхний индекс " T " здесь и далее обозначаетоперацию транспонирования.Требуется найти решение x   ( x 1 ,..., x  n )T  R n системы, подстановка кото-рого в систему приводит к верному равенству A x   b .А.

МЕТОД ПРОСТЫХ ИТЕРАЦИЙМетодика решения задачиШаг 1. Преобразовать систему Ax  b к виду x  x   одним из описанныхспособов.x (0 )Шаг 2. Задать начальное приближение решения x (0) произвольно или положить  , а также малое положительное число  (точность).

Положить k  0 .Шаг 3. Вычислить следующее приближение x (k 1) по формулеx (k 1)  x (k )   .Шаг 4. Если выполнено условие окончания x (k 1)  x (k )   , процесс завершить и положить x   x (k 1) . Иначе положить k  k  1 и перейти к п.3.Пример 1. Методом простых итераций с точностью   0,01 решить системулинейных алгебраических уравнений:2 x1  2 x 2  10 x 3  14 ,10 x1  x 2  x 3  12 ,2 x1  10 x 2  x 3  13.227 1. Так как 2  2  10 , 1  10  1 , 1  2  10 , условие преобладаниядиагональных элементов не выполняется. Переставим уравнения местами так, чтобывыполнялось условие преобладания диагональных элементов:10 x1  x 2  x 3  12 ,2 x1  10 x 2  x 3  13,2 x1  2 x 2  10 x 3  14 .10  1  1 , 10  2  1 , 10  2  2 .

Выразим из первого уравненияПолучаемx1 , из второго x 2 , из третьего x 3 :x1   0,1  x 2  0,1  x 3  1,2 ,x 2   0,2  x1  0,1  x 3  1,3 ,x 3   0,2  x1  0,2  x 2  1,4 ;Заметим, что1 0  0,1  0,1 1,2  0  0,1  ;    1,3  .    0,2  0,2  0,21,4 0   max  0,2 ; 0,3 ; 0,4   0,4  1 , следовательно, условие сходимости(теорема) выполнено.2. Зададим x(0 )1,2      1,3  . В поставленной задаче   0,01 .1,4  3. Выполним расчеты по формуле x (k 1)  x (k )   :x (k 1)(k ) 0  0,1  0,1   x1  1,2     0,20  0,1    x 2(k )    1,3  , k  0,1,... ,  0,2  0,2  x (k )  1,4 0  3   илиx1(k 1)   0,1x 2(k )  0,1x 3(k )  1,2 ;x 2(k 1)   0,2 x1(k )  0,1x 3(k )  1,3 ;k  0,1,... ,x 3(k 1)   0,2 x1(k )  0,2 x 2(k )  1,4 ;до выполнения условия окончания и результаты занесем в табл.

1.Таблица 1kx1(k )x 2(k )x 3(k )x (k )  x (k 1)0123451,20000,93001,01800,99461,00150,99961,30000,92001,02400,99341,00200,99951,40000,9001,03000,99161,00240,99930,50,130,03840,01080,0027< 22814. Расчет закончен, поскольку условие окончания x (k 1)  x (k )  0,0027  выполнено.Приближенное решение задачи: x   (0,9996 ; 0,9995 ; 0,9993)T . Очевидно, точное решение: x   (1 ; 1 ; 1)T .Б. МЕТОД ЗЕЙДЕЛЯМетодика решения задачиШаг 1.

Преобразовать систему Ax  b к виду x  x   одним из описанныхспособов.Шаг 2. Задать начальное приближение решения x (0) произвольно или положитьx (0)   , а также малое положительное число  (точность). Положить k  0 .Шаг 3. Произвести расчеты по формулеx1( k 1)  11 x1(k )  12 x 2( k )  13 x 3( k )  ...

 1n x n(k )  1 ,x 2( k 1)   21 x1( k 1)   22 x 2(k )   23 x 3(k )  ...   2n x n( k )   2 ,(*)x 3( k 1)   31 x1( k 1)   32 x 2( k 1)   33 x 3( k )  ...   3n x n( k )   3 ,x n( k 1)   n1 x1(k 1)   n 2 x 2( k 1)   n3 x 3( k 1)  ...   nn 1 x n(k11)   nn x n(k )   n .(в каждое последующее уравнение подставляются значения неизвестных, полученныхиз предыдущих уравнений, что показано в записи стрелками)илиx (k 1)  Lx (k 1)  Ux (k )   ,где L,U являются разложениями матрицы  : 0  21L    31  n100 3200 n2 n3000 0 ,  0 11 0U  0 012 220013  1n  23   2n  33   3n  .   0   nn и найти x (k 1) .Шаг 4. Если выполнено условие окончания x (k 1)  x (k )   , процесс завершить и положить x   x (k 1) . Иначе положить k  k  1 и перейти к п.3.229Пример 2.

Методом Зейделя с точностью   0,001 решить систему линейныхалгебраических уравнений:2 x1  2 x 2  10 x 3  14 ,10 x1  x 2  x 3  12 ,2 x1  10 x 2  x 3  13 . 1. Приведем систему Ax  b к виду x  x   так же, как в примере 1:x1   0,1  x 2  0,1  x 3  1,2 ,x 2   0,2  x1  0,1  x 3  1,3 ,x 3   0,2  x1  0,2  x 2  1,4 ;Так как 1 0  0,1  0,1     0,20  0,1  ;  0,2  0,20 1,2     1,3  .1,4   max  0,2 ; 0,3 ; 0,4   0,4  1 , условие сходимости выполняется.2. Зададим x (0)  (1,2; 0; 0)T . В поставленной задаче   0,001 .3.

Выполним расчеты по формуле (*):x1(k 1)   0,1x 2(k )  0,1x 3(k )  1,2 ;x 2(k 1)   0,2 x1(k 1)  0,1x 3(k )  1,3 ;k  0,1,... ,x 3(k 1)   0,2 x1(k 1)  0,2 x 2(k 1)  1,4 ;и результаты занесем в табл. 2.Таблица 2kx1(k )x 2(k )x 3(k )012341,20001,20000,99920,99961,000001,06001,00541,00021,000000,94800,99911,00001,0000x(k ) x (k 1)11,06000,10080,00520,0004< Очевидно, найденное решение x   (1 ; 1 ; 1)T является точным.4.

Расчет завершен, поскольку условие окончания x (k 1)  x (k )  0,0004  выполнено.230ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХУРАВНЕНИЙПОСТАНОВКА ЗАДАЧИПусть дано нелинейное уравнениеf (x )  0 ,(*)где f ( x ) – функция, определенная и непрерывная на некотором промежутке.Этапы решения нелинейных уравненийПервый этап. Находятся отрезки ai , bi  , внутри каждого из которых содержится один простой или кратный корень ( x i  ai , bi  ). Этот этап называется процедуройотделения корней. По сути, на нем осуществляется грубое нахождение корней x i .Второй этап.

Грубое значение каждого корня x i уточняется до заданной точности одним из численных методов, в которых реализуются последовательные приближения.А. МЕТОД ПРОСТЫХ ИТЕРАЦИЙМетодика решения задачиШаг 1. Уравнение f ( x )  0 равносильным преобразованием привести к видуx  ( x ) . Это преобразование может быть осуществлено различными путями, но длясходимости нужно обеспечить выполнение условия ( x )    1 (  – некотораяконстанта). При этом задача сводится к нахождению абсциссы точки пересеченияпрямой y  x и кривой y  ( x ) (рис.

1).yyxy  ( x )0xxРис. 1Шаг 2. Задать начальное приближение x (0 )  [a, b ] и малое положительное число . Положить k  0 .231Шаг 3. Вычислить следующее приближение:x ( k 1)  ( x ( k ) ) .Шаг 4. Если x (k 1)  x (k )   , итерации завершаются и x   x (k 1) . Еслиx ( k 1)  x ( k )   , положить k  k  1 и перейти к п.3.Способы преобразования уравненияПреобразование уравнения f ( x )  0 к равносильному виду x  ( x ) можетбыть выполнено неоднозначно.1.

Можно заменить уравнение f ( x )  0 на равносильное x  x  c f ( x ) , гдеc  const  0 . Тогда, принимая правую часть этого уравнения за ( x ) и раскрывая( x )  1  c f ( x )  1 , получаем условие  2  c f ( x )  0 .2. Можно выразить x из уравнения f ( x )  0 так, чтобы для полученного уравнения x  ( x ) выполнялось условие сходимости ( x )  1 в окрестности искомогокорня.Пример 1.

Найти решение уравнения x 3  x  1  0 методом простых итерацийс точностью 1  0,01 и  2  0,001 . I. Отделим корень уравнения. Уравнение имеет три корня, среди которых покрайней мере один действительный, поскольку это уравнение нечетной степени.Преобразуем уравнение к равносильному виду: x 3  x  1 и найдем точки пересечения графиков y  x 3 и y  x  1 (рис. 2).yy  x3y  x 121011Рис. 2Очевидно, корень уравнения x   [  2;  1 ] .232xII. Преобразуем уравнение к виду x  ( x ) . Для этого запишем его сначала вформе x  x 3  1 . Легко показать, что функция ( x )  x 3  1 не удовлетворяет условию сходимости, поскольку ( x )  3x 2 , ( 2)  12  1 , ( 1)  3  1 . Поэтому воспользуемся другим преобразованием.В результате получим x  3 x  1 .