next up previous
Next: Aproximace metodou nejmenších čtverců Up: Čebyševovy aproximace Previous: Čebyševova úloha

Čebyševovy polynomy

Aproximace Čebyševovými polynomy se lehce konstruuje a je téměř tak přesná jako nejlepší stejnoměrná aproximace. Často se používá pro výpočet funkcí.

Pro interpolaci Čebyševovými polynomy se libovolný interval lineárně transformuje na interval $\langle -1, 1 \rangle$ Každému $t \in \langle a, b \rangle$ přiřadíme hodnotu $x \in \langle -1, 1 \rangle$ funkčním předpisem

\begin{displaymath}
x = \frac{t - \frac{1}{2}\; (a+b) }{b - a}\ \ .
\end{displaymath}

Čebyševův polynom lze psát ve tvaru

\begin{displaymath}
T_n(x) = \cos(n \arccos x)
\end{displaymath}

Polynomy 0-tého a 1-ního stupně jsou tedy $T_0(x) = 1$ a $T_1(x) = x$. Čebyševův polynom $n+1$-tého stupně lze též vyjádřit pomocí rekurentního vztahu

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

Pomocí rekurentního vztahu lze odvodit tvar dalších Čebyševových polynomů

$\displaystyle T_2(x)$ $\textstyle =$ $\displaystyle 2x^2 - 1,$  
$\displaystyle T_3(x)$ $\textstyle =$ $\displaystyle 4x^3 - 3x,$  
$\displaystyle T_4(x)$ $\textstyle =$ $\displaystyle 8x^4 - 8x^2 + 1 \ \ .$  

Kořeny a extrémy Čebyševův polynom $T_n(x)$$n$ kořenů v intervalu $\langle -1, 1 \rangle$ v bodech

\begin{displaymath}
x = \cos \left( \frac{\pi \; (k~- \frac{1}{2})}{n} \right)\ \qquad
k=1,2,\dots,n
\end{displaymath}

V intervalu $\langle -1, 1 \rangle$$n+1$ extrémů $\vert T_n(x)\vert = 1$ v bodech $x = \cos \left( k\, \pi / n\right)$, kde $k = 0,1,\dots,n$.

Ortogonalita
Čebyševovy polynomy jsou ortogonální polynomy s vahou $\frac{1}{\sqrt{1-x^2}}$ na intervalu $\langle -1, 1 \rangle$

\begin{displaymath}
\int \limits_{-1}^{1} \frac{T_i(x) T_j(x)}{\sqrt{1-x^2}} dx ...
...c{\pi}{2} & i=j \not= 0 \\
\pi & i = j = 0
\end{array}\right.
\end{displaymath}

Diskrétní ortogonalita
Nechť $x_k$, $k = 1, \dots, m$ jsou kořeny Čebyševova polynomu $T_m (x)$. Pak pro $\forall i,j < m$ platí

\begin{displaymath}
\sum_{k=1}^m T_i(x_k) T_j(x_k) = \left\{
\begin{array}{ll}
0...
...\frac{m}{2} & i = j \not= 0 \\
m & i=j=0
\end{array}\right.
.
\end{displaymath}

Aproximace Čebyševovými polynomy
Funkci $f(x)$ aproximujeme

$\displaystyle f(x) \approx T(x)$ $\textstyle =$ $\displaystyle \frac{1}{2} c_0 + \sum_{j=1}^{N-1} c_j T_j(x)\ \ ,$  
$\displaystyle {\rm kde} \qquad
c_j$ $\textstyle =$ $\displaystyle \frac{2}{N} \sum_{k=1}^{N} f \left[ \cos \left( \frac{\pi
(k~-\fr...
...{2})}{N} \right) \right] \cos \left( \frac{\pi j (k~-
\frac{1}{2})}{N} \right).$  

Hodnoty funkce $f(x)$ jsou rovny hodnotám funkce $T(x)$ ve všech $N$ nulových bodech polynomu $T_N(x)$.

Výpočet funkce pomocí Čebyševových polynomů
Často volíme pro výpočet koeficientů relativně vysoký řád aproximace $N \simeq 30 - 50$ (procedura CHEBFT v knihovně Numerical Recipies). Koeficienty Čebyševova rozvoje jdou obvykle $\rightarrow 0$ relativně rychle. Vysoké $N$ dovoluje přesně stanovit počet členů potřebných pro výpočet funkce se zadanou přesností $\varepsilon$. Pokud je $\sum_{k=m}^N \vert c_k\vert < \varepsilon$, potom pro výpočet funkce stačí použít prvních $m$ členů rozvoje (procedura CHEBEV v knihovně Numerical Recipies).

Pozn. Počítání Lagrangeova polynomu s body danými nulovými body Čebyševova polynomu je možné, ale pro $N > 8$ je méně přesné a obtížnější.

Pozn. Procedura CHEBEV používá pro sumu funkcí zadaných rekurentně používá Clenshawovy formule.
Pokud je řada funkcí dána rekurentně

\begin{displaymath}
F_{n+1}(x) = \alpha (n, x)\; F_n(x) + \beta (n, x)\; F_{n-1}(x)
\end{displaymath}

pak lze sumu

\begin{displaymath}
f(x) = \sum_{k=0}^N c_k F_k(x)
\end{displaymath}

počítat tak, že postupně provádíme
$\displaystyle y_{N+2}$ $\textstyle =$ $\displaystyle 0 \ \ , \qquad y_{N+1} = 0$  
$\displaystyle y_k$ $\textstyle =$ $\displaystyle \alpha(k,x) y_{k+1} + \beta(k+1, x) y_{k+2} + c_k\ \ , \qquad
k=N, N-1, \dots, 1$  
$\displaystyle f(x)$ $\textstyle =$ $\displaystyle \beta (1,x) F_0(x) y_2 + F_1(x) y_1 + F_0(x) c_0\ \ .$  

Clenshawova formule nemusí být vhodná pro $\forall$ řady (může vést i ke katastrofální ztrátě přesnosti).

Integrál a derivace pomocí Čebyševových polynomů
Koeficienty $C_i$ Čebyševova rozvoje integrálu funkce $f(x)$ jsou dány

\begin{displaymath}
C_i = \frac{c_{i-1} - c_{i+1}}{2i}\ \ , \qquad {\rm kde}\ \; i > 0\ \ .
\end{displaymath}

kde $c_i$ jsou koeficienty Čebyševova rozvoje funkce $f(x)$.
Pro derivaci funkce $f(x)$ platí vzorec

\begin{displaymath}
c'_{i-1} = c'_{i+1} + 2ic_i\ \ , \qquad {\rm kde}\ \; i = n-2, \dots, 1\ \ .
\end{displaymath}


next up previous
Next: Aproximace metodou nejmenších čtverců Up: Čebyševovy aproximace Previous: Čebyševova úloha
Jiri Limpouch
2000-03-24