Интерполяционный многочлен Лагранжа

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

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

Определение

Этот пример показывает интерполяционный многочлен Лагранжа для четырёх точек (-9,5), (-4,2), (-1,-2) и (7,9), а также полиномы y_i l_i(x), каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных x_j

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

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

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

$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.

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

Основная статья: Интерполяция алгебраическими многочленами

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

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

С точки зрения линейной алгебры

На единственность интерполяционного многочлена можно также взглянуть с точки зрения СЛАУ. Рассмотрим систему уравнений $P(x_{0})=y_{0},P(x_{1})=y_{1},\dots ,P(x_{n})=y_{n}$. В явном виде она записывается как:

$${\begin{cases}a_{0}+a_{1}x_{0}+a_{2}x_{0}^{2}+\dots +a_{n}x_{0}^{n}=y_{0},\\a_{0}+a_{1}x_{1}+a_{2}x_{1}^{2}+\dots +a_{n}x_{1}^{n}=y_{1},\\\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots ,\\a_{0}+a_{1}x_{n}+a_{2}x_{n}^{2}+\dots +a_{n}x_{n}^{n}=y_{n}\\\end{cases}}$$

Её можно переписать в виде системы уравнений $Xa=y$ с неизвестным вектором $a=(a_{0},a_{1},\dots ,a_{n})$:

$${\begin{bmatrix}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n}\\\end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\\vdots \\a_{n}\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n}\end{bmatrix}}$$

Матрица $X$ в такой системе является матрицей Вандермонда и её определитель равен $\prod \limits _{i<j}(x_{i}-x_{j})$. Соответственно, если все точки $x_{0},x_{1},\dots ,x_{n}$ различны, то матрица невырождена и система обладает единственным решением.

С точки зрения китайской теоремы об остатках

По теореме Безу остаток от деления $P(x)$ на $(x-a)$ равен $P(a)$. Таким образом, всю систему можно воспринимать в виде системы сравнений:

$${\begin{cases}P(x)\equiv y_{0}{\pmod {x-x_{0}}},\\P(x)\equiv y_{1}{\pmod {x-x_{1}}},\\\dots ,\\P(x)\equiv y_{n}{\pmod {x-x_{n}}},\\\end{cases}}$$

По китайской теореме об остатках у такой системы есть единственное решение по модулю $(x-x_{0})(x-x_{1})\dots (x-x_{n})$, то есть, заданная система однозначно определяет многочлен степени не выше $n$. Такое представление многочлена в виде наборов остатков по модулям мономов аналогично представлению числа в виде остатков от деления на простые модули в системе остаточных классов. При этом явная формула для многочлена Лагранжа также может быть получена в соответствии с формулами китайской теоремы: ${\textstyle P(x)=\sum \limits _{i=0}^{n}y_{i}M_{i}M_{i}^{-1}}$, где $M_{i}=\prod \limits _{j\neq i}(x-x_{j})$ и $M_{i}^{-1}=\prod \limits _{j\neq i}(x-x_{j})^{-1}{\pmod {x-x_{i}}}=\prod \limits _{j\neq i}(x_{i}-x_{j})^{-1}$.

Пример

Функция тангенса и интерполяция

Найдем формулу интерполяции для $f(x)=\mathop {\mathrm {tg} } \nolimits (x)$ имеющей следующие значения:

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

$l_{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)$

$l_{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)$

$l_{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)$

$l_{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)$

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

Получим

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

Применения

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

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

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

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

Многочлены Лагранжа степеней от нулевой до пятой для функции $\cos(5\pi x)$

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

$f(x)\approx \sum _{i=0}^{n}f(x_{i})l_{i}(x)$

В частности,

$\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.

Случай равномерного распределения узлов интерполяции

В случае равномерного распределения узлов интерполяции x_j выражаются через расстояние между узлами интерполяции h и начальную точку x₀:

$x_{i}\equiv {x_{0}+ih}$,

и, следовательно,

${x_{j}-x_{i}}\equiv (j-i)h.$

Подставив эти выражения в формулу базисного полинома и вынеся h за знаки перемножения в числителе и знаменателе, получим

$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}\prod \limits _{i=0,\,i\neq j}^{n}(j-i)}$

Теперь можно ввести замену переменной

$y={{x-x_{0}} \over h}$

и получить полином от y, который строится с использованием только целочисленной арифметики. Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования длинной арифметики.

См. также

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

Ссылки

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