Многочлен Чебышева
Содержание
Введение
Возможно всё было так: Чебышёв нашёл крутой многочлен n-ой степени: $T_n = cos(n \cdot arccos(x))$
Назвали его многочленом Чебышева. Выглядит как не многочлен, но это именно он. Немного подумав можно прийти к такому выводу:
$$\cos((n+1) \cdot \arccos(x)) = 2 \cdot \cos(\arccos(x)) \cdot \cos(n \cdot \arccos(x)) - \cos((n-1) \cdot \arccos(x))$$
$$\cos((n+1) \cdot \arccos(x)) = 2 \cdot x \cdot \cos(n \cdot \arccos(x)) - \cos((n-1) \cdot \arccos(x))$$
$$T_{n+1} = 2 \cdot x \cdot T_n - T_{n-1}$$
Всё равно не похоже на многочлен…
Воспользуемся этой формулой в явном виде:
$$T_0 = \cos(0 \cdot \arccos(x)) = 1$$
$$T_1 = \cos(1 \cdot \arccos(x)) = x$$
$$T_2 = 2 \cdot x \cdot T_1 - T_0 = 2x^2 - 1$$
$$T_3 = 2 \cdot x \cdot T_2 - T_1 = 4x^3 - 3x$$
$$T_4 = 2 \cdot x \cdot T_3 - T_2 = 8x^4 - 8x^2 + 1$$
$$T_5 = 2 \cdot x \cdot T_4 - T_3 = 16x^5 - 20x^3 + 5x$$
$$…$$
Теперь видно, что именно многочлены. Проверьте, например так:
$$T_5(3.2) = \cos(5 \cdot \arccos(3.2)) = 4729.35…$$
$$T_5(3.2) = 16 \cdot (3.2)^5 - 20 \cdot (3.2)^3 + 5 \cdot (3.2) = 4729.35…$$
Зачем всё это? Есть очень крутая особенность у этих многочленов:
На промежутке [-1, 1]: $\max_{[-1, 1]}(T_n) = 1$, $\min_{[-1, 1]}(T_n) = -1$
Старший коэф. перед $x^n$ равен $2^{(n-1)}$
Давайте нормализируем многочлен:
Пусть $T^*_n = \frac{T_n}{2^{(n-1)} }$
Зачем нужен $T^*_n$? У него есть ещё более крутые особенности:
На промежутке [-1, 1]: $\max_{[-1, 1]}(T^n) = \frac{1}{ 2^{(n-1)} }$, $\min{[-1, 1]}(T^_n) = -\frac{1}{ 2^{(n-1)} }$
Старший коэф. перед $x^n$ равен 1
1-ая особенность особенно значимая
Узлы Чебышёва
Теперь нужно найти корни этого многочлена:
$$T^*_n = 0$$
$$\frac{\cos(n \cdot \arccos(x))}{2^{(n-1)}} = 0$$
$$\cos(n \cdot \arccos(x)) = 0$$
$$n \cdot \arccos(x) = \frac{\pi}{2} + \pi \cdot k$$
$$\arccos(x) = \frac{\pi}{2 \cdot n} + \frac{\pi \cdot k}{n}$$
$$x = \cos(\frac{pi}{2 \cdot n} + \frac{\pi \cdot k}{n})$$
$$x_k = \cos( \frac{ (2 \cdot k + 1) \cdot \pi }{2 \cdot n} )$$, k = 0, 1, 2, …, n-1
Замечу: Тут именно от 0 до n-1. Т. е. кол-во узлов = n шт
Т. е. $T^*_n = \frac{1}{2^{(n-1)}} \cdot (x-x_0) \cdot (x-x_1) \cdot …$
Находим на отрезке от [-1, 1] узлы $x_k$:
$$x_1 = \cos( \frac{ (2 \cdot 0 + 1) \cdot \pi }{2 \cdot n} )$$
$$x_2 = \cos( \frac{ (2 \cdot 1 + 1) \cdot \pi }{2 \cdot n} )$$
$$…$$
И этим иксам [$x_1$, $x_2$, …] соответствуют игреки [$y_1=f(x_1)$, $y_2=f(x_2)$, …]. Всё, можно интерполировать
Почему именно так? Помните оценку погрешности интерполяционных многочленов?
Оценка погрешности
$\max_{[-1, 1]}(|f(x)-L_n(x)|) \leq \frac{M_{n+1}} {(n+1)!} \cdot \max_{[-1,1]}(|\omega_n(x)|)$, где $M_{n+1}=\max_{[-1,1]}(\frac{d^{(n+1)}f}{dx^{(n+1)}})$
То есть производная (n+1)-го порядка $f^{(n+1)}_x$
Что такое $\omega_n$? Это и есть $T^*_{n+1}$
Помните его max и min из особенности 1? $\max_{[-1,1]}(|\omega_n|) = \max_{[-1,1]}(|T^*_{n+1}|) = \frac{1}{ 2^n }$. Т. е. оооооочень маленькое число уже хотя бы при n=5
Т.е. $$\max_{[-1, 1]}{(|f(x)-L_n(x)|)} \leq \frac{M_{n+1}}{(n+1)!} \cdot \frac{1}{2^n}$$
Но это ведь на отрезке [-1, 1]. Кому это нужно? Ну перенесём на наш отрезок [a, b] (аффинное преобразование):
$$x_k = \frac{1}{2} \cdot ((b-a) \cdot \cos( \frac{(2 \cdot k + 1) \cdot \pi}{2 \cdot n + 2} ) + b + a)$$, k = 0, 1, …, n
Вывод этой формулы - это путь ниндзя, и поэтому каждый его должен пройти сам, если, конечно, есть желание…
$$T^*_n = \frac{1}{2^{n-1}} \cdot (x-x_0) \cdot (x-x_1) \cdot …$$
А что там с погрешностью? Это тоже путь ниндзя, но вот формула:
$$\max_{[a,b]}(|w_n(x)|) = \frac{(b-a)^{(n+1)}}{2^{(2 \cdot n+1)}}$$
$$\max_{[a, b]}(|f(x)-L_n(x)|) \leq \frac{M_{n+1}}{(n+1)!} \cdot \frac{(b-a)^{(n+1)}}{2^{(2 \cdot n+1)}}$$
где $$M_{n+1}=\max_{[a,b]}(\frac{d^{(n+1)}f}{dx^{(n+1)}})$$
Главное помнить, что n - это степень многочлена, а не количество узлов
Код
Что мы хотим вообще? Хотим функцию findChebyshevNodes(), которая бы просто вернула “массив” правильных “иксов”. Код будет на matlab, как бы сильно не хотелось обратного:
% a - левая граница
% b - правая граница
% n - кол-во "иксов" (узлов)
function res = findChebyshevNodes(a, b, n)
n = n-1; % потому что в формуле используется степень многочлена, которая на 1 меньше кол-ва узлов
res = zeros(1, n+1);
for i = 1:(n+1)
res(i) = (1/2)*((b-a)*cos( ((2*(i-1)+1)*pi)/(2*n+2) ) + b + a);
end
и заодно высчитать максимальную погрешность:
%max[a, b](|f(x)-L_n(x)|) <= (M_{n+1} / (n+1)!)*( (b-a)^(n+1) / (2^(2*n+1)) ), где M_{n+1}=max[a,b](d^(n+1)f/dx^(n+1))
%Здесь n - это степень многочлена, а не кол-во точек (их на 1 больше)
function res = findChebyshevDefect(n_dots)
n = n_dots;
a = 1;
b = 71;
res = ((здесь M_{n+1}) / factorial(n))*( (b-a)^n / (2^(2*n-1)) );
Дальше, зная “иксы”=X, найдём “игреки”=Y и подставим в какую-нибудь фукцию, которая делает интерполяцию.
14 Апреля, 2021 г.