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

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

Учитывая набор данных пар координат $(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]