Интерполационна задача на Лагранж. Представяне на грешката

Нека върху реалната права имаме поредица от точки $x_0 < x_1 < \cdots < x_n$. Нека също имаме поредицата $y_0, y_1, ... , y_n$ от реални или комплексни числа.
Поредицата $x_i$ наричаме интерполационни възли.

Интерполационна задача на Лагранж

Да се намери $P(x) \in \pi_n$ (алгебричен полином от ред не по-голям от $n$), такъв че $P(x_i) = y_i$ за $i \in 0, 1, ... , n$.
Съществува ли такъв, и ако да — единствен ли е?

Твърдение

При зададени $x_i$ и $y_i$, съществува единствен полином, който е решение на интерполационната задача на Лагранж.

Д-во:
Нека полиномът е от вида $P(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$.
Изискването от задачата на Лагранж представлява линейна система с $n + 1$ уравнения и $n + 1$ неизвестни. Тази система има единствено решение, тогава и само тогава, когато рангът на матрицата
$$\left( \begin{array}{ccccc} 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{array} \right)$$
е максимален, което означава, че детерминантата на матрицата ще е различна от нула. В конкретния случай, получаваме детерминантата на Вандермонд
$$\det = \prod\limits_{0 \le i < j \le n } (x_i - x_j),$$за която е известно, че е различна от нула при $x_i \ne x_j$, $i \ne j$. С това твърдението е доказано.

Построяване на полинома

Доказано е, ама ние сме нагли и искаме да получим самия полином. За целта първо решаваме специалната интерполационна задача на Лагранж:
Нека $k \in \{0, 1, ... , n\}$. Търсим алгебричен полином $l_k(x) \in \pi_n$, такъв че
$l_k(x_i) = \begin{cases} 0, \quad i \in \{0, 1, ... , n\} \setminus \{k\} \\ 1, \quad i = k \end{cases}$

Ако имаме такива помощни полиномчета, то полиномът на Лагранж се получава лесно.
Обозначаваме решението на интерполационната задача с $L_n(f;x)$1. Наричаме го интерполационен полином на $f$.
$L_n(f;x) = \underset{k = 0}{\overset{n}{\sum}} l_k(x)f(x_k)$
(Директно се проверява, че горното удовлетворява условията, а сме доказали, че има само един такъв полином.)

Да получим общия вид:
$l_k(x) = c(x - x_0)(x - x_1) \dots (x - x_{k-1})(x - x_{k+1}) \dots (x - x_n)$
$l_k(x_k) = 1 = c\underset{i = 0, i \ne k}{\overset{n}{\prod}} (x_k - x_i) \Rightarrow c = \cfrac{1}{\underset{i = 0, i \ne k}{\overset{n}{\prod}} (x_k - x_i)}$

Следователно
$l_k(x) = \underset{i = 0, i \ne k}{\overset{n}{\prod}}\cfrac{x - x_i}{x_k - x_i}$

Да направим още две означения:
$\omega(x) = (x - x_0)(x - x_1)\dots(x - x_n)$
$\omega_k(x) = \cfrac{\omega(x)}{x - x_k}$

Тогава са верни следните:
$l_k(x) = \cfrac{\omega_k(x)}{\omega_k(x_k)}$
$\omega_k(x_k) = \omega'(x_k) , \ k \in \{0, 1, ..., n\}$

Второто може да се обясни по два начина:

  • $\omega_k(x_k) = \underset{x \to k}{\lim} \cfrac{\omega(x)}{x - x_k} \overset{L'hopital}{=} \underset{x \to x_k}{\lim} \cfrac{\omega'(x)}{1} = \omega'(x_k)$
  • $\omega_k(x_k) = \underset{x \to k}{\lim} \cfrac{\omega(x)}{x - x_k} = \underset{x \to k}{\lim} \cfrac{\omega(x) - \omega(x_k)}{x - x_k} \overset{definition}{=} \omega'(x_k)$2

Полиномите $l_k(x)$ ще наричаме базисни полиноми на Лагранж. Тези полиноми образуват базис (умопомрачително, нали?).
И след всичките тези прелюдии:

Решението на (неспециалната) интерполационна задача на Лагранж е $\underset{k = 0}{\overset{n}{\sum}}l_k(x)y_k$.

Да се убедим: Полагаме $x = x_i$ за $i \in \{0, 1, ..., n\}$.
$P(x_i) = \displaystyle \sum_{k = 0}^n l_k(x_i)(y_k) = l_i(x_i)y_i = y_i$3

Твърдение (Следствие от единствеността)

От единствеността на решението на интерполационната задача на Лагранж непосредствено следва, че:
Ако $f(x) \in \pi_n$, то $L_n(f;x) \equiv f(x)$.

Доказателство 1:
$f(x)$ е полином от n-та степен.
$L_n(f;x)$ също е полином от n-та степен.
И двата полинома имат една и съща стойност в n+1 точки.
Сега да образуваме тяхната разлика $p(x) = f(x) - L_n(f;x)$. Очевидно $p(x) \in \pi_n$, защото е разлика на два полинома от $n$та степен и освен това има $n+1$ различни точки, в които се нулира. Сега използваме основната теорема на алгебрата, именно че полином от $n$та степен има точно $n$ корена (може да има многократни корени, но никога повече от $n$ различни), от където заключваме, че $p(x)$ може да е единствено константата нула. Следователно $f(x) \equiv L_n(f;x)$.

Доказателство 2:
Ако $f(x)$ е полином от n-та степен, то той удовлетворява условието да бъде собственото си решение на интерполационната задача на Лагранж. Доказахме вече, че тя има само едно решение. Следователно, $f(x)$ е равно на собствения си полином на Лагранж.

Tеорема (грешка при интерполация по Лагранж)

Нека $a \le x_0 < x_1 < \dots < x_n \le b$ и $f \in C^{n+1}[a, b]$4. Тогава за всяко $x \in [a, b]$ съществува точка $\xi \in [a, b]$, такава че
$f(x) - L_n(f; x) = \cfrac{f^{(n+1)}(\xi)} {(n+1)!}\omega(x)$

Д-во:
Очевидно формулата е вярна при $x=x_i$, защото тогава двете страни са равни на нула, затова да предположим, че $x\ne x_i\quad\forall\ i$. Основната стъпка при доказателството на тази-иначе-очевидна теорема е образуването на следната помощна функция:

(1)
\begin{align} F(t) = f(t) - L_n(f;t) - c \omega(t) \end{align}

където $c$ е параметър.

Забелязваме, че в точките $x_0, x_1, \dots, x_n$ нашата функция се анулира при каквато и да е стойност на $c$.
$F(x_k) = f(x_k) - L_n(f; x_k) - c 0 = f(x_k) - f(x_k) = 0, \ k = 0, 1, \dots, n$

Сега идеята е да си изберем такава стойност на параметъра $c$, че $F(t) = 0$ и за точката $t = x$:

(2)
\begin{align} 0 = F(x) = f(x) - L_n(f; x) - c \omega(x) \Longrightarrow c = \frac{f(x) - L_n(f; x)}{\omega(x)} \ (\star) \end{align}

До тук имаме, че нашата функция $F(t)$ си има $n+2$ различни нули (понеже $F(t) = 0, \ t = x, x_0, x_1, \dots, x_n$)
По теоремата на Рол (от Анализ 1) следва, че $F'(t)$ ще има поне $n+1$ нули в инервала $(a, b)$ (тук разглеждаме условията за теоремата м/у две последователни нули на $F(t)$)

Аналогично $F''(t)$ ще има поне $n$ нули.
Така, след $n+1$ стъпки, ще раберем, че $F^{(n+1)} (t)$ ще има поне една нула в интервала $(a,b)$.
Означаваме тази нула с $\xi \in (a,b)$ и за нея знаем, че

(3)
\begin{align} 0 = F^{(n+1)} (\xi) = f^{(n+1)} (\xi) - 0 - c(n+1)! \Longrightarrow c = \frac{f^{(n+1)} (\xi)}{(n+1)!} \end{align}

От $(\star)$, след приравняване на двата израза които получихме за параметъра $c$ и малко разместаване получаваме исканото:

(4)
\begin{align} f(x) - L_n(f; x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \omega(x) \quad \Box \end{align}

Следствие (оценка на грешката)

Ако за $\forall x \in [a,b], \ |f^{(n+1)}(x)| \le M$, където $M$ е някаква константа, тогава
$|f(x)-L_n(f;x)| \le \cfrac{M}{(n+1)!}|\omega(x)| \quad \forall x \in [a,b]$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License