Численные методы. Ионкин (2013) (1160444), страница 13
Текст из файла (страница 13)
Пусть в (* ) существует и не обращается в ноль непрерывная первая производная функции (): ′ () ̸= 0, ∈ (* ).Разложим (* ) по формуле Тейлора в малой окрестности точки ∈ (* ): (* ) = () + (* − ) ′ () + . . .и отбросим в этом разложении величины, имеющие второй и выше порядок малости по(* − ).Заменив * на +1 и на , получим уравнение ( ) + (+1 − ) ′ ( ) = 0, ∈ Z+ .Учитывая, что ′ ( ) ̸= 0, и разрешив последнее уравнение относительно +1 , имеем:+1 = − ( ), ′ ( ) ∈ Z+ .(2)Определение. Итерационный процесс поиска корня уравнения (1), задаваемый формулой (2), называется итерационным методом Ньютона.Дадим геометрическую интерпретацию метода Ньютона.
Рассмотрим точку (0 , (0 )).Определим первую итерацию 1 рассматриваемого процесса как абсциссу точки пересечения с осью касательной к функции () в точке . Аналогично получаем значение2 как точку пересечения с осью касательной к функции () в точке (1 , (1 )).Продолжая таким образом, на -ом шаге получаем значение , приближающее корень *уравнения (1) с заданной точностью.* 210Выпишем уравнение касательной к функции () в точке : − ( ) = ′ ( )( − ).Очевидно, что значение +1 , найденное по формуле (2), представляет собой абсциссу точкипересечения с осью касательной к кривой = (), проведенной через точку ( , ( )).§3. Метод Ньютона и метод секущих75Замечание. Итерационный метод Ньютона часто называют методом касательных.Если не выполнено условие неравенства нулю производной функции () в области (* ), то метод Ньютона может расходиться.
На графике показан пример такого случая.*1 0 2Замечание 1. Метод Ньютона является вычислительно сложным, поскольку на каждой итерации проводится вычисление значений производной функции (), что является,вообще говоря, неустойчивым процессом.Замечание 2. При решении задач на практике часто рассматривается модифицированный метод Ньютона, задаваемый формулой+1 = − ( ), ∈ Z+ . ′ (0 )Преимущество этого метода перед классическим методом заключается в том, что в немне требуется вычислять значения функции ′ () на каждой итерации. Однако при этоммодифицированный метод Ньютона сходится медленнее классического метода Ньютона.Метод Ньютона для нелинейных систем уравненийРассмотрим систему двух нелинейных уравнений:{︃1 (1 , 2 ) = 02 (1 , 2 ) = 0.(3)Пусть точка (*1 , *2 ) — решение этой системы. Разложим значение функции 1 (*1 , *2 ) по формуле Тейлора в малой окрестности точки (1 , 2 ), лежащей в окрестности решения:1 (*1 , *2 ) = 1 (1 , 2 ) + (*1 − 1 )1 (1 , 2 )1 (1 , 2 )+ (*2 − 2 )+ ...12Заменим в этом разложении на , * на +1, = 1, 2 и учтем, что (*1 , *2 ) — решениепервого уравнения системы (3):1 (1 , 2 ) + (+1− 1 )1 1 (1 , 2 )+1 1 (1 , 2 )+(−)= 0.2212(4)Аналогичным образом разложив функцию 2 (*1 , *2 ) по формуле Тейлора и произведя такую же замену переменных, получим2 (1 , 2 ) + (+1− 1 )1 2 (1 , 2 )+1 2 (1 , 2 )+(−)= 0.2212(5)76Глава 3.
Численное решение нелинейных уравнений и систем нелинейных уравненийВведем векторы = (1 , 2 ) , = (1 , 2 )и матрицу Якоби системы (3) — матрицу из частных производных функций 1 () и 2 ():⎞⎛11()()⎟⎜ 12⎟⎜(6)() = ⎜⎟.⎠⎝ 22()()12Перепишем уравнения (4) и (5) в матричном виде: ( ) + ( )(+1 − ) = .(7)Пусть матрица Якоби невырождена. Выразим ( + 1)-ую итерацию через -ую:+1 = − −1 ( ) ( ), ∈ Z+ .(8)Заметим, что нахождение матрицы не является простой процедурой, так как нахождениепроизводных является, вообще говоря, неустойчивым процессом.Замечание. При поиске значения каждой следующей итерации +1 необходимо сначаларешить следующую систему:( ) = − ( ), ∈ Z+ ,где = +1 − . Теперь значение +1 получается из найденного : +1 = + .Теперь перейдем к рассмотрению системы из > 2 нелинейных уравнений⎧⎪⎪1 (1 , 2 , .
. . , ) = 0⎪⎪⎨ ( , , . . . , ) = 02 1 2.⎪...⎪⎪⎪⎩ ( , , . . . , ) = 0 1 2(9)Введем векторы = (1 , 2 , . . . , ) , = (1 , 2 , . . . , )и матрицу Якоби системы (9): = ( ), =,, = 1, .Запишем схему итерационного метода Ньютона, используя матрицу Якоби:+1 = − −1 ( ) ( ), ∈ Z+ .Заметим, что вычислять матрицу на каждом шаге достаточно трудоемко.Замечание.
Аналогично одномерному случаю можно рассматривать модифицированныйметод Ньютона для решения нелинейных систем:+1 = − −1 (0 ) ( ), ∈ Z+ .Реализация модифицированного метода Ньютона проще классического варианта, но скорость сходимости при данном подходе меньше.§4. Сходимость метода Ньютона.
Оценка скорости сходимости77Метод секущихРанее мы рассматривали одношаговые методы решения нелинейных уравнений — методпростых итераций и итерационный метод Ньютона. Рассмотрим многошаговый итерационный метод — метод секущих.Запишем итерационный метод Ньютона для решения уравнения (1):+1 = − ( ), ∈ Z+ , 0 ∈ (* ). ′ ( )Заменим производную ′ ( ) на соответствующий дискретный аналогставим это отношение в уравнение (10).Получим итерационный метод+1 = −( − −1 ) ( ), ( ) − (−1 )(10) ( )− (−1 ) −−1 ∈ N, 0 , 1 заданы.и под-(11)Определение.
Итерационный процесс (11) задает двухшаговый метод решения нелинейных уравнений, называемый методом секущих.Рассмотрим геометрическую интерпретацию метода секущих.+1 −1Через точки (−1 , (−1 )), ( , ( )) проводится секущая. За новое значение +1принимается абсцисса точки пересечения секущей и оси . Иначе говоря, на отрезке[−1 , ] функция () интерполируется полиномом первой степени, и за очередное приближение +1 принимается корень этого полинома.§4Сходимость метода Ньютона.
Оценка скорости сходимостиРассмотрим функцию (), ∈ R и уравнение () = 0.(1)Пусть * — корень этого уравнения, и определена его окрестность радиуса , не содержащаядругих корней уравнения: (* ) = { : | − * | < },78Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравненийпричем заданная функция () определена на этой окрестности.Будем считать, что начальное приближение 0 ∈ (* ) задано. Запишем формулуитерационного метода Ньютона решения уравнения (1):+1 = − ( ), ∈ Z+ , 0 ∈ (* ). ′ ( )Будем рассматривать итерационный метод Ньютона как метод простой итерации с функцией ()() = − ′. ()При изучении сходимости метода простой итерации было замечено, что, если | ′ ()| < 1при ∈ (* ), то он сходится. Предполагая, что функция () дифференцируема достаточное количество раз, продифференцируем функцию (): ′ () = 1 −( ′ ())2 − () ′′ () () ′′ ()=.( ′ ())2( ′ ())2Так как * — корень уравнения (1), то (* ) = 0, и, следовательно, ′ (* ) = 0.
В предположении, что (* ) — достаточно малая окрестность, из непрерывности функции ′ (), ∈ (* ), следует неравенство | ′ ()| < 1 и сходимость метода.Введем погрешность приближенного решения: = − * .Покажем, что связь между и +1 квадратичная. Рассмотрим выражение для +1 : +1 = +1 − * = ( + * ) − (* ).(2)Разложим ( + * ) по формуле Тейлора и учтем, что ′ (* ) = 0:11 +1 = (* ) + ′ (* ) + ′′ (˜ ) ( )2 − (* ) = ′′ (˜ )( )2 ,22(3)˜ = + , ∈ R, || < 1.Замечание. Пусть функция () трижды непрерывно дифференцируема в окрестности (* ).
Тогда(︂)︂ () ′′ () ′′′. () =( ′ ())2Пусть существует постоянная > 0 такая, что для любого ∈ (* ) выполняетсянеравенство⃒1⃒(4) > ⃒ ′′ ()⃒ .2Из этого неравенства и уравнения (3) следует оценка| +1 | 6 |( )2 |.Домножим это неравенство на и обозначим = | |. Тогда получим, что +1 6 ( )2 .Отсюда следует, что 6 ( 0 )2 , значит,(︀ ⃒ ⃒)︀2 | | 6 ⃒ 0 ⃒,(5)§4. Сходимость метода Ньютона.
Оценка скорости сходимости791 (︀ ⃒⃒ 0 ⃒⃒)︀2. Введем обозначение = |0 |. Если 0 < < 1, то последовательность { }∞=0 стремитсяк нулю: −→ 0,| | 6→∞и итерационный метод Ньютона сходится. Условие на (0 < < 1) будет выполнено, если110 < | 0 | < , то есть |0 − * | 6 .Таким образом, мы доказали следующую теорему.Теорема 1. Пусть существует такая константа > 0, для которой выполнена оценка1 ⃒⃒ ′′ ⃒⃒ () 6 ,2 ∈ (* ).Тогда если начальное приближение 0 выбрать в соответствии с условием|0 − * | 61,то итерационный метод Ньютона сходится, и имеет место оценка:| − * | <)︀21 (︀ |0 − * |.Замечание 1. Если итерационный метод Ньютона сходится, то достаточно быстро.Замечание 2.
Из условий теоремы следует, что начальное приближение нужно выбирать достаточно близко к точному решению рассматриваемого уравнения.Замечание 3. Другие рассмотренные нами методы (модифицированный метод Ньютонаи метод секущих) обладают, по крайней мере, линейной сходимостью. Это следует изтого, что если их записать в виде +1 = ( ), то (* ) = * и ′ (* ) ̸= 0. Например,′ *)для модифицированного метода Ньютона ′ (* ) = 1 − ′ (, и чем ближе взять 0 к * ,(0 )тем быстрее будет сходимость.Глава 4Разностные методы решения задачматематической физики§1ВведениеЭта глава посвящена решению задач математической физики с помощью численных методов.
Численные методы позволяют находить решение произвольной дифференциальнойзадачи, в то время как аналитические подходы разработаны лишь для некоторых классовзадач и, как правило, используют целый ряд допущений. К примеру, мы будем рассматривать уравнение теплопроводности, которое является аналитически неразрешимым, еслиобласть задания уравнения определена произвольным образом, или уравнение содержитпеременные коэффициенты.
Разностные схемы позволят нам находить решение уравнениятеплопроводности и в таких сложных случаях.Постановка задачи. Рассмотрим классическую формулировку первой краевой задачи дляуравнения теплопроводности в области = {(, ) : ∈ (0, 1), ∈ (0, ]} для некоторого > 0. Для простоты возьмем коэффициент при производной искомой функции в правойчасти уравнения равным единице.(, ) 2 (, )=+ (, ),2Выпишем краевые условия первого рода:{︃(0, ) = 1 ()(1, ) = 2 (),(, ) ∈ .(1) ∈ [0, ],(2) ∈ [0, 1].(3)и начальное условие:(, 0) = 0 (),Заметим, что мы рассматриваем только те задачи, для которых существует классическое решение, то есть решение задачи существует, единственно и удовлетворяет условиям:1.
Решение обладает достаточной гладкостью, то есть функция (, ) непрерывна взамкнутой области = {(, ) : ∈ [0, 1], ∈ [0, ]}, непрерывно дифференцируемаодин раз по и два раза по внутри области .2. (, ) удовлетворяет внутри области уравнению (1), на границе — условию (2)и условию (3) в начальный момент времени.§1. Введение81Кроме того, условия на границе (2) и в начальный момент времени должны быть согласованы: 1 (0) = 0 (0) и 2 (0) = 0 (1).Из курса «Уравнения математической физики» известно, что в такой постановке существует единственное решение (, ), которое непрерывно зависит от правой части уравнения (, ), начального условия 0 () и краевых условий (2).Чтобы решить эту задачу численно, поставим ей в соответствие разностную схему, тоесть дискретный аналог рассматриваемого уравнения и дополнительных условий.
Такимобразом мы сведем непрерывную задачу к конечной системе линейных уравнений, которыеуже можно решать с использованием вычислительных машин.Сначала введем в рассматриваемой области равномерную по переменным и сетку.Определение. Сеткой в заданной области называется совокупность конечного числаточек, принадлежащих данной области.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
