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

В численном анализе — интерполяционный полином Лагранжа это уникальный полином наименьшей степени , который интерполирует заданный набор данных.

Учитывая набор данных пар координат $(x_{j},y_{j})$ с $0\leq j\leq k,$ тот $x_{j}$ называются узлами , а $y_{j}$ называются ценностями . Полином Лагранжа $L(x)$ имеет степень ${\textstyle \leq k}$ и принимает каждое значение в соответствующем узле, $L(x_{j})=y_{j}.$

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

Использование полиномов Лагранжа включает Ньютона-Котеса метод численного интегрирования , схему разделения секретов Шамира в криптографии и коррекцию ошибок Рида-Соломона в теории кодирования .

Для равноотстоящих друг от друга узлов интерполяция Лагранжа подвержена Рунге явлению больших колебаний .

Определение

Учитывая набор ${\textstyle k+1}$ узлы $\{x_{0},x_{1},\ldots ,x_{k}\}$ , которые все должны быть различны, $x_{j}\neq x_{m}$ для индексов $j\neq m$ , базис Лагранжа для многочленов степени ${\textstyle \leq k}$ для этих узлов представляет собой набор полиномов ${\textstyle \{\ell _{0}(x),\ell _{1}(x),\ldots ,\ell _{k}(x)\}}$ каждый степени ${\textstyle k}$ которые принимают значения ${\textstyle \ell _{j}(x_{m})=0}$ если ${\textstyle m\neq j}$ и ${\textstyle \ell _{j}(x_{j})=1}$ . Используя дельту Кронекера, это можно записать ${\textstyle \ell _{j}(x_{m})=\delta _{jm}.}$ Каждый базисный полином может быть явно описан произведением:

${\begin{aligned}\ell _{j}(x)&={\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})}}\\[8mu]&=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}{\vphantom {\Bigg |}}.\end{aligned}}$

Обратите внимание, что числитель ${\textstyle \prod _{m\neq j}(x-x_{m})}$ имеет ${\textstyle k}$ корни в узлах ${\textstyle \{x_{m}\}_{m\neq j}}$ в то время как знаменатель ${\textstyle \prod _{m\neq j}(x_{j}-x_{m})}$ масштабирует полученный полином так, что ${\textstyle \ell _{j}(x_{j})=1.}$

Интерполирующий полином Лагранжа для этих узлов через соответствующие значения $\{y_{0},y_{1},\ldots ,y_{k}\}$ представляет собой линейную комбинацию:

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

Каждый базисный полином имеет степень ${\textstyle k}$ , поэтому сумма ${\textstyle L(x)}$ имеет степень ${\textstyle \leq k}$ , и он интерполирует данные, потому что ${\textstyle L(x_{m})=\sum _{j=0}^{k}y_{j}\ell _{j}(x_{m})=\sum _{j=0}^{k}y_{j}\delta _{mj}=y_{m}.}$

Интерполяционный полином уникален. Доказательство: предположим полином ${\textstyle M(x)}$ степени ${\textstyle \leq k}$ интерполирует данные. Тогда разница ${\textstyle M(x)-L(x)}$ равен нулю в ${\textstyle k+1}$ отдельные узлы ${\textstyle \{x_{0},x_{1},\ldots ,x_{k}\}.}$ Но единственный полином степени ${\textstyle \leq k}$ с более чем ${\textstyle k}$ корни — это функция постоянного нуля, поэтому ${\textstyle M(x)-L(x)=0,}$ или ${\textstyle M(x)=L(x).}$

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

Каждый базисный полином Лагранжа ${\textstyle \ell _{j}(x)}$ можно переписать как произведение трех частей, функцию ${\textstyle \ell (x)=\prod _{m}(x-x_{m})}$ общий для каждого базисного полинома, константа, специфичная для узла ${\textstyle w_{j}=\prod _{m\neq j}(x_{j}-x_{m})^{-1}}$ (называемый барицентрическим весом ), и часть, представляющая смещение от ${\textstyle x_{j}}$ к ${\textstyle x}$ : ^[4]

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

Путем факторинга ${\textstyle \ell (x)}$ из суммы можно записать полином Лагранжа в так называемой первой барицентрической форме :

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

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

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

Для любого ${\textstyle x,}$ ${\textstyle \sum _{j=0}^{k}\ell _{j}(x)=1}$ потому что постоянная функция ${\textstyle g(x)=1}$ – уникальный многочлен степени $\leq k$ интерполяция данных ${\textstyle \{(x_{0},1),(x_{1},1),\ldots ,(x_{k},1)\}.}$ Таким образом, мы можем еще больше упростить барицентрическую формулу, разделив $L(x)=L(x)/g(x)\colon$

{\begin{aligned}L(x)&=\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}{\Bigg /}\ell (x)\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}\\[10mu]&=\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}y_{j}{\Bigg /}\sum _{j=0}^{k}{\frac {w_{j}}{x-x_{j}}}.\end{aligned}}

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

Эта вторая форма имеет преимущества в стоимости и точности вычислений: она позволяет избежать оценки $\ell (x)$ ; работа по вычислению каждого члена в знаменателе $w_{j}/(x-x_{j})$ уже сделано в вычислительной технике ${\bigl (}w_{j}/(x-x_{j}){\bigr )}y_{j}$ и поэтому вычисление суммы в знаменателе стоит всего ${\textstyle k}$ операции сложения; за оценочные баллы ${\textstyle x}$ которые находятся близко к одному из узлов ${\textstyle x_{j}}$ , катастрофическая отмена обычно будет проблемой для значения ${\textstyle (x-x_{j})}$ , однако эта величина появляется как в числителе, так и в знаменателе, и они сокращаются, обеспечивая хорошую относительную точность конечного результата.

Используя эту формулу для оценки $L(x)$ в одном из узлов $x_{j}$ приведет к неопределенному результату $\infty y_{j}/\infty$ ; компьютерные реализации должны заменить такие результаты $L(x_{j})=y_{j}.$

Каждый базисный полином Лагранжа также можно записать в барицентрической форме:

\ell _{j}(x)={\frac {w_{j}}{x-x_{j}}}{\Bigg /}\sum _{m=0}^{k}{\frac {w_{m}}{x-x_{m}}}.

Взгляд из линейной алгебры

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

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

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

Пример

Мы хотим интерполировать $f(x)=x^{2}$ по домену $1\leq x\leq 3$ в трех узлах $\{1,\,2,\,3\}$ :

{\begin{aligned}x_{0}&=1,&&&y_{0}=f(x_{0})&=1,\\[3mu]x_{1}&=2,&&&y_{1}=f(x_{1})&=4,\\[3mu]x_{2}&=3,&&&y_{2}=f(x_{2})&=9.\end{aligned}}

Узловой полином $\ell$ является

\ell (x)=(x-1)(x-2)(x-3)=x^{3}-6x^{2}+11x-6.

Барицентрические веса

{\begin{aligned}w_{0}&=(1-2)^{-1}(1-3)^{-1}={\tfrac {1}{2}},\\[3mu]w_{1}&=(2-1)^{-1}(2-3)^{-1}=-1,\\[3mu]w_{2}&=(3-1)^{-1}(3-2)^{-1}={\tfrac {1}{2}}.\end{aligned}}

Базисные полиномы Лагранжа:

{\begin{aligned}\ell _{0}(x)&={\frac {x-2}{1-2}}\cdot {\frac {x-3}{1-3}}={\tfrac {1}{2}}x^{2}-{\tfrac {5}{2}}x+3,\\[5mu]\ell _{1}(x)&={\frac {x-1}{2-1}}\cdot {\frac {x-3}{2-3}}=-x^{2}+4x-3,\\[5mu]\ell _{2}(x)&={\frac {x-1}{3-1}}\cdot {\frac {x-2}{3-2}}={\tfrac {1}{2}}x^{2}-{\tfrac {3}{2}}x+1.\end{aligned}}

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

{\begin{aligned}L(x)&=1\cdot {\frac {x-2}{1-2}}\cdot {\frac {x-3}{1-3}}+4\cdot {\frac {x-1}{2-1}}\cdot {\frac {x-3}{2-3}}+9\cdot {\frac {x-1}{3-1}}\cdot {\frac {x-2}{3-2}}\\[6mu]&=x^{2}.\end{aligned}}

Во (второй) барицентрической форме

L(x)={\frac {\displaystyle \sum _{j=0}^{2}{\frac {w_{j}}{x-x_{j}}}y_{j}}{\displaystyle \sum _{j=0}^{2}{\frac {w_{j}}{x-x_{j}}}}}={\frac {\displaystyle {\frac {\tfrac {1}{2}}{x-1}}+{\frac {-4}{x-2}}+{\frac {\tfrac {9}{2}}{x-3}}}{\displaystyle {\frac {\tfrac {1}{2}}{x-1}}+{\frac {-1}{x-2}}+{\frac {\tfrac {1}{2}}{x-3}}}}.

Примечания

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

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

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

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

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

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

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},

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

R(x)={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)(t-x_{0})\cdots (t-x_{k})}}dt={\frac {\ell (x)}{2\pi i}}\int _{C}{\frac {f(t)}{(t-x)\ell (t)}}dt.

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

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

Вывод ^[7]

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

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

L^{(k+1)}=0,{\tilde {R}}^{(k+1)}=C\cdot (k+1)!

(Поскольку высшая сила

x

в

{\tilde {R}}(x)

является

k+1

)

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

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

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

С $F(x_{p})=0$ у нас есть $R(x_{p})={\tilde {R}}(x_{p})={\frac {f^{k+1}(\xi )}{(k+1)!}}\prod _{i=0}^{k}(x_{p}-x_{i})$

Производные

я производная $d-$ интерполяционного полинома Лагранжа может быть записана через производные базисных полиномов:

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

Напомним (см. § Определение выше), что каждый базисный полином Лагранжа равен

${\begin{aligned}\ell _{j}(x)&=\prod _{\begin{smallmatrix}m=0\\m\neq j\end{smallmatrix}}^{k}{\frac {x-x_{m}}{x_{j}-x_{m}}}.\end{aligned}}$

Первую производную можно найти с помощью правила произведения :

{\begin{aligned}\ell _{j}'(x)&=\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\Biggl [}{\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}}}{\Biggr ]}\\[5mu]&=\ell _{j}(x)\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{x-x_{i}}}.\end{aligned}}

Вторая производная

{\begin{aligned}\ell _{j}''(x)&=\sum _{\begin{smallmatrix}i=0\\i\neq j\end{smallmatrix}}^{k}{\frac {1}{x_{j}-x_{i}}}{\Biggl [}\sum _{\begin{smallmatrix}m=0\\m\neq (i,j)\end{smallmatrix}}^{k}{\Biggl (}{\frac {1}{x_{j}-x_{m}}}\prod _{\begin{smallmatrix}n=0\\n\neq (i,j,m)\end{smallmatrix}}^{k}{\frac {x-x_{n}}{x_{j}-x_{n}}}{\Biggr )}{\Biggr ]}\\[10mu]&=\ell _{j}(x)\sum _{0\leq i<m\leq k}{\frac {2}{(x-x_{i})(x-x_{m})}}\\[10mu]&=\ell _{j}(x){\Biggl [}{\Biggl (}\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{x-x_{i}}}{\Biggr )}^{2}-\sum _{\begin{smallmatrix}i=0\\i\not =j\end{smallmatrix}}^{k}{\frac {1}{(x-x_{i})^{2}}}{\Biggr ]}.\end{aligned}}

Третья производная

{\begin{aligned}\ell _{j}'''(x)&=\ell _{j}(x)\sum _{0\leq i<m<n\leq k}{\frac {3!}{(x-x_{i})(x-x_{m})(x-x_{n})}}\end{aligned}}

и то же самое для высших производных.

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

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

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

См. также

Ссылки

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

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

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

[1] Лагранж, Жозеф-Луи (1795). «Урок пятый. Об использовании кривых при решении задач». Элементарные уроки математики (на французском языке). Париж. Переиздано в Серре, Джозеф-Альфред , изд. (1877). Работы Лагранжа . Полет. 7. Готье-Виллар. стр. 271–287 . Переведено как «Лекция V. Об использовании кривых при решении задач» . Лекции по элементарной математике . Перевод МакКормака, Томаса Дж. (2-е изд.). Открытый суд. 1901. стр. 127–149.

[2] Уоринг, Эдвард (1779). «Задачи об интерполяциях» . Философские труды Королевского общества . 69 : 59–67. дои : 10.1098/rstl.1779.0008 .

[3] Мейеринг, Эрик (2002). «Хронология интерполяции: от древней астрономии до современной обработки сигналов и изображений» (PDF) . Труды IEEE . 90 (3): 319–342. дои : 10.1109/5.993400 .

[4] Беррю, Жан-Поль ; Трефетен, Ллойд Н. (2004). «Барицентрическая интерполяция Лагранжа» (PDF) . Обзор СИАМ . 46 (3): 501–517. Бибкод : 2004SIAMR..46..501B . дои : 10.1137/S0036144502417715 .

[5] Квартерони, Альфио ; Салери, Фаусто (2003). Научные вычисления с MATLAB . Тексты по информатике и технике. Том. 2. Спрингер. п. 66. ИСБН 978-3-540-44363-6 . .

[6] Абрамовиц, Милтон ; Стегун, Ирен Энн , ред. (1983) [июнь 1964 г.]. «Глава 25, уравнение 25.2.3» . Справочник по математическим функциям с формулами, графиками и математическими таблицами . Серия «Прикладная математика». Том. 55 (Девятое переиздание с дополнительными исправлениями десятого оригинального издания с исправлениями (декабрь 1972 г.); первое изд.). Вашингтон, округ Колумбия; Нью-Йорк: Министерство торговли США, Национальное бюро стандартов; Дуврские публикации. п. 878. ИСБН 978-0-486-61272-0 . LCCN 64-60036 . МР 0167642 . LCCN 65-12253 .

[7] «Интерполяция» (PDF) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]