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

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

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

Содержание

1 Определение
2 Примеры
3 Применения
- 3.1 Случай равномерного распределения узлов интерполяции
4 См. также
5 Внешние ссылки

Определение

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

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

$L(x) = \sum_{i=0}^n y_i l_i(x)$

где базисные полиномы определяются по формуле:

$l_i(x)=\prod_{j=0, j\neq i}^{n} \frac{x-x_j}{x_i-x_j} = \frac{x-x_0}{x_i-x_0} \cdots \frac{x-x_{i-1}}{x_i-x_{i-1}} \frac{x-x_{i+1}}{x_i-x_{i+1}} \cdots \frac{x-x_{n}}{x_i-x_{n}}\,\!$

$l_i(x)$ обладают следующими свойствами:

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

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

Примеры

Пример 1

Функция тангенса и интерполяция

Найдем формулу интерполяции для ƒ(x) = tan(x) имеющей следующие значения:

$\begin{align} x_0 & = -1.5 & & & & & f(x_0) & = -14.1014 \\ x_1 & = -0.75 & & & & & f(x_1) & = -0.931596 \\ x_2 & = 0 & & & & & f(x_2) & = 0 \\ x_3 & = 0.75 & & & & & f(x_3) & = 0.931596 \\ x_4 & = 1.5 & & & & & f(x_4) & = 14.1014. \end{align}$

$\ell_0(x)={x - x_1 \over x_0 - x_1}\cdot{x - x_2 \over x_0 - x_2}\cdot{x - x_3 \over x_0 - x_3}\cdot{x - x_4 \over x_0 - x_4} ={1\over 243} x (2x-3)(4x-3)(4x+3)$

$\ell_1(x) = {x - x_0 \over x_1 - x_0}\cdot{x - x_2 \over x_1 - x_2}\cdot{x - x_3 \over x_1 - x_3}\cdot{x - x_4 \over x_1 - x_4} = {} -{8\over 243} x (2x-3)(2x+3)(4x-3)$

$\ell_2(x)={x - x_0 \over x_2 - x_0}\cdot{x - x_1 \over x_2 - x_1}\cdot{x - x_3 \over x_2 - x_3}\cdot{x - x_4 \over x_2 - x_4} ={3\over 243} (2x+3)(4x+3)(4x-3)(2x-3)$

$\ell_3(x)={x - x_0 \over x_3 - x_0}\cdot{x - x_1 \over x_3 - x_1}\cdot{x - x_2 \over x_3 - x_2}\cdot{x - x_4 \over x_3 - x_4} =-{8\over 243} x (2x-3)(2x+3)(4x+3)$

$\ell_4(x)={x - x_0 \over x_4 - x_0}\cdot{x - x_1 \over x_4 - x_1}\cdot{x - x_2 \over x_4 - x_2}\cdot{x - x_3 \over x_4 - x_3} ={1\over 243} x (2x+3)(4x-3)(4x+3).$

Получим

$\begin{align}L(x) &= {1\over 243}\Big(f(x_0)x (2x-3)(4x-3)(4x+3) \\ & {} \qquad {} - 8f(x_1)x (2x-3)(2x+3)(4x-3) \\ & {} \qquad {} + 3f(x_2)(2x+3)(4x+3)(4x-3)(2x-3) \\ & {} \qquad {} - 8f(x_3)x (2x-3)(2x+3)(4x+3) \\ & {} \qquad {} + f(x_4)x (2x+3)(4x-3)(4x+3)\Big)\\ & = 4.834848x^3 - 1.477474x. \end{align}$

Пример 2

$\begin{align} x_0 & = 1 & & & f(x_0) & = 1 \\ x_1 & = 2 & & & f(x_1) & = 4 \\ x_2 & = 3 & & & f(x_2) & =9. \end{align}$

$\begin{align} L(x) &= {1}\cdot{x - 2 \over 1 - 2}\cdot{x - 3 \over 1 - 3}+{4}\cdot{x - 1 \over 2 - 1}\cdot{x - 3 \over 2 - 3}+{9}\cdot{x - 1 \over 3 - 1}\cdot{x - 2 \over 3 - 2} \\[10pt] &= x^2. \end{align}$

Пример 3

$x_0=1\,$	$f(x_0)=1\,$
$x_1=2\,$	$f(x_1)=8\,$
$x_2=3\,$	$f(x_2)=27\,$

$\begin{align} L(x) &= {1}\cdot{x - 2 \over 1 - 2}\cdot{x - 3 \over 1 - 3}+{8}\cdot{x - 1 \over 2 - 1}\cdot{x - 3 \over 2 - 3}+{27}\cdot{x - 1 \over 3 - 1}\cdot{x - 2 \over 3 - 2} \\[8pt] &= 6x^2 - 11x + 6. \end{align}$

Применения

Используя полином Лагранжа можно показать, что $\sum_{i=1}^k {P}_{n}(i)={T}_{n+1}(k)=k{T}_{n}(k)$

если ${P}_{n}(i)={i}^n$ , то первые два по старшинству коэффициента многочлена ${T}_n(k)={{{k}^n}\over{n+1}}+{{{k}^{n-1}}\over{2}}+\dots$

Указанная выше сумма задаёт биективное отображение между ${P}_{n}(i)$ и ${T}_{n}(k)$

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

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

$f(x) \approx \sum_{i=0}^n f(x_i) l_i(x)$

В частности,

$\int\limits_a^b f(x)dx \approx \sum_{i=0}^n f(x_i) \int\limits_a^b l_i(x) dx$

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

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

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

$x_i \equiv {x_0 + ih}$ ,

и, следовательно,

${x_j - x_i} \equiv (j - i)h.$

Подставив эти выражения в формулу базисного полинома и вынеся h за знаки перемножения в числителе и знаменателе, получим

$l_j(x) = { \prod_{i=0,\,i \ne j}^n {(x - x_i) \over (x_j - x_i)}} = {\prod\limits_{i=0,\,i \ne j}^n (x - x_0 - ih) \over h^{n-1} \prod\limits_{i=0,\,i \ne j}^n (j - i)}$

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

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

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

См. также

Имеется викиучебник по теме
«Реализация интерполяционного многочлена Лагранжа на разных языках программирования»

Внешние ссылки

М.А. Тынкевич Глава 7.6.1. Интерполяционный многочлен Лагранжа // Численные методы анализа. — Кемерово, 2002. — ISBN 5-89070-042-1
А.Г. Хованский. Полиномы Лагранжа и их применения. Видео-лекция. VI Летняя школа "Современная математика", Дубна, 2006.

В этой статье не хватает ссылок на источники информации.

Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.
Эта отметка установлена 13 мая 2011.

Категории:

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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное

Смотреть что такое "Интерполяционный многочлен Лагранжа" в других словарях:

Интерполяционный многочлен — Интерполяционный многочлен: Интерполяционный многочлен Лагранжа Интерполяционный многочлен Ньютона Интерполяция алгебраическими многочленами … Википедия
Многочлен Лагранжа — Интерполяционный многочлен Лагранжа многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n + 1 пар чисел , где все xi различны, существует единственный многочлен L(x) степени не более n, для которого L(xi) = yi.… … Википедия
Лагранжа полином — Интерполяционный многочлен Лагранжа многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n + 1 пар чисел , где все xi различны, существует единственный многочлен L(x) степени не более n, для которого L(xi) = yi.… … Википедия
ИНТЕРПОЛЯЦИОННЫЙ ПРОЦЕСС — процесс получения последовательности интерполирующих функций {fn(z)} при неограниченном возрастании числа n условий интерполирования. Если интерполирующие функции fn(z)представлены в виде частных сумм некоторого функционального ряда, то последний … Математическая энциклопедия
Интерполяционная формула Лагранжа — Интерполяционный многочлен Лагранжа многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n + 1 пар чисел , где все xi различны, существует единственный многочлен L(x) степени не более n, для которого L(xi) = yi.… … Википедия
Полином Лагранжа — Интерполяционный многочлен Лагранжа многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n + 1 пар чисел , где все xi различны, существует единственный многочлен L(x) степени не более n, для которого L(xi) = yi.… … Википедия
Список объектов, названных в честь Лагранжа — Существует несколько математических и физических объектов, носящих имя французского математика XVIII века Луи Жозефа Лагранжа: Теоремы Теорема Лагранжа в математическом анализе см. формула конечных приращений Теорема Лагранжа (теория групп) … Википедия
ИНТЕРПОЛИРОВАНИЕ — в вычислительной математике способ приближенного или точного нахождения какой либо величины по известным отдельным значениям этой же или других величин, связанных с ней. На основе И. построен ряд приближенных методов решения математич. задач.… … Математическая энциклопедия
Интерполирование с кратными узлами — Интерполирование с кратными узлами задача о построении многочлена минимальной степени, принимающего в некоторых точках (узлах интерполяции) заданные значения, а также заданные значения производных до некоторого порядка. Показывается, что… … Википедия
Интерполяционные формулы — Интерполяционные формулы в математике формулы, дающие приближённое выражение функции при помощи интерполяции, то есть через интерполяционный многочлен степени , значения которого в заданных точках совпадают со значениями функции в этих… … Википедия

Словари и энциклопедии на Академике

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

Содержание

Определение