книги / Численные методы. Ч. 1
.pdfРис. 3.4. Геометрический смысл процедуры метода Ньютона
Пример 3.2. Требуется определить корни уравнения |
f(x) = х2 - а = 0. |
||||
Согласно рассмотренному методу Ньютона строится итерационная процедура |
|||||
ХМ 1 . Х, , . Ф |
1 |
|
|
||
|
- Х |
Г |
И |
‘ |
|
Поскольку |
|
|
|
|
|
f'(x,°)) = 2x,“l , |
|
|
|||
,(«♦!) _ „О _ (Х' |
) ~ 8 _ х(»> _ 1 х1») + _ ± |
||||
|
2х(о) |
х |
|
2^ |
' 2х(п) |
Таким образом, применение процедуры метода Ньютона к заданному уравнению |
|||||
приводит к вычислительному процессу |
|
|
|
|
|
х,п*1 = |
+ |
— |
1 . |
|
|
х |
2l |
|
x M J |
|
|
Для а=2 “точное” решение х = Л = 1,4142135624. Результаты расчетов
приведены в табл. 3.2.
Последовательность получения приближенного решения уравнения х2 - 2 = 0 методом Ньютона
Номер |
Приближения решения |
||
итерации |
|||
2,0 |
-10,0 |
||
1 |
|||
2 |
1,5 |
-5.1 |
|
3 |
1,416666667 |
-2,746078431 |
|
4 |
1,414215686 |
-1.737194874 |
|
5 |
1,414213562 |
-1.444238095 |
|
6 |
1,4142135624 |
-1,414525655 |
|
7 |
1,4142135624 |
-1,414213597 |
|
8 |
1,4142135624 |
-1,4142135624 |
|
Теорема 3.2. Пусть выполнены следующие предположения: |
|||
- х - корень уравнения |
f(x) = 0; |
|
|
- первая производная f'(x) * 0 Vx е А = {х | |х - х|< г}; |
|
||
- вторая производная f "(х) непрерывна в А; |
|
||
- константа С = |
- х| < I . где М, = inf|f'(x)| >0, |
М ; = sup|f"(x)| |
|
Тогда, если х(0) е А, то метод Ньютона сходится, причем |
|||
|
x(N)- x < с 2‘ -' х |
(3.7) |
|
Доказательство.
Для оценки погрешности решения воспользуемся формулой Тейлора для функции
f(x) возле точки х(п):
f(x) = f(x(nl) + f'(x<n,) (x - х"”) + J ^ ( x - х"")2 $<•> 6 (х '"\х ).
В силу f(x) = 0 получаем соотношение
f(x‘">) |
j , r t ' “ ) ( ; |
г (х (п)) |
> 2f'(x<"f |
С другой стороны, согласно методу Ньютона
f(x |
г |
/ ,n. |
f ( X ' n ) |
|
х'п1 - - |
Г |
/ i - |
||
|
(х |
), |
1 |
> Г (х - ) |
=(*<"' -*)+(*- *'“1 +^ | Ц ( х - ‘“О1
Отсюда,
fWc(n)\
X<D+1) - X = ТГ7-4(х- Х<П) )2. (3.8) 2f'(x(n)) V '
то есть имеет место квадратичная сходимость.
Пусть х(0) е А, £ е А . Из формулы (3.8) получаем
+ 2f'(x(0|) V >
то есть оценка (3.7) выполнена для N=1. Допустим, что формула (3.7) верна для произвольного q. С учетом условия С< 1, имеем
|х(ч>- х| < с 2<, ||х<0) - х| :£ |х,0) - х| < г ,
то есть х(ч) € А, £(ч) е А , а следовательно определены
М, = infjf'(х)| >0, М2 = sup|f"(x)j.
Из соотношения (3.8) получаем
2f'(x«)' > 2МЛ /
Согласно (3.7)
(х « - х ) 2 = |х<’>-х |'|х (ч) - х |^ С 2,-‘ •С2,-'(х(0) - х ) 2 =С 2,+,-2(х<,|) - х ) 2
С учетом этого, из предыдущего выражения следует:
и,*» |
1 2M,V |
< Ма.с ^ -» (х<« _ х)2 = с ,,*,-г[- ^ -|х ,°| - х|1 |х,0>- |
||||
1 |
' 2М, |
V |
' |
[2М ,1 |
'J 1 |
|
= С2<Н"2С-|х(0) - х| = С2<Н_1|х(0) -х|.
Но это как раз и означает, что формула (3.7) справедлива при N = q+1.
В силу С<1 из выражения (3.7) следует сходимость метода Ньютона:
|х(п) - х|--------- |
>0, |
что и требовалось доказать.
Модификации метода Ньютона
Одна из модификаций метода Ньютона заключается в том, что производную от функции f(x) определяют лишь один раз для начальной точки итерационного процесса (рис. 3.5 а):
х (п+1) _ х (п)
При таком способе решения уравнения скорость сходимости уменьшается, иногда существенно. Эту модификацию метода целесообразно применять в том случае, когда вычисление производной связано с большими затратами вычислительных ресурсов (времени, оперативной памяти), либо когда аналитический вид функции f(x) неизвестен, что часто бывает при решении прикладных инженерных проблем. Кроме того, практически всегда можно подобрать начальное значение х((1) таким образом, что f'(x(0)) * 0, то есть не будет аварийной остановки вычислительного алгоритма.
Другая модификация (метод секущих) заключается в замене производной функции f(x) ее разностным аналогом (рис. 3.5 Ь):
х (п+1) _ *<*»)
Г(х,п,)~ f(x<n_0) *
В этом случае получена двухточечная схема, то есть для начала расчетов необходимо задать две начальные точки х(,,\ х(,)
Пример 3.3. Определить корни уравнения
f(x) = х2 -4х + 3 = 0.
Точное решение этого уравнения: х, = I, х2 = 3.
Для использования метода простых итераций представим это уравнение в форме
(3.2): |
|
_ х2 +3 |
(р(х) = хг +3 |
4 |
4 |
4
Для проверки условий сходимости в качестве константы условия Липшица возьмем
|
X |
С= тах|ф'(х)| = т а х - |
|
хеЛ 1 v 71 |
х е Л 2 |
Очевидно, что 0 < С < 1 на интервале (-2, 2), г = 2. Центр интервала а = 0. При этих параметрах условие теоремы
|ф(а) “ а| = ^ > (1- С) • г = (1 - 0,9999...) • 2 = 0,0000.. .02
не выполняется, чем объясняется отсутствие сходимости решения, например, при начальном приближении х(0) =4.
Поскольку
Р(х) = 2х -4,
алгоритм метода Ньютона в соответствии с выражением (3.6) записывается в виде
|
и |
1 - » |
2х(п)- 4 |
2х(в)- 4 * |
|
Результаты вычисления по обоим алгоритмам приведены в табл. 3.3.
Рис. 3.5. Схемы модифицирования метода Ньютона:
а - с начальным значением касательной; b - метод секущих
Возможно, что на заданном отрезке может оказаться несколько корней. В этом случае итерационный процесс позволит вычислить какой-то один корень уравнения. Для отделения корней в некоторых случаях можно воспользоваться следующим приемом.
Системы нелинейных уравнений
Рассмотрим систему m нелинейных алгебраических уравнений:
......0 = 0. f2(xi-x2......Xm) = 0,
f.(x ,.x ,..... xm) = 0.
Введем обозначения:
х,
X = | х2 1 e R ”
x,tn
Теперь задача о решении системы нелинейных алгебраических уравнений может быть сформулирована следующим образом: необходимо найти вектор X .
(3.9)
В общем случае итерационные методы решения системы нелинейных алгебраических уравнений могут быть представлены в канонической форме
|
(З.Ю) |
где Х(Н) - начальное приближение; числа г |
и матрицы В(п+,) имеющие обратные. - |
итерационные параметры. |
|
Метод простых итераций
Из выражения (3.10) можно получить систему линейных алгебраических уравнений относительно искомых неизвестных:
g (n + l)j^ (n + l) _ g (n + l)j £ (n ) _
В |
частном |
случае |
стационарного |
итерационного |
метода. |
когда |
В(п+,) = В = const. |
т(п+,) = т = const, последнее выражение преобразуется к виду |
|
||||
|
|
|
Х(п+И =Х (П. _ тВ-'р (Х<">)- |
|
|
|
Иначе говоря, исходная итерационная процедура сводится к схеме метода
простых итераций: |
|
|
|
|
|
|
|
|
|
|
|
Х(п+|) = ф (х (")), |
ф (х (п,)= Х(о) -TB“'F (x (n)). |
(3.11) |
|||||
Вектор X e R ra, для |
которого |
Х = ф (х ), |
называется |
неподвижной |
точкой |
||||
оператора Ф. Очевидно, что вектор X является решением уравнения X = Ф(Х) |
тогда и |
||||||||
только тогда, когда он является неподвижной точкой. |
|
|
|
||||||
Оператор |
Ф |
является сжимающим на |
множестве O e R m |
с коэффициентом |
|||||
сжатия С, если |
Vx,,x2 еП |
имеет место |
|
|
|
|
|
|
|
|
|
|
|Ф(Х2) ~ Ф(х,)|| 5 С • |(ха - |
X,| . |
|
|
|
||
Теорема 3.3. Пусть оператор Ф определен на множестве А = |х |
е Rm | ||Х - а|| < г} и |
||||||||
является сжимающим на этом множестве с коэффициентом сжатия С , причем |
|
||||||||
|
|
|
||ф(а) - а| £ (l - С) • г, |
0 < С < 1 . |
|
|
|
||
Тогда в |
А |
оператор Ф имеет единственную неподвижную точку |
X |
||||||
итерационный метод (3.11) сходится к X при любом начальном |
Х*0* еА . Имеет место |
||||||||
оценка погрешности: |
|
|
|
|
|
|
|
|
|
|x (N)- x | s c N|x <0,- x | .
Доказательство этой теоремы изложено в книгах [4. 9].
Метод релаксации
Положим в выражении (3.11) матрицу В = Е (тождественное преобразование), тогда Ф^Х<П)) = X<n) - TF^X1”1) . Метод сходится, если (ф'(х)||<1 VX еА . В этом
случае
'« .о |
«10 |
«10 |
dx, |
dx, |
дкт |
Ф'(Х) = E -tF '(X ). F’(X) = |
|
|
« ■ О |
« ■ ( ) |
« ■ О |
дх, |
дх: |
дкт |
М етод Ньютона |
|
|
|
|
|
|
Как и ранее, выберем в окрестности |
решения X вектор X и воспользуемся |
|||||
формулой Тейлора для функций ^(х,,х2,..мХт ), |
i = 1,т: |
|
||||
|
|
|
т |
яг/Мв> F(a) |
|
|
......xm) = f i(x|"»,x<->.......x<->)+z |
^ |
|
|
|||
C ’ |
|
|
|
|
|
|
где W - e A . |
|
|
|
|
|
|
c(n) |
|
|
|
|
|
|
.‘эт . |
|
|
|
|
|
|
С учетом того, |
что |
fj(x,,x2..... Хщ) = 0, |
i = l,m, итерационная процедура метода |
|||
Ньютона принимает форму |
|
|
|
|||
п> |
affx(n) т<“> |
Т<"Л |
|
|
|
|
Z |
' -'- |
J ......" к *"- x f )) +f>(x!”>’x<“)........ х" ) =0- |
i=1’ra- |
|||
В матричной записи последнее соотношение имеет вид |
|
|||||
|
|
F'(x(”))-(x<M,) - X(o,)+ F(x(n))= 0, |
(3.12) |
|||
где вид матрицы |
|
j определен выше. Сравнение формулы (3.12) с выражением |
||||
(3.10) позволяет определить итерационные параметры: |
|
|||||
|
|
|
g(n+o _ |
j, |
х(п+,) = 1. |
|
Соотношение (3.12) позволяет построить вычислительный итерационный алгоритм:
Х(«+1>=х<“>- |F'(X(“)))’, F(X(")).
Теорема 3.4. Пусть выполнены условия:
1.Оператор F(X) определен в замкнутом шаре |Х - Х (0)|^ г , дважды
дифференцируем там, при этом вторая производная ограничена И х )1<;М.
2. F'^X(0)j имеет обратный оператор, для нормы которого выполнена оценка
( F'(X<°>))"LD .
