WikiSort.ru - Не сортированное

Интерполяцио́нный многочле́н Лагра́нжа — многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n+1 пар чисел (x₀, y₀), (x₁, y₁),…, (x_n, y_n), где все x_j различны, существует единственный многочлен L(x) степени не более n, для которого L(x_j) = y_j.

В простейшем случае (n=1) — это линейный многочлен, график которого — прямая, проходящая через две заданные точки.

Определение

Лагранж предложил способ вычисления таких многочленов:

${\displaystyle L(x)=\sum _{i=0}^{n}y_{i}l_{i}(x)}$

где базисные полиномы определяются по формуле:

${\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}}}}$

l_i(x) обладают следующими свойствами:

• являются многочленами степени n
• l_i(x_i) = 1
• l_i(x_j) = 0 при j ≠ i

Отсюда следует, что L(x), как линейная комбинация l_i(x), может иметь степень не больше n, и L(x_i) = y_i.

Единственность

Существует единственный многочлен степени не превосходящей ${\displaystyle n}$ , принимающий заданные значения в ${\displaystyle n+1}$ точке (что является обобщением факта, что через любые две точки проходит единственная прямая). Действительно, предположим, что существуют два различных многочлена степени не более ${\displaystyle n}$ : ${\displaystyle P(x)}$ и ${\displaystyle Q(x)}$ , для которых верно, что для ${\displaystyle n+1}$ пар чисел${\displaystyle (x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n}),}$ где все ${\displaystyle x_{j}}$ различны, ${\displaystyle P(x_{j})=Q(x_{j})=y_{j}.}$

Рассмотрим многочлен ${\displaystyle L(x)=P(x)-Q(x)}$ . Подставляя ${\displaystyle x_{j}}$ вместо ${\displaystyle x}$ (${\displaystyle 0\leq j\leq n}$ ), получаем, что ${\displaystyle L(x_{j})=P(x_{j})-Q(x_{j})=y_{j}-y_{j}=0}$ . Таким образом, многочлен ${\displaystyle L(x)}$ имеет ${\displaystyle n+1}$ корней, и все они различны. Следовательно ${\displaystyle L(x)=0}$ , так как ненулевой многочлен степени, не превосходящей ${\displaystyle n}$ имеет не более ${\displaystyle n}$ корней. Следовательно ${\displaystyle P(x)=Q(x)}$ . ■

Пример

Найдем формулу интерполяции для f(x) = tan(x) имеющей следующие значения:

${\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}}}$

${\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)}$

${\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)}$

${\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)}$

${\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)}$

${\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).}$

Получим

${\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}}}$

Применения

Используя полином Лагранжа можно показать, что ${\displaystyle \sum _{i=1}^{k}{P}_{n}(i)={T}_{n+1}(k)=k{T}_{n}(k)}$

если ${\displaystyle {P}_{n}(i)={i}^{n}}$ , то первые два по старшинству коэффициента многочлена ${\displaystyle {T}_{n}(k)={{{k}^{n}} \over {n+1}}+{{{k}^{n-1}} \over {2}}+\dots }$

Указанная выше сумма задаёт биективное отображение между ${\displaystyle {P}_{n}(i)}$ и ${\displaystyle {T}_{n}(k)}$

Полиномы Лагранжа используются для интерполяции, а также для численного интегрирования.

Пусть для функции f(x) известны значения y_i=f(x_i) в некоторых точках. Тогда мы можем интерполировать эту функцию как

${\displaystyle f(x)\approx \sum _{i=0}^{n}f(x_{i})l_{i}(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}$

Значения интегралов от l_i не зависят от f(x), и их можно вычислить заранее, зная последовательность x_j.

См. также

• Схема Эйткена
• Интерполяционные формулы Ньютона
• Интерполяция с кратными узлами
• Схема разделения секрета Шамира
• Комбинаторная теорема о нулях

Имеется викиучебник по теме
«Интерполяционный многочлен Лагранжа»

Ссылки

• М. А. Тынкевич. Глава 7.6.1. Интерполяционный многочлен Лагранжа // Численные методы анализа. — Кемерово, 2002. — ISBN 5-89070-042-1.
• А. Г. Хованский. Полиномы Лагранжа и их применения. Видео-лекция. VI Летняя школа «Современная математика», Дубна, 2006.