Задача интерполяции
| Определение: |
| Система узлов — набор из чисел [math]x_0 \lt x_1 \lt x_2 \lt \ldots \lt x_n[/math] и [math]y_0, y_1, y_2, \ldots ,y_n[/math]. |
Дана система узлов. Требуется найти полином [math]P_n[/math] степени не выше [math]n[/math] такой, что [math]P_n(x_k) = y_k, k=\overline{0,n}[/math].
Будем искать его в форме Лагранжа, хотя имеется ряд равносильных представлений, например, в
форме Ньютона.
Докажем от противного, что таких полиномов не более одного. Допустим, что существует еще один такой полином [math]\tilde P_n[/math].
Рассмотрим полином [math]M_n = P_n - \tilde P_n[/math]. Тогда [math]M_n(x_k) = y_k - y_k = 0, k = \overline{0,n}[/math],
то есть этот полином имеет [math]n+1[/math] корень, но [math]\deg M_n \le n[/math]. Получили противоречие.
Будем искать его в форме Лагранжа. Для этого построим фундаментальные полиномы.
| Определение: |
| Фундаментальные полиномы [math]\Phi_j(x)[/math] степени не выше [math]n[/math] — полиномы, отвечающие заданной
системе узлов [math]x_0 \lt x_1 \lt x_2 \lt \ldots \lt x_n[/math] такие, что
[math]
\Phi_j(x_k) = \left\{
\begin{aligned}
1 & ,\quad k = j\\
0 & ,\quad k \ne j\\
\end{aligned}\right.
[/math]. |
Для его построения обозначим за [math]\omega_n(x) = \prod\limits_{j = 0}^n (x - x_j)[/math]. Это полином степени [math]n + 1[/math].
Составим выражение [math]\frac{\omega_n(x)}{(x - x_j) \cdot \omega_n'(x_j)}[/math], [math]x \ne x_j[/math]. В этом случае дробь корректно определена.
При [math]x \to x_j[/math] получаем неопределённость [math]\frac00[/math]. Раскроем её по правилу Лопиталя: [math]\frac{\omega'_n(x)}{\omega_n'(x_j)} = 1[/math] при [math]x \to x_j[/math].
Тогда доопределим по непрерывности дробь единицей. Но при [math]x \ne x_j[/math] — это полином [math]n[/math]-й степени. Значит,
[math]\Phi_j(x) = \frac{\omega_n(x)}{(x-x_j) \cdot \omega_n'(x_j)}[/math].
Тогда
[math]
\Phi_j(x_k) = \left\{
\begin{aligned}
1 & ,\quad k = j\\
0 & ,\quad k \ne j\\
\end{aligned}\right.
[/math], что и требовалось.
Обозначим [math]L_n(x) = \sum\limits_{j = 0}^n y_j \Phi_j(x)[/math].
[math]L_n(x_k) = \sum\limits_{j = 0}^n y_j \Phi_j(x_k) = y_k \Phi_k(x_k) = y_k[/math].
Требуемый полином [math]L_n(x)[/math] найден.
Замечание: из формулы для фундаментальных полиномов [math]\Phi_j(x)[/math] легко записать в развёрнутом виде:
[math]
\Phi_j(x) = \frac
{(x-x_0)(x - x_1)\cdots(x - x_{j- 1})(x - x_{j + 1})\cdots(x - x_n)}
{(x_j - x_0)(x_j - x_0)\cdots(x_j - x_{j-1})(x_j - x_{j + 1})\cdots(x_j - x_n)}
[/math]
Трактовки и другие задачи
Выведенную ранее формулу Тейлора можно трактовать следующим образом:
«Дана функция [math]f(x)[/math]. Найти полином [math]T_n[/math] степени не выше [math]n[/math] такой, что [math]f^{(k)}(x_0) = T_n^{(k)}(x_0), k = \overline{0, n}[/math]».
Ранее мы обнаружили, что это
[math]T_n(x) = \sum\limits_{k = 0}^n \frac
{f^{(k)}(x_0)}
{k!}
\cdot (x - x_0)^k
[/math].
Теперь другая задача: «Дана функция [math]f[/math] и система узлов. Требуется найти полином [math]L_n[/math] степени не выше [math]n[/math] такой, что
[math]\forall x_j: j = \overline{0..n}\quad L_n(x_j) = f(x_j)[/math]
»
Положим [math]L_n(x) = \sum\limits_{j = 0}^n \Phi_j(x_j) \cdot f(x_j)[/math]. По пункту 1 этот полином решает поставленную задачу.
Для полинома Тейлора [math]f(x) = T_n(x) + \frac
{f^{(n + 1)}(c_x)}
{(n + 1)!} \cdot (x - x_0)^{n + 1}
[/math].
Сейчас будет доказана теорема, аналогичная теореме об интерполяционном полиноме Лагранжа, после чего станет ясно, что это задачи одного класса.
Во втором случае это изложено на языке производных, а в первом — через значения функции в точках.
Эти два метода метода можно комбинировать, лишь бы информативных значений было [math]n + 1[/math]. Такие промежуточные задачи называют
интерполированием по Эрмиту. Но они никому не нужны.
Теорема Лагранжа
| Теорема (Лагранжа): |
Пусть [math]f[/math] [math]n + 1[/math] раз дифференцируема на [math]\langle a; b\rangle[/math]. На этом промежутке задана система узлов.
Тогда для соответственного интерполяционного полинома Лагранжа выполняется равенство
[math]f(x) = L_n(x) + \frac{f^{n + 1}(c_x)}{(n+1)!} \cdot \omega_n(x)[/math], где [math]c_x[/math] — некоторая точка из [math]\langle a; b \rangle[/math], зависящая от [math]x[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Случай [math]x = x_k[/math] тривиален.
Пусть тогда [math]x \ne x_k[/math].
Для доказательства применим теорему Ролля. Определим вспомогательную функцию [math]g(t) = f(t) - L_n(t)- k \omega_n(t)[/math], где [math]k[/math] — коэффициент,
подлежащий определению, а [math]x[/math] дано.
[math]\forall j = \overline{0, n}:\quad g(x_j) = f(x_j) - L_n(x_j) - k \omega_n(x_j) = 0[/math]
Для определения [math]k[/math] потребуем, чтобы [math]g(x)[/math] было равно [math]0[/math].
[math]g(x) = f(x) - L_n(x) - k \omega_n(x) = 0[/math]
[math]\omega_n(x) \ne 0[/math], так как [math]x \ne x_j[/math].
[math]k = \frac{f(x) - L_n(x)}{\omega_n(x)}\quad (1)\, .[/math]
Итак, при выбранном [math]k[/math] будет [math]g(x_j) = 0[/math], [math]g(x) = 0[/math], то есть [math]g[/math] принимает нулевые значения в [math]n + 2[/math] точках. Очевидно,
из узлов и точки [math]x[/math] можно сделать [math]n + 1[/math] последовательный отрезок. На конце каждого из них [math]g[/math] принимает значение [math]0[/math].
Значит, по теореме Ролля на каждом из них найдётся по корню производной. Из полученных корней можно сделать [math]n[/math] отрезков,
на каждом из них по теореме Ролля найдётся по корню второй производной… В конце концов останется один отрезок, границами которого
будут корни [math]g^{(n)}[/math]. Тогда по теореме Ролля на этом отрезке найдётся корень [math]g^{(n + 1)}[/math]. Его и обозначим за [math]c_x[/math].
Подведём промежуточный итог: найдено [math]c_x[/math] такое, что [math]g^{(n + 1)}(c_x) = 0[/math].
[math]g(t) = f(t) - L_n(t) - k \omega_n(t)[/math]
Продифференцируем [math]n + 1[/math] раз. [math]\deg L_n(x) \leq n \Rightarrow L_n^{(n + 1)} = 0[/math]. [math]\omega_n(t) = t^{n + 1} + \ldots \Rightarrow \omega^{(n + 1)}_n = (n + 1)![/math].
Таким образом, [math]g^{(n + 1)}(t) = f^{(n + 1)}(t) - k\cdot (n + 1)![/math].
Подставим [math]t = c_x[/math].
[math]0 = g^{(n + 1)}(c_x) = f^{(n + 1)}(c_x) - k\cdot (n + 1)![/math]
[math]k = \frac{f^{(n + 1)}(c_x)}{(n + 1)!}\quad (2)\, .[/math]
Утверждение теоремы напрямую следует из равенств [math](1)[/math] и [math](2)[/math] . |
| [math]\triangleleft[/math] |
Следствие
В условиях теоремы выполняется неравенство [math]|f(x) - L_n(x)| \leq \frac{M_{n + 1}}{(n + 1)!} (b - a)^{n + 1}[/math], где
[math]M_{n + 1} = \sup\limits_{\langle a; b \rangle} |f^{(n + 1)}|.[/math]
Оно следует из того, что для всех [math]x[/math] на [math]\langle a; b \rangle\,|x - x_j| \le b - a.[/math]
Замечание
Следует понимать, что на самом деле какую бы систему узлов мы не взяли на [math]\langle a; b \rangle[/math] как по числу
точек в ней, так и по характеру распределения значений, для этого промежутка всегда можно построить непрерывную функцию, для которой ее интерполяционный многочлен будет отличаться от неё сколь угодно много.
