Численные методы. Ионкин (2012) (неоффициальные) (косяки есть) (1160437), страница 10
Текст из файла (страница 10)
Если предположить,Заменим 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 ) = 0f (x , x , . . . , x ) = 02 12n...fm (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)71Метод секущихЗапишем метод Ньютонаxn+1 = xn −f (xn ), n = 1, 2, 3, . . . , x0 ∈ 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+1xnxn−1§4 Сходимость метода Ньютона. Оценка скорости сходимостиРассматриваем метод Ньютона для нелинейного уравненияf (x) = 0(1)72f (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 −S 0 (x) = 1 −(f 0 (x))2 − f (x)f 00 (x)f (x)f 00 (x)=(f 0 (x))2(f 0 (x))2Следовательно, S 0 (x∗ ) = 0 так как f (x∗ ) = 0. Введем погрешность zn = xn − x∗ .
Покажем, что этa погрешность на двух соседних итерациях будет связана квадратичнымобразом. Рассмотрим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 1 f (x)f 00 (x) 00(4)|0.5S (x)| 6 M или, что то же самое 6M2(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)Утверждение. Пусть существует константа 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τ × wh7374tTτx1hСовокупность всех узлов в определенный момент времени будем называть слоем.yin = y(xi , tn ),fin = f (xi , tn ),(xi , tn ) ∈ ω τ,h .Выпишем явную разностную схему:ny n − 2yin + yi+1yin+1 − yin= i−1+ f (xi , tn ), (xi , fn ) ∈ ωτ hτh2(y0n+1 = µ1 (tn+1 )tn+1 ∈ ω τ,hn+1yN= µ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 = yin +τ nn(yi−1 − 2yin + yi+1) + τ fin2h(y0n+1 = µ1 (tn+1 )n+1yN= µ2 (tn+1 )i = 1, N − 1При изучении разностных схем возникают следующие вопросы:1. Погрешность аппроксимации.752. Существование и единственность решения разностных схем.3. Алгоритм нахождения численного решения.4. Сходимость разностный схемы к решению исходной задачи.5. Устойчивость решения по начальному условию и правой части.Явная разностная схема является условно сходящейся, т.е.
еслиγ=τ6 0.5,h2(7)тогда разностная схема сходится, иначе она сходиться не будет. Также явная разностная схема является условно устойчивой.Теперь введем погрешность разностной схемы:zin = yin − U (xi , tn )(8)yin = zin + UinПодставим yin в разностное уравнение.nn− 2zin + zi+1zi−1zin+1 − zin=+ ψin2τhn+1z0n+1 = zN= 0,zi0 = 0(9)(10)Выпишем погрешность аппроксимации на решение:ψin =nnUi−1− 2Uin + Ui+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 )2676Полученные разложения подставим в формулу:ψin =uni−1 − 2uni + uni+1 un+1− unii+ fin−h2τПриведя подобные слагаемые, получаем оценку ψin = O(τ + h2 )Докажем, что условия (7) достаточно для сходимости в норме k · kc .ky n kc = max |yin |06i6Nτ6 0.5 Тогда разностная схема (4)-(6) сходится в норме k · kc .
Разрешимh2задачу относительно (n+1) слоя.Пусть γ =nnzin+1 = zin + γ(zi−1− 2zin + zi+1) + τ ψinСоберем подобные члены.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 ||zin+1 | 6 (1 − 2γ)kz n kc + 2γkz n k + τ kψ n kc = kz n kc + τ kψ n kcТак как это справедливо для всех i, тоkz n+1 kc 6 kz n kc + τ kψ n kcРассматривая формулу как рекуррентную, получимkzn+10kc 6 kz kc + τnXkψ k kc(12)k=0Так какkψ k k 6 M (τ + h2 ),M > 0,где M не зависит от τ и h.
Тогда мы можем записать, чтоkz n+1 kc 6 M tn+1 (τ + h2 )tn+1 6 T.Положим M T = M1 , которая не зависит от шагов τ и h. Теперь получаем окончательную оценку:kz n+1 k 6 M (τ + h2 ).Если τ → 0,h → 0, то kz n+1 kc → 0.77Т.е. kyin+1 − Uin+1 k → 0. Таким образом, имеет место сходимость численногорешения к решению исходной задачи c первым порядком по τ и вторым по h.Если мы рассмотрим разностную схему, но при нулевых краевых условиях,тооценка будет для y:nXn+1ky kc 6 kU0 kc +τ kf k kc(14)k=0Говорят, что разностная схема устойчива в k·kc по начальному условию и по правой части. Оценка (14) называется априорной оценкой.
Таким образом мы показали,что условие (7) является достаточным. Теперь покажем, что оно также является инеобходимым.Выпишем однородное уравнение, соответствующее неоднородному уравнению(4):ny n − 2yin + yn+1yin+1 − yin= i−1(15)τh2Будем искать некоторые частные решение в следующем виде:yjn = q n eijhϕ .(16)гдеi2 = −1,ϕ ∈ R.Подставим эту формулу в уравнениеnnyin+1 = yin + γ(yi−1− 2yin + yi+1).Тогда мы получим выражение для q:q = 1 + γ(eihϕ − 2 + e−ihϕ ) = 1 + 2γ(cos(hϕ) − 1) = 1 − 4γ sin2hϕ2Видно, что |q| > 1 означает неустойчивость.hϕ< −1,2hϕ,2 < 4γ sin221 − 4γ sin2Откуда получаем, чтоγ>121Если |q| > 1, т.е. γ > , то гармоники будут неограниченно возрастать и раз2ностная схема будет расходиться.1Таким образом, условие γ 6 является необходимым и достаточны для сходи2мости и устойчивости явной разностной схемы.78§2 Чисто неявная разностная схема (схема с опережением) для первой краевой задачи уравнения теплопроводностиЗадача (1) - (3) остается прежней.n+1y n+1 − 2yin+1 + yi+1yin+1 − yin= i−1+ f (xi , tn+1 ), (xi , tn+1 ) ∈ ωτ hτh2(y0n+1 = µ1 (tn+1 )tn+1 ∈ ω τynn+1 = µ2 (tn+1 )yi0 = U0 (xi ),xi ∈ ω h(4)(5)(6)Мы поставили в соответствие задаче (1) - (3) разностную схему (4) - (6).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
