От последната теорема на предната тема изникна едно логично следствие:
Ако $|f^{(n+1)}(x)| \leq M,\ \forall x \in [a,b]$, тогава
(1)От лявата страна на това неравенство стои грешката при интерполацията на функцията $f(x)$, а от дясно - нейното ограничение отгоре (на грешката, не на функцията). Нормално е да искаме тази грешка да е най-малка - ще минимизираме израза отдясно.
Екстремална задача
Да се намерят интерполационни възли $x_1 < x_2 < \dots < x_n$ в интервала $[a, b]$, такива че
(2)да е възможно най-малък.
Оказва се, че решението на тази задача се извежда чрез полиномите на Чебишов от първи род (а дали той ги е написал специално по този повод - who knows).
Полиноми на Чебишов от първи род
Дефиниция
(3)Това е полиномът на Чебишов от първи род от $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)или, иначе
(5)Надявам се да е лесно видимо за всички, че според тази формула $T_n(x)$ е полином за всяко естествено число $n$.
Св. 2 (екстремални точки)
Имайки предвид дефиницията $T_n(x) = \cos(n \arccos x), \ x \in [-1, 1]$, следното е повече от ясно:
(6)Хубаво е да се сетим, че
(7)Така определяме и екстремалните точки:
(8)на $T_n(x)$ в интервала $[-1, 1]$.
Това са всички екстремални точки, тъй като за всички цели числа $\eta_k$ описва циклично тези $n+1$ точки.
Заслужава си и да се отбележи, че
(9)И директно се проверява, че $T_n(\eta_k) = (-1)^{k}$, т.е. $|T_n(\eta_k)| = 1, \ k = 0, 1, \dots, n$
Св. 3 (нули на полинома)
(10)Така определяме нулите на $T_n(x)$:
(11)Св. 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$
Тогава
Равенството е изпълнено тогава и само тогава, когато
(13)Където $x^*_i, i=1..n$ е дефинирано в Свойство 3 на Полиномите на Чебишов.
Това е графиката на $\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)Тази линейна смяна и нейната обратна трансформират интервалите $[a,b]$ и $[-1,1]$ един в друг. Съответно грешката ще порасне ако се преместим в по-широк от текущия интервал.
така $x_k = \frac{a+b}{2} + \frac{x_k^*(b - a)}{2}$