ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4696
Скачиваний: 6
Лекция 3
26
Многочлен Ньютона.
Приведём ещё одну форму записи интерполя-
ционного полинома:
P
n
(x) = A
0
+ A
1
(x
− x
0
) + A
2
(x
− x
0
)(x
− x
1
) + . . . +
+ A
n
(x
− x
0
)(x
− x
1
) . . . (x
− x
n
−1
). (3.1)
Требование совпадения значений полинома с заданными значениями функ-
ции приводит к системе линейных уравнений с треугольной матрицей для
неопределённых коэффициентов
A
i
,
i = 0, 1, . . . , n:
A
0
= f
0
,
A
0
+ A
1
(x
1
− x
0
) = f
1
,
A
0
+ A
1
(x
2
− x
0
) + A
2
(x
2
− x
0
)(x
2
− x
1
) = f
2
,
· · ·
A
0
+ A
1
(x
n
− x
0
) + A
2
(x
n
− x
0
)(x
n
− x
1
) + . . . +
+A
n
(x
n
− x
0
)(x
n
− x
1
)
· · · (x
n
− x
n
−1
) = f
n
.
численное решение которой не составляет труда.
Интерполяционный полином, записанный в форме (3.1), называется по-
линомом Ньютона. Он интересен тем, что каждая частичная сумма его
первых
(m+1) слагаемых представляет собой интерполяционный полином
m-й степени, построенный по первым (m + 1) табличным данным.
Сравнение форм Лагранжа и Ньютона.
Многочлен Лагранжа и
многочлен Ньютона суть один и тот же многочлен, записанный в различ-
ных формах. У каждой из форм записи есть свои достоинства:
Лекция 3
27
Многочлен Лагранжа
Многочлен Ньютона
удобно,
если
тре-
буется
приближать
различные
функции,
заданные табличными
значениями в одних и
тех же точках
• удобно, если в качестве результата нуж-
на непосредственно формула, приближа-
ющая функцию
f (x)
• удобно, если требуется добавить но-
вый узел
x
n+1
; достаточно найти только
новый неизвестный коэффициент
A
n+1
,
остальные
A
i
,
i = 0, 1, . . . , n остаются
неизменными
Погрешность интерполяции.
Ошибка приближения функции интер-
поляционным полиномом
n-ой степени в точке x — это разность R
n
(x) =
f (x)
− P
n
(x).
Рассмотрим полином специального вида
(n + 1)-ой степени:
ω
n+1
(x) = (x
− x
0
)(x
− x
1
) . . . (x
− x
n
) =
n
Y
i=0
(x
− x
i
).
Теорема 3.1. Пусть на отрезке
[a, b], таком, что x
i
∈ [a, b], i = 0, 1, . . . , n,
функция
f (x) (n + 1) раз непрерывно дифференцируема. Тогда
R
n
(x) =
f
(n+1)
(x
0
)
(n + 1)!
ω
n+1
(x),
где
x
0
∈ [a, b].
Доказательство. Будем искать погрешность в виде
R
n
(x) = C(x)ω
n+1
(x),
(3.2)
где
C(x) — функция, ограниченная на [a, b] (при такой форме записи вы-
ражения для погрешности гарантируется, что она обращается в ноль в
узлах интерполяции).
Чтобы получить представление о
C(x), рассмотрим вспомогательную
функцию
ϕ(x) = f (x)
− P
n
(x)
− C(ξ)ω
n+1
(x),
(3.3)
Лекция 3
28
где
ξ — некоторое фиксированное значение на отрезке [a, b]. Очевидно, на
[a, b] функция ϕ(x) имеет (n + 2) нуля. Это узлы интерполяции и точка
x = ξ. Согласно теореме Ролля, существует точка x
0
∈ [a, b], в которой
ϕ
(n+1)
(x
0
) = 0. Продифференцировав 3.3 (n + 1) раз и подставив x = x
0
,
получим
0 = ϕ
(n+1)
(x
0
) = f
(n+1)
(x
0
)
− (n + 1)!C(ξ).
Отсюда
C(ξ) =
f
(n+1)
(x
0
)
(n+1)!
. (Ясно, что
x
0
в теореме Ролля зависит от располо-
жения нулей функции
ϕ(x); тем самым x
0
представляет собой некоторую
неявную зависимость
x
0
= x
0
(ξ) и полученное отношение действительно
определяет функцию от
ξ.)
Переобозначая
C(ξ) на C(x) и учитывая 3.2, получаем утверждение
теоремы.
Хочется контролировать поведение
ω
n+1
(x) на отрезке [a, b]. Сравним,
к примеру, поведение на отрезке
[
−1, 1] ω
10
(x) c выбором равноотстоящих
узлов (
−1, −
8
9
,
−
7
9
, . . . ,
8
9
, 1) и ω
10
(x) с узлами Чебышёва (cos
19π
20
,
cos
17π
20
,
cos
15π
20
, . . . , cos
π
20
).
Из рисунка 3.1 видно, что многочлен
ω
10
(x) меньше отклоняется от оси
Ox: max
[
−1,1]
ω
10
(x)
≈ 2·10
−3
< 13
·10
−3
≈ max
[
−1,1]
ω
10
(x). Оказывается, что среди
всех многочленов
ω
n+1
(x) с главным коэффициентом 1 и (n + 1) корнем
на отрезке
[a, b] многочлены Чебышёва менее всего отклоняются от нуля.
При больших
n > 10 интерполяция по равноотстоящим узлам практи-
чески не используется:
1. может не быть сходимости (функция Рунге
f (x) =
1
1+25x
2
, у которой
ошибка интерполяции с ростом
n бесконечно возрастает);
2. даже малые погрешности в табличных данных приводят к большим
(неустранимым) ошибкам интерполяции.
При интерполяции по чебышёвским узлам этих неприятностей нет.
В таблице приведены результаты приближения интерполяционными по-
линомами различной степени функции Рунге
Лекция 3
29
PSfrag
replaemen
ts
−1
−0.5
0
0
.
5
1
×10
−
3
−15
−10
−5
0
5
PSfrag
replaemen
ts
−1
−0.5
0
0
.
5
1
×10
−
3
−2
−1
0
1
2
а)
б)
Рис. 3.1: Многочлен
ω
n+1
(x) = (x
− x
0
)(x
− x
1
)
· . . . · (x − x
n
) при выборе
а) равноотстоящих на
[
−1, 1] узлов; б) чебышёвских узлов.
n
0, 7 < x < 1
|x| < 0, 7 Чебышёвские узлы
4
0,44
0,37
0,40
8
1,01
0,24
0,17
10
1,88
0,3
0,11
20
40,0
0,12
0,01
Функция Рунге — «нехорошая» для интерполирования функция.
Лекция 4
30
1.4
Лекция 4
1.4.1
Многочлены Чебышёва.
Рекуррентная форма записи
Многочлены Чебышёва
T
n
(x), где n
>
0, определяются соотношениями
T
0
(x) = 1,
T
1
(x) = x,
T
n+1
(x) = 2xT
n
(x)
− T
n
−1
(x) при n > 0.
(4.1)
Например,
T
2
(x) = 2x
2
− 1,
T
3
(x) = 4x
3
− 3x,
T
4
(x) = 8x
4
− 8x
2
+ 1, T
5
(x) = 16x
5
− 20x
3
+ 5x.
Тригонометрическая форма записи.
Для любого
θ справедливо cos((n+
1)θ) = 2 cos θ cos nθ
− cos((n − 1)θ). При θ = arccos x получим
cos((n + 1) arccos x) = 2x cos(n arccos x)
− cos((n − 1) arccos x).
(4.2)
Рассмотрим выражение
cos(n arccos x) при n = 0 и n = 1:
cos(0
· arccos x) = 1 = T
0
(x),
cos(1
· arccos x) = x = T
1
(x).
(4.3)
Видно, что (4.3) и (4.2) равносильно (4.1), поэтому при всех
n T
n
(x) =
cos(n arccos x).
Явная форма записи.
Рекуррентное соотношение (4.1) является раз-
ностным. Для его решения заменяют
T
n
(x) на µ
n
. После подстановки и
сокращения получаем:
µ
2
− 2µx + 1 = 0
с корнями
µ
1,2
= x
±
p
x
2
− 1.
При
x
6= ±1 корни простые, поэтому
T
n
(x) = c
1
(x)µ
n
1
+ c
2
(x)µ
n
2
.