Полином Лагранжа - Lagrange polynomial - Wikipedia

Это изображение показывает для четырех точек ((−9, 5), (−4, 2), (−1, −2), (7, 9)), (кубический) интерполяционный полином L(Икс) (пунктирный, черный), который представляет собой сумму масштабированный базисные полиномы у₀ℓ₀(Икс), у₁ℓ₁(Икс), у₂ℓ₂(Икс) и у₃ℓ₃(Икс). Полином интерполяции проходит через все четыре контрольные точки, и каждая масштабированный базисный полином проходит через соответствующую контрольную точку и равен 0, где Икс соответствует трем другим контрольным точкам.

В числовой анализ, Полиномы Лагранжа используются для полиномиальная интерполяция. По заданному набору точек ${\displaystyle (x_{j},y_{j})}$ без двух ${\displaystyle x_{j}}$ равны, полином Лагранжа - полином наименьшего степень который предполагает при каждом значении ${\displaystyle x_{j}}$ соответствующее значение ${\displaystyle y_{j}}$, так что функции совпадают в каждой точке.

Хотя назван в честь Жозеф-Луи Лагранж, опубликовавший его в 1795 г., метод был впервые открыт в 1779 г. Эдвард Уоринг^[1] Это также простое следствие формулы, опубликованной в 1783 г. Леонард Эйлер.^[2]

Использование полиномов Лагранжа включает Метод Ньютона – Котеса из численное интегрирование и Схема секретного обмена Шамиром в криптография.

Интерполяция Лагранжа чувствительна к Феномен Рунге большого колебания. Как меняются точки ${\displaystyle x_{j}}$ требует пересчета всего интерполянта, часто проще использовать Полиномы Ньютона вместо.

Определение

Здесь мы строим базисные функции Лагранжа 1-го, 2-го и 3-го порядков в двуединичной области. Линейные комбинации базисных функций Лагранжа используются для построения интерполяционных полиномов Лагранжа. Базисные функции Лагранжа обычно используются в анализ методом конечных элементов в качестве основы для форм-функций элементов. Кроме того, обычно в качестве естественного пространства для определения конечных элементов используется двуединичная область.

Учитывая набор k + 1 точка данных

${\displaystyle (x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{k},y_{k})}$

где нет двух ${\displaystyle x_{j}}$ такие же, интерполяционный полином в форме Лагранжа это линейная комбинация

${\displaystyle L(x):=\sum _{j=0}^{k}y_{j}\ell _{j}(x)}$

базисных многочленов Лагранжа

${\displaystyle \ell _{j}(x):=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}={\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_{k})}{(x_{j}-x_{k})}},}$

куда ${\displaystyle 0\leq j\leq k}$. Обратите внимание, как, учитывая исходное предположение, что нет двух ${\displaystyle x_{j}}$ одинаковы, то (когда ${\displaystyle m\neq j}$) ${\displaystyle x_{j}-x_{m}\neq 0}$, поэтому это выражение всегда четко определено. Причина пары ${\displaystyle x_{i}=x_{j}}$ с ${\displaystyle y_{i}\neq y_{j}}$ не допускаются, так как нет функции интерполяции ${\displaystyle L}$ такой, что ${\displaystyle y_{i}=L(x_{i})}$ будет существовать; функция может получить только одно значение для каждого аргумента ${\displaystyle x_{i}}$. С другой стороны, если также ${\displaystyle y_{i}=y_{j}}$, то эти две точки фактически будут одной точкой.

Для всех ${\displaystyle i\neq j}$, ${\displaystyle \ell _{j}(x)}$ включает термин ${\displaystyle (x-x_{i})}$ в числителе, поэтому все произведение будет равно нулю в ${\displaystyle x=x_{i}}$:

${\displaystyle \forall ({j\neq i}):\ell _{j}(x_{i})=\prod _{m\neq j}{\frac {x_{i}-x_{m}}{x_{j}-x_{m}}}={\frac {(x_{i}-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x_{i}-x_{i})}{(x_{j}-x_{i})}}\cdots {\frac {(x_{i}-x_{k})}{(x_{j}-x_{k})}}=0.}$

С другой стороны,

$${\displaystyle \ell _{j}(x_{j}):=\prod _{m\neq j}{\frac {x_{j}-x_{m}}{x_{j}-x_{m}}}=1}$$

Другими словами, все базисные полиномы равны нулю в точке ${\displaystyle x=x_{i}}$, Кроме ${\displaystyle \ell _{j}(x)}$, для которого справедливо ${\displaystyle \ell _{j}(x_{j})=1}$, потому что в нем отсутствует ${\displaystyle (x-x_{j})}$ срок.

Следует, что ${\displaystyle y_{j}\ell _{j}(x_{j})=y_{j}}$, поэтому в каждой точке ${\displaystyle x_{j}}$, ${\displaystyle L(x_{j})=y_{j}+0+0+\dots +0=y_{j}}$, показывая, что ${\displaystyle L}$ точно интерполирует функцию.

Доказательство

Функция L(Икс) ищется многочлен от Икс наименьшей степени, которая интерполирует данный набор данных; то есть принимает значение у_j на соответствующем Икс_j для всех точек данных j:

${\displaystyle L(x_{j})=y_{j}\qquad j=0,\ldots ,k.}$

Обратите внимание:

• В ${\displaystyle \ell _{j}(x)}$ Существуют k факторов в продукте, и каждый фактор содержит один Икс, так L(Икс) (что является суммой этих k-степени полиномов) должен быть полиномом степени не выше k.
• ${\displaystyle \ell _{j}(x_{i})=\prod _{\begin{smallmatrix}m=0\\m\neq j\end{smallmatrix}}^{k}{\frac {x_{i}-x_{m}}{x_{j}-x_{m}}}.}$

Разверните этот продукт. Поскольку в продукте отсутствует термин, где м = j, если я = j тогда все термины появляются ${\displaystyle {\frac {x_{j}-x_{m}}{x_{j}-x_{m}}}=1}$. Кроме того, если я ≠ j затем один член в продукте буду быть (для м = я), ${\displaystyle {\frac {x_{i}-x_{i}}{x_{j}-x_{i}}}=0}$, обнуление всего продукта. Так,

${\displaystyle \ell _{j}(x_{i})=\delta _{ji}={\begin{cases}1,&{\text{if }}j=i\\0,&{\text{if }}j\neq i\end{cases}},}$

куда ${\displaystyle \delta _{ij}}$ это Дельта Кронекера. Так:

${\displaystyle L(x_{i})=\sum _{j=0}^{k}y_{j}\ell _{j}(x_{i})=\sum _{j=0}^{k}y_{j}\delta _{ji}=y_{i}.}$

Таким образом, функция L(Икс) является многочленом степени не выше k и где L(Икс_я) = у_я.

Кроме того, интерполирующий полином уникален, как показано теоремой о неразрешенности в полиномиальная интерполяция статья.

Также верно, что:

${\displaystyle \sum _{j=0}^{k}\ell _{j}(x)=1\qquad \forall x}$

так как это должен быть многочлен степени не выше, k и проходит через все эти k + 1 точка данных:

${\displaystyle (x_{0},1),\ldots ,(x_{j},1),\ldots ,(x_{k},1)}$

в результате получается горизонтальная линия, так как прямая линия - единственный многочлен степени меньше k +1, который проходит через k +1 точка совмещения.

Перспектива из линейной алгебры

Решение проблема интерполяции приводит к проблеме в линейная алгебра сводится к инверсии матрицы. Используя стандартный мономиальный базис для нашего интерполяционного полинома ${\displaystyle L(x)=\sum _{j=0}^{k}x^{j}m_{j}}$, мы должны инвертировать Матрица Вандермонда ${\displaystyle (x_{i})^{j}}$ решать ${\displaystyle L(x_{i})=y_{i}}$ для коэффициентов ${\displaystyle m_{j}}$ из ${\displaystyle L(x)}$. Выбирая лучший базис, базис Лагранжа, ${\displaystyle L(x)=\sum _{j=0}^{k}l_{j}(x)y_{j}}$, мы просто получаем единичная матрица, ${\displaystyle \delta _{ij}}$, что является обратным к самому себе: базис Лагранжа автоматически переворачивает аналог матрицы Вандермонда.

Эта конструкция аналогична конструкции Китайская теорема об остатках. Вместо того, чтобы проверять остатки целых чисел по модулю простых чисел, мы проверяем остатки многочленов при делении на линеары.

Кроме того, когда заказ большой, Быстрое преобразование Фурье может использоваться для определения коэффициентов интерполированного полинома.

Примеры

Пример 1

Мы хотим интерполировать ƒ(Икс) = Икс² в диапазоне 1 ≤Икс ≤ 3, учитывая эти три балла:

${\displaystyle {\begin{aligned}x_{0}&=1&&&f(x_{0})&=1\\x_{1}&=2&&&f(x_{1})&=4\\x_{2}&=3&&&f(x_{2})&=9.\end{aligned}}}$

Интерполирующий полином:

${\displaystyle {\begin{aligned}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{aligned}}}$

Пример 2

Мы хотим интерполировать ƒ(Икс) = Икс³ в диапазоне 1 ≤Икс ≤ 4, учитывая эти четыре балла:

${\displaystyle x_{0}=1}$	${\displaystyle f(x_{0})=1}$
${\displaystyle x_{1}=2}$	${\displaystyle f(x_{1})=8}$
${\displaystyle x_{2}=3}$	${\displaystyle f(x_{2})=27}$
${\displaystyle x_{3}=4}$	${\displaystyle f(x_{3})=64}$

Интерполирующий полином:

${\displaystyle {\begin{aligned}L(x)&={1}\cdot {x-2 \over 1-2}\cdot {x-3 \over 1-3}\cdot {x-4 \over 1-4}+{8}\cdot {x-1 \over 2-1}\cdot {x-3 \over 2-3}\cdot {x-4 \over 2-4}+{27}\cdot {x-1 \over 3-1}\cdot {x-2 \over 3-2}\cdot {x-4 \over 3-4}+{64}\cdot {x-1 \over 4-1}\cdot {x-2 \over 4-2}\cdot {x-3 \over 4-3}\\[8pt]&=x^{3}\end{aligned}}}$

Примечания

Пример интерполяционной расходимости для набора полиномов Лагранжа.

Форма Лагранжа интерполяционного полинома показывает линейный характер полиномиальной интерполяции и уникальность интерполяционного полинома. Поэтому ему отдают предпочтение в доказательствах и теоретических аргументах. Уникальность также можно увидеть из обратимости матрицы Вандермонда из-за того, что Определитель Вандермонда.

Но, как видно из конструкции, каждый раз узел Икс_k изменения, необходимо пересчитать все базисные полиномы Лагранжа. Лучшая форма интерполяционного полинома для практических (или вычислительных) целей - это барицентрическая форма интерполяции Лагранжа (см. Ниже) или Полиномы Ньютона.

Лагранж и другая интерполяция в равноотстоящих точках, как в примере выше, дают полином, колеблющийся выше и ниже истинной функции. Это поведение имеет тенденцию расти с увеличением количества точек, что приводит к расхождению, известному как Феномен Рунге; проблему можно решить, выбрав точки интерполяции на Чебышевские узлы.^[3]

Базисные полиномы Лагранжа можно использовать в численное интегрирование вывести Формулы Ньютона – Котеса.

Барицентрическая форма

С помощью

${\displaystyle \ell (x)=(x-x_{0})(x-x_{1})\cdots (x-x_{k})}$

${\displaystyle \ell '(x_{j})={\frac {\mathrm {d} \ell (x)}{\mathrm {d} x}}{\Big |}_{x=x_{j}}=\prod _{i=0,i\neq j}^{k}(x_{j}-x_{i})}$

мы можем переписать базисные полиномы Лагранжа как

${\displaystyle \ell _{j}(x)={\frac {\ell (x)}{\ell '(x_{j})(x-x_{j})}}}$

или, определив барицентрические веса^[4]

${\displaystyle w_{j}={\frac {1}{\ell '(x_{j})}}}$

мы можем просто написать

${\displaystyle \ell _{j}(x)=\ell (x){\frac {w_{j}}{x-x_{j}}}}$

который обычно называют первая форма формулы барицентрической интерполяции.

Преимущество этого представления состоит в том, что теперь полином интерполяции можно оценить как

${\displaystyle L(x)=\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}}$

который, если веса ${\displaystyle w_{j}}$ были предварительно рассчитаны, требуется только ${\displaystyle {\mathcal {O}}(k)}$ операции (оценка ${\displaystyle \ell (x)}$ и веса ${\displaystyle w_{j}/(x-x_{j})}$) в отличие от ${\displaystyle {\mathcal {O}}(k^{2})}$ для вычисления базисных многочленов Лагранжа ${\displaystyle \ell _{j}(x)}$ индивидуально.

Формула барицентрической интерполяции также может быть легко обновлена ​​для включения нового узла. ${\displaystyle x_{k+1}}$ разделив каждый из ${\displaystyle w_{j}}$, ${\displaystyle j=0\dots k}$ к ${\displaystyle (x_{j}-x_{k+1})}$ и строительство нового ${\displaystyle w_{k+1}}$ как указано выше.

Мы можем еще больше упростить первую форму, сначала рассмотрев барицентрическую интерполяцию постоянной функции ${\displaystyle g(x)\equiv 1}$:

${\displaystyle g(x)=\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}.}$

Разделение ${\displaystyle L(x)}$ к ${\displaystyle g(x)}$ не изменяет интерполяцию, но дает

${\displaystyle L(x)={\frac {\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}}{\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}}}}$

который называется вторая форма или же истинная форма формулы барицентрической интерполяции. Эта вторая форма имеет то преимущество, что ${\displaystyle \ell (x)}$ не нужно оценивать для каждой оценки ${\displaystyle L(x)}$.

Остаток в формуле интерполяции Лагранжа

При интерполяции заданной функции ж полиномом степени k в узлах ${\displaystyle x_{0},...,x_{k}}$ мы получаем остаток ${\displaystyle R(x)=f(x)-L(x)}$ который можно выразить как^[5]

${\displaystyle R(x)=f[x_{0},\ldots ,x_{k},x]\ell (x)=\ell (x){\frac {f^{(k+1)}(\xi )}{(k+1)!}},\quad \quad x_{0}<\xi <x_{k},}$

куда ${\displaystyle f[x_{0},\ldots ,x_{k},x]}$ это обозначение для разделенные различия. В качестве альтернативы, остаток может быть выражен как контурный интеграл в комплексной области как

${\displaystyle R(z)={\frac {\ell (z)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-z)(t-z_{0})\cdots (t-z_{k})}}dt={\frac {\ell (z)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-z)\ell (t)}}dt.}$

Остаток можно связать как

${\displaystyle |R(x)|\leq {\frac {(x_{k}-x_{0})^{k+1}}{(k+1)!}}\max _{x_{0}\leq \xi \leq x_{k}}|f^{(k+1)}(\xi )|.}$

Вывод^[6]

Четко, ${\displaystyle R(x)}$ равен нулю в узлах. Найти ${\displaystyle R(x)}$ в какой-то момент ${\displaystyle x_{p}}$. Определите новую функцию ${\displaystyle F(x)=f(x)-L(x)-R(x)}$ и выберите ${\displaystyle R(x)=C\cdot \prod _{i=0}^{k}(x-x_{i})}$ (Это гарантирует ${\displaystyle R(x)=0}$ в узлах), где ${\displaystyle C}$ - константа, которую нам необходимо определить для данного ${\displaystyle x_{p}}$. Сейчас же ${\displaystyle F(x)}$ имеет ${\displaystyle k+2}$ нулей (на всех узлах и ${\displaystyle x_{p}}$) между ${\displaystyle x_{0}}$ и ${\displaystyle x_{k}}$ (включая конечные точки). При условии, что ${\displaystyle f(x)}$ является ${\displaystyle k+1}$-раз дифференцируемые, ${\displaystyle L(x)}$ и ${\displaystyle R(x)}$ являются многочленами, а значит, бесконечно дифференцируемы. К Теорема Ролля, ${\displaystyle F^{(1)}(x)}$ имеет ${\displaystyle k+1}$ нули, ${\displaystyle F^{(2)}(x)}$ имеет ${\displaystyle k}$ нули ... ${\displaystyle F^{(k+1)}}$ имеет 1 ноль, скажем ${\displaystyle \xi ,\,x_{0}<\xi <x_{k}}$. Явно пишу ${\displaystyle F^{(k+1)}(\xi )}$:

${\displaystyle F^{(k+1)}(\xi )=f^{(k+1)}(\xi )-L^{(k+1)}(\xi )-R^{(k+1)}(\xi )}$

${\displaystyle L^{(k+1)}=0,R^{(k+1)}=C\cdot (k+1)!}$ (Потому что наивысшая мощность ${\displaystyle x}$ в ${\displaystyle R(x)}$ является ${\displaystyle k+1}$)

${\displaystyle 0=f^{(k+1)}(\xi )-C\cdot (k+1)!}$

Уравнение можно переписать как

${\displaystyle C={\frac {f^{(k+1)}(\xi )}{(k+1)!}}}$

Производные

В ${\displaystyle d}$th производные полинома Лагранжа можно записать как

${\displaystyle L^{(d)}(x):=\sum _{j=0}^{k}y_{j}\ell _{j}^{(d)}(x)}$.

Для первой производной коэффициенты имеют вид

${\displaystyle \ell _{j}^{(1)}(x):=\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}\left[{\frac {1}{x_{j}-x_{i}}}\prod _{\begin{smallmatrix}m=0\\m\not =(i,j)\end{smallmatrix}}^{k}{\frac {x-x_{m}}{x_{j}-x_{m}}}\right]}$

а для второй производной

${\displaystyle \ell _{j}^{(2)}(x):=\sum _{\begin{smallmatrix}i=0\\i\neq j\end{smallmatrix}}^{k}{\frac {1}{x_{j}-x_{i}}}\left[\sum _{\begin{smallmatrix}m=0\\m\neq (i,j)\end{smallmatrix}}^{k}\left({\frac {1}{x_{j}-x_{m}}}\prod _{\begin{smallmatrix}l=0\\l\neq (i,j,m)\end{smallmatrix}}^{k}{\frac {x-x_{l}}{x_{j}-x_{l}}}\right)\right]}$.

С помощью рекурсии можно вычислить формулы для высших производных.

Конечные поля

Полином Лагранжа также можно вычислить в конечные поля. Это имеет приложения в криптография, например, в Обмен секретами Шамира схема.

Смотрите также

• Алгоритм Невилла
• Форма Ньютона интерполяционного полинома
• Полином Бернштейна
• Теорема Карлсона
• Константа Лебега (интерполяция)
• Система Chebfun
• Таблица ньютоновских рядов
• Ковариант Фробениуса
• Формула Сильвестра
• Коэффициент конечной разности

Рекомендации

1. Уоринг, Эдвард (9 января 1779 г.). «Проблемы с интерполяцией». Философские труды Королевского общества. 69: 59–67. Дои:10.1098 / рстл.1779.0008.
2. Мейеринг, Эрик (2002). «Хронология интерполяции: от древней астрономии до современной обработки сигналов и изображений» (PDF). Труды IEEE. 90 (3): 319–342. Дои:10.1109/5.993400.
3. Quarteroni, Alfio; Салери, Фаусто (2003). Научные вычисления с MATLAB. Тексты по вычислительной науке и технике. 2. Springer. п. 66. ISBN  978-3-540-44363-6..
4. Беррут, Жан-Поль; Трефетен, Ллойд Н. (2004). «Барицентрическая интерполяция Лагранжа» (PDF). SIAM Обзор. 46 (3): 501–517. Дои:10.1137 / S0036144502417715.
5. Абрамовиц, Милтон; Стегун, Ирен Энн, ред. (1983) [июнь 1964]. «Глава 25, уравнение 25.2.3». Справочник по математическим функциям с формулами, графиками и математическими таблицами. Прикладная математика. 55 (Девятое переиздание с дополнительными исправлениями, десятое оригинальное издание с исправлениями (декабрь 1972 г.); первое изд.). Вашингтон, округ Колумбия.; Нью-Йорк: Министерство торговли США, Национальное бюро стандартов; Dover Publications. п. 878. ISBN  978-0-486-61272-0. LCCN  64-60036. МИСТЕР  0167642. LCCN  65-12253.
6. «Интерполяция» (PDF).

внешняя ссылка

• «Формула интерполяции Лагранжа», Энциклопедия математики, EMS Press, 2001 [1994]
• АЛГЛИБ имеет реализации на C ++ / C # / VBA / Pascal.
• GSL имеет полиномиальный интерполяционный код в C
• ТАК есть пример MATLAB, который демонстрирует алгоритм и воссоздает первое изображение в этой статье
• Метод интерполяции Лагранжа - Примечания, PPT, Mathcad, Mathematica, MATLAB, Maple в Институт целостных численных методов
• Полином интерполяции Лагранжа на www.math-linux.com
• Вайсштейн, Эрик В. «Интерполирующий многочлен Лагранжа». MathWorld.
• Полином Лагранжа в ProofWiki
• Динамическая интерполяция Лагранжа с JSXGraph
• Численные вычисления с функциями: Проект Chebfun
• Функция листа Excel для бикубической интерполяции Лагранжа
• Полиномы Лагранжа в Python