Задачи интерполирования функции

Задача интерполяция

Определение:

Система узлов — набор чисел [math]x_1 \lt x_2 \lt x_3 \lt \ldots \lt x_n[/math] и [math]y_1, y_2, y_3, \ldots ,y_n[/math].

Дана система узлов [math]x_1 \lt x_2 \lt x_3 \lt \ldots \lt x_n[/math] и [math]y_1, y_2, y_3, \ldots ,y_n[/math]. Требуется найти полином [math]P_n[/math] степени не выше [math]n[/math] такой, что [math]P_n(x_k) = y_k[/math].

Будем искать его в форме Лагранжа, хотя имеется ряд равносильных представлений, например, в форме Ньютона.

Очевидно, что если такой полином существует, то только один.

Будем искать его в форме Лагранжа. Для этого построим фундаментальные полиномы.

Определение:

Фундаментальные полиномы [math]\Phi_j(x)[/math] степени не выше [math]n[/math] — полиномы, отвечающие заданной системе узлов [math]x_0 \lt x_1 \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]

TODO: заголовок

Выведенную ранее формулу Тейлора можно трактовать следующим образом: «Дано [math]f(x)[/math]. Найти полином [math]T_n[/math] степени не выше [math]n[/math] такой, что [math]f^{(k)}(x_0) = T_n^{(k)}(x_0)[/math]».

Ранее мы обнаружили, что это [math]T_n(x) = \sum\limits_{k = 0}^n \frac {f^{(k)}(x_0)} {k!} \cdot (x - x_0)^k [/math].

Теперь другая задача: «Дана функция и система узлов. Требуется найти полином степени не выше [math]n[/math] такой, что [math]\forall x_j: j = \overline{0..n}\quad T(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, k = \overline{1, n}[/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]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)}[/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 = (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)!}$, $k = \frac{f(x) - L_n(x)}{\omega_n(x)}[/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]\langle a; b \rangle[/math] как по числу точек в ней, так и по характеру распределения значений, для этого промежутка всегда можно построить интерполяционный многочлен, который будет отличаться от неё сколь угодно много(нипанянтна — прим. наборщика)