Полиноми на Чебишов. Минимизиране на грешката при интерполиране

От последната теорема на предната тема изникна едно логично следствие:

Ако $|f^{(n+1)}(x)| \leq M,\ \forall x \in [a,b]$, тогава

(1)
\begin{align} |f(x) - L_n(f;x)| \leq \frac{M}{(n+1)!} |w(x)|, \ \forall x \in [a,b] \end{align}

От лявата страна на това неравенство стои грешката при интерполацията на функцията $f(x)$, а от дясно - нейното ограничение отгоре (на грешката, не на функцията). Нормално е да искаме тази грешка да е най-малка - ще минимизираме израза отдясно.

Екстремална задача

Да се намерят интерполационни възли $x_1 < x_2 < \dots < x_n$ в интервала $[a, b]$, такива че

(2)
\begin{align} \max_{x \in [a,b]} |(x - x_1)(x - x_2) \dots (x - x_n)| \end{align}

да е възможно най-малък.

Оказва се, че решението на тази задача се извежда чрез полиномите на Чебишов от първи род (а дали той ги е написал специално по този повод - who knows).

Полиноми на Чебишов от първи род

Дефиниция

(3)
\begin{align} T_n(x) = \cos(n. \arccos x),\ x \in [-1, 1] \end{align}

Това е полиномът на Чебишов от първи род от $n$-та степен1 (определен в интервала $[-1, 1]$, а не в $[a, b]$)

Свойства

Св. 1 (те са полиноми)

Д-во:
Непосредствено от дефиницията се проверява, че
$T_0 (x) = 1$ и $T_1(x) = x$, т.е при $n = 1, 2$ свойството е вярно.

Сега си припомняме една често използвана формула от четиризначните таблици, а именно:
$\cos x + \cos y = 2 \cos \frac{x - y}{2} \cos \frac{x + y}{2}$

Сега се съгласете, че според тази формула е вярно и следното:
$\cos (n+1) \theta + \cos (n-1) \theta = 2 \cos \theta \cos n \theta, \ \theta \in [0, \pi]$

Полагаме $x = \cos \theta \in [-1, 1] \Longrightarrow \theta = \arccos x \Longrightarrow T_n(x) = \cos (n \theta)$

И така получаваме и рекурентната връзка за полиномите на Чебишов:

(4)
\begin{eqnarray} T_{n+1}(x) + T_{n-1}(x) &=& \cos(n+1) \theta + \cos (n-1) \theta \\ &=& 2 \cos \theta \cos (n \theta) \\ &=& 2xT_n(x) \end{eqnarray}

или, иначе

(5)
\begin{equation} T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x) \end{equation}

Надявам се да е лесно видимо за всички, че според тази формула $T_n(x)$ е полином за всяко естествено число $n$.

Св. 2 (екстремални точки)

Имайки предвид дефиницията $T_n(x) = \cos(n \arccos x), \ x \in [-1, 1]$, следното е повече от ясно:

(6)
\begin{align} | T_n(x)| \leq 1, \ x \in [-1, 1] \end{align}

Хубаво е да се сетим, че

(7)
\begin{eqnarray} T_n(x) = \pm 1 &\iff& \cos(n. \arccos x) = \pm 1 \\ &\iff& n. \arccos x = k \pi, \ k \in \mathbb{Z} \\ &\iff& \arccos x = \frac{k\pi}{n} \\ &\iff& x = \cos \frac{k \pi}{n}, \ k = 0, 1, \dots, n \\ \end{eqnarray}

Така определяме и екстремалните точки:

(8)
\begin{align} \eta_k = \cos \frac{k \pi}{n}, \ k = 0, 1, \dots, n \end{align}

на $T_n(x)$ в интервала $[-1, 1]$.
Това са всички екстремални точки, тъй като за всички цели числа $\eta_k$ описва циклично тези $n+1$ точки.

Заслужава си и да се отбележи, че

(9)
\begin{align} 1 = \eta_1 > \eta_2 > \dots > \eta_n = -1 \end{align}

И директно се проверява, че $T_n(\eta_k) = (-1)^{k}$, т.е. $|T_n(\eta_k)| = 1, \ k = 0, 1, \dots, n$

Св. 3 (нули на полинома)

(10)
\begin{eqnarray} T_n(x) = 0 &\iff& \cos(n. \arccos x) = 0 \\ &\iff& n. \arccos x = \frac{(2k - 1)\pi}{2}, \ k \in \mathbb{Z} \\ &\iff& \arccos x = \frac{(2k - 1)\pi}{2n} \\ &\iff& x = \cos \frac{(2k - 1) \pi}{2n} \end{eqnarray}

Така определяме нулите на $T_n(x)$:

(11)
\begin{align} x^{*}_k = \cos \frac{(2k - 1) \pi}{2n}, \ k = 1, 2, \dots, n \ :\ T_n(x^{*}_k) = 0 \end{align}

Св. 4 (старши коефициент)

При $n \geq 1$ коефициентът пред $x^n$ в $T_n(x)$ е $2^{n-1}$
(т.е. $\frac{1}{2^{n-1}} T_n(x)$ е полином със старши коефициент 1).

Д-во:
От рекурентната връзка между полиномите на Чебишов се вижда, че коефициентът пред $x^n$ в $T_n(x)$ се получава като коефициента пред $x^{n-1}$ в $T_{n-1}(x)$ се умножи с 2.
И понеже при $n = 1$ знаем, че $T_1(x) = 2^0 x$, то коефициентът пред $x^n$ в $T_n(x)$ не може да е друго освен $2^{n-1}$.

Теорема (основно екстремално свойство на полиномите на Чебишов)

Нека $\omega(x) = x^n + a_1x^{n-1} + \dots + a_n$
Тогава

(12)
\begin{align} \max_{x \in [-1, 1]} |\omega(x)| \geq \max_{x \in [-1, 1]} \bigg| \frac{1}{2^{n-1}} T_n(x) \bigg| \end{align}

Равенството е изпълнено тогава и само тогава, когато

(13)
\begin{align} \omega(x) = \frac{1}{2^{n-1}} T_n(x) = (x - x^*_1)(x - x^*_2) \dots (x - x^*_n) = \tilde{\omega} (x) \end{align}

Където $x^*_i, i=1..n$ е дефинирано в Свойство 3 на Полиномите на Чебишов.

wx5.png

Това е графиката на $\tilde \omega(x)$ за $n = 5$. Както виждате тя прегражда2 $y_1 = -\frac{1}{2^{n-1}}$ и $y_2 = \frac{1}{2^{n-1}}$ точно 5 пъти.

Д-во:
Да допуснем, че съществува полином $\omega(x)$, такъв че $\max | \omega(x) | < \frac{1}{2^{n-1}}$. Тогава в интервал $[-1, 1]$, той ще остава в ивицата $( -\frac{1}{2^{n-1}}, \frac{1}{2^{n-1}} )$ по $y$. Тогава той ще пресича $\tilde\omega(x)$ поне $n$ пъти - т.е. полинома $\omega(x) - \tilde\omega(x)$ ще има поне $n$ корена. Но той е от максимум $n - 1$-ва степен (защото старшите коефициенти на $\omega(x)$ и $\tilde\omega(x)$ са еднакви (равни на 1). Следователно $\omega(x) - \tilde\omega(x)$ е нулевия полином.

За единствеността - допускаме, че съществува друг полином $\omega(x)$, който е различен от $\tilde\omega(x)$ и $\max |\omega(x)| = \frac{1}{2^{n-1}}$. Тогава $\omega(x)$ може да минава и през допирните точки на $\tilde\omega(x)$ с $y = \pm \frac{1}{2^{n-1}}$, които обаче се броят за 2 корена (един двукратен), следователно пак излиза, че разликата им има поне $n$ корена.

Извод

Когато интерполираме в интервал $[a, b] = [-1, 1]$, най-добрият избор на интерполационни възли е $x_k = x_k^* = \cos\frac{(2k-1)\pi}{2n}$.
При този избор и $f^{(n)}(x) \le M$ имаме, че $| f(x) - L_{n-1}(f;x) | \le \frac{M}{n!} \frac{1}{2^{n-1}} \quad \forall x \in [-1, 1]$.

Произволен интервал

Ако интервалът не е $[-1, 1]$, тогава може линейно да променим точките - ако $t \in [-1, 1]$ е произволна точка, която искаме да "закараме" в интервала $[a, b]$ използваме формулата:

(14)
\begin{align} x = \frac{a+b}{2} + \frac{t(b - a)}{2} \end{align}

Тази линейна смяна и нейната обратна трансформират интервалите $[a,b]$ и $[-1,1]$ един в друг. Съответно грешката ще порасне ако се преместим в по-широк от текущия интервал.
така $x_k = \frac{a+b}{2} + \frac{x_k^*(b - a)}{2}$

(15)
\begin{eqnarray} \max_{x \in [a, b]} |\omega(x)| &=& \left(\frac{b-a}{2}\right)^n \max |(t-t_1)(t-t_2)\cdots(t-t_n)| \\ &\ge& \left(\frac{b-a}{2}\right)^n \frac{1}{2^{n-1}} \end{eqnarray}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License