ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4689
Скачиваний: 6
Определитель Вандермонда
146
11. Решение системы линейных уравнений методом
LU -разложений
12. Вычисление обратной матрицы методом
LU -разложений
13. Численное решение дифференциальных уравнений методом Рунге-
Кутты 4-го порядка
14. Интегрирование методом Гаусса Литература: [5] гл.4, §3.
15. Решение системы нелинейных уравнений методом Ньютона Литера-
тура: [5] гл.5, §4.
16. Численное решение дифференциальных уравнений методом Адамса
Литература: [5] гл.6, §3.
17. Поиск собственных значений матрицы степенным методом
18. Решение системы линейных уравнений методом релаксации
19. Решение системы линейных уравнений методом наискорейшего гра-
диентного спуска
4.2
Определитель Вандермонда
Будем вычислять определитель Вандермонда индуктивно, избавляясь на
k-ом шаге от x
k
. Вначале имеем:
∆(x
1
, x
2
, . . . , x
n
) =
1
1
· · ·
1
x
1
x
2
· · ·
x
n
x
2
1
x
2
2
· · ·
x
2
n
...
...
. . .
...
x
n
−1
1
x
n
−1
2
· · · x
n
−1
n
.
Определитель Вандермонда
147
Вычитая первый столбец из всех последующих и разложив полученный
определитель по первой строке имеем:
∆(x
1
, x
2
, . . . , x
n
) =
1
0
· · ·
0
x
1
x
2
− x
1
· · ·
x
n
− x
1
x
2
1
x
2
2
− x
2
1
· · ·
x
2
n
− x
2
1
...
...
. . .
...
x
n
−1
1
x
n
−1
2
− x
n
−1
1
· · · x
n
−1
n
− x
n
−1
1
=
=
x
2
− x
1
x
3
− x
1
· · ·
x
n
− x
1
x
2
2
− x
2
1
x
2
3
− x
2
1
· · ·
x
2
n
− x
2
1
...
...
. . .
...
x
n
−1
2
− x
n
−1
1
x
n
−1
3
− x
n
−1
1
· · · x
n
−1
n
− x
n
−1
1
.
Теперь вычтем из каждой строки предыдущую, умноженную на
x
1
:
∆(x
1
, x
2
, . . . , x
n
) =
=
x
2
− x
1
x
3
− x
1
· · ·
x
n
− x
1
x
2
(x
2
− x
1
)
x
3
(x
3
− x
1
)
· · ·
x
n
(x
n
− x
1
)
...
...
. . .
...
x
n
−2
2
(x
2
− x
1
) x
n
−2
3
(x
3
− x
1
)
· · · x
n
−2
n
(x
n
− x
1
)
.
Вынесем из каждого столбца общий множитель:
∆(x
1
, x
2
, . . . , x
n
) = (x
2
−x
1
)(x
3
−x
1
) . . . (x
n
−x
1
)
1
1
· · ·
1
x
2
x
3
· · ·
x
n
...
...
. . .
...
x
n
−2
2
x
n
−2
3
· · · x
n
−2
n
=
= (x
2
− x
1
)(x
3
− x
1
) . . . (x
n
− x
1
)∆(x
2
, . . . , x
n
).
С определителем
∆(x
2
, . . . , x
n
) выполним такие же вычисления:
∆(x
1
, x
2
, . . . , x
n
) =
= (x
2
− x
1
)(x
3
− x
1
) . . . (x
n
− x
1
)
· (x
3
− x
2
) . . . (x
n
− x
2
)∆(x
3
, . . . , x
n
)
Модифицированный метод Ньютона
148
Продолжив вычисления получим:
∆(x
1
, x
2
, . . . , x
n
) = (x
2
− x
1
)(x
3
− x
1
) . . . (x
n
− x
1
)
·
· (x
3
− x
2
) . . . (x
n
− x
2
) . . . (x
n
− x
n
−1
) =
Y
i<j
(x
j
− x
i
).
4.3
Ряд Тейлора
Теорема 11.2. Если функция
f (x) имеет n + 1 производную на отрезке
с концами
a и x, то для произвольного положительного числа p спра-
ведливо, что
f (x) =
n
X
k=0
f
(k)
(a)
k!
(x
− a)
k
+ R
n+1
(x),
где остаточный член
R
n+1
(x) может быть представлен в одной из сле-
дующих форм:
1. форма Шлёмильха—Роша:
R
n+1
(x) =
x
−a
x
−ξ
p
(x
−ξ)
n+1
n!p
f
(n+1)
(ξ), где ξ
∈ [a, x];
2. форма Лагранжа:
R
n+1
(x) =
(x
−a)
n+1
(n+1)!
f
(n+1)
(ξ), ξ
∈ [a, x];
3. форма Коши:
R
n+1
(x) =
(x
−a)
n+1
(1
−θ)
n
n!
f
(n+1)
[a + θ(x
− a)], где 0 < θ < 1;
4. интегральная форма:
R
n+1
(x) =
1
n!
x
R
a
(x
− t)
n
f
(n+1)
(t) dt;
5. форма Пеано:
R
n+1
(x) = o[(x
− a)
n
].
4.4
Модифицированный метод Ньютона
Покажем, что модифицированный метод Ньютона имеет квадратичную
скорость сходимости.
Модифицированный метод Ньютона
149
Пусть уравнение
f (x) = 0 имеет корень x
∗
кратности
p. Последнее по
определению кратного корня означает, что
f (x
∗
) = f
0
(x
∗
) = f
00
(x
∗
) = . . . = f
(p
−1)
(x
∗
) = 0, но f
(p)
(x
∗
)
6= 0.
Из обоих частей модифицированного метода Ньютона
x
n+1
= x
n
−
pf (x
n
)
f
0
(x
n
)
отнимем
x
∗
x
n+1
− x
∗
= x
n
− x
∗
−
pf (x
n
)
f
0
(x
n
)
=
(x
n
− x
∗
)f
0
(x
n
)
− pf(x
n
)
f
0
(x
n
)
.
Если обозначить
F (x) = (x
− x∗)f
0
(x)
− pf(x), то числитель можно заме-
нить на
F (x
n
):
x
n+1
− x
∗
=
F (x
n
)
f
0
(x
n
)
.
(4.1)
Несложно заметить, что
F (x) = (x
− x
∗
)f
0
(x)
− pf(x)
⇒ F (x
∗
) = 0,
F
0
(x) = (x
− x
∗
)f
00
(x)
− (p − 1)f
0
(x)
⇒ F
0
(x
∗
) = 0,
F
00
(x) = (x
− x
∗
)f
000
(x)
− (p − 2)f
00
(x)
⇒ F
00
(x
∗
) = 0,
· · ·
· · ·
F
(p
−1)
(x) = (x
− x
∗
)f
(p)
(x)
−
−(p − (p − 1))f
(p
−1)
(x)
⇒ F
(p
−1)
(x
∗
) = 0,
F
(p)
(x) = (x
− x
∗
)f
(p+1)
(x)
−
−(p − p))f
(p)
(x) = (x
− x
∗
)f
(p+1)
(x)
⇒ F
(p)
(x
∗
) = 0.
Разложим теперь
F (x
n
) в ряд Тейлора с центром в точке x
∗
. Остаточный
член запишем в интегральной форме.
F (x
n
) = F (x
∗
)
| {z }
=0
+ F
0
(x
∗
)
|
{z
}
=0
(x
n
− x
∗
) + F
00
(x
∗
)
|
{z
}
=0
(x
n
− x
∗
)
2
2!
+ . . . +
+ F
(p
−1)
(x
∗
)
|
{z
}
=0
(x
n
− x
∗
)
p
−1
(p
− 1)!
+
1
(p
− 1)!
x
n
Z
x
∗
F
(p)
(t)(x
n
− t)
p
−1
dt =
=
1
(p
− 1)!
x
n
Z
x
∗
F
(p)
(t)(x
n
− t)
p
−1
dt.
Модифицированный метод Ньютона
150
Вспомним, что
F
(p)
(t) = (t
− x
∗
)f
(p+1)
(t). Тогда
F (x
n
) =
1
(p
− 1)!
x
n
Z
x
∗
(x
n
− t)
p
−1
(t
− x
∗
)f
(p+1)
(t) dt.
Так как функция
(x
n
− t)
p
−1
(t
− x
∗
) не меняет знак на отрезке [x
∗
, x
n
],
то можно применить теорему о среднем и вынести
f
(p+1)
(t) из-под знака
интеграла:
F (x
n
) =
f
(p+1)
(ξ
n
)
(p
− 1)!
x
n
Z
x
∗
(x
n
− t)
p
−1
(t
− x
∗
) dt,
где
ξ
n
∈ [x
∗
, x
n
].
Легко получить, что
x
n
Z
x
∗
(x
n
− t)
p
−1
(t
− x
∗
) dt =
(x
n
− x
∗
)
p+1
p(p + 1)
.
В итоге
F (x
n
) =
f
(p+1)
(ξ
n
)
(p
− 1)!
·
(x
n
− x
∗
)
p+1
p(p + 1)
=
f
(p
−1)
(ξ
n
)(x
n
− x
∗
)
p+1
(p + 1)!
.
Числитель выражения (4.1) получен, рассмотрим теперь знаменатель.
Разложим
f
0
(x
n
) в ряд Тейлора с центром разложения x
∗
. Остаточный
член ряда запишем в форме Лагранжа:
f
0
(x
n
) = f
0
(x
∗
)
| {z }
=0
+ f
00
(x
∗
)
|
{z
}
=0
(x
n
− x
∗
) + f
000
(x
∗
)
|
{z
}
=0
(x
n
− x
∗
)
2
2!
+ . . . +
+ f
(p
−1)
(x
∗
)
|
{z
}
=0
(x
n
− x
∗
)
(p
−2)
(p
− 2)!
+ f
(p)
(η
n
)
(x
n
− x
∗
)
(p
−1)
(p
− 1)!
=
= f
(p)
(η
n
)
(x
n
− x
∗
)
(p
−1)
(p
− 1)!
,
где
η
n
∈ [x
∗
, x
n
].
Вернёмся теперь к (4.1):
x
n+1
−x
∗
=
F (x
n
)
f
0
(x
n
)
=
f
(p+1)
(ξ
n
)(x
n
− x
∗
)
p+1
(p + 1)!
!,
f
(p)
(η
n
)
(x
n
− x
∗
)
(p
−1)
(p
− 1)!
!
=
=
1
p(p
− 1)
·
f
(p
−1)
(ξ
n
)
f
(p)
(η
n
)
(x
n
− x
∗
)
2
.