ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4686
Скачиваний: 6
Лекция 2
21
Иллюстрация теоремы приведена на рис. 2.3. Поскольку формулировки
и доказательства всех пунктов теоремы совершенно аналогичны, ограни-
чимся доказательством первого пункта.
Доказательство. Монотонность последовательности
{x
k
} докажем по ин-
дукции. По условию
x
0
= b. Предположим, что для некоторого k
>
0
выполняются неравенства
x
∗
< x
k
6
b, и докажем, что тогда
x
∗
< x
k+1
< x
k
.
(2.6)
Так как
f (x
∗
) = 0 и x
k+1
= x
k
−
f (x
k
)
f
0
(x
k
)
, то справедливо
x
k
− x
k+1
=
f (x
k
)
−f(x
∗
)
f
0
(x
k
)
. Воспользуемся формулой конечных приращений Лагранжа. То-
гда получим
x
k
− x
k+1
=
(x
k
− x
∗
)f
0
(ξ
k
)
f
0
(x
k
)
, где ξ
k
∈ (x
∗
, x
k
).
(2.7)
Пусть выполнены условия
f
0
(x) > 0 и f
00
(x) > 0. Тогда
0 <
f
0
(ξ
k
)
f
0
(x
k
)
< 1,
причём последнее неравенство является следствием монотонного возрас-
тания
f
0
(x). Таким образом,
0 <
(x
k
− x
∗
)f
0
(ξ
k
)
f
0
(x
k
)
< x
k
− x
∗
,
и из (2.7) получим
0 < x
k
−x
k+1
< x
k
−x
∗
, т.е. получим требуемое неравен-
ство (2.6). Таким образом, последовательность
{x
k
} монотонно убывает и
ограничена снизу числом
x
∗
. Поэтому данная последовательность имеет
предел, который в силу непрерывности функции
f (x) и условия f
0
(x
∗
)
6= 0
совпадает с корнем
x
∗
уравнения
f (x) = 0.
Определение 2. Число
x
∗
является корнем уравнения
f (x) = 0 крат-
ности
p, если f (x
∗
) = f
0
(x
∗
) = . . . = f
(p
−1)
(x
∗
) = 0, но f
(p)
(x
∗
)
6= 0.
Корень кратности
p = 1 называется простым.
Только простой корень метод Ньютона находит быстро. Поиск крат-
ного корня сильно замедляется. Рассмотрим в качестве примера корень
Лекция 2
22
кратности
2 (то есть f (x
∗
) = f
0
(x
∗
) = 0, но f
00
(x
∗
)
6= 0). Очевидно, в
выражении (2.5) производная
f
0
(x
n
) близка к 0. Разложим f
0
(x
n
) в ряд
Тейлора с центром в точке
x
∗
:
f
0
(x
n
) = f
0
(x
∗
)
| {z }
=0
+f
00
(η
n
)(x
n
− x
∗
) = f
00
(η
n
)(x
n
− x
∗
),
где
η
n
∈ [x
n
, x
∗
]. В итоге (2.5) можно переписать так:
|x
n+1
− x
∗
| =
1
2
|f
00
(ξ
n
)
|
|f
0
(x
n
)
|
|x
n
− x
∗
|
2
=
1
2
|f
00
(ξ
n
)
|
|f
00
(η
n
)(x
n
− x
∗
)
|
|x
n
− x
∗
|
2
=
=
1
2
·
|f
00
(ξ
n
)
|
|f
00
(η
n
)
|
· |x
n
− x
∗
|.
У множителя
|x
n
− x
∗
| пропала степень 2. То есть скорость убывания
погрешности стала линейной.
В случае кратного корня применяют модифицированный метод Ньюто-
на:
x
n+1
= x
n
−
pf (x
n
)
f
0
(x
n
)
, где
p — кратность корня. Добавление коэффициен-
та
p сохраняет квадратичную скорость сходимости к корню. Обоснование
этого факта приведено в конце пособия в разделе «приложения».
Очевидным недостатком метода Ньютона является необходимость вы-
числения производной на каждой итерации. Может оказаться, что на под-
готовку очередного значения
f
0
(x
n
) уйдет слишком много машинного вре-
мени и это перевесит выигрыш в малом числе итераций метода Ньютона.
Иногда упрощают вычисления, используя на каждой итерации значение
производной в точке
x
0
(заменяют
f
0
(x
n
) на f
0
(x
0
)): x
n+1
= x
n
−
f (x
n
)
f
0
(x
0
)
. Это,
к сожалению, лишает метод квадратичной скорости сходимости.
1.2.4
Метод секущих
Очевидно, вблизи корня касательная к графику функции в точке
(x
n
, f (x
n
))
и прямая, проходящая через точки
(x
n
−1
, f (x
n
−1
)) и (x
n
, f (x
n
)) очень близ-
ки. Можно приближённо считать
f
0
(x
n
)
≈
f (x
n
)
− f(x
n
−1
)
x
n
− x
n
−1
.
Лекция 2
23
Последняя замена даёт метод секущих :
x
n+1
= x
n
−
f (x
n
)(x
n
− x
n
−1
)
f (x
n
)
− f(x
n
−1
)
.
Скорость убывания погрешности в методе секущих
q
1,62n
. Это выше линейной ско-
рости
q
n
, но меньше квадратичной
q
2n
.
Метод
Дихотомия
Простые итерации
Ньютон
Секущие
Убывание ошибки
(1/2)
n
q
n
,
0 < q < 1
q
2n
,
0 < q < 1 q
1,62
,
0 < q < 1
Лекция 3
24
1.3
Лекция 3
èíòåðïîëÿöèÿ
ìí-í
Ëàãðàíæ
à
(Íüþòîíà)
ìí-í
Ýðìèò
à
êó
ñî÷íàÿ
êó
ñî÷íî-ëèíåéíàÿ
êó
ñî÷íî-êâàäðàòè÷íàÿ
êó
ñî÷íî-êóáè÷åñê
àÿ
ñïëàéíû
1.3.1
Интерполяция многочленами
Пусть задана конечная таблица
x
0
x
1
x
2
· · · x
n
y
0
y
1
y
2
· · · y
n
, где
x
0
< x
1
< . . . <
x
n
, отражающая некоторую функциональную зависимость
y(x). Такая
таблица может быть получена в ходе проведения эксперимента или в ре-
зультате трудоёмких расчётов. Последнее означает, что получение значе-
ние
y(x), где x не содержится в таблице, может быть невозможно (напри-
мер, если эксперимент уже закончен) или сопряжено с большими затрата-
ми (например, несколько минут или часов машинного или человеческого
времени).
Но на практике нужно знать значение функции в точках отличных от
табличных. Различают два случая: определение
y(x), где x
∈ [x
0
, x
n
] (ар-
гумент
x находится между табличными значениями) — это интерполяция;
и определение
y(x), где x /
∈ [x
0
, x
n
] (аргумент x находится за пределами
табличных значений) — это экстраполяция.
Одним из широко используемых способов приближения функции, за-
данной таблично в
n + 1 точке, есть приближение её многочленами степе-
ни
n.
Многочлен Лагранжа.
Будем называть
x
i
,
i = 0, 1, . . . , n узлами ин-
терполяции.
Лекция 3
25
Рассмотрим многочлен
P
n
(x) = a
n
x
n
+ a
n
−1
x
n
−1
+ . . . + a
1
x + a
0
степени
не выше
n (некоторые коэффициенты, включая главный коэффициент,
могут равняться нулю). Потребуем, чтобы
P
n
(x) совпадал с функцией в
табличных точках, то есть пусть
P
n
(x
k
) = y
k
, где
k = 0, 1, . . . , n. Получим
систему уравнений относительно
a
i
,
k = 0, 1, . . . , n:
a
n
x
n
0
+ a
n
−1
x
n
−1
0
+ . . . + a
1
x
0
+ a
0
= y
0
,
a
n
x
n
1
+ a
n
−1
x
n
−1
1
+ . . . + a
1
x
1
+ a
0
= y
1
,
· · ·
a
n
x
n
n
+ a
n
−1
x
n
−1
n
+ . . . + a
1
x
n
+ a
0
= y
n
.
Определитель последней системы есть определитель Вандермонда (см.
приложение):
∆ =
1 x
0
x
2
0
· · · x
n
0
1 x
1
x
2
1
· · · x
n
1
... ...
. . . ...
1 x
n
x
2
n
· · · x
n
n
=
n
Y
i,j=0
(i
6=j)
(x
i
− x
j
).
В самом начале мы потребовали, чтобы
x
0
< x
1
< . . . < x
n
. Значит, ни од-
на скобка не даст нуля и, следовательно,
∆
6= 0. Последнее означает, что
система имеет единственное решение. Несложно проверить, что следую-
щий многочлен в точности соответствует этому решению (если подставить
табличное
x
k
получим
y
k
):
P
n
(x) = y
0
(x
− x
1
)(x
− x
2
) . . . (x
− x
n
)
(x
0
− x
1
)(x
0
− x
2
) . . . (x
0
− x
n
)
+ . . . +
+ y
k
(x
− x
0
) . . . (x
− x
k
−1
)(x
− x
k+1
) . . . (x
− x
n
)
(x
k
− x
0
) . . . (x
k
− x
k
−1
)(x
k
− x
k+1
) . . . (x
k
− x
n
)
+ . . . +
y
n
(x
− x
0
)(x
− x
1
) . . . (x
− x
n
−1
)
(x
n
− x
0
)(x
n
− x
1
) . . . (x
n
− x
n
−1
)
=
n
X
k=0
y
k
L
(k)
n
(x)
L
(k)
n
(x
k
)
,
где
L
(k)
n
(x) = (x
− x
0
) . . . (x
− x
k
−1
)(x
− x
k+1
) . . . (x
− x
n
) — полиномы n-ой
степени специального вида.