Численные методы. Соснин (2005) (1160462), страница 10
Текст из файла (страница 10)
Основным этапом нашего доказательства будет получение xk+1 из xk . Получимоценку погрешности на (k + 1)-й итерации из определения итерационного процесса:(xk − x∗ )f 0 (xk ) − f (xk )f (xk )∗−x==f 0 (xk )f 0 (xk )F (xk )= {обозначим F(x) = (x − x∗ )f 0 (x) − f(x)} = 0 k .f (x )xk+1 − x∗ = xk −Преобразуем F (xk ) по формуле Ньютона-Лейбница:kk∗Zxk0∗∗F (ξ)dξ = {F(x ) = f(x ) = 0} =F (x ) = F (x ) +x∗kZx0ZxF (ξ)dξ =x∗(ξ − x∗ )f 00 (ξ)dξ.x∗Применив к последнему интегралу формулу среднего значения (ξk ∈ [x∗ ; xk ]), получимkF (xk ) = f 00 (ξk )Zx(ξ − x∗ )dξ = f 00 (ξk )(xk − x∗ )2.2x∗Подставив запись для F (xk ) в выражение для погрешности, получимxk+1 − x∗ = f 00 (ξk )(xk − x∗ )2.2f 0 (xk )Так как вторая производная по модулю ограничена сверху, а первая — снизу, то из последнегоравенства следует, что метод Ньютона имеет квадратичную скорость сходимости.Докажем оценку на погрешность по индукции.50Глава 3.
ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙБаза индукции. Рассмотрим погрешность при k = 1 :x1 − x∗ = f 00 (ξ0 )|x0 − x∗ |2M2 |x0 − x∗ | 0∗6{ξ∈U(x)}6|x − x∗ | = q|x0 − x∗ |.0r2f 0 (x0 )2m1Таким образом, база индукции верна.Предположение индукции. Пусть оценка (3.9) выполняется для некоторого k :|xk − x∗ | 6 q 2k−1|x0 − x∗ |.Индуктивный переход. Докажем, что она выполняется для k + 1. Согласно показанному ранее,|xk+1 − x∗ | = |f 00 (ξ k )||xk − x∗ |2.2|f 0 (xk )|ξk ∈ Ur (x∗ ), так как ξk выбиралась в соответствии с теоремой о среднем, и поэтому принадлежитотрезку Ur (x∗ ).Получим верхнюю оценку, используя предположение индукции:|f 00 (ξ k )|M2 (xk − x∗ )2|xk − x∗ |2M2 2k −1 266(q) · |x0 − x∗ |2 .0k2|f (x )|2m12m1Вспомним, что мы обозначалиM2 0|x − x∗ | = q, тогда получим:2m1|xk+1 − x∗ | 6 q 2k+1−1|x0 − x∗ |.Откуда следует, что оценка верна, и, следовательно, теорема доказана (q < 1 по предположению, ипри k −→ ∞ правая часть стремится к нулю, а это значит, что последовательность сходится к x∗ ).Замечание.M2 |x0 − x∗ |< 1.
Но как это проверить, ведь мы не знаем2m1∗точного решения x ? Можно поступить так.1. В условии теоремы мы требуем, чтобыРассмотрим условиеM2 |x0 − x∗ |< 1.2m1(3.10)Распишем f (x0 ) = f (x0 ) − f (x∗ ) = f 0 (x)(x0 − x∗ ), тогда|x0 − x∗ | =|f (x0 )||f (x0 )|6.0|f (x)|m1Подставим эту запись для |x0 − x∗ | в (3.10), тогда из неравенстваM2 |f (x0 )|<12m21следует, что выполняется условие (3.10).Таким образом, зная m1 и M2 , можно подбирать x0 , исходя из этого неравенства (подбираемдостаточно малую окрестность на этапе локализации корней, и дальше работаем с ней; еслиокрестность велика, уточняем расположение корня).2. В условии требовалось, чтобы x∗ был простым вещественным корнем; если же x∗ — коренькратности p, то метод Ньютона будет иметь квадратичную скорость сходимости, если некоторымобразом подправить итерационную последовательность.3.6.
РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ3.651Решение систем нелинейных уравненийПерейдем к поиску численных методов для решения систем нелинейных уравнений. Пусть имеется nуравнений следующего вида:fi (x1 , x2 , . . . , xn ) = 0, i = 1, n.(3.11)Поиск решений данной системы обычно проводится в два этапа: сначала проходит разделение решений (термин имеет тот же смысл, что и локализация корней при решении одиночных уравнений), азатем на полученных участках производится их уточнение.
Как мы увидим, для поиска решений систембудут применяться те же методы, что и для поиска корней одиночных уравнений, но с небольшимимодификациями.Метод простой итерацииИтак, мы решаем систему вида (3.11). Построим итерационный процесс для нахождения точногорешения (обозначим его x∗ ) на отрезке [a; b]. Для этого потребуем, чтобы оно являлось решениемтакой системы уравнений:xi = Si (x1 , x2 , .
. . , xn ), i = 1, n,(3.12)где Si — некоторая функция. Будем задавать Si (x) в виде:Si (x1 , x2 , . . . , xn ) = xi − τi (x1 , x2 , . . . , xn )fi (x1 , x2 , . . . , xn ).где τi — функция-параметр, не обращающаяся в нуль в некоторой окрестности x∗ . Легко проверить,что в данном случае x∗ будет решением (3.12). Теперь зададим итерационный процесс следующимобразом (xkl — координаты вектора xk , который должен будет сходиться к решению):xk+1= Sl (xk1 , xk2 , . .
. , xkn ),lk = 0, 1, . . .При этом задается вектор x0 — начальное приближение.Итак, мы ожидаем сходимость: k→∞xk = (xk1 , xk2 , . . . , xkn )T −→ x∗ .Для одиночных уравнений достаточным условием сходимости было выполнение неравенства|S 0 (x)| < 1всюду на рассматриваемом отрезке. Посмотрим, что нам потребуется в данном случае для уменьшенияпогрешности на каждом шаге:zik+1 = xk+1− x∗i = Si (xk1 , xk2 , .
. . , xkn ) − Si (x∗1 , x∗2 , . . . , x∗n ).iПусть у функций Si существуют первые производные. Тогда мы можем применить обобщеннуюформулу Лагранжа и получим:Si (xk1 , xk2 , . . . , xkn ) − Si (x∗1 , x∗2 , . . . , x∗n ) =nX∂Si (ξ1k , ξ2k , . .
. , ξnk ) k(xl − x∗l ).∂xll=1Соберем все производные в одну матрицу: Ak = (akij ) =формула может быть переписана так:z k+1 = Ak z k .∂Si (ξ1k , ξ2k , . . . , ξnk )∂xj. Тогда предыдущая52Глава 3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙИз этого следует, что ||z k+1 || = ||Ak z k || 6 ||Ak || · ||z k ||. Таким образом, если для всех k на нашемотрезке [a; b] выполняется неравенство||Ak || 6 q < 1,(3.13)то последовательность ||z k || будет сходится по норме.
Этого нам будет достаточно. ∂Si будет иметь норму,Заметим, что условие (3.13) будет выполнено, если матрица A = max [a; b] ∂xj меньшую единицы. Тогда, очевидно, ||Ak || 6 ||A||, и процесс будет сходиться. Такое требование можноудовлетворить, подбирая параметры τi . В частности, связывая их с производными функций fi (x),можно получить метод Ньютона.Метод НьютонаЗдесь мы требуем от функций fi (x1 , x2 , . . . , xn ) существование первых производных. Согласноопределению x∗ ,fi (x∗1 , x∗2 , .
. . , x∗n ) = 0, i = 1, n.(3.14)Теперь с помощью преобразований этого тождества получим формулу для итерационного процесса.Для этого зададимся k-м приближением xk = (xk1 , xk2 , . . . , xkn )T и зафиксируем некоторое i ∈ [1; n].Заметим, что (3.14) можно переписать так:fi (xk1 + (x∗1 − xk1 ), xk2 + (x∗2 − xk2 ), . . . , xkn + (x∗n − xkn )) = 0.Применив обобщенную формулу Лагранжа, получим:fi (xk1 , xk2 , . . . , xkn ) +nX∂fi (ξ1k , ξ2k , .
. . , ξnk ) ∗(xl − xkl ) = 0.∂xll=1, получим такую формулу для поискаТеперь, заменив ξ k на xk , а x∗l — на новое приближение xk+1l:nX∂fi (xk1 , xk2 , . . . , xkn ) k+1fi (xk1 , xk2 , . . . , xkn ) +(xl − xkl ) = 0.(3.15)∂xlxk+1ll=1Обозначив∆xkl=xk+1l−xkl ,перепишем ее так:nX∂fi (xk1 , xk2 , .
. . , xkn )∆xkl = −fi (xk1 , xk2 , . . . , xkn ).∂xll=1Это система линейных уравнений для поиска ∆xk вида A∆xk = −f. Решая ее, мы находим ∆xk ,а затем и xk+1= xkl + ∆xkl для l = 1, n.lТеорему о сходимости данного метода мы напишем неформально и примем без доказательства.Теорема 3.3. В достаточно малой окрестности искомого корня итерационный процесс по методуНьютона (задаваемый формулой (3.15)) сходится, если определитель матрицы A не обращается вэтой окрестности в нуль.
При этом скорость сходимости — квадратичная.Замечание. Данный итерационный процесс сходится быстро: для достижения неравенства (обычный для метода Ньютона критерий завершения ИП)||xk+1 − xk || < εпри ε = 10−5 достаточно всего 3-5 итераций. Однако он требует большого объема вычислений — ведьна каждом шаге нам приходится решать систему уравнений.3.6. РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ53Примеры решения нелинейных уравненийПример 3.1. (Метод простой итерации)Пусть f (x) = x3 − x − 1. Найдем корень уравнения x3 − x − 1 = 0 на отрезке [−2; 3].
Для началапроведем локализацию корней: введем на отрезке сетку и посчитаем значение функции в ее узлах:−2−7xif (xi )−1−10−11−125323Так как f (1)f (2) < 0, а наша функция непрерывна, то на отрезке [1; 2] обязательно есть кореньуравнения. Будем искать его методом простой итерации.1. Как уже говорилось, мы ставим в соответствие уравнению f (x) = 0 уравнение x = S(x), где S(x)наиболее часто берется в виде S(x) = x − τ (x)f (x). Выберем τ (x) = τ > 0.
ТогдаS(x) = x − τ (x3 − x − 1).Соответственно, итерационный процесс задается так:xk+1 = S(xk ) = xk − τ ((xk )3 − xk − 1).Для его сходимости, согласно замечанию к теореме 3.1, нам было достаточно выполнения неравенства |S 0 (x)| < 1 на [1; 2]. Посмотрим, какие ограничения это условие даст на τ :|S 0 (x)| < 1 ⇐⇒ |1 − τ (3x2 − 1)| < 1 ⇐⇒−1 < 1 − τ (3x2 − 1) < 1.(3.16)При x ∈ [1; 2] и для любого положительного τ правое неравенство в (3.16) верно всегда.
Левоенеравенство перепишется так:2τ< 2.3x − 1При x ∈ [1; 2] знаменатель дроби достигает минимума при x = 2. Отсюда итоговое ограничение наτ таково:22=.τ<3 · 22 − 11111 39. В этом случае S(x) = x −(x − x − 1), max |S 0 (x)| =. Это число —111111x∈[1; 2]знаменатель геометрической прогрессии, характеризующей скорость сходимости процесса. Как видно,оно не очень мало, и сходится все медленно. Насколько медленно, можно понять из таблицы первыхприближений:Возьмем τ =k012345— в данном примере x∗ ≈ 1.32472.xk1.11.169911.221611.257841.282181.29802xk+1 = S(xk )1.169911.221611.257841.282181.298021.3081254Глава 3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ2.
Можно по-разному выбирать функцию S(x) :x3 − x − 1 = 0 =⇒ x =— и можно взять S(x) =√3√3x + 1.x + 1. При этом скорость сходимости будет выше, так какS 0 (x) =13(x + 1)231<23(1 + 1) 3≈ 0.2 = q.3. С другой стороны,x3 − x − 1 = 0 ⇐⇒ x = x3 − 1.Однако, если взять S(x) = x3 − 1, то S 0 (x) = 3x2 > 1 на [1; 2], что противоречит достаточномуусловию сходимости.Пример 3.2. (Метод простой итерации и метод Ньютона)Будем искать корень уравнения x3 − 1 = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
