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

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

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

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

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

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

$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_a^b f(x)dx \approx \sum_{j=0}^n f(x_j) \int_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_{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}\,\!$

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

Категории: Интерполяция | Многочлены | Математический анализ

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

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

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

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

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

Views

Навигация

Участие

Поиск

На других языках