Интерполяцио́нный многочле́н Лагра́нжа — многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n+1 пар чисел (x0 , y0 ), (x1 , y1 ),…, (xn , yn ), где все xj различны, существует единственный многочлен L(x) степени не более n , для которого L(xj ) = yj .
В простейшем случае (n=1 ) — это линейный многочлен, график которого — прямая, проходящая через две заданные точки.
Этот пример показывает интерполяционный многочлен Лагранжа для четырёх точек
(-9,5) ,
(-4,2) ,
(-1,-2) и
(7,9) , а также полиномы
yi li (x) , каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных
xj
Лагранж предложил способ вычисления таких многочленов:
L
(
x
)
=
∑
i
=
0
n
y
i
l
i
(
x
)
{\displaystyle L(x)=\sum _{i=0}^{n}y_{i}l_{i}(x)}
где базисные полиномы определяются по формуле:
l
i
(
x
)
=
∏
j
=
0
,
j
≠
i
n
x
−
x
j
x
i
−
x
j
=
x
−
x
0
x
i
−
x
0
⋯
x
−
x
i
−
1
x
i
−
x
i
−
1
⋅
x
−
x
i
+
1
x
i
−
x
i
+
1
⋯
x
−
x
n
x
i
−
x
n
{\displaystyle l_{i}(x)=\prod _{j=0,j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}={\frac {x-x_{0}}{x_{i}-x_{0}}}\cdots {\frac {x-x_{i-1}}{x_{i}-x_{i-1}}}\cdot {\frac {x-x_{i+1}}{x_{i}-x_{i+1}}}\cdots {\frac {x-x_{n}}{x_{i}-x_{n}}}}
li (x) обладают следующими свойствами:
являются многочленами степени n
li (xi ) = 1 li (xj ) = 0 при j ≠ i
Отсюда следует, что L(x) , как линейная комбинация li (x) , может иметь степень не больше n , и L(xi ) = yi .
Функция тангенса и интерполяция
Найдем формулу интерполяции для f(x) = tan(x ) имеющей следующие значения:
x
0
=
−
1.5
f
(
x
0
)
=
−
14
,
1014
x
1
=
−
0.75
f
(
x
1
)
=
−
0
,
931596
x
2
=
0
f
(
x
2
)
=
0
x
3
=
0.75
f
(
x
3
)
=
0
,
931596
x
4
=
1.5
f
(
x
4
)
=
14
,
1014.
{\displaystyle {\begin{aligned}x_{0}&=-1.5&&&&&f(x_{0})&=-14,1014\\x_{1}&=-0.75&&&&&f(x_{1})&=-0,931596\\x_{2}&=0&&&&&f(x_{2})&=0\\x_{3}&=0.75&&&&&f(x_{3})&=0,931596\\x_{4}&=1.5&&&&&f(x_{4})&=14,1014.\end{aligned}}}
ℓ
0
(
x
)
=
x
−
x
1
x
0
−
x
1
⋅
x
−
x
2
x
0
−
x
2
⋅
x
−
x
3
x
0
−
x
3
⋅
x
−
x
4
x
0
−
x
4
=
1
243
x
(
2
x
−
3
)
(
4
x
−
3
)
(
4
x
+
3
)
{\displaystyle \ell _{0}(x)={x-x_{1} \over x_{0}-x_{1}}\cdot {x-x_{2} \over x_{0}-x_{2}}\cdot {x-x_{3} \over x_{0}-x_{3}}\cdot {x-x_{4} \over x_{0}-x_{4}}={1 \over 243}x(2x-3)(4x-3)(4x+3)}
ℓ
1
(
x
)
=
x
−
x
0
x
1
−
x
0
⋅
x
−
x
2
x
1
−
x
2
⋅
x
−
x
3
x
1
−
x
3
⋅
x
−
x
4
x
1
−
x
4
=
−
8
243
x
(
2
x
−
3
)
(
2
x
+
3
)
(
4
x
−
3
)
{\displaystyle \ell _{1}(x)={x-x_{0} \over x_{1}-x_{0}}\cdot {x-x_{2} \over x_{1}-x_{2}}\cdot {x-x_{3} \over x_{1}-x_{3}}\cdot {x-x_{4} \over x_{1}-x_{4}}={}-{8 \over 243}x(2x-3)(2x+3)(4x-3)}
ℓ
2
(
x
)
=
x
−
x
0
x
2
−
x
0
⋅
x
−
x
1
x
2
−
x
1
⋅
x
−
x
3
x
2
−
x
3
⋅
x
−
x
4
x
2
−
x
4
=
3
243
(
2
x
+
3
)
(
4
x
+
3
)
(
4
x
−
3
)
(
2
x
−
3
)
{\displaystyle \ell _{2}(x)={x-x_{0} \over x_{2}-x_{0}}\cdot {x-x_{1} \over x_{2}-x_{1}}\cdot {x-x_{3} \over x_{2}-x_{3}}\cdot {x-x_{4} \over x_{2}-x_{4}}={3 \over 243}(2x+3)(4x+3)(4x-3)(2x-3)}
ℓ
3
(
x
)
=
x
−
x
0
x
3
−
x
0
⋅
x
−
x
1
x
3
−
x
1
⋅
x
−
x
2
x
3
−
x
2
⋅
x
−
x
4
x
3
−
x
4
=
−
8
243
x
(
2
x
−
3
)
(
2
x
+
3
)
(
4
x
+
3
)
{\displaystyle \ell _{3}(x)={x-x_{0} \over x_{3}-x_{0}}\cdot {x-x_{1} \over x_{3}-x_{1}}\cdot {x-x_{2} \over x_{3}-x_{2}}\cdot {x-x_{4} \over x_{3}-x_{4}}=-{8 \over 243}x(2x-3)(2x+3)(4x+3)}
ℓ
4
(
x
)
=
x
−
x
0
x
4
−
x
0
⋅
x
−
x
1
x
4
−
x
1
⋅
x
−
x
2
x
4
−
x
2
⋅
x
−
x
3
x
4
−
x
3
=
1
243
x
(
2
x
+
3
)
(
4
x
−
3
)
(
4
x
+
3
)
.
{\displaystyle \ell _{4}(x)={x-x_{0} \over x_{4}-x_{0}}\cdot {x-x_{1} \over x_{4}-x_{1}}\cdot {x-x_{2} \over x_{4}-x_{2}}\cdot {x-x_{3} \over x_{4}-x_{3}}={1 \over 243}x(2x+3)(4x-3)(4x+3).}
Получим
L
(
x
)
=
1
243
(
f
(
x
0
)
x
(
2
x
−
3
)
(
4
x
−
3
)
(
4
x
+
3
)
−
8
f
(
x
1
)
x
(
2
x
−
3
)
(
2
x
+
3
)
(
4
x
−
3
)
+
3
f
(
x
2
)
(
2
x
+
3
)
(
4
x
+
3
)
(
4
x
−
3
)
(
2
x
−
3
)
−
8
f
(
x
3
)
x
(
2
x
−
3
)
(
2
x
+
3
)
(
4
x
+
3
)
+
f
(
x
4
)
x
(
2
x
+
3
)
(
4
x
−
3
)
(
4
x
+
3
)
)
=
4
,
834848
x
3
−
1
,
477474
x
.
{\displaystyle {\begin{aligned}L(x)&={1 \over 243}{\Big (}f(x_{0})x(2x-3)(4x-3)(4x+3)\\&{}\qquad {}-8f(x_{1})x(2x-3)(2x+3)(4x-3)\\&{}\qquad {}+3f(x_{2})(2x+3)(4x+3)(4x-3)(2x-3)\\&{}\qquad {}-8f(x_{3})x(2x-3)(2x+3)(4x+3)\\&{}\qquad {}+f(x_{4})x(2x+3)(4x-3)(4x+3){\Big )}\\&=4,834848x^{3}-1,477474x.\end{aligned}}}
Используя полином Лагранжа можно показать, что
∑
i
=
1
k
P
n
(
i
)
=
T
n
+
1
(
k
)
=
k
T
n
(
k
)
{\displaystyle \sum _{i=1}^{k}{P}_{n}(i)={T}_{n+1}(k)=k{T}_{n}(k)}
если
P
n
(
i
)
=
i
n
{\displaystyle {P}_{n}(i)={i}^{n}}
T
n
(
k
)
=
k
n
n
+
1
+
k
n
−
1
2
+
…
{\displaystyle {T}_{n}(k)={{{k}^{n}} \over {n+1}}+{{{k}^{n-1}} \over {2}}+\dots }
Указанная выше сумма задаёт биективное отображение между
P
n
(
i
)
{\displaystyle {P}_{n}(i)}
T
n
(
k
)
{\displaystyle {T}_{n}(k)}
Полиномы Лагранжа используются для интерполяции , а также для численного интегрирования .
Пусть для функции f(x) известны значения yi =f(xi ) в некоторых точках. Тогда мы можем интерполировать эту функцию как
f
(
x
)
≈
∑
i
=
0
n
f
(
x
i
)
l
i
(
x
)
{\displaystyle f(x)\approx \sum _{i=0}^{n}f(x_{i})l_{i}(x)}
В частности,
∫
a
b
f
(
x
)
d
x
≈
∑
i
=
0
n
f
(
x
i
)
∫
a
b
l
i
(
x
)
d
x
{\displaystyle \int \limits _{a}^{b}f(x)dx\approx \sum _{i=0}^{n}f(x_{i})\int \limits _{a}^{b}l_{i}(x)dx}
Значения интегралов от li не зависят от f(x) , и их можно вычислить заранее, зная последовательность xj .
Случай равномерного распределения узлов интерполяции [ править | править вики-текст ] В случае равномерного распределения узлов интерполяции xj выражаются через расстояние между узлами интерполяции h и начальную точку x0 :
x
i
≡
x
0
+
i
h
{\displaystyle x_{i}\equiv {x_{0}+ih}}
и, следовательно,
x
j
−
x
i
≡
(
j
−
i
)
h
.
{\displaystyle {x_{j}-x_{i}}\equiv (j-i)h.}
Подставив эти выражения в формулу базисного полинома и вынеся h за знаки перемножения в числителе и знаменателе, получим
l
j
(
x
)
=
∏
i
=
0
,
i
≠
j
n
(
x
−
x
i
)
(
x
j
−
x
i
)
=
∏
i
=
0
,
i
≠
j
n
(
x
−
x
0
−
i
h
)
h
n
−
1
∏
i
=
0
,
i
≠
j
n
(
j
−
i
)
{\displaystyle l_{j}(x)={\prod _{i=0,\,i\neq j}^{n}{(x-x_{i}) \over (x_{j}-x_{i})}}={\prod \limits _{i=0,\,i\neq j}^{n}(x-x_{0}-ih) \over h^{n-1}\prod \limits _{i=0,\,i\neq j}^{n}(j-i)}}
Теперь можно ввести замену переменной
y
=
x
−
x
0
h
{\displaystyle y={{x-x_{0}} \over h}}
и получить полином от y , который строится с использованием только целочисленной арифметики . Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования длинной арифметики .
