|
(x)
d f i
(x) ”
d x t
d x
2
d x ,n
d f -
(x)
d f ,
(x)
d f ,
(x)
F '(* ) =
d x x
d x
2
d * m
Ут «
d f m
(*)
df..,
(x)
_
d x x
dx, ,
d x m
-
(П)
П р и м е р 2.
Метод Пикара.
Пусть
F(x)
представляется в виде
F(x) = Ax-\-G
(х),
где
А
— матрица
пг'Хпг.
Тогда итерации можно определить следую
щим образом:
Axh+i + G{xk)
=0.
209
Итерационный метод можно переписать в виде
A( x k~'—xk) + F ( x h) =
О,
т. е. в канонической форме (3) с
Bh+I = A, xh+l= \.
Можно и здесь
ввести итерационный параметр и рассматривать более общий ме
тод
vk+i
k
А -
------ — +
F(xk) = Q.
П р и м е р 3.
Метод Ньютона
для системы уравнений (Г) стро
ится следующим образом.
Пусть приближение
xk = (x%, хки
. . . ,
хкп)т
уже известно. Выпи
шем разложение функции
fi(xu х2,
. . . .
хт)
по формуле Тейлора в
точке
хк,
t /
\
е
/
k
k
к \
, /
k \
d/i (
а
)
fi
ЛГ2, • • . |
%tn)
—
fi
(-^Lt -*-2» • ■
■
f
%rn)
+ (-^l
-^-l)
д
“f“
UX±
+
(xi
d x ~
, ,
k. dh(x‘)
\Xm
—
Xtn)
dx„
+ 0{ \x — xk
I2),
и отбросим величины второго порядка малости. Тогда система (1)
заменится системой уравнений
т
g t
i x k \
2 ( ^ 7 — М) “
------
Vji{xk) =
0,
i = l , 2 , . .. , т,
(12)
/=1
>
линейной относительно приращений
xs
—
х),
/ = 1, 2, . . . ,
т.
Реше
ние
х = { х и х2,
. . . ,
хт) Т
системы (12) примем за следующее при
ближение и обозначим через
хк+1 —
( 4 Д . . . ,
хк
г.1)т.
Таким образом, итерационный метод Ньютона для (1) опреде
ляется системой уравнений
m
д ! ( x k )
V (*/
f l -
Х к )
-Ц — L
+
и (хк)
= О,
t = l , 2 ____
ш,
(13)
.2—
ах,-
из которой последовательно, начиная с заданного х° =
(х°и ..
.
,хп
п1)
,
находятся векторы
хк, k =l ,
2,. . .
Систему (13) можно записать в векторном виде
F' (xh) {хк+'
—
xh)A-F(xk)
=0,
k = 0,
1, . . . ,
х°
задан,
(14)
где матрица
F'(x)
определена согласно (11). Таким образом, ме
тод Ньютона имеет канонический вид (3), где
Bk+l = F'(xk),
тй+1 = 1.
Для реализации метода Ньютона необходимо существование
матриц
(F'(xk) ) ~\
обратных
F'(xk).
По поводу сходимости метода
Ньютона для систем уравнений можно сказать то же, что и в слу-
210
чае одного уравнения, а именно, метод имеет квадратичную сходи
мость, если начальное приближение выбрано достаточно хорошо.
Приведем без доказательства одну из теорем о сходимости метода Нью
тона.
Пусть
Ет — множество m-мерных вещественных векторов с нормой 1|х|| =
/
т
у/,
= [
,|И !| — норма матрицы
А, подчиненная
данной
норме
вектора.
V
i
= 1
.
Обозначим
Ur (x°) = {.<<=Ет: ||х—х°\\ < г}
и предположим, что в шаре
UT(x°) функции fi(x), i =
1, 2 ,
. . . ,
т, непрерывно
дифференцируемы.
Т е о р е м а 2.
Предположим, что в UT(x°) матрица F'(x) удовлетворяет ус
ловию Липшица с постоянной L, т. е.
НЕ' (х1)— F' (л?) ||
L\\x'— дг2||
для любых х ’, x2e U r (x°). Пусть в UT(xA) матрица ( Е ' ( х ) ) - 1 существует, причем
элементы ее непрерывны и
1!(
F’ ( x ) ) - 4 ] ^ M .
Если начальное приближение х° таково, что ||.F(xo) И =^т) и
причем
оо
Мц
2 92*-1 < г,
k—{'
то система уравнений (
2
)
имеет решение x . e U r (x0), к которому сходится метод
Ньютона (14). Оценка погрешности дается неравенством
,
( А 1
II
к —
-X» | 5С
Мт\
-----
-k .
1-Доказательство теоремы 2 можно найти в [42].
П р и м е р 4.
Модифицированный метод Ньютона
имеет вид
F'(x°) (xk+i—xh) + F ( x k)
= 0
(15)
и обладает линейной сходимостью. Упрощение в численной реали
зации по сравнению с обычным методом Ньютона состоит в том,
что матрицу
F' (х)
надо обращать не на каждой итерации, а лишь
один раз. Возможно циклическое применение модифицированного
метода Ньютона, когда
F'(x)
обращается через определенное чис
ло итераций.
П р и м е р 5.
Метод Ньютона с параметром
имеет вид
F'
(.
хk)
+
F (xk) =
0.
(16)
T
hi
Рассмотренные до сих пор методы являлись линейными отно
сительно новой итерации я*41. Возможны и нелинейные методы, ког
211
да для вычисления
xh+i
приходится решать нелинейные системы
уравнений. Приведем примеры таких методов.
П р и м е р 6.
Нелинейный метод Якоби
для системы (1) имеет
вид
/;
(4, 4, ■
k
k+l
k
, Xj—
i,
Xi t Xij-iy
.
i
= 1, 2 , . . . , m.
4 0 = 0,
(17)
Здесь для отыскания
xk+l
необходимо решить m независимых
скалярных уравнений. Для решения скалярного уравнения можно
применить какой-либо из итерационных методов, рассмотренных
в § 1, причем не обязательно применять один и тот же метод для
всех уравнений.
П р и м е р 7.
Нелинейный метод Зейделя
состоит в последова
тельном решении уравнений
f.(yk+l xk+l
4 +l
у
k
4л — n
11
, л2 , . . . ,
л1
, л4+1, . . . »
Лт)
— и
(18)
гаЬ.
1
относительно переменной х,- ,
i =
1, 2, . . . , m.
Большое распространение получили гибридные методы, когда
внешние итерации осуществляются одним методом, а внутренние —
другим. При этом число внутренних итераций может быть фикси
рованным и не очень большим, так что внутренние итерации не до
водятся до сходимости. В результате получается некоторый новый
метод, сочетающий свойства исходных методов. Приведем приме
ры таких методов.
П р и м е р 8.
Внешние итерации
—
по Зейделю и внутренние
—
по Ньютону.
Здесь в качестве основной (внешней) итерации выби
рается нелинейный метод Зейделя (18), а для нахождения 4 +l
используется метод Ньютона. Обозначим г/, = х*+1. Тогда итерации
определяются следующим образом:
4
+ 1
r * + l
y .S
4
4
ч
/ Л - 1
S\
.
(,-П , Х2 , . . . , Л,-!,
у
и л4+1, . . . ,
Хщ) [tji
—
Уц
-f-
+ П4+\
,
44,4,4»
.........4.) = о,
„s-и
5 = 0 , 1 , . . . , / ,
4 = 4 , yl4 = x Y \
i'= l, 2........
m.
(19)
Здесь индексом s обозначен номер внутренней итерации.
Иногда в (19) делают всего одну внутреннюю итерацию, пола
гая
1 = 0, ya
i = x t , y \ —
4 fl. Тогда приходят к следующему итера
ционному методу:
4 li.
( v k+l
rk+l
4+i 4
x k
,
Л2 » • • • t
Li X i, Л^-i, .
dxi
4- f- (xkH
v - +1
4 4
1 / l \Л 1
* • • • t
1» X/ > X l + l t
. • , x m) (X; +1 — X;)
. . . , 4 . ) = 0,
k = 0,
1 , . . . (20)
212
В частности, при
т =
2 метод (20) принимает вид
dfl(xJ' ^ (4Л - 4)
+
h (4,4) =
0,
dXl
(
21
)
(*Г \ 4
(х!н - х к)
+
h
( 4 +1, **) = 0.
иХ%
П р и м е р 9.
Внешние итерации— по Ньютону и внутренние
—
по Зейделю.
Запишем метод Ньютона для системы (2) в виде
F'
(xft) (x*+1—
хк) + F {хк)
=0,
(22)
dfi (*к)
где
F' (xk) =
(йц),
ау =
---------,
i, / = 1, 2, .. .,
m.
Для решения
dxj
системы линейных уравнений (22) воспользуемся методом Зейделя.
Напомним (см. § 1 гл. 2), что для линейной системы
A w + F = Q
(23)
метод Зейделя строится следующим образом. Матрица
А
представ
ляется в виде суммы
А =
Л _+ /)-|-Л +, где матрицы Л_,
А+, D
соот
ветственно нижняя треугольная, верхняя треугольная и диагональ
ная. Итерации метода Зейделя строятся по правилу
{A_+ D )wa+l+ A +wa+ F = 0,
s = 0, 1, . . . , / ,
(24)
и система (24) решается путем обращения нижней треугольной
матрицы
A-A-D.
В случае системы (22) надо положить
A = F'(xk),
вычислить по
следовательно векторы
ws
согласно (24), начиная с
w° =
0, и поло
жить
wl+l = xk+l
—
хк,
так что
хк+> = xk-\-wI+l.
Заметим, что итерации по Зейделю можно осуществлять и от
носительно вектора х',+1.
Пусть в (24) совершается только одна итерация, т. е.
1 =
0. Тог
да, учитывая, что ш° = 0,
wl = xk+l
—
хк,
получим метод
(А
_+£>)
(xk+l—хк)
+ F (**) = 0,
(25)
где Л _ + 0 — «нижняя треугольная» часть матрицы Якоби (11),
вычисленной при
х = х к.
В частности, при
т =
2 метод (25) принимает вид
(хк
и 4 ) (хк+1
-
4 )
+
h (хк, Хк)
= о,
и
(А4) (4п -А + -&-
(4 ,
А
( 4 м -
А +и А А
= о.
дх\
дх2
(26)
Сопоставление (21) и (26) показывает, что методы, рассмот
ренные в двух последних примерах, не совпадают.
213
Г Л А В А 6
Do'stlaringiz bilan baham: |
