08.2 – Tschebyscheff-Polynome

 

Die Funktionen

{T_n}\left( x \right) = \cos \left( {n\arccos x} \right),\quad x \in \left[ {-1,1} \right],\quad n = 0,1, \ldots

heißen Tschebyscheff-Polynome.

a )

Zeigen Sie, dass die Funktionen {T_n} Polynome vom Grad n sind, indem Sie folgende Rekursion beweisen:

{T_0}\left( x \right) = 1,\quad {T_1}\left( x \right) = x

{T_n}\left( x \right) = 2x{T_{n-1}}\left( x \right)-{T_{n-2}}\left( x \right)

b )

Zeigen Sie, dass {T_n}\left( 1 \right) = 1,\:\:{T_n}\left( {-1} \right) = {\left( {-1} \right)^n},\:\:\left| {{T_n}\left( x \right)} \right| \leq 1\:\:\forall x \in \left[ {-1,1} \right]

c )

Bestimmen Sie alle Stellen {\xi _k} mit \left| {{T_n}\left( {{\xi _k}} \right)} \right| = 1, sowie die Nullstellen von {T_n}

d )

Zeigen Sie, dass die Tschebyscheff-Polynome folgende Orthogonalitätseigenschaft besitzen:

\int_{-1}^1 {{T_n}\left( x \right){T_m}\left( x \right)\frac{{dx}}{{\sqrt {1-{x^2}} }}} = \left\{ {\begin{array}{*{20}{c}}{0\quad n \ne m} \\{\pi \quad n = m = 0} \\{\frac{\pi }{2}\quad n = m \ne 0} \\ \end{array} } \right.

e )

Beweisen Sie folgende Aussage:
Es sei n \in \mathbb{N} beliebig, aber fest, {x_i} mit i = 0, \ldots ,n die Nullstellen von {T_{n+1}}\left( x \right) und

{\pi _{n+1}}\left( x \right) = \prod\limits_{i = 0}^n {\left( {x-{x_i}} \right)}

Dann gilt für alle {q_{n+1}} \in {\mathbb{P}_{n+1}} mit führendem Koeffizienten 1 die Ungleichung

{\left\| {{q_{n+1}}} \right\|_{C\left[ {-1,1} \right]}} \geq {\left\| {{\pi _{n+1}}} \right\|_{C\left[ {-1,1} \right]}} = {2^{-n}}

mit Gleichheit genau dann, wenn {q_{n+1}} = {\pi _{n+1}}

f )

Warum eignen sich die Nullstellen der Tschebyscheff-Polynome besonders als Stützstellen bei der Polynominterpolation?

Lösung

a )

{T_n}\left( x \right) = \cos \left( {n\arccos x} \right)

{T_0}\left( x \right) = \cos \left( 0 \right) = 1

{T_1}\left( x \right) = \cos \left( {\arccos x} \right) = x

Additionstheorem:

\cos \left( {n\alpha } \right) = 2\cos \alpha \cos \left( {\left( {n-1} \right)\alpha } \right)-\cos \left( {\left( {n-2} \right)\alpha } \right)

{T_n}\left( x \right) = \cos \left( {n\arccos x} \right)

= 2\cos \left( {\arccos x} \right)\cos \left( {\left( {n-1} \right)\arccos x} \right)-\cos \left( {\left( {n-2} \right)\arccos x} \right)

= 2x{T_{n-1}}\left( x \right)-{T_{n-2}}\left( x \right)

Es handelt sich also tatsächlich um Polynome.

b )

{T_n}\left( 1 \right) = \cos \left( {n\arccos \left( 1 \right)} \right) = \cos \left( 0 \right) = 1

{T_n}\left( {-1} \right) = \cos \left( {n\arccos \left( {-1} \right)} \right) = \cos \left( {n\left( {2k-1} \right)\pi } \right) = {\left( {-1} \right)^n}

\left| {\cos \left( x \right)} \right| \leq 1\quad \Rightarrow \quad \left| {{T_n}\left( x \right)} \right| = \left| {\cos \left( {n\arccos \left( x \right)} \right)} \right| \leq 1

c )

Wir suchen nun die Extremstellen:

\left| {{T_n}\left( {{\xi _k}} \right)} \right| = 1

\quad \Rightarrow \quad \cos \left( {n \cdot \arccos \left( {{\xi _k}} \right)} \right) = \pm 1

\quad \Rightarrow \quad n \cdot \arccos \left( {\frac{k}{n}\pi } \right) = k\pi

\quad \Rightarrow \quad {\xi _k} = \cos \left( {\frac{k}{n}\pi } \right)

Nullstellen:

{T_n}\left( {{x_k}} \right) = 0

\quad \Rightarrow \quad \cos \left( {n \cdot \arccos \left( {{x_k}} \right)} \right) = 0

\quad \Rightarrow \quad n \cdot \arccos \left( {{x_k}} \right) = \left( {2k-1} \right)\frac{\pi }{2}

\quad \Rightarrow \quad {x_k} = \cos \left( {\frac{{2k-1}}{{2n}}\pi } \right)

d )

Substitution:

x = \cos \left( \varphi \right)\quad \Rightarrow \quad dx = -\sin \left( \varphi \right)d\varphi

{T_k}\left( x \right) = {T_k}\left( {\cos \left( \varphi \right)} \right) = \cos \left( {k \cdot \arccos \left( {\cos \left( \varphi \right)} \right)} \right) = \cos \left( {k \cdot \varphi } \right)

\quad \Rightarrow \quad \int_{-1}^1 {\frac{{{T_k}\left( x \right){T_j}\left( x \right)}}{{\sqrt {1-{x^2}} }}dx} = \int_0^\pi {\frac{{\cos \left( {k \cdot \varphi } \right)\cos \left( {j\varphi } \right)}}{{\sqrt {1-{{\cos }^2}\left( \varphi \right)} }}\sin \left( \varphi \right)d\varphi }

Es gilt:

{\sin ^2}\left( \varphi \right)+{\cos ^2}\left( \varphi \right) = 1\quad \Rightarrow \quad \sqrt {1-{{\cos }^2}\left( \varphi \right)} = \sin \left( \varphi \right)\quad \forall \varphi \in \left[ {0,\pi } \right]

Daher können wir kürzen und erhalten:

\int_{-1}^1 {\frac{{{T_k}\left( x \right){T_j}\left( x \right)}}{{\sqrt {1-{x^2}} }}dx}

= \int_0^\pi {\frac{{\cos \left( {k \cdot \varphi } \right)\cos \left( {j\varphi } \right)}}{{\sqrt {1-{{\cos }^2}\left( \varphi \right)} }}\sin \left( \varphi \right)d\varphi }

= \int_0^\pi {\cos \left( {k \cdot \varphi } \right)\cos \left( {j\varphi } \right)d\varphi }

Fallunterscheidung:

1. k \ne j:

\int_0^\pi {\cos \left( {k \cdot \varphi } \right)\cos \left( {j\varphi } \right)d\varphi } = \left[ {\frac{{\sin \left( {k-j} \right)\varphi }}{{2\left( {k-j} \right)}}+\frac{{\sin \left( {k+j} \right)\varphi }}{{2\left( {k+j} \right)}}} \right]_0^\pi = 0

2. k = j = 0:

\int_0^\pi {1d\varphi } = \pi

3. k = j \ne 0:

\int_0^\pi {{{\cos }^2}\left( {k\varphi } \right)d\varphi } = \left[ {\frac{1}{2}\varphi +\frac{1}{{4k}}\sin \left( {2k\varphi } \right)} \right]_0^\pi = \frac{\pi }{2}

e )

{\pi _{n+1}}\left( x \right) = \prod\limits_{i = 0}^n {\left( {x-{x_i}} \right)}

Zeige:

Für {q_{n+1}} \in {\mathbb{P}_{n+1}} mit führendem Koeffizienten 1 gilt:

{\left\| {{q_{n+1}}} \right\|_{C\left[ {-1,1} \right]}} \geq {\left\| {{\pi _{n+1}}} \right\|_{C\left[ {-1,1} \right]}} = {2^{-n}}

Beweis:

{\pi _{n+1}}\left( x \right) = {2^{-n}}{T_{n+1}}\left( x \right)

Dies gilt, da der führende Koeffizient von {T_{n+1}} {2^n} ist (vergleiche Rekursion).

In Aufgabe c) wurde gezeigt, dass das Maximum des Tschebyscheff-Polynoms 1 ist:

{\left\| {{T_{n+1}}} \right\|_{C\left[ {-1,1} \right]}} = 1\quad \Rightarrow \quad {\left\| {{\pi _{n+1}}} \right\|_{C\left[ {-1,1} \right]}} = {2^{-n}}

Indirekter Beweis für die Optimalität:

Sei {q_{n+1}} \in {\mathbb{P}_{n+1}} mit führendem Koeffizienten 1 und

{\left\| {{q_{n+1}}} \right\|_{C\left[ {-1,1} \right]}} < {2^{-n}} (Annahme gilt nicht, soll später auf Widerspruch führen)

Wir betrachten nun die Differenz zwischen dem {q_{n+1}} und dem {\pi _{n+1}}:

{r_n} = {\pi _{n+1}}-{q_{n+1}}

Da beide den führenden Koeffizienten 1 haben, fallen die höchsten Terme weg, die Differenz wird zu einem Polynom n-ten Grades:

{r_n} = {\pi _{n+1}}-{q_{n+1}} \in {\mathbb{P}_n}

Jetzt nutzen wir das Ergebnis von Aufgabe d). Für {\xi _k} = \cos \left( {\frac{{k\pi }}{{n+1}}} \right),\quad k = 0,1, \ldots ,n+1 gilt:

{\pi _{n+1}}\left( {{\xi _k}} \right) = {2^{-n}}{T_{n+1}}\left( {{\xi _k}} \right) = {2^{-n}}{\left( {-1} \right)^k}

Wegen der Annahme {\left\| {{q_{n+1}}} \right\|_{C\left[ {-1,1} \right]}} < {2^{-n}} gilt:

{r_n}\left( {{\xi _k}} \right)\left\{ {\begin{array}{*{20}{c}}{ > 0\quad wenn\:\:k\:\:gerade} \\{ < 0\quad wenn\:\:k\:\:ungerade} \\ \end{array} } \right.

Daraus folgt, dass {r_n}\left( x \right) mindestens ein Mal das Vorzeichen wechselt. Die Funktion hat daher mindestens eine Nullstelle. Daraus folgt, dass {r_n}\left( x \right) \equiv 0 das Nullpolynom ist (Fundamentalsatz der Algebra).

\quad \Rightarrow \quad {\pi _{n+1}}\left( x \right) = {q_{n+1}}\left( x \right)

Dies steht im Gegensatz zu

{\left\| {{q_{n+1}}} \right\|_{C\left[ {-1,1} \right]}} < {2^{-n}}

und

{\left\| {{T_{n+1}}} \right\|_{C\left[ {-1,1} \right]}} = 1\quad \Rightarrow \quad {\left\| {{\pi _{n+1}}} \right\|_{C\left[ {-1,1} \right]}} = {2^{-n}}

f )

Folgt aus e) und der Fehlerdarstellung aus Aufgabe 1 d).