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

Материал из свободной русской энциклопедии «Традиция»
(перенаправлено с «Полином»)
Перейти к: навигация, поиск
Этот пример показывает интерполяционный многочлен Лагранжа для четырёх точек (-9,5), (-4,2), (-1,-2) и (7,9), а также полиномы yj lj(x), каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных xi

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

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

Определение[править]

Лагранж предложил способ вычисления таких многочленов: $$L(x) = \sum_{j=0}^n y_j l_j(x)$$ где базисные полиномы определяются по формуле: $$l_j(x)=\prod_{i=0, j\neq i}^{n} \frac{x-x_i}{x_j-x_i} = \frac{x-x_0}{x_j-x_0} \cdots \frac{x-x_{j-1}}{x_j-x_{j-1}} \frac{x-x_{j+1}}{x_j-x_{j+1}} \cdots \frac{x-x_{n}}{x_j-x_{n}}\,\!$$ \(l_j(x)\) обладают следущими свойствами:

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

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

Применения[править]

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

Пусть для функции \(f(x)\) известны значения \(y_j=f(x_j)\) в некоторых точках. Тогда мы можем интерполировать эту функцию как $$f(x) \approx \sum_{j=0}^n f(x_j) l_j(x)$$

В частности, $$\int\limits_a^b f(x)dx \approx \sum_{j=0}^n f(x_j) \int\limits_a^b l_j(x) dx$$ Значения интегралов от \(l_j\) не зависят от \(f(x)\), и их можно вычислить заранее, зная последовательность \(x_i\).

Для случая равномерного распределения по отрезку узлов интерполяции[править]

В указанном случае можно выразить \(x_i\) через расстояние между узлами интерполяции h и начальную точку \(x_0\): $$ x_j \equiv {x_0 + jh},$$ и, следовательно, $$ {x_i - x_j} \equiv (i - j)h .$$ Подставив эти выражения в формулу базисного полинома и вынеся h за знаки перемножения в числителе и знаменателе, получим $$l_i(x) = { \prod_{j=0,\,j \ne i}^n {(x - x_j) \over (x_i - x_j)}} = {\prod\limits_{j=0,\,j \ne i}^n (x - x_0 - jh) \over h^{n-1} \prod\limits_{j=0,\,j \ne i}^n (i - j)}$$ Теперь можно ввести замену переменной $$y = {{x - x_0} \over h}\,\!$$ и получить полином от \(y\), который строится с использованием только целочисленной арифметики. Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования алгоритмов с многобайтным представлением чисел.

Ссылки[править]

  1. http://www.oval.ru/enc/57435.html

Внешние ссылки[править]