Конспект лекций - 3ий поток, лектор - Ионкин (1113828), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

Рассмотрим следующий итерационный процесс:xn+1 − xn+ f (xn ) = 0,τ(6)где n ∈ N0 , x0 ∈ Ua , τ > 0.Пусть для определенности f 0 (x) > 0. Запишем метод (6), как метод простойитерации:S(x) = x − τ f (x).В силу первого замечания, если |S 0 (x)| < 1, то сходимость есть.S 0 (x) = 1 − τ f 0 (x), в предположении, что f — гладкая.ОбозначимM1 = max |f 0 (x)|.x∈Ua (x∗ )Тогда|1 − τ M1 | < 1=⇒−1 < 1 − τ M1 < 1=⇒0<τ <2.M167Ускорение сходимости итерационного метода (метод Эйткена)Пусть известно, что две соседние итерации удовлетворяют следующему условию:xn − x∗ ≈ Aq n ,n = 1, 2, 3, . .

.Запишем 3 соседних итерации:xn−1 − x∗ ≈ Aq n−1(7)xn − x∗ ≈ Aq n(8)xn+1 − x∗ ≈ Aq n+1(9)Поставим задачу выразить корень через эти итерации:x∗ ≈ xn+1 − Aq n+1 ,(xn+1 − xn )2 = A2 q 2n (q − 1)2 ,(xn+1 − 2xn + xn − 1) = Aq n−1 (q − 1)2 .(xn+1 − xn )2= Aq n+1 .(xn+1 − 2xn + xn−1 )В итогеx∗ ≈ xn+1 −(xn+1 − xn )2.(xn+1 − 2xn + xn−1 )Так как все равенства приближенные, то x∗ берется за значение xn+1 итерации.§3 Метод Ньютона и метод секущихРассматриваем нелинейное уравнениеf (x) = 0(1)Корень уравнения локализован, то есть указана окрестность Ua (x∗ ). Обозначим n –ю итерацию через xn . Тогда запишем:xn+1 = xn −f (xn ), n = 0, 1, 2, 3, .

. . x0 ∈ Ua (x∗ )f 0 (xn )(2)Методом Ньютона решения нелинейного уравнения f (x) = 0 называется метод, записанный в виде (2). Для доказательства сходимости метода Ньютона будем требовать,чтобы функция была гладкой до третей производной. ( так же этот метод называетсяметодом касательных)Если дана функция f (x) то уравнение касательной в точке (xn , f (xn )) будетиметь вид: y − f (xn ) = f 0 (xn )(x − xn ).

Тогда за xn+1 принимается абсцисса точки,в которой касательная пересекает ось ординат. Формулу (2) легко получить из следующих соображений. Разложим по формуле Тейлора в окрестности корня: f (x∗ ) =680 = f (x) + (x∗ − x)f 0 (xn ) + . . . . Тогда если вместо x∗ подставить xn+1 и вместо x − xn, то получим:0 = f (xn ) + (xn+1 − xn )f 0 (xn )Разрешим уравнение относительно xn+1 при условии, что f 0 (x) 6= 0 :xn+1 = xn −f (xn )f 0 (xn )Приведем графически пример, когда при неудачном выборе начального приближения метод Ньютона зациклится:yxx∗x1x0x2Рассмотрим модифицированный метод Ньютона:xn+1 = xn −f (xn ), n = 0, 1, 2, 3, . .

. x0 ∈ Ua (x∗ )f 0 (x0 )(3)Один из плюсов этого метода - не нужно считать производную на каждой итерации.Но сходимость этого метода ( в смысле скорости) будет хуже чем (2). Запишеммодифицированный метод Ньютона для нелинейных систем. Пусть существует дванелинейных уравнения :(f1 (x1 , x2 ) = 0f2 (x1 , x2 ) = 0В качестве решения системы понимается точка (x∗1 , x∗2 ), в которой fi (x∗1 , x∗2 ) = 0, i =691, 2.

Разложим обе функции в ряд Тейлора:0 = f1 (x∗1 , x∗2 ) = f1 (x1 , x2 ) + (x∗1 − x1 )∂f1 (x1 , x2 )∂f1 (x1 , x2 )+ (x∗2 − x2 )+ ...∂x1∂x20 = f2 (x∗1 , x∗2 ) = f2 (x1 , x2 ) + (x∗1 − x1 )∂f2 (x1 , x2 )∂f2 (x1 , x2 )+ (x∗2 − x2 )+ ...∂x1∂x2Сделаем замену xi на xni , x∗i на xn+1innnnn+1n+1n ∂f1 (x1 , x2 )nnn ∂f1 (x1 , x2 )))+(x−x,xf(x)+(x−x=0 1 1 21212∂xn1∂xn2nnnnn+1n+1nnn ∂f2 (x1 , x2 )n ∂f2 (x1 , x2 )f(x,x)+(x−x)+(x−x)=0 2 1 21212∂xn1∂xn2Чтобы записать данную систему в компактном виде, введем векторы f =(f1 , f2 )T , x = (x1 , x2 )T и матрицу∂f1 ∂f1 1 ∂x2 (5)J(x) =  ∂x∂f2 ∂f2 ∂x1 ∂x2: f (xn ) = J(xn )(xn+1 −xn ) = 0.

Если предположить,Заменим xi на xni , x∗i на xn+1iчто J(xn ) обратима, тоxn+1 = xn − J −1 (xn )f (xn )(6)Чтобы на каждой итерации не обращать матрицу J, вводят вектор V n+1 = xn+1 −x : f (xn ) + J(xn )V n = 0. Найдя этот вектор, можно найти xn+1 по формуле : xn+1 =xn + V n+1Запишем метод для любого количества нелинейных уравнений:f1 (x1 , x2 , . . .

, xn ) = 0f (x , x , . . . , x ) = 02 12n...fn (x1 , x2 , . . . , xn ) = 0nМетод Ньютона для этой системы получается аналогичным образом. Пусть J =∂fi(fij ), fij =, i = 1, m j = 1, m , квадратная матрица порядка m и векторы∂xjf = (f1 , f2 , . . . , fm )T x = (x1 , x2 , . . . , xm )T . Тогда метод Ньютона будет иметь вид:xn+1 = xn − J −1 (xn )f (xn )где n = 0, 1, 2, 3, . . . , и x0 – задано из окрестности корня.(7)70Метод секущихЗапишем метод Ньютонаxn+1 = xn −f (xn ), n = 1, 2, 3, . . . , x∗ ∈ Ua (x∗ )f 0 (xn )решения уравнения f (x) = 0. Исходя из этой формулы, заменим производную на ееf (xn ) − f (xn+1 ). Теперь полудискретный аналог и подставим в формулу: f 0 (xn ) =xn − xn+1чим итерационный метод, называемый методом секущих:xn+1 = xn −(xn − xn+1 )f (xn )f (xn ) − f (xn+1 )(8)где n = 0, 1, 2, 3, .

. . x0 , x1 − заданы. Этот метод является двухшаговым. Значение xn+1 находится с использованием xn и xn−1 . На рисунке изображена графическаяиллюстрация описанного метода:yграфиксекущаяxxn+1 xnxn−1§4 Сходимость метода Ньютона. Оценка скорости сходимостиРассматриваем метод Ньютона для нелинейного уравненияf (x) = 0(1)71f (xn ), где n = 0, 1, 2, 3, . . . и x0 ∈ Ua (x∗ )f 0 (xn )Метод Ньютона можно трактовать как метод простой итерации:xn+1 = xn −xn+1 = S(xn )(3)f (x). При изучении сходимости метода простой итерации было заf 0 (x)мечено, что простая итерация (3) сходится, если |S 0 (x)| = q < 1 для x ∈ Ua (x∗ ) .Продифференцируем S(x):где S(x) = x −f (x)f 00 (x)(f 0 (x))2 − f (x)f 00 (x)=S (x) = 1 −(f 0 (x))2(f 0 (x))20Следовательно, S 0 (x) = 0 так как f (x∗ ) = 0. Введем погрешность zn = xn − x∗ .

Покажем, что это погрешность на двух соседних итерациях будет связана квадратичнымобразом. Рассмотримzn+1 = xn+1 − x∗ = S(zn + x∗ ) − S(x∗ ).Разложим это по формуле Тейлора: zn+1 = S(x∗ ) + S 0 (x∗ )zn + 0.5S 00 (x)zn2 − S(x∗ ) =0.5S 00 (x)zn2 , где x = x∗ + θzn , |θ| < 1.

Предположим, что существует постояннаяM > 0 такая, что для ∀x ∈ Ua (x∗ ) выполняется неравенство:0 00f(x)f(x)16M|0.5S 00 (x)| 6 M или, что то же самое (4)2(f 0 x)2Оценим zn+1 : |zn+1 | 6 M |zn2 |. Домножим это неравенство на M и введем функциюVn = M |zn |. Тогда получим Vn+1 6 Vn2 . То есть две соседние погрешности связаnны квадратично. Применяя эту формулу как рекуррентную, получим: Vn 6 V02 ивернувшись к z :1nnM |zn | 6 (M |z0 |)2 и |zn | 6(M |z0 |)2(5)MОбозначим через q величину M |z0 | и если q < 1, то метод Ньютона сходится.Следовательно, начальное приближение x0 нужно выбирать так, чтобы выполнялось неравенство:1|x0 − x∗ | <(6)MТогда итерационный метод Ньютона сходится и имеет место оценка:|xn − x∗ | <1n(M |x0 − x∗ |)2M(7)Утверждение 7.

Пусть существует константа M , удовлетворяющая условию(4) и пусть в некоторой окрестности корня Ua (x∗ ) , a = a(M ) начальное приближение выбирается в соответствии с условием (6). Тогда итерационный методНьютона решения уравнения (1) сходится и имеет место оценка (7).Доказательство: Данное утверждение было доказано выше.Глава 4Разностные методы решения задачматематической физики§1 Явная разностная схема для первой краевой задачи уравнения теплопроводностиПостановка задачи:∂ 2U∂U=+ f (x, t)(1)∂t∂x2где x ∈ (0, 1) t ∈ (0, T ] . Уравнение решается внутри области.

Выпишем краевыеусловия первого рода:(U (0, t) = µ1 (t)t ∈ [0, T ](2)U (1, t) = µ2 (t)А так же начальное условие:U0 (x) = U (x, 0), x ∈ [0, 1](3)Задача состоит в нахождении непрерывной в замкнутой области функцииU (x, t), удовлетворяющей внутри области уравнению (1), на границе – условию (2) иначальному условию (3).Известно, что решение данной задачи существует, единственно и устойчиво.Введем сетку:1wh = {xi = ih, i = 1, N − 1, h = } где h > 0 – шаг по переменной x.N1wh = {xi = ih, i = 0, N , h = }Nwτ = {tj = jτ , j = 1, j0 , τ j0 = T }wτ = {tj = jτ , j = 0, j0 , τ j0 = T } где τ > 0 – шаг по времени.Тогда множество внутренних узлов wτ h = wτ × wh и множество всех узлов: wτ h =wτ × wh73tTτx1hСовокупность всех узлов в определенный момент времени будем называть слоем.yin = y(xi , tn ),fin = f (xi , tn ),(xi , tn ) ∈ ω τ,h .Выпишем явную разностную схему:nnyi−1− 2yin + yi+1yin+1 − yin=+ f (xi , tn ), (xi , fn ) ∈ ωτ hτh2(y0n+1 = µ1 (tn+1 )tn+1 ∈ ω τ,hynn+1 = µ2 (tn+1 )yi0 = U0 (xi ),xi ∈ ω(4)(5)(6)Совокупность узлов, в которых записывается разностная схема, называют шаблоном.

Здесь использован четырехточечный шаблон вида:tn+1ii−1ii+1tnТаким образом задаче (1)-(3) мы поставили в соответствие её дискретный аналог(4)-(6). Возникает система линейных алгебраических уравнений, которая и называется разностной схемой.Записанная разностная схема использует два слоя : tn+1 и tn . В слое tn беретсятри узла : (i − 1), (i), (i + 1), а в слое tn+1 только (i)-ый узел. То есть разностнаясхема записана на четырехточечном шаблоне.Решение на (n+1) слое находится по явный формуле :yin+1 = yi +τ nn(y − 2yin + yi+1) + τ fih2 i−1(y0n+1 = µ1 (tn+1 )n+1yN= µ2 (tn+1 )i = 1, N − 1При изучении разностных схем возникают следующие вопросы:1.

Погрешность аппроксимации.742. Существование и единственность решения разностных схем.3. Алгоритм нахождения численного решения.4. Сходимость разностный схемы к решению исходной задачи.5. Устойчивость решения по начальному условию и правой части.Явная разностная схема является условно сходящейся, т.е. еслиγ=τ6 0.5,h2(7)тогда разностная схема сходится, иначе она сходиться не будет. Также явная разностная схема является условно устойчивой.Теперь введем погрешность разностной схемы:zin = yin − U (xi , tn )(8)yin = zin + UinПодставим yin в разностное уравнение.nz n − 2zin + zi+1zin+1 − zin= i−1+ ψin2τhz0n+1 = zN n + 1 = 0,zi0 = 0(9)(10)Выпишем погрешность аппроксимации на решение:ψin =nn− 2Uin + Un+1Ui−1Uin+1 − Uin−+ finh2τ(11)(xi , tn ) ∈ ωτ hОпределение. ψin называется погрешностью аппроксимации разностной схемы нарешение исходной задачи.Задача.

Доказать, что ψin = O(τ + h2 )Решение: Разложим u(xi , tn+1 ) в узле (xi , tn ) по формуле Тейлора:u(xi , tn+1 ) = un+1= u(xi , tn ) + ut (xi , tn )τ + O(τ 2 )iРазложим u(xi+1 , tn ) в узле (xi , tn ) по формуле Тейлора:11u(xi+1 , tn ) = uni+1 = u(xi , tn ) + ux (xi , tn )h + uxx (xi , tn )h2 + uxxx (xi , tn )h3 + O(h4 )26Разложим u(xi−1 , tn ) в узле (xi , tn ) по формуле Тейлора:11u(xi−1 , tn ) = uni−1 = u(xi , tn ) − ux (xi , tn )h + uxx (xi , tn )h2 − uxxx (xi , tn )h3 + O(h4 )2675Полученные разложения подставим в формулу:ψin =uni−1 − 2uni + uni+1 un+1− unii+ fin−h2τПриведя подобные слагаемые ,получаем оценку ψin = O(τ + h2 )Докажем, что условия (7) достаточно для сходимости с норме k · kc .ky k kc = max |yin |06i6Nτ6 0.5 Тогда разностная схема (4)-(6) сходится в норме k · kc .h2Разрешим задачу относительно (n+1) слоя.Пусть γ =Nnzin+1 = zin + γ(zi−1− 2zin + zi+1) + τ ψinCоберем подобные члены.nnzin+1 = (1 − 2γ)zin + γ(zi−1+ zi+1) + τ ψin(1 − 2γ) > 0Следовательно,nn|zin+1 | 6 (1 − 2γ)|zin | + γ(|zi−1| + |zi+1|) + τ |ψin |nn|zin+1 | 6 (1 − 2γ)kzin kc + γ(kzi−1k + kzi+1kc ) + τ kψin kc = kz n kc + kψ n kcТак как это справедливо для всех i, тоkz n+1 kc 6 kz n kc + τ kψ n kcРассматривая формулу как рекуррентную, получимkzn+1nkc 6 kz kc + TnXkψkc(12)k=0Так какkψ k k 6 M (τ + h2 ),M > 0,где M не зависит от τ и h.

Характеристики

Список файлов лекций