main (1160440), страница 13
Текст из файла (страница 13)
′ (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).Чтобы решить эту задачу численно, поставим ей в соответствие разностную схему, тоесть дискретный аналог рассматриваемого уравнения и дополнительных условий.
Такимобразом мы сведем непрерывную задачу к конечной системе линейных уравнений, которыеуже можно решать с использованием вычислительных машин.Сначала введем в рассматриваемой области равномерную по переменным и сетку.Определение. Сеткой в заданной области называется совокупность конечного числаточек, принадлежащих данной области. Эти точки называются узлами сетки.В частности, равномерная сетка размера ( − 1) × , , ∈ N в рассматриваемойобласти вводится так:{︁}︁{︀}︀ℎ = = ℎ, = 1, ( − 1) , = = , = 1, ,1> 0, => 0.Величину ℎ назовем шагом по переменной , величину — шагом по времени.Тогда множество точекℎ = ℎ × ⊂ ℎ=задает равномерную сетку с шагом ℎ по переменной и шагом по времени в области .Эта сетка изображена на рисунке.Tℎ1Аналогичным образом введем равномерную сетку размера ( + 1) × ( + 1) на замыкании области с теми же размерами шагов ℎ и по переменной и по временисоответственно.
Эту сетку задает множество точек ℎ = ℎ × ⊂ = {(, ) : ∈ [0, 1], ∈ [0, ]},где{︀}︀{︀}︀ ℎ = = ℎ, = 0, , = = , = 0, .В дальнейшем везде, где мы рассматриваем уравнение теплопроводности, будем использовать введенные сетки, если не указано иное.82Глава 4. Разностные методы решения задач математической физикиЗамечание. В общем случае сетки могут иметь более сложную структуру, например,использовать переменный шаг, который зависит от расположения конкретной пары узлов, или для многомерной области иметь более сложную структуру расположения узлов относительно друг друга (в рассматриваемом примере равномерная сетка являетсяпрямоугольной). В последнее время часто используются сетки, автоматически подстраивающиеся под решение конкретной задачи.Определение.
Совокупность всех узлов в фиксированный момент времени называется слоем. Слой, для которого = 0, будем называть нулевым слоем, в котором заданоначальное приближение.§2Явная разностная схема. Погрешность, сходимость, устойчивостьРассмотрим уравнение теплопроводности с краевыми условиями первого рода:(, ) 2 (, )=+ (, ),2(, ) ∈ = {(, ) : ∈ (0, 1), ∈ (0, ]},(1){︃(0, ) = 1 ()(1, ) = 2 (), ∈ [0, ],(2)(, 0) = 0 (), ∈ [0, 1](3)и построим для него разностную схему.Воспользуемся сетками ℎ и ℎ , введенными в первом параграфе данной главы на множествах и соответственно.Определение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
