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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определение[править | править исходный текст]

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

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

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}} \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\ne i

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

Пример[править | править исходный текст]

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

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


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

Получим

 \begin{align}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{align}

Применения[править | править исходный текст]

Используя полином Лагранжа можно показать, что \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)

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

Пусть для функции 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_0:

 x_i \equiv {x_0 + ih},

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

 {x_j - x_i} \equiv (j - i)h.

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

l_j(x) = { \prod_{i=0,\,i \ne j}^n {(x - x_i) \over  (x_j - x_i)}} = 
                {\prod\limits_{i=0,\,i \ne j}^n (x - x_0 - ih) \over h^{n-1} \prod\limits_{i=0,\,i \ne j}^n (j - i)}

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

y = {{x - x_0} \over h}\,\!

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

См. также[править | править исходный текст]

Внешние ссылки[править | править исходный текст]