1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 79
Текст из файла (страница 79)
. ,известен ещё с античности и часто называется методом Герона. Длялюбого положительного начального приближения x(0) он порождаетубывающую, начиная с x(1) , последовательность,которая быстро схо√дится к арифметическому значению a.Метод Ньютона требует вычисления на каждом шаге производнойот функции f , что может оказаться неприемлемым или труднодостижимым. Одна из очевидных модификаций метода Ньютона состоит втом, чтобы «заморозить» производную в некоторой точке и вести итерации по формулеx(k+1) ← x(k) −f (x(k) ),f ′ (x̌)k = 0, 1, 2, . . . ,где x̌ — фиксированная точка, в которой берётся производная. Получаем стационарный итерационный процесс, который существенно прощев реализации, но он имеет качественно более медленную сходимость.Для определения погрешности приближённого решения x̃ и контроля точности вычислений можно применять формулу|x̃ − x∗ | ≤|f (x̃)|,minξ∈[a,b] |f ′ (ξ)|(4.15)4854.4.
Классические методы решения уравненийкоторая следует из теоремы Лагранжа о среднем (формулы конечныхприращений):f (x̃) − f (x∗ ) = f ′ (ξ)(x̃ − x∗ ),где ξ — некоторая точка, заключённая между x̃ и x∗ , т. е. ξ ∈ { x̃, x∗ }.Ясно, что тогда|f (x̃) − f (x∗ )| ≥ min |f ′ (ξ)| · |x̃ − x∗ |,ξи при minξ∈[a,b] |f ′ (ξ)| 6= 0 получаем оценку (4.15). Отметим её очевидную аналогию с оценкой (3.136) для погрешности решения системлинейных уравнений.4.4дМетоды ЧебышёваМетоды Чебышёва для решения уравнения f (x) = 0 основаны наразложении по формуле Тейлора функции f −1 , обратной к f .
Они могут иметь произвольно высокий порядок точности, определяемый количеством членов разложения для f −1 , но практически обычно ограничиваются небольшими порядками.Предположим, что вещественная функция f является гладкой и монотонной на интервале [a, b], так что она взаимно однозначно отображает этот интервал в некоторый интервал [α, β]. Как следствие, существует обратная к f функция g = f −1 : [α, β] → [a, b], которая имеет туже гладкость, что и функция f .Итак, пусть известно некоторое приближение x̃ к решению x∗ уравнения f (x) = 0. Обозначив y = f (x̃), разложим обратную функцию g вточке y по формуле Тейлора с остаточным членом в форме Лагранжа:g(0) = g(y) + g ′ (y) (0 − y) + g ′′ (y)(0 − y)2(0 − y)p+ .
. . + g (p) (y)2p!+ g (p+1) (ξ)(0 − y)p+1(p + 1)!pXy p+1yl+ (−1)p+1 g (p+1) (ξ),(−1)l g (l) (y)= g(y) +l!(p + 1)!l=14864. Решение нелинейных уравнений и их системгде ξ — какая-то точка между 0 и y. Возвращаясь к переменной x,будем иметь∗x = x̃ +pXl(−1) g(l)l=1lp+1 f (x̃)f (x̃)p+1 (p+1)f (x̃)+ (−1)g(ξ).l!(p + 1)!В качестве следующего приближения к решению мы можем взять, отбросив остаточный член, значениеx̃ +pXl(−1) gl=1(l)l f (x̃).f (x̃)l!Подытоживая сказанное, определим итерации(k+1)x(k)←x+pXl(−1) gl=1(l)l f (x̃)f (x̃),l!k = 0, 1, 2, .
. . ,которые и называются методом Чебышёва p-го порядка.Как на практике найти производные обратной функции g?Зная производные функции f в какой-то точке, мы можем найти ипрозводные обратной функции g. В самом деле, последовательно дифференцируя тождество x = g f (x) , получимg ′ f (x) f ′ (x) = 1,2g ′′ f (x) f ′ (x) + g ′ f (x) f ′′ (x) = 0,3g ′′′ f (x) f ′ (x) + g ′′ f (x) · 2f ′ (x)f ′′ (x)+ g ′′ f (x) f ′ (x) f ′′ (x) + g ′ f (x)) f ′′′ (x) = 0,......,илиg ′ f (x) f ′ (x) = 1,2g ′′ f (x) f ′ (x) + g ′ f (x) f ′′ (x) = 0,3g ′′′ f (x) f ′ (x) + 3g ′′ f (x) f ′ (x) f ′′ (x) + g ′ f (x)) f ′′′ (x) = 0,.......4.5.
Классические методы решения систем уравнений487 ′′′Относительнонеизвестныхзначенийпроизводныхgf(x),gf(x),′′′g f (x) и т. д. эта система соотношений имеет треугольный вид, позволяющий найти их последовательно одну за другой:1g ′ f (x) = ′,f (x)gg′′′′′g f (x) f ′′ (x)f ′′ (x)=−f (x) = −23 ,f ′ (x)f ′ (x)3g ′′ f (x) f ′ (x) f ′′ (x) + g ′ f (x)) f ′′′ (x)f (x) = −3f ′ (x)2f ′′ (x)f ′′′ (x)= −35 −4f ′ (x)f ′ (x)и так далее.Для p = 1 расчётные формулы метода Чебышёва имеют видx(k+1) ← x(k) −f (x(k) ),f ′ (x(k) )k = 0, 1, 2, . . .
,что совпадает с методом Ньютона.Для p = 2 расчётные формулы метода Чебышёва таковы2f ′′ (x(k) ) f (x(k) )f (x(k) )(k+1)(k),k = 0, 1, 2, . . . .x← x − ′ (k) −3f (x )2 f ′ (x(k) )Наиболее часто методом Чебышёва называют именно этот итерационный процесс, так как методы более высокого порядка из этого семейства на практике используются редко.4.5Классические методырешения систем уравнений4.5аМетод простой итерацииСхема применения метода простой итерации для систем уравненийв принципе не отличается от случая одного уравнения. Исходная система уравнений F (x) = 0 должна быть каким-либо способом приведена4884.
Решение нелинейных уравнений и их системк равносильному рекуррентному виду, например,x = x − ΛF (x),где Λ — неособенная матрица, и далее, после выбора некоторого начального приближения x(0) , запускается итерационный процессx(k+1) ← Φ(x(k) ),k = 0, 1, 2, . . . ,где Φ(x) = x − ΛF (x). При благоприятных обстоятельствах последовательность {x(k) } сходится, и её пределом является искомое решениесистемы уравнений. Для обеспечения сходимости итераций к решениюстараются удовлетворить теореме Банаха о неподвижной точке или жееё аналогу — теореме Шрёдера.4.5бМетод Ньютона и его модификацииПусть для системы уравненийF1 ( x1 , x2 , .
. . , xn ) F2 ( x1 , x2 , . . . , xn )......Fn ( x1 , x2 , . . . , xn )= 0,= 0,...= 0,или, кратко, F (x) = 0, известно некоторое приближение x̃ к решениюx∗ . Если F — плавно меняющаяся (гладкая функция), то естественноприблизить её в окрестности точки x̃ линейной функцией, т. е.F (x) ≈ F (x̃) + F ′ (x̃) (x − x̃),где F ′ (x̃) — матрица Якоби отображения F в точке x̃. Далее для вычисления следующего приближения к решению системы уравнений естественно взять решение системы линейных алгебраических уравненийF (x̃) + F ′ (x̃) (x − x̃) = 0,которая получается из приближения F . Следовательно, очередным приближением к решению может быть−1x = x̃ − F ′ (x̃)F (x̃).4.5.
Классические методы решения систем уравнений489Итерационный процесс−1x(k+1) ← x(k) − F ′ (x(k) )F (x(k) ),k = 0, 1, 2, . . . ,называют методом Ньютона.Метод Ньютона требует вычисления на каждом шаге матрицы производных функции F и решения систем линейных алгебраических уравнений с изменяющейся матрицей. Нередко подобные трудозатраты могут стать излишне обременительными.
Если зафиксировать точку x̌, вкоторой вычисляется эта матрица производных, то получим упрощённый стационарный итерационный процесс−1x(k+1) ← x(k) − F ′ (x̌)F (x(k) ),k = 0, 1, 2, . . . ,который часто называют модифицированным методом Ньютона. Здесьрешение систем линейных уравнений с одинаковыми матрицами F (x̌)можно осуществлять по упрощённым алгоритмам, к примеру, найдяодин раз LU-разложение матрицы и далее используя его.Один из наиболее часто используемых результатов о сходимостиметода Ньютона — этоТеорема 4.5.1 (теорема Л.В. Канторовича о методе Ньютона)Пусть отображение F определено в открытой области D и имеетнепрерывную вторую производную F ′′ в замыкании cl D.
Пусть, кроме того, существует такой непрерывный линейный оператор Γ0 =−1F (x0 ), что Γ0 F (x0 ) ≤ η и kΓ0 F ′′ (x)k < K для всех x ∈ cl D инекоторых констант η и K. Еслиh = Kη ≤и12√1 − 2hη,hто уравнение F (x) = 0 имеет решение x⋆ , к которому сходится методНьютона, как исходный, так и модифицированный. При этомr ≥ r0 =1−kx⋆ − x0 k ≤ r0 .Для исходного метода Ньютона сходимость описывается оценкойkx⋆ − xk k ≤kη(2h)2 ,2k hk = 0, 1, 2, . . . ,4904. Решение нелинейных уравнений и их система для модифицированного метода верна оценка√ηkx⋆ − xk k ≤ (1 − 1 − 2h)k+1 ,k = 0, 1, 2, .
. . ,hпри условии h < 21 .Доказательство и дальнейшие результаты на эту тему можно найтив книге [17].4.6Интервальные линейныесистемы уравненийПредметом рассмотрения настоящего пункта являются интервальные системы линейных алгебраических уравнений (ИСЛАУ) видаAx = b,(4.16)где A = ( aij ) — это интервальная m×n-матрица и b = ( bi ) — интервальный m-вектор. Для интервальных уравнений решения и множестварешений могут быть определены разнообразными способами (см. [37]),но ниже мы ограничимся так называемым объединённым множествомрешений для (4.16), которое образовано всевозможными решениями xточечных систем Ax = b, когда матрица A и вектор b независимо пробегают A и b соответственно. Объединённое множество решений определяется строго какΞ(A, b) = { x ∈ Rn | (∃ A ∈ A)(∃ b ∈ b)(Ax = b)},(4.17)и ниже мы будем называть его просто множеством решений интервальной линейной системы (4.16), так как другие множества решений нами не исследуются.
Точное описание множества решений можетрасти экспоненциально с размерностью вектора неизвестных n, а потому является практически невозможным уже при n, превосходящемнесколько десятков. С другой стороны, в большинстве реальных постановок задач точное описание на самом деле и не нужно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
