Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Интерполяцио́нный многочле́н Лагра́нжамногочлен минимальной степени, принимающий данные значения в данном наборе точек. Для 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.

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

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

Файл:Lagrangepolys.png

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

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,\,i \ne j}^n {(x - x_j) \over  (x_i - x_j)}} = 
                {\prod\limits_{j=0,\,i \ne j}^n (x - x_0 - jh) \over h^{n-1} \prod\limits_{j=0,\,i \ne j}^n (i - j)}

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

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

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


cs:Lagrangeova interpolacenl:Lagrange-polynoomsr:Лагранжов полином uk:Многочлен Лагранжа

Викия-сеть

Случайная вики