ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4685
Скачиваний: 6
Лекция 2
16
и согласно (2.3) имеем т. e.
|x
k+p
− x
k
|
6
|x
1
− x
0
|
p
X
j=1
q
k+j
−1
= q
k
1
− q
p
1
− q
|x
1
− x
0
|
6
q
k
1
− q
|x
1
− x
0
|,
т.е.
x
k+p
− x
k
6
q
k
1
− q
|x
1
− x
0
|,
k, p = 1, 2, . . .
Поскольку правая часть последнего неравенства стремится к нулю при
k
→ ∞ и не зависит от p, последовательность {x
k
} является фундамен-
тальной. Следовательно, существует
lim
k
→∞
x
k
= x
∗
∈ U
r
(a).
Переходя в
x
n+1
= ϕ(x
n
) к пределу при k
→ ∞ и учитывая непрерывность
функции
ϕ(x), получим x
∗
= ϕ(x
∗
), т. е. x
∗
— решение уравнения
x = ϕ(x).
Предположим, что
x
0
∗
— какое-то ещё решение уравнения
x = ϕ(x),
принадлежащее отрезку
U
r
(a). Тогда
x
∗
− x
0
∗
= ϕ(x
∗
)
− ϕ(x
0
∗
)
и по условию теоремы
|x
∗
− x
0
∗
|
6
q
|x
∗
− x
0
∗
|.
Так как
q < 1, последнее неравенство может выполняться лишь при x
0
∗
=
x
∗
, т. е. решение единственно.
Докажем оценку погрешности (2.2). Итерационное соотношение даёт
x
k+1
− x
∗
= ϕ(x
k
)
− ϕ(x
∗
),
и так как
x
k
, x
∗
∈ U
r
(a), приходим к неравенству
|x
k+1
− x
∗
|
6
q
|x
k
− x
∗
|,
справедливому для всех
k = 0, 1, . . ., из которого и следует оценка (2.2).
Следствие (1). Если
|ϕ
0
(x)
|
6
q < 1 для всех x
∈ U
r
(a), выполнено
условие
|ϕ(a) − a|
6
(1
− q)r и x
0
∈ U
r
(a), то уравнение x = ϕ(x) име-
ет единственное решение
x
∗
∈ U
r
(a), метод x
n+1
= ϕ(x
n
) сходится и
справедлива оценка
|x
k
− x
∗
|
6
q
k
|x
0
− x
∗
|, k = 0, 1, 2, . . .
Лекция 2
17
Доказательство. Воспользуемся формулой конечных приращений:
ϕ(x
0
)
− ϕ(x
00
) = (x
0
− x
00
)
· ϕ(ξ),
ξ
∈ (x
0
, x
00
).
Следовательно,
ϕ(x) является липшиц-непрерывной на U
r
(a). Все условия
теоремы выполняются.
Следствие (2). Пусть уравнение
ϕ(x) = x имеет решение x
∗
, функция
ϕ(x) непрерывно дифференцируема на отрезке
U
r
(x
∗
) =
{x : |x − x
∗
|
6
r
}
и
|ϕ
0
(x
∗
)
| < 1. Тогда существует ε > 0 такое, что на отрезке U
r
(x
∗
)
уравнение
ϕ(x) = x не имеет других решений и метод x
n+1
= ϕ(x
n
)
сходится, если только
x
0
∈ U
ε
(x
∗
).
Доказательство. Поскольку
ϕ(x) непрерывно дифференцируема на от-
резке
U
r
(x
∗
) и
|ϕ
0
(x
∗
)
| < 1, найдутся числа q ∈ (0, 1) и ε ∈ (0, r] такие, что
|ϕ
0
(x)
|
6
q < 1 для всех x
∈ U
ε
(x
∗
).
Оба следствия говорят о сходимости
{x
n
} к корню x
∗
. При этом след-
ствие 1 гарантирует существование и единственность корня в области
U
r
(a). Следствие 2, наоборот, требует от нас уверенности, что корень есть
в области, где
|ϕ
0
(x)
| < 1.
Критерий останова.
Вблизи корня итерации сходятся примерно как
геометрическая прогрессия со знаменателем
q = (x
n
−x
n
−1
)/(x
n
−1
−x
n
−2
).
Чтобы сумма дальнейших её членов не превосходила
ε, должен выпол-
няться критерий сходимости
q
x
n
− x
n
−1
1
− q
=
(x
n
− x
n
−1
)
2
|2x
n
−1
− x
n
− x
n
−2
|
< ε.
При выполнении этого условия итерации можно прекращать.
Лекция 2
18
1.2.3
Метод Ньютона.
Пусть задано уравнение
f (x) = 0. Запишем начальную сумму ряда Тей-
лора для
f (x):
f (x)
≈ f(x
0
) + (x
− x
0
)f
0
(x
0
).
Заменим в исходном уравнении функцию
f (x) полученным приближени-
ем:
f (x
0
) + (x
− x
0
)f
0
(x
0
) = 0.
Если теперь выразить
x и затем сделать замену x
0
→ x
n
,
x
→ x
n+1
,
получим итерационный процесс
x
n+1
= x
n
−
f (x
n
)
f
0
(x
n
)
.
(2.4)
Мы получили определение метода Ньютона или метода касательных. По-
следнее название обусловлено работой метода:
- из начального приближения
x
n
строим перпендикуляр к оси абсцисс
до пересечения с графиком функции
f (x);
- через полученную точку пересечения проводим касательную к графи-
ку
f (x) до пересечения с осью абсцисс (точка x
n+1
);
- повторяем все сначала ...
Предполагая, что
f (x) дважды непрерывно дифференцируема, напи-
шем разложение в ряд Тейлора в корне
x
∗
в окрестности
n-го приближе-
ния:
f (x
∗
) = 0 = f (x
n
) + f
0
(x
n
)(x
∗
− x
n
) +
1
2
f
00
(ξ
n
)(x
∗
− x
n
)
2
,
где
ξ
n
∈ [x
∗
, x
n
].
Разделив последнее соотношение на
f
0
(x
n
) и перенеся первые два сла-
гаемых из правой части в левую, получим:
x
n
−
f (x
n
)
f
0
(x
n
)
− x
∗
=
1
2
f
00
(ξ
n
)
f
0
(x
n
)
(x
n
− x
∗
)
2
,
что, учитывая (2.4), переписываем в виде
x
n+1
− x
∗
=
1
2
f
00
(ξ
n
)
f
0
(x
n
)
(x
n
− x
∗
)
2
.
Лекция 2
19
Отсюда
|x
n+1
− x
∗
| =
1
2
|f
00
(ξ
n
)
|
|f
0
(x
n
)
|
|x
n
− x
∗
|
2
.
(2.5)
Получаем оценку
|x
n+1
− x
∗
|
6
1
2
M
2
m
1
|x
n
− x
∗
|
2
,
где
M
2
= max
[a,b]
|f
00
(x)
|, m
1
= min
[a,b]
|f
0
(x)
|.
Очевидно, ошибка на каждом шаге убывает, если
1
2
M
2
m
1
|x
0
− x
∗
| < 1
Требуется хорошее начальное приближение. На рис. 2.2 видно, как из-за
плохого начального приближения метод Ньютона зацикливается.
b
a
x
∗
x
f (x)
Рис. 2.2: Пример плохого приближения в методе Ньютона
Теорема 2.3. Пусть задана функция
f (x) и определён итерационный
процесс
x
k+1
= x
k
−
f (x
k
)
f
0
(x
k
)
. Если для всех
x
∈ [a, b] справедливо одно из
следующих:
1)
f
0
(x) > 0, f
00
(x) > 0 и x
0
= b,
2)
f
0
(x) < 0, f
00
(x) < 0 и x
0
= b,
)
тогда
{x
k
}
монотонно убывает и
сходится к
x
∗
;
3)
f
0
(x) > 0, f
00
(x) < 0 и x
0
= a,
4)
f
0
(x) < 0, f
00
(x) > 0 и x
0
= a,
)
тогда
{x
k
}
монотонно возрастает и
сходится к
x
∗
.
Лекция 2
20
x
0
= b
x
1
x
2
x
∗
f
0
> 0
f
00
> 0
y
x
x
0
= a x
1
x
2
x
∗
f
0
< 0
f
00
> 0
y
x
x
0
= b
x
1
x
2
x
∗
f
0
< 0
f
00
< 0
y
x
x
0
= a x
1
x
2
x
∗
f
0
> 0
f
00
< 0
y
x
Рис. 2.3: Условия сходимости метода Ньютона