WikiSort.ru - Не сортированное

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

Определение

Обозначим через ${\displaystyle P_{i,\dots ,j}(x)}$ многочлен Лагранжа, полученный интерполяцией базовых точек ${\displaystyle (x_{i},y_{i}),(x_{i+1},y_{i+1}),\dots ,(x_{j},y_{j})}$ . Тогда верно следующее соотношение

${\displaystyle P_{i}(x)=y_{i}}$ (вырожденный случай, многочлен нулевой степени — константа)

${\displaystyle P_{i,\dots ,j}(x)={\frac {1}{x_{j}-x_{i}}}{\begin{vmatrix}x-x_{i}&P_{i,\dots ,j-1}(x)\\x-x_{j}&P_{i+1,\dots ,j}(x)\end{vmatrix}}}$

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

Доказательство легко произвести по индукции. Не ограничивая общности, для удобства примем ${\displaystyle i=0}$ , ${\displaystyle j=n}$ .

Пусть ${\displaystyle P_{0,\dots ,n-1}(x)}$ и ${\displaystyle P_{1,\dots ,n}(x)}$  — многочлены Лагранжа для соответствующих наборов точек. Это значит, что ${\displaystyle P_{0,\dots ,n-1}(x)=\sum \limits _{i=0}^{n-1}{y_{i}\prod \limits _{j=0;j\not =i}^{n-1}{\frac {x-x_{j}}{x_{i}-x_{j}}}}}$ и ${\displaystyle P_{1,\dots ,n}(x)=\sum \limits _{i=1}^{n}{y_{i}\prod \limits _{j=1;j\not =i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}}}$

Если обозначить ${\displaystyle A_{i}=\prod \limits _{j=0;j\not =i}^{n}{(x-x_{j})}}$ ; ${\displaystyle T_{i}=y_{i}\prod \limits _{j=0;j\not =i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}}$ и ${\displaystyle X_{i}=\prod \limits _{j=1;j\not =i}^{n-1}{(x_{i}-x_{j})}}$ , то очевидно, что

${\displaystyle {\frac {1}{x_{n}-x_{0}}}{\begin{vmatrix}x-x_{0}&P_{0,\dots ,n-1}(x)\\x-x_{n}&P_{1,\dots ,n}(x)\end{vmatrix}}=T_{0}+T_{n}+\sum \limits _{i=1}^{n-1}{y_{i}\left({{\frac {A_{i}}{X_{i}(x_{i}-x_{n})(x_{n}-x_{0})}}-{\frac {A_{i}}{X_{i}(x_{i}-x_{0})(x_{n}-x_{0})}}}\right)}=}$

${\displaystyle =T_{0}+T_{n}+\sum \limits _{i=1}^{n-1}{y_{i}{\frac {A_{i}x_{n}-A_{i}x_{0}}{X_{i}(x_{i}-x_{n})(x_{i}-x_{0})(x_{n}-x_{0})}}}=T_{0}+T_{n}+\sum \limits _{i=1}^{n-1}{y_{i}{\frac {A_{i}}{X_{i}(x_{i}-x_{n})(x_{i}-x_{0})}}}=\sum \limits _{i=0}^{n}{T_{i}}}$ ,

что совпадает с многочленом Лагранжа.

Производительность

См. также

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

Для улучшения этой статьи по математике желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Добавить иллюстрации.