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

Интерполяцио́нный многочле́н Лагра́нжа — многочлен минимальной степени, принимающий заданные значения в заданном наборе точек, то есть решающий задачу интерполяции.

ОпределениеПравить

 

Интерполяционный многочлен Лагранжа для четырёх точек (-9,5), (-4,2), (-1,-2) и (7,9), а также полиномы $y_i{l}_i(x)$$y_{i}l_{i}(x)$ , каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных.

Пусть задана $n+1$$n+1$  пара чисел $(x_0,y_0),(x_1,y_1),\dots <!--\; \dots \; -->,(x_n,y_n),$$(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n}),$  где все $x_j$$x_{j}$  различны. Требуется построить многочлен $L(x)$$L(x)$  степени не более $n$$n$ , для которого $L(x_j)=y_j$$L(x_{j})=y_{j}$ .

Общий случайПравить

Ж. Л. Лагранж предложил следующий способ вычисления таких многочленов:

$L(x)=\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}{y}_i{l}_i(x),$$L(x)=\sum _{i=0}^{n}y_{i}l_{i}(x),$ 

где базисные полиномы $l_i$$l_{i}$  определяются по формуле

$l_i(x)=\underset{j=0,j\ne <!--\; \ne \; -->i}{\overset{n}{\prod <!--\; \prod \; -->}}\frac{x-<!--\; -\; -->x_j}{x_i-<!--\; -\; -->x_j}=\frac{x-<!--\; -\; -->x_0}{x_i-<!--\; -\; -->x_0}\cdots <!--\; \cdots \; -->\frac{x-<!--\; -\; -->x_{i-<!--\; -\; -->1}}{x_i-<!--\; -\; -->x_{i-<!--\; -\; -->1}}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_{i+1}}{x_i-<!--\; -\; -->x_{i+1}}\cdots <!--\; \cdots \; -->\frac{x-<!--\; -\; -->x_n}{x_i-<!--\; -\; -->x_n}$$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}}}\cdot {\frac {x-x_{i+1}}{x_{i}-x_{i+1}}}\cdots {\frac {x-x_{n}}{x_{i}-x_{n}}}$ 

Для любого $i=0,\dots <!--\; \dots \; -->,n$$i=0,\ldots ,n$  многочлен $l_i$$l_{i}$  имеет степень $n$$n$  и

$l_{i}(x_{j})=\left\{{\begin{array}{rl}0,&j\neq i,\\1,&j=i.\end{array}}\right.$ 

Отсюда следует, что $L(x)$$L(x)$ , являющийся линейной комбинацией многочленов $l_i(x)$$l_{i}(x)$ , имеет степень не больше $n$$n$  и $L(x_i)=y_i$$L(x_{i})=y_{i}$ .

Случай равноотстоящих узлов интерполяцииПравить

Пусть узлы интерполяции $x_j$$x_{j}$  являются равноотстоящими, то есть выражаются через начальную точку $x_0$$x_{0}$  и некоторую фиксированную положительную величину $h$$h$  следующим образом:

$x_j=x_0+jh.$$x_{j}=x_{0}+jh.$ 

Отсюда следует, что

$x_j-<!--\; -\; -->x_i=(j-<!--\; -\; -->i)h.$$x_{j}-x_{i}=(j-i)h.$ 

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

$l_j(x)=\underset{i=0,i\ne <!--\; \ne \; -->j}{\overset{n}{\prod <!--\; \prod \; -->}}\frac{(x-<!--\; -\; -->x_i)}{(x_j-<!--\; -\; -->x_i)}=\frac{\underset{i=0,i\ne <!--\; \ne \; -->j}{\overset{n}{\prod <!--\; \prod \; -->}}(x-<!--\; -\; -->x_0-<!--\; -\; -->ih)}{h^n\underset{i=0,i\ne <!--\; \ne \; -->j}{\overset{n}{\prod <!--\; \prod \; -->}}(j-<!--\; -\; -->i)}$$l_{j}(x)={\prod _{i=0,\,i\neq j}^{n}{(x-x_{i}) \over (x_{j}-x_{i})}}={\prod \limits _{i=0,\,i\neq j}^{n}(x-x_{0}-ih) \over h^{n}\prod \limits _{i=0,\,i\neq j}^{n}(j-i)}$ 

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

$y=\frac{x-<!--\; -\; -->x_0}{h}$$y={{x-x_{0}} \over h}$ 

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

$l_j(x)=l_j(x_0+yh)=(-<!--\; -\; -->1{)}^{n-<!--\; -\; -->j}{C}_n^j\frac{y(y-<!--\; -\; -->1)\dots <!--\; \dots \; -->(y-<!--\; -\; -->n)}{(y-<!--\; -\; -->i)n!}.$$l_{j}(x)=l_{j}(x_{0}+yh)=(-1)^{n-j}C_{n}^{j}{\dfrac {y(y-1)\ldots (y-n)}{(y-i)n!}}.$ 

Данные величины называются коэффициентами Лагранжа. Они не зависят ни от $y_0,\dots <!--\; \dots \; -->,y_n$$y_{0},\ldots ,y_{n}$ , ни от $h$$h$  и потому могут быть вычислены заранее и записаны в виде таблиц. Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования длинной арифметики.

Остаточный членПравить

Если считать числа $y_0,\dots <!--\; \dots \; -->,y_n$$y_{0},\ldots ,y_{n}$  значениями некоторой функции $f$$f$  в узлах $x_0,\dots <!--\; \dots \; -->,x_n$$x_{0},\ldots ,x_{n}$ , то ошибка интерполирования функции $f$$f$  многочленом $L$$L$  равна

$f(x)-<!--\; -\; -->L(x)=\frac{f^{(n+1)}(\mathrm{\xi <!--\; \xi \; -->})}{(n+1)!}(x-<!--\; -\; -->x_0)\dots <!--\; \dots \; -->(x-<!--\; -\; -->x_n),$$f(x)-L(x)={\dfrac {f^{(n+1)}(\xi )}{(n+1)!}}(x-x_{0})\ldots (x-x_{n}),$ 

где $\mathrm{\xi <!--\; \xi \; -->}$$\xi$  – некоторая средняя точка между наименьшим и наибольшим из чисел $x_0,\dots <!--\; \dots \; -->,x_n$$x_{0},\ldots ,x_{n}$ . Полагая $M_{n+1}=\underset{x\in <!--\; \in \; -->[x_0,x_n]}{sup}|f^{(n+1)}(x)|$$M_{n+1}=\sup _{x\in [x_{0},x_{n}]}|f^{(n+1)}(x)|$ , можно записать

$|f(x)-<!--\; -\; -->L(x)|⩽<!--\; ⩽\; -->\frac{M_{n+1}}{(n+1)!}|(x-<!--\; -\; -->x_0)\dots <!--\; \dots \; -->(x-<!--\; -\; -->x_n)|.$$|f(x)-L(x)|\leqslant {\dfrac {M_{n+1}}{(n+1)!}}|(x-x_{0})\ldots (x-x_{n})|.$ 

ЕдинственностьПравить

Основная статья: Интерполяция алгебраическими многочленами

Существует единственный многочлен степени не превосходящей $n$$n$ , принимающий заданные значения в $n+1$$n+1$  заданной точке.

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

Предположим, что существуют два различных многочлена $P(x)$$P(x)$  и $Q(x)$$Q(x)$  степени не более $n$$n$ , для которых верно, что для $n+1$$n+1$  пар чисел $(x_0,y_0),(x_1,y_1),\dots <!--\; \dots \; -->,(x_n,y_n),$$(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n}),$  где все $x_j$$x_{j}$  различны, $P(x_j)=Q(x_j)=y_j.$$P(x_{j})=Q(x_{j})=y_{j}.$  Рассмотрим многочлен $L(x)=P(x)-<!--\; -\; -->Q(x)$$L(x)=P(x)-Q(x)$ . Подставляя в него $x_j$$x_{j}$  ($0\le <!--\; \le \; -->j\le <!--\; \le \; -->n$$0\leq j\leq n$ ), получаем, что $L(x_j)=P(x_j)-<!--\; -\; -->Q(x_j)=y_j-<!--\; -\; -->y_j=0$$L(x_{j})=P(x_{j})-Q(x_{j})=y_{j}-y_{j}=0$ . Таким образом, многочлен $L(x)$$L(x)$  имеет $n+1$$n+1$  корней и все они различны. Следовательно $L(x)\equiv <!--\; \equiv \; -->0$$L(x)\equiv 0$ , так как ненулевой многочлен степени не превосходящей $n$$n$  имеет не более $n$$n$  корней. Следовательно, $P(x)=Q(x)$$P(x)=Q(x)$ . ■ ■

Это утверждение является обобщением того факта, что через любые две точки проходит единственная прямая.

С точки зрения линейной алгебрыПравить

На единственность интерполяционного многочлена можно также взглянуть с точки зрения СЛАУ. Рассмотрим систему уравнений $P(x_0)=y_0,P(x_1)=y_1,\dots <!--\; \dots \; -->,P(x_n)=y_n$$P(x_{0})=y_{0},P(x_{1})=y_{1},\dots ,P(x_{n})=y_{n}$ . В явном виде она записывается как

$\{\begin{array}{l}{a}_0+a_1{x}_0+a_2{x}_0^2+\cdots <!--\; \cdots \; -->+a_n{x}_0^n=y_0,\\ a_0+a_1{x}_1+a_2{x}_1^2+\cdots <!--\; \cdots \; -->+a_n{x}_1^n=y_1,\\ \dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->\dots <!--\; \dots \; -->,\\ a_0+a_1{x}_n+a_2{x}_n^2+\cdots <!--\; \cdots \; -->+a_n{x}_n^n=y_n\end{array}$${\begin{cases}a_{0}+a_{1}x_{0}+a_{2}x_{0}^{2}+\dots +a_{n}x_{0}^{n}=y_{0},\\a_{0}+a_{1}x_{1}+a_{2}x_{1}^{2}+\dots +a_{n}x_{1}^{n}=y_{1},\\\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots ,\\a_{0}+a_{1}x_{n}+a_{2}x_{n}^{2}+\dots +a_{n}x_{n}^{n}=y_{n}\\\end{cases}}$ 

Её можно переписать в виде системы уравнений $Xa=y$$Xa=y$  с неизвестным вектором $a=(a_0,a_1,\dots <!--\; \dots \; -->,a_n)$$a=(a_{0},a_{1},\dots ,a_{n})$ :

${\begin{bmatrix}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n}\\\end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\\vdots \\a_{n}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}$ 

Матрица $X$$X$  в такой системе является матрицей Вандермонда и её определитель равен $\prod \limits _{i<j}(x_{i}-x_{j})$ . Соответственно, если все точки $x_0,x_1,\dots <!--\; \dots \; -->,x_n$$x_{0},x_{1},\dots ,x_{n}$  различны, то матрица невырождена и система обладает единственным решением.

С точки зрения китайской теоремы об остаткахПравить

По теореме Безу остаток от деления $P(x)$$P(x)$  на $(x-<!--\; -\; -->a)$$(x-a)$  равен $P(a)$$P(a)$ . Таким образом, всю систему можно воспринимать в виде системы сравнений:

$\{\begin{array}{l}P(x)\equiv <!--\; \equiv \; -->y_0(\mathrm{mod}x-<!--\; -\; -->x_0),\\ P(x)\equiv <!--\; \equiv \; -->y_1(\mathrm{mod}x-<!--\; -\; -->x_1),\\ \dots <!--\; \dots \; -->,\\ P(x)\equiv <!--\; \equiv \; -->y_n(\mathrm{mod}x-<!--\; -\; -->x_n),\end{array}$${\begin{cases}P(x)\equiv y_{0}{\pmod {x-x_{0}}},\\P(x)\equiv y_{1}{\pmod {x-x_{1}}},\\\dots ,\\P(x)\equiv y_{n}{\pmod {x-x_{n}}},\\\end{cases}}$ 

По китайской теореме об остатках у такой системы есть единственное решение по модулю $(x-<!--\; -\; -->x_0)(x-<!--\; -\; -->x_1)\dots <!--\; \dots \; -->(x-<!--\; -\; -->x_n)$$(x-x_{0})(x-x_{1})\dots (x-x_{n})$ , то есть, заданная система однозначно определяет многочлен степени не выше $n$$n$ . Такое представление многочлена в виде наборов остатков по модулям мономов аналогично представлению числа в виде остатков от деления на простые модули в системе остаточных классов. При этом явная формула для многочлена Лагранжа также может быть получена в соответствии с формулами китайской теоремы: $P(x)=\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}{y}_i{M}_i{M}_i^{-<!--\; -\; -->1}$${\textstyle P(x)=\sum \limits _{i=0}^{n}y_{i}M_{i}M_{i}^{-1}}$ , где $M_i=\underset{j\ne <!--\; \ne \; -->i}{\prod <!--\; \prod \; -->}(x-<!--\; -\; -->x_j)$$M_{i}=\prod \limits _{j\neq i}(x-x_{j})$  и $M_i^{-<!--\; -\; -->1}=\underset{j\ne <!--\; \ne \; -->i}{\prod <!--\; \prod \; -->}(x-<!--\; -\; -->x_j{)}^{-<!--\; -\; -->1}(\mathrm{mod}x-<!--\; -\; -->x_i)=\underset{j\ne <!--\; \ne \; -->i}{\prod <!--\; \prod \; -->}(x_i-<!--\; -\; -->x_j{)}^{-<!--\; -\; -->1}$$M_{i}^{-1}=\prod \limits _{j\neq i}(x-x_{j})^{-1}{\pmod {x-x_{i}}}=\prod \limits _{j\neq i}(x_{i}-x_{j})^{-1}$ .

ПримерПравить

 

Приближение функции $f(x)=\text{tg}(x)$$f(x)={\mbox{tg}}(x)$  (синяя линия) многочленом $L(x)=4,834848x^3-<!--\; -\; -->1,477474x$$L(x)=4,834848x^{3}-1,477474x$  (зелёная линия).

Найдем формулу интерполяции для $f(x)=\mathrm{t}\mathrm{g}<!--\; \; -->(x)$$f(x)=\mathop {\mathrm {tg} } \nolimits (x)$  имеющей следующие значения:

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

$l_0(x)=\frac{x-<!--\; -\; -->x_1}{x_0-<!--\; -\; -->x_1}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_2}{x_0-<!--\; -\; -->x_2}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_3}{x_0-<!--\; -\; -->x_3}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_4}{x_0-<!--\; -\; -->x_4}=\frac{1}{243}x(2x-<!--\; -\; -->3)(4x-<!--\; -\; -->3)(4x+3)$$l_{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)$ 

$l_1(x)=\frac{x-<!--\; -\; -->x_0}{x_1-<!--\; -\; -->x_0}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_2}{x_1-<!--\; -\; -->x_2}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_3}{x_1-<!--\; -\; -->x_3}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_4}{x_1-<!--\; -\; -->x_4}=-<!--\; -\; -->\frac{8}{243}x(2x-<!--\; -\; -->3)(2x+3)(4x-<!--\; -\; -->3)$$l_{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)$ 

$l_2(x)=\frac{x-<!--\; -\; -->x_0}{x_2-<!--\; -\; -->x_0}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_1}{x_2-<!--\; -\; -->x_1}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_3}{x_2-<!--\; -\; -->x_3}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_4}{x_2-<!--\; -\; -->x_4}=\frac{3}{243}(2x+3)(4x+3)(4x-<!--\; -\; -->3)(2x-<!--\; -\; -->3)$$l_{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)$ 

$l_3(x)=\frac{x-<!--\; -\; -->x_0}{x_3-<!--\; -\; -->x_0}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_1}{x_3-<!--\; -\; -->x_1}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_2}{x_3-<!--\; -\; -->x_2}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_4}{x_3-<!--\; -\; -->x_4}=-<!--\; -\; -->\frac{8}{243}x(2x-<!--\; -\; -->3)(2x+3)(4x+3)$$l_{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)$ 

$l_4(x)=\frac{x-<!--\; -\; -->x_0}{x_4-<!--\; -\; -->x_0}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_1}{x_4-<!--\; -\; -->x_1}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_2}{x_4-<!--\; -\; -->x_2}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->x_3}{x_4-<!--\; -\; -->x_3}=\frac{1}{243}x(2x+3)(4x-<!--\; -\; -->3)(4x+3).$$l_{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{aligned}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{aligned}}$ 

ПримененияПравить

 

Многочлены Лагранжа степеней от нулевой до пятой для функции $\cos <!--\; \; -->(5\mathrm{\pi <!--\; \pi \; -->}x)$$\cos(5\pi x)$ 

Численное интегрированиеПравить

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

$f(x)\approx <!--\; \approx \; -->\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}f(x_i)l_i(x).$$f(x)\approx \sum _{i=0}^{n}f(x_{i})l_{i}(x).$ 

Полученное выражение можно использовать для приближённого вычисления определённого интеграла от функции $f$$f$ :

$\underset{a}{\overset{b}{\int <!--\; \int \; -->}}f(x)dx\approx <!--\; \approx \; -->\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}f(x_i)\underset{a}{\overset{b}{\int <!--\; \int \; -->}}{l}_i(x)dx$$\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$$l_{i}$  не зависят от $f(x)$$f(x)$  и их можно вычислить заранее с использованием последовательности $x_j$$x_{j}$ .

ЛитератураПравить

• Березин, И. С., Жидков Н. П. Методы вычислений. Том I. — 2-е изд., стереотипное – М.: Физматлит. 1962.

СсылкиПравить

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

См. такжеПравить

• Схема Эйткена
• Интерполяционные формулы Ньютона
• Интерполяция с кратными узлами
• Схема разделения секрета Шамира
• Комбинаторная теорема о нулях
• Интерполяция алгебраическими многочленами