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

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

В простейшем случае 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}}\,\!

Легко видеть что lj(x) обладают такими свойствами:

  • Это полиномы степени n
  • lj(xj) = 1
  • lj(xi) = 0 при i\ne j

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

Применения

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

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

f(x) \approx \sum_{j=0}^n f(x_j) l_j(x)

В частности,

\int_a^b f(x)dx \approx \sum_{j=0}^n f(x_j) \int_a^b l_j(x) dx

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

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

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

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_{j=0,i \ne j}^n (x - x_0 - jh) \over h^{n-1} \prod_{j=0,i \ne j}^n (i - j)} = {{{h^{n-1}}\prod_{j=0,i \ne j}^n ({{x - x_0} \over h} - j)} \over {h^{n-1} \prod_{j=0,i \ne j}^n (i - j)}}\,\!.

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

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

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home