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

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

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

Система узлов — набор из чисел $x_0 \lt x_1 \lt x_2 \lt \ldots \lt x_n$ и $y_0, y_1, y_2, \ldots ,y_n$.

Дана система узлов. Требуется найти полином $P_n$ степени не выше $n$ такой, что $P_n(x_k) = y_k, k=\overline{0,n}$.

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

Докажем от противного, что таких полиномов не более одного. Допустим, что существует еще один такой полином $\tilde P_n$. Рассмотрим полином $M_n = P_n - \tilde P_n$. Тогда $M_n(x_k) = y_k - y_k = 0, k = \overline{0,n}$, то есть этот полином имеет $n+1$ корень, но $\deg M_n \le n$. Получили противоречие.

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

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

Фундаментальные полиномы $\Phi_j(x)$ степени не выше $n$ — полиномы, отвечающие заданной системе узлов $x_0 \lt x_1 \lt x_2 \lt \ldots \lt x_n$ такие, что $\Phi_j(x_k) = \left\{ \begin{aligned} 1 & ,\quad k = j\\ 0 & ,\quad k \ne j\\ \end{aligned}\right.$.

Для его построения обозначим за $\omega_n(x) = \prod\limits_{j = 0}^n (x - x_j)$. Это полином степени $n + 1$.

Составим выражение $\frac{\omega_n(x)}{(x - x_j) \cdot \omega_n'(x_j)}$, $x \ne x_j$. В этом случае дробь корректно определена. При $x \to x_j$ получаем неопределённость $\frac00$. Раскроем её по правилу Лопиталя: $\frac{\omega'_n(x)}{\omega_n'(x_j)} = 1$ при $x \to x_j$. Тогда доопределим по непрерывности дробь единицей. Но при $x \ne x_j$ — это полином $n$-й степени. Значит, $\Phi_j(x) = \frac{\omega_n(x)}{(x-x_j) \cdot \omega_n'(x_j)}$.

Тогда $\Phi_j(x_k) = \left\{ \begin{aligned} 1 & ,\quad k = j\\ 0 & ,\quad k \ne j\\ \end{aligned}\right.$, что и требовалось.

Обозначим $L_n(x) = \sum\limits_{j = 0}^n y_j \Phi_j(x)$.

$L_n(x_k) = \sum\limits_{j = 0}^n y_j \Phi_j(x_k) = y_k \Phi_k(x_k) = y_k$.

Требуемый полином $L_n(x)$ найден.

Замечание: из формулы для фундаментальных полиномов $\Phi_j(x)$ легко записать в развёрнутом виде:

$\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)}$

Трактовки и другие задачи

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

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

Теперь другая задача: «Дана функция $f$ и система узлов. Требуется найти полином $L_n$ степени не выше $n$ такой, что $\forall x_j: j = \overline{0..n}\quad L_n(x_j) = f(x_j)$ »

Положим $L_n(x) = \sum\limits_{j = 0}^n \Phi_j(x_j) \cdot f(x_j)$. По пункту 1 этот полином решает поставленную задачу. Для полинома Тейлора $f(x) = T_n(x) + \frac {f^{(n + 1)}(c_x)} {(n + 1)!} \cdot (x - x_0)^{n + 1}$.

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

Эти два метода метода можно комбинировать, лишь бы информативных значений было $n + 1$. Такие промежуточные задачи называют интерполированием по Эрмиту. Но они никому не нужны.

Теорема Лагранжа

Теорема (Лагранжа):

Пусть $f$ $n + 1$ раз дифференцируема на $\langle a; b\rangle$. На этом промежутке задана система узлов. Тогда для соответственного интерполяционного полинома Лагранжа выполняется равенство $f(x) = L_n(x) + \frac{f^{n + 1}(c_x)}{(n+1)!} \cdot \omega_n(x)$, где $c_x$ — некоторая точка из $\langle a; b \rangle$, зависящая от $x$.

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

$\triangleright$

Случай $x = x_k$ тривиален. Пусть тогда $x \ne x_k$. Для доказательства применим теорему Ролля. Определим вспомогательную функцию $g(t) = f(t) - L_n(t)- k \omega_n(t)$, где $k$ — коэффициент, подлежащий определению, а $x$ дано. $\forall j = \overline{0, n}:\quad g(x_j) = f(x_j) - L_n(x_j) - k \omega_n(x_j) = 0$ Для определения $k$ потребуем, чтобы $g(x)$ было равно $0$. $g(x) = f(x) - L_n(x) - k \omega_n(x) = 0$ $\omega_n(x) \ne 0$, так как $x \ne x_j$. $k = \frac{f(x) - L_n(x)}{\omega_n(x)}\quad (1)\, .$ Итак, при выбранном $k$ будет $g(x_j) = 0$, $g(x) = 0$, то есть $g$ принимает нулевые значения в $n + 2$ точках. Очевидно, из узлов и точки $x$ можно сделать $n + 1$ последовательный отрезок. На конце каждого из них $g$ принимает значение $0$. Значит, по теореме Ролля на каждом из них найдётся по корню производной. Из полученных корней можно сделать $n$ отрезков, на каждом из них по теореме Ролля найдётся по корню второй производной… В конце концов останется один отрезок, границами которого будут корни $g^{(n)}$. Тогда по теореме Ролля на этом отрезке найдётся корень $g^{(n + 1)}$. Его и обозначим за $c_x$. Подведём промежуточный итог: найдено $c_x$ такое, что $g^{(n + 1)}(c_x) = 0$. $g(t) = f(t) - L_n(t) - k \omega_n(t)$ Продифференцируем $n + 1$ раз. $\deg L_n(x) \leq n \Rightarrow L_n^{(n + 1)} = 0$. $\omega_n(t) = t^{n + 1} + \ldots \Rightarrow \omega^{(n + 1)}_n = (n + 1)!$. Таким образом, $g^{(n + 1)}(t) = f^{(n + 1)}(t) - k\cdot (n + 1)!$. Подставим $t = c_x$. $0 = g^{(n + 1)}(c_x) = f^{(n + 1)}(c_x) - k\cdot (n + 1)!$ $k = \frac{f^{(n + 1)}(c_x)}{(n + 1)!}\quad (2)\, .$ Утверждение теоремы напрямую следует из равенств $(1)$ и $(2)$ .

$\triangleleft$

Следствие

В условиях теоремы выполняется неравенство $|f(x) - L_n(x)| \leq \frac{M_{n + 1}}{(n + 1)!} (b - a)^{n + 1}$, где $M_{n + 1} = \sup\limits_{\langle a; b \rangle} |f^{(n + 1)}|.$

Оно следует из того, что для всех $x$ на $\langle a; b \rangle\,|x - x_j| \le b - a.$

Замечание

Следует понимать, что на самом деле какую бы систему узлов мы не взяли на $\langle a; b \rangle$ как по числу точек в ней, так и по характеру распределения значений, для этого промежутка всегда можно построить интерполяционный многочлен, который будет отличаться от неё сколь угодно много (нипанянтна — прим. наборщика)