Материал: Вычислительный эксперимент и методы вычислений
y
−
y
i
−
1
y
i
−
y
i
−
1
=
x
−
x
i
−
1
x
i
−
x
i
−
1
.
(29)
Отсюда находим
y
=
a
i
x
+
b
i
,
x
i
−
1
6
x
6
x
i
,
(30)
a
i
=
y
i
−
y
i
−
1
x
i
−
x
i
−
1
,
b
i
=
y
i
−
1
−
a
i
x
i
−
1
.
Многочлен Лагранжа
Будем строить интерполяционный многочлен, единый для всего отрезка
[
x
0
, x
n
]
, в виде линейной комбинации многочленов степени
n
L
(
x
) =
y
0
l
0
(
x
) +
y
1
l
1
(
x
) +
...
+
y
n
l
n
(
x
)
(31)
так, чтобы многочлены
l
i
(
x
)
обращались в нуль во всех узлах интерпо-
ляции, кроме
i
-го, где он должен равняться единице. Этим условиям
при
i
= 0
отвечает многочлен вида:
l
0
(
x
) =
(
x
−
x
1
)(
x
−
x
2
)(
x
−
x
3
)
...
(
x
−
x
n
)
(
x
0
−
x
1
)(
x
0
−
x
2
)(
x
0
−
x
3
)
...
(
x
0
−
x
n
)
.
(32)
Аналогично,
l
1
(
x
) =
(
x
−
x
0
)(
x
−
x
2
)(
x
−
x
3
)
...
(
x
−
x
n
)
(
x
1
−
x
0
)(
x
1
−
x
2
)(
x
1
−
x
3
)
...
(
x
1
−
x
n
)
,
l
2
(
x
) =
(
x
−
x
0
)(
x
−
x
1
)(
x
−
x
3
)
...
(
x
−
x
n
)
(
x
2
−
x
0
)(
x
2
−
x
1
)(
x
2
−
x
3
)
...
(
x
2
−
x
n
)
,
...
(33)
l
i
(
x
) =
(
x
−
x
0
)
...
(
x
−
x
i
−
1
)(
x
−
x
i
+1
)
...
(
x
−
x
n
)
(
x
i
−
x
0
)
...
(
x
i
−
x
i
−
1
)(
x
i
−
x
i
+1
)
...
(
x
i
−
x
n
)
,
...
l
n
(
x
) =
(
x
−
x
0
)(
x
−
x
1
)(
x
−
x
2
)
...
(
x
−
x
n
−
1
)
(
x
n
−
x
0
)(
x
n
−
x
1
)(
x
n
−
x
2
)
...
(
x
n
−
x
n
−
1
)
.
Подставляя (32),(33) в (31) получаем интерполяционный многочлен
Лагранжа:
L
(
x
) =
n
X
i
=0
y
i
(
x
−
x
0
)
...
(
x
−
x
i
−
1
)(
x
−
x
i
+1
)
...
(
x
−
x
n
)
(
x
i
−
x
0
)
...
(
x
i
−
x
i
−
1
)(
x
i
−
x
i
+1
)
...
(
x
i
−
x
n
)
.
(34)
16
Единственность найденного решения следует из единственности решения
системы (27). Если положить
n
= 1
в (34), то получим рассмотренный
ранее случай линейной интерполяции, при
n
= 2
– случай квадратичной
интерполяции
L
(
x
) =
(
x
−
x
1
)(
x
−
x
2
)
(
x
0
−
x
1
)(
x
0
−
x
2
)
y
0
+
(
x
−
x
0
)(
x
−
x
2
)
(
x
1
−
x
0
)(
x
1
−
x
2
)
y
1
+
+
(
x
−
x
0
)(
x
−
x
1
)
(
x
2
−
x
0
)(
x
2
−
x
1
)
y
2
.
(35)
Многочлен Ньютона
При построении интерполяционного многочлена Лагранжа не накла-
дывалось никакого требования на распределение узлов интерполяции.
Рассмотрим случай равноотстоящих по оси
x
узлов интерполяции. Вве-
дем
h
=
x
i
−
x
i
−
1
– шаг интерполяции,
h
=
const
.
Конечные разности
Разности первого порядка (первые разности):
∆
y
0
=
y
1
−
y
0
=
f
(
x
0
+
h
)
−
f
(
x
0
)
,
∆
y
1
=
y
2
−
y
1
=
f
(
x
0
+ 2
h
)
−
f
(
x
0
+
h
)
,
...
∆
y
n
−
1
=
y
n
−
y
n
−
1
=
f
(
x
0
+
nh
)
−
f
(
x
0
+ (
n
−
1)
h
)
.
Разности второго порядка (вторые разности):
∆
2
y
0
= ∆
y
1
−
∆
y
0
,
∆
2
y
1
= ∆
y
2
−
∆
y
1
,
Разности порядка
k
:
∆
k
y
i
= ∆
k
−
1
y
i
+1
−
∆
k
−
1
y
i
,
i
= 0
,
1
, ..., n
−
1
.
Конечные разности выражаются через значения функции
∆
2
y
0
= ∆
y
1
−
∆
y
0
= (
y
2
−
y
1
)
−
(
y
1
−
y
0
) =
y
2
−
2
y
1
+
y
0
,
∆
3
y
0
= ∆
2
y
1
−
∆
2
y
0
=
...
=
y
3
−
3
y
2
+ 3
y
1
−
y
0
.
В общем случае
∆
k
y
i
=
k
X
j
=0
(
−
1)
j
C
j
k
y
i
+
k
−
j
,
(36)
17
C
j
k
=
k
!
j
!(
k
−
j
)!
.
Интерполяционный многочлен Ньютона будем искать в следующем
виде:
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
)
.
(37)
График многочлена должен проходить через заданные узлы, то есть
N
(
x
i
) =
y
i
i
= 0
,
1
, ..., n
. Для нахождения коэффициентов многочлена
получаем систему
N
(
x
0
) =
a
0
=
y
0
,
N
(
x
1
) =
a
0
+
a
1
(
x
1
−
x
0
) =
a
0
+
a
1
h
=
y
1
,
N
(
x
2
) =
a
0
+
a
1
(
x
2
−
x
0
) +
a
2
(
x
2
−
x
0
)(
x
2
−
x
1
) =
=
a
0
+ 2
a
1
h
+ 2
a
2
h
2
=
y
2
,
...
Отсюда находим коэффициенты
a
i
:
a
0
=
y
0
,
a
1
=
y
1
−
a
0
h
=
y
1
−
y
0
h
=
∆
y
0
h
,
a
2
=
y
2
−
a
0
−
2
a
1
h
2
h
2
=
y
2
−
a
0
−
2∆
y
0
2
h
2
=
∆
2
y
0
2
h
2
,
...
a
k
=
∆
k
y
0
k
!
h
k
,
k
= 0
,
1
,
2
, ..., n.
Подставляя в (37), получаем
N
(
x
) =
y
0
+
∆
y
0
h
(
x
−
x
0
) +
∆
2
y
0
2!
h
2
(
x
−
x
0
)(
x
−
x
1
) +
...
+
+
∆
n
y
0
n
!
h
n
(
x
−
x
0
)(
x
−
x
1
)
...
(
x
−
x
n
−
1
)
.
(38)
Если ввести переменную
t
=
x
−
x
0
h
, то
x
=
x
0
+
th,
x
−
x
1
h
=
x
−
x
0
−
h
h
=
t
−
1
,
x
−
x
2
h
=
t
−
2
,
...,
x
−
x
n
−
1
h
=
t
−
n
+ 1
.
18
В результате получаем
N
(
x
) =
N
(
x
0
+
th
) =
y
0
+
t
∆
y
0
+
t
(
t
−
1)
2!
∆
2
y
0
+
...
+
+
t
(
t
−
1)
...
(
t
−
n
+ 1)
n
!
∆
n
y
0
.
(39)
Полученное выражение называется первым интерполяционным много-
членом Ньютона для интерполирования вперед. Оно справедливо на всем
отрезке
[
x
0
, x
n
]
, но для уменьшения ошибок округления разумно исполь-
зовать его только для левой половины рассматриваемого отрезка.
Полученная формула для интерполирования вперед практически
неудобна для интерполирования функции вблизи конца отрезка. В этом
случае используют формулу для многочлена Ньютона для интерполиро-
вания назад, которую мы сейчас и получим.
Интерполирующий полином запишем в следующем виде:
N
(
x
) =
a
0
+
a
1
(
x
−
x
n
) +
a
2
(
x
−
x
n
)(
x
−
x
n
−
1
) +
...
+
a
n
(
x
−
x
x
)(
x
−
x
n
−
1
)
...
(
x
−
x
1
)
.
(40)
Из условия совпадения значения многочлена и функции в узлах находим:
N
(
x
n
) =
y
n
⇒
a
0
=
y
n
,
N
(
x
n
−
1
) =
y
n
−
1
⇒
y
n
+
a
1
(
−
h
) =
y
n
−
1
⇒
a
1
=
y
n
−
y
n
−
1
h
=
∆
y
n
−
1
h
.
Аналогично находим
a
2
=
y
n
−
2
y
n
−
1
+
y
n
−
2
2
h
2
=
∆
2
y
n
−
2
2
h
2
,
и в общем случае, применяя метод математической индукции, можно
строго доказать, что
a
k
=
∆
k
y
n
−
k
k
!
h
k
.
Подставляя найденные коэффициенты в (40), получаем
N
(
x
) =
y
n
+
∆
y
n
−
1
1!
h
(
x
−
x
n
) +
∆
2
y
n
−
2
2!
h
2
(
x
−
x
n
)(
x
−
x
n
−
1
) +
...
+
+
∆
n
y
0
n
!
h
n
(
x
−
x
n
)
...
(
x
−
x
1
)
.
(41)
19
Делая замену
t
=
x
−
x
n
h
, окончательно находим
N
(
x
) =
N
(
x
n
+
th
) =
y
n
+
t
∆
y
n
−
1
+
t
(
t
+ 1)
2!
∆
2
y
n
−
2
+
...
+
+
t
(
t
+ 1)
...
(
t
+
n
−
1)
n
!
∆
n
y
0
.
(42)
Формула (42) – второй интерполяционный многочлен Ньютона для ин-
терполирования назад.
Отметим, что существует один и только один интерполяционный мно-
гочлен при заданном наборе узлов интерполяции. Формулы Лагранжа,
Ньютона и др. порождают один и тот же многочлен, разница состоит в
алгоритме их построения.
3.3.
Точность интерполяции
Значения интерполяционного многочлена
y
=
ϕ
(
x
)
и рассматривае-
мой функции
y
=
f
(
x
)
в узлах
x
=
x
i
,
(
i
= 0
,
1
, ..., n
)
в точности совпада-
ют. Если исследуемая функция — многочлен степени
n
, то
f
(
x
)
≡
ϕ
(
x
)
.
В остальных случаях разность
R
(
x
) =
f
(
x
)
−
ϕ
(
x
)
6
= 0
.
Очевидно, что
R
(
x
)
есть погрешность интерполяции и называется оста-
точным членом интерполяционной формулы. Можно показать, что оста-
точный член интерполяционного многочлена Лагранжа имеет вид
R
L
(
x
) =
(
x
−
x
0
)(
x
−
x
1
)
...
(
x
−
x
n
)
(
n
+ 1)!
f
(
n
+1)
(
x
0
)
.
(43)
В этой формуле
f
(
n
+1)
(
x
0
)
– производная
(
n
+ 1)
-го порядка функции
f
(
x
)
в некоторой точке
x
0
∈
[
x
0
, x
n
]
.
Из анализа (43) следует, что погрешность интерполяции тем выше,
чем ближе точка
x
лежит к концам отрезка
[
x
0
, x
n
]
. Если же использо-
вать интерполяционный многочлен вне отрезка
[
x
0
, x
n
]
, то погрешность
возрастает очень заметно.
Остаточный член интерполяцинного многочлена Ньютона для случая
равноотстоящих узлов следует из (43)
R
N
(
x
) =
t
(
t
−
1)
...
(
t
−
n
)
(
n
+ 1)!
f
(
n
+1)
(
x
0
)
h
n
+1
,
t
=
x
−
x
0
h
.
(44)
20