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

Можно проверить, что ( x )  1 на отрезке 2;  1 , т.е. достаточные условия сходимости выполняются.2. Зададим начальное приближение x ( 0 )  1 . Решим задачу с различной точностью 1 и  2 .3,4. Выполним расчеты по формуле:x k 1 3x k   1 , k  0,1, 2,...Результаты расчетов приведены в табл. 1.Таблица 1kx (k )x (k )  x (k 1)0-1,000-12345-1,2599-1,3123-1,3223-1,3243-1,32460,25990,05240,01000,00200,0003Если 1  0,01 , то x   1,3223 , а если  2  0,001 , то x   1,3246 .Пример 2.

Найти корни уравнения x 3  x 2  9 x  9  0 методом простых итераций с точностью   0,001 . I. Отделить корни уравнения x 3  x 2  9 x  9  0 . Уравнение имеет три корня, среди которых по крайней мере один действительный.Преобразуем уравнение к равносильному виду: x 3  x 2  9 x  9 . Найдем абсциссы точек пересечения графиков y  x 3 и y  x 2  9 x  9 (на рис. 2 указаны дваиз трех полученных промежутков).Результат отделения корней – три промежутка [0,5; 2] , [2; 4] , [ 4;  2] .Заметим, что отрезки могут быть сужены, например, вместо отрезка [2; 4] можно принять [2,5; 4] .233y4y  x32024xy  x 2  9x  9Рис. 3II.

Преобразуем уравнение к виду x  ( x ) : x  3 x 2  9 x  9 .Можно показать, что на отрезках [2; 4] , [ 4;  2] функция ( x )  3 x 2  9 x  9удовлетворяет условию ( x )  1 . На отрезке [0,5; 2] используем другой вид уравнеx3 x2x3 x2ния: x  1 . Также легко проверить, что функция ( x )  1 удов9999летворяет достаточному условию сходимости на отрезке [0,5; 2] .2. В качестве начальных приближений выберем:– точку x (0 )  2 на отрезке [ 4;  2] ;– точку x (0 )  0,5 на отрезке [0,5; 2] ;– точку x (0)  2 на отрезке [2; 4] .В поставленной задаче   0,001 .3,4. Выполним расчеты по формуле x k 1  3 x k 2 9 x k   9 , k  0,1,2,... ,с начальными значениями x (0 )  2 и x (0)  2 и по формуле 3  x k  2  1 , k  0,1,2,...

,x k x k 1 99с начальным значением x (0 )  0,5 . Результаты расчетов занесены в табл. 2-4.234Таблица 2kx (k )Таблица 3x (k )  x (k 1)02,0000-12,35130,351322,60560,254332,76940,163842,86820,098852,92550,057362,95820,032772,97670,018582,98700,010292,99270,0057102,99590,0032112,99770,0018122,99870,0010kx (k )x (k )  x (k 1)012345-2,0000-2,8438-2,9816-2,9979-2,9997-2,999970,84380,13780,01630,00180,00027Таблица 4k01234x(k )0,500000,986110,998490,999830,99998x(k ) x (k 1)0,48610,012380,001340,00015В результате получены приближенные значения корней: x1  2,99997 ,x 2  0,99998 , x 3  2,9987 .Обратим внимание на сильное различие в числе итераций, потребовавшихся длянахождения корней x   3 (табл.

2) и x   3 (табл. 3), с помощью одной и той жеформулы. Заметим, что в окрестности корня x   3 значения модуля производнойфункции ( x )  3 x 2  9 x  9 равны: (2)  0,784 ; (2,3513)  0,673 ;(2,6056)  0,618 ; (2,9977)  0,556 . С другой стороны, в окрестности корняx   3 имеем: (2)  0,206 ; (2,8438)  0,124 ; (2,9977)  0,111 . Анализ ре-зультатов показывает, что чем меньше значения модуля производной (x ) , тем быстрее сходимость.

235Б. МЕТОД НЬЮТОНАМетод Ньютона (метод касательных) является одним из наиболее популярныхчисленных методов. Он реализуется по формуле:x (k 1)  x (k ) f ( x (k ) )f ( x (k ) ), k  0,1, 2,...yBf ( x (0 ) )y  f (x )a0CxAx ( 2)x (1)bx (0 )xРис. 4В точке x (0) строится касательная к графику функции. Следующей точкой x (1)является точка пересечения касательной с осью абсцисс. Далее процесс продолжаетсяаналогично.Теорема (о достаточных условиях сходимости метода Ньютона).Пусть выполняются следующие условия:1.

Функция f ( x ) определена и дважды дифференцируема на a, b  .2. Отрезку a, b  принадлежит только один простой корень x  , так чтоf (a )  f (b )  0 .3. Производные f ( x ), f ( x ) на a, b  сохраняют знак, и f ( x )  0 .4. Начальное приближение x (0 ) удовлетворяет неравенствуf ( x (0) )  f ( x (0) )  0 (знаки функций f ( x ) и f ( x ) в точке x ( 0 ) совпадают).Тогда с помощью метода Ньютона можно вычислить корень уравненияf ( x )  0 с любой точностью.236Методика решения задачиШаг 1.

Задать начальное приближение x (0) так, чтобы выполнялось неравенство f ( x (0) )  f ( x (0) )  0 , а также малое положительное число  . Положить k  0 .Шаг 2. Вычислить x (k 1) по формулеx (k 1)  x (k ) f ( x (k ) )f ( x (k ) ).Шаг 3. Если x (k 1)  x (k )   , процесс завершить и положить x   x (k 1) .Если x (k 1)  x (k )   , положить k  k  1 и перейти к п.2.Пример 3.

Методом Ньютона найти корень уравнения x 3  x  1  0 . В примере 1 корень был отделен: x    2;  1.1. Зададим начальное приближение x (0 ) . Так как f ( x )  3x 2  1 , f ( x )  6 x ,то f ( 2)  5 , f ( x )  0 при x   2;  1 . Поэтому f (2) f (2)  0 и x (0 )  2 .Положим   0,001 .2,3. Результаты расчетов по формуле:x(k 1)x(k )x   x  1 , k  0,1,... ,3x   1(k ) 3(k )(k ) 2приведены в табл.

5.Таблица50kx (k )x (k )  x (k 1)-2,0000-12345-1,545455-1,359615-1,325801-1,324719-1,3247180,4545450,1858400,0338140,0010820,000001Найденное приближенное решение x   1,3247 2. Пример 4. Найти корни уравненияx 3  x 2  9x  9  0методом Ньютона с точностью   0,001 . Процедура отделения корней была выполнена в примере 2. В качестве отрезков [ai , bi ] , которым принадлежат корни уравнения, выберем [ 4;  2] , 2,5; 4 ,[0,5; 2] .Так как f ( 4)  3,5 ; f ( 2)  15 , т.е. f ( 4) f (2)  0 , производныеf ( x )  6 x  2  0 , f ( x )  3x 2  2 x  9  0 сохраняют знак при x   4;  2 , то условия сходимости выполняются.237Так как f (2,5)   4,125 ; f (4)  21 , т.е.

f (2,5) f (4 )  0 , и производныеf ( x )  0 , f ( x )  0 сохраняют знак при x  2,5; 4 , то условия сходимости на этомотрезке тоже выполняются.Так как f (0,5)  4,375 ; f (2)  5 , т.е. f (0,5) f (2)  0 , и производныеf ( x )  0 , f ( x )  0 сохраняют знак при x  0,5; 2 , то условия сходимости выполняются.1. Зададим начальные приближения: на отрезке [0,5; 2] выберем x (0 )  0,5 , таккак f (0,5)  f (0,5)  0 ; на отрезке [ 4,  2] выберем x (0)   4 , так какf (4)  f (4)  0 ; аналогично на отрезке 2,5; 4 выберем x (0)  4 .

В поставленной задаче   0,001 .2,3. Результаты расчетов по формуле:x(k 1)x(k )x   x   9x  9 ,3 x   2 x9(k ) 3(k ) 2(k )(k ) 2(k )k  0,1,... ,приведены в табл. 6–8.Таблица 60k1- 4,00000x (k )x (k )  x (k 1)-234-3,255319-3,023383-3,000225-3,0000000,7446810,2319360,0231580,000225Таблица 7k0123x (k )0,50000,9729730,99982461,0000000x (k )  x (k 1)-0,4729730,02685160,0001754Таблица8kx (k )x (k )  x (k 1)x204,0000-123453,3225813,0514843,0016743,0000023,00000,67741940,27109690,0498090,0016712  10 6В результате получены приближенные значения корней: x 1  3,0000 ; 1,0000 ; x 3  3,0000 .238В.

МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯМетодика решения задачиШаг 1. Найти начальный интервал неопределенности L0  a0 , b0  одним из методов отделения корней, задать малое положительное число  . Положить k  0 .Шаг 2. Найти середину текущего интервала неопределенности:ck ak  bk2.Шаг 3. Если f (ak )  f (ck )  0 , то положить ak 1  ak , bk 1  ck , а еслиf (ck )  f (bk )  0 , то принять ak 1  ck , bk 1  bk . В результате находится текущийинтервал неопределенности Lk 1  ak 1 , bk 1 .Шаг 4. Если bk 1  ak 1   , то процесс завершить: x   Lk 1  ak 1 , bk 1  .a bk 1.Приближенное значение корня можно найти по формуле x   k 12Если bk 1  ak 1   , положить k  k  1 и перейти к п.2.Пример 5.

Найти корень уравнения x 3  x  1  0 методом половинного деления с точностью 1  0,01 и  2  0,0005 . I. Результат отделения корня уравнения x   [  2;  1 ] , поэтомуa0  2 , b0  1 .II. Функция непрерывна на отрезке  2;  1 , имеет единственный простой корень. На концах отрезка функция имеет значения f (2)  5 , f (1)  1 , противоположные по знаку. Результаты расчетов приведены в табл.

9.k01234567891011f (a k )-5-0,875-0,875-0,224-0,224-0,08-0,015-0,015-0,015-0,007-0,0025-0,0003ak-2-1,5-1,5-1,375-1,375-1,34375-1,3282-1,3282-1,3282-1,3263-1,3253-1,3248bk-1-1-1,25-1,25-1,3125-1,3125-1,3125-1,3204-1,3243-1,3243-1,3243-1,3243f (bk )110,29650,29650,050,050,050,0180,00180,00180,00180,0018ck ak  bkТаблица 9f (c k )bk  a k2-1,5-1,25-1,375-1,3125-1,34375-1,3282-1,3204-1,3243-1,3263-1,3253-1,3248--0,8750,2965-0,2240,05-0,08-0,0150,0180,0018-0,007-0,0025-0,0003-10,50,250,1250,06250,031250,01560,007810,00390,0020,0010,0005Если 1  0,01 , корень x    1,3282;  1,3204 , а если  2  0,0005 – корень239x    1,3248;  1,3243 или x  x  1,3282  1,3204 1,3243 при 1  0,01 ;2 1,3248  1,3243 1,3245 при  2  0,0005 .

2Пример 6. Найти корень уравнения x 3  x 2  9 x  9  0 методом половинногоделения с точностью   0,01 . Уточним корень, лежащий на отрезке 2,5; 4 . Результаты расчетов поместимв табл. 10.Таблица10k012345678f (a k )-4,125-4,125-1,3769-1,3769-0,3672-0,3672-0,0933-0,0933-0,02349ak2,52,52,8752,8752,96872,96872,99212,99212,99804bk43,253,253,06253,06253,01563,01563,00393,0039f (bk )213,51563,51560,78150,78150,18940,18940,04690,0469ck ak  bkf (c k )bk  a k3,5156-1,37690,78149-0,36720,18945-0,09330,0469-0,023490,0116471,50,750,3750,18750,093750,046870,023440,011720,0058623,252,8753,06252,968753,015622,992183,00392,998043,00097В результате найден интервал 2,99804; 3,0039 и приближенное значение корняx   3,00097 .Аналогично могут быть найдены интервалы, содержащие остальные корниуравнения.240.