Полином Лагранжа

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

В численном анализе , полиномы Лагранжа используются для полиномиальной интерполяции . Для данного набора точек, у которых нет двух равных значений, полином Лагранжа является полиномом самой низкой степени, который принимает для каждого значения соответствующее значение , так что функции совпадают в каждой точке.${\ 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): = \ сумма _ {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})}},}$

где . Обратите внимание на то, как, учитывая исходное предположение, что нет двух одинаковых, then (when ) , поэтому это выражение всегда четко определено. Причина, по которой пары с недопустимы, заключается в том , что не существует такой интерполяционной функции ; функция может получить только одно значение для каждого аргумента . С другой стороны, если также , то эти две точки фактически будут одной точкой.${\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_{j}}$${\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 ( x ) является полиномом от x наименьшей степени, который интерполирует данный набор данных; то есть, он принимает значение y _j в соответствующем x _j для всех точек данных j :

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

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

• В произведении есть k множителей, и каждый множитель содержит один x , поэтому L ( x ) (который является суммой этих полиномов k -степени) должен быть полиномом степени не выше k .${\displaystyle \ell _{j}(x)}$
• ${\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}}}.}$

Разверните этот продукт. Поскольку в продукте отсутствует термин, где m = j , если i = j, то все термины, которые появляются, являются . Кроме того, если i ≠ j, то один член в продукте будет (для m = i ) , обнуляя весь продукт. Так,${\displaystyle {\frac {x_{j}-x_{m}}{x_{j}-x_{m}}}=1}$${\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 ( x ) является многочленом степени не выше k и где L ( x _i ) = y _i .

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

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

${\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}}$ δ i j {\displaystyle \delta _{ij}}

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

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

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

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

Мы хотим интерполировать ƒ ( x ) =  x ² в диапазоне 1 ≤  x  ≤ 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 [ править ]

Мы хотим интерполировать ƒ ( x ) =  x ³ в диапазоне 1 ≤  x  ≤ 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}}}$

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

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

Но, как видно из построения, каждый раз, когда узел x _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)}$

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

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

${\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] [ править ]

Ясно, что в узлах равен нулю. Чтобы найти точку . Определите новую функцию и выберите (это гарантирует в узлах), где - константа, которую мы должны определить для данного . Теперь имеет нули (на всех узлах и ) между и (включая конечные точки). Если предположить , что это -кратный дифференцируема, и многочлены, и поэтому бесконечно дифференцируемы. По теореме Ролля , имеют нули, имеют нули ... имеют 1 ноль, скажу . Явно пишу :${\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)}}$${\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}$

${\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
• Таблица ньютоновских рядов
• Ковариант Фробениуса
• Формула Сильвестра
• Коэффициент конечной разности

Ссылки [ править ]

Внешние ссылки [ править ]

Wikibook Реализация алгоритма имеет страницу на тему: полиномиальная интерполяция

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