Численные методы. Ионкин (методичка) (2015) (1160451), страница 13
Текст из файла (страница 13)
Аналогично получаем значение2 как точку пересечения с осью касательной к функции () в точке (1 , (1 )).Продолжая таким образом, на -м шаге получаем значение , приближающее корень *уравнения (1) с заданной точностью.* 210§23. Метод Ньютона и метод секущих75Выпишем уравнение касательной к функции () в точке : − ( ) = ′ ( )( − ).Очевидно, что значение +1 , найденное по формуле (2), представляет собой абсциссу точкипересечения с осью касательной к кривой = (), проведенной через точку ( , ( )).Замечание.Итерационный метод Ньютона часто называют методом касательных.Если не выполнено условие неравенства нулю производной функции () в области (* ), то метод Ньютона может расходиться.
На графике показан пример такого случая.*1 0 2Замечание 1. Метод Ньютона является вычислительно сложным, поскольку на каждой итерации проводится вычисление значений производной функции (), что является,вообще говоря, неустойчивым процессом.При решении задач на практике часто рассматривается модифицированный метод Ньютона, задаваемый формулойЗамечание 2.+1 = − ( ), ∈ Z+ .
′ (0 )Преимущество этого метода перед классическим методом заключается в том, что в немне требуется вычислять значения функции ′ () на каждой итерации. Однако при этоммодифицированный метод Ньютона сходится медленнее классического метода Ньютона.Вопросы сходимости метода Ньютона излагаются в §4.Метод Ньютона для нелинейных систем уравненийРассмотрим систему из двух нелинейных уравнений:{︃1 (1 , 2 ) = 0.2 (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 )+ ...1276Заменим в этом разложении на , * на +1, = 1, 2 и учтем, что (*1 , *2 ) — решениепервого уравнения системы (3):1 (1 , 2 ) + (+1− 1 )11 (1 , 2 )1 (1 , 2 )+ (+1− 2 )= 0.212(4)Аналогичным образом, разложив функцию 2 (*1 , *2 ) по формуле Тейлора и произведятакую же замену переменных, получим2 (1 , 2 ) + (+1− 1 )1Введем векторы2 (1 , 2 )2 (1 , 2 )+ (+1− 2 )= 0.212(5) = (1 , 2 ) , = (1 , 2 )и матрицу Якоби системы (3) — матрицу из частных производных функций 1 () и 2 ():⎛⎞11()()⎜ 1⎟2⎜⎟() = ⎜(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Введем векторы = (1 , 2 , . . . , ) , = (1 , 2 , . . . , )и матрицу Якоби системы (9): = ( ), =,, = 1, .Запишем схему итерационного метода Ньютона, используя матрицу Якоби:+1 = − −1 ( ) ( ), ∈ Z+ .Заметим, что вычислять матрицу на каждом шаге достаточно трудоемко.(9)§23. Метод Ньютона и метод секущих77Аналогично одномерному случаю можно рассматривать модифицированныйметод Ньютона для решения нелинейных систем:Замечание.+1 = − −1 (0 ) ( ), ∈ Z+ .Реализация модифицированного метода Ньютона проще классического варианта, но скорость сходимости при данном подходе меньше.Метод секущихИтерационный метод решения уравнения (1) называется одношаговым,если для нахождения + 1-й итерации корня +1 используется только -я итерация .
Если для нахождения +1 используется не только , но и предыдущие ей другиеитерации, то метод называется многошаговым.Определение.Ранее мы рассматривали одношаговые методы решения нелинейных уравнений — методпростых итераций и итерационный метод Ньютона. Рассмотрим многошаговый итерационный метод — метод секущих.Запишем итерационный метод Ньютона для решения уравнения (1):+1 = − ( ), ∈ Z+ , 0 ∈ (* ). ′ ( )Заменим производную ′ ( ) на соответствующий дискретный аналогставим это отношение в уравнение (10).Получим итерационный метод+1 = −( − −1 ) ( ), ( ) − (−1 )(10) ( )− (−1 ) −−1 ∈ N, 0 , 1 заданы.и под-(11)Итерационный процесс (11) задает двухшаговый метод решения нелинейных уравнений, называемый методом секущих.Определение.Рассмотрим геометрическую интерпретацию метода секущих.+1 −1Через точки (−1 , (−1 )), ( , ( )) проводится секущая.
За новое значение +1принимается абсцисса точки пересечения секущей и оси . Иначе говоря, на отрезке[−1 , ] функция () интерполируется полиномом первой степени, и за очередное приближение +1 принимается корень этого полинома.78§24Сходимость метода Ньютона. Оценка скорости сходимостиРассмотрим функцию (), ∈ R и уравнение () = 0.(1)Пусть * — вещественный корень этого уравнения, и определена его окрестность радиуса, не содержащая других корней уравнения: (* ) = { : | − * | < },причем заданная функция () определена на этой окрестности.Будем считать, что начальное приближение 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§24.
Сходимость метода Ньютона. Оценка скорости сходимости79Из этого неравенства и уравнения (3) следует оценка| +1 | 6 |( )2 |.(5)Домножим это неравенство на и обозначим = | |. Тогда получим, что +1 6 ( )2 .Отсюда следует, что 6 ( 0 )2 , значит,(︀ ⃒ ⃒)︀2 | | 6 ⃒ 0 ⃒,1 (︀ ⃒⃒ 0 ⃒⃒)︀2 .Введем обозначение = |0 |.
Если 0 < < 1, то последовательность { }∞=0 стремитсяк нулю: −→ 0,| | 6→∞и итерационный метод Ньютона сходится. Условие на (0 < < 1) будет выполнено, если110 < | 0 | < , то есть |0 − * | < .Таким образом, мы доказали следующую теорему.Теорема 1.Пусть существует такая константа > 0, для которой выполнена оценка1 ⃒⃒ ′′ ⃒⃒ () 6 ,2 ∈ (* ).Тогда если начальное приближение 0 выбрать в соответствии с условием|0 − * | <1,то итерационный метод Ньютона сходится, и имеет место оценка:| − * | 6)︀21 (︀ |0 − * |.Замечание 1. Если итерационный метод Ньютона сходится, то достаточно быстро.При наличии оценки вида (5) говорят о квадратичной сходимости метода.Замечание 2.
Из условий теоремы следует, что начальное приближение нужно выбирать достаточно близко к точному решению рассматриваемого уравнения.Другие рассмотренные нами методы (модифицированный метод Ньютонаи метод секущих) обладают, по крайней мере, линейной сходимостью. Это следует изтого, что если их записать в виде +1 = ( ), то (* ) = * и ′ (* ) ̸= 0. Например,′ *)для модифицированного метода Ньютона ′ (* ) = 1 − ′ (, и чем ближе взять 0 к * ,(0 )тем быстрее будет сходимость.Замечание 3.Глава IVРазностные методы решения задачматематической физики§25Первая краевая задача для уравнения теплопроводностиЭта глава посвящена решению задач математической физики с помощью численных методов.
Численные методы позволяют находить приближенное решение широкого классадифференциальных задач, в то время как аналитические подходы разработаны лишь длянекоторых классов задач и, как правило, используют целый ряд допущений. К примеру, мы будем рассматривать уравнение теплопроводности, которое является аналитическинеразрешимым, если область задания уравнения определена произвольным образом, илиуравнение содержит переменные коэффициенты. Разностные схемы позволят нам находитьрешение уравнения теплопроводности и в таких сложных случаях.Рассмотрим классическую формулировку первой краевой задачи дляуравнения теплопроводности в области = {(, ) : ∈ (0, 1), ∈ (0, ]} для некоторого > 0.
Для простоты возьмем коэффициент при второй производной искомой функции вправой части уравнения равным единице.Постановка задачи.(, ) 2 (, )=+ (, ),2Выпишем краевые условия первого рода:{︃(0, ) = 1 ()(1, ) = 2 (),(, ) ∈ . ∈ [0, ],(2) ∈ [0, 1].(3)и начальное условие:(, 0) = 0 (),(1)Заметим, что мы рассматриваем только те задачи, для которых существует классическое решение.
Это означает:1. Решение обладает достаточной гладкостью, то есть функция (, ) непрерывна взамкнутой области = {(, ) : ∈ [0, 1], ∈ [0, ]}, непрерывно дифференцируемаодин раз по и два раза по внутри области .2. (, ) удовлетворяет внутри области уравнению (1), на границе — условию (2)и условию (3) в начальный момент времени.§25. Первая краевая задача для уравнения теплопроводности81Кроме того, условия на границе (2) и в начальный момент времени должны быть согласованы: 1 (0) = 0 (0) и 2 (0) = 0 (1).Из курса «Уравнения математической физики» (см. также [11]) известно, что в такойпостановке существует единственное решение (, ), которое непрерывно зависит от правойчасти уравнения (, ), начального условия 0 () и краевых условий (2).Чтобы решить эту задачу численно, поставим ей в соответствие разностную схему, тоесть дискретный аналог рассматриваемого уравнения и дополнительных условий.
Такимобразом мы сведем непрерывную задачу к конечной системе линейных уравнений, которыеуже можно решать с использованием вычислительных машин.Сначала введем в рассматриваемой области равномерную по переменным и сетку.Сеткой в заданной области называется совокупность конечного числаточек, принадлежащих данной области. Эти точки называются узлами сетки.Определение.В частности, равномерная сетка размера ( − 1) × , , ∈ N в рассматриваемойобласти вводится так:{︁}︁{︀}︀ℎ = = ℎ, = 1, ( − 1) , = = , = 1, ,1> 0, => 0.Величину ℎ назовем шагом по переменной , величину — шагом по времени.Тогда множество точек ℎ = × ℎ ⊂ ℎ=задает равномерную сетку с шагом ℎ по переменной и шагом по времени в области .Эта сетка изображена на рисунке.Tℎ1Аналогичным образом введем равномерную сетку размера ( + 1) × ( + 1) на замыкании области с теми же размерами шагов ℎ и по переменной и по переменной соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
