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

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

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

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

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

Лагранж предложил способ вычисления таких многочленов: L ( x ) = j = 0 n y j l j ( x ) L(x) = \sum_{j=0}^n y_j l_j(x) где базисные полиномы определяются по формуле: l j ( x ) = i = 0 , j i n x x i x j x i = x x 0 x j x 0 x x j 1 x j x j 1 x x j + 1 x j x j + 1 x x n x j x n 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 ) l_j(x) обладают следущими свойствами:

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

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

ПримененияПравить

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

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

В частности, a b f ( x ) d x j = 0 n f ( x j ) a b l j ( x ) d 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 l_j не зависят от f ( x ) f(x) , и их можно вычислить заранее, зная последовательность x i x_i .

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

В указанном случае можно выразить x i x_i через расстояние между узлами интерполяции h и начальную точку x 0 x_0 : x j x 0 + j h , x_j \equiv {x_0 + jh}, и, следовательно, x i x j ( i j ) h . {x_i - x_j} \equiv (i - j)h . Подставив эти выражения в формулу базисного полинома и вынеся h за знаки перемножения в числителе и знаменателе, получим l i ( x ) = j = 0 , j i n ( x x j ) ( x i x j ) = j = 0 , j i n ( x x 0 j h ) h n 1 j = 0 , j i n ( i j ) 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 h y = {{x - x_0} \over h}\,\! и получить полином от y y , который строится с использованием только целочисленной арифметики. Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования алгоритмов с многобайтным представлением чисел.

СсылкиПравить

Внешние ссылкиПравить