Orthonormale Polynome - Beweis der Drei-Term-Rekursion (vollständige Induktion)

02.08.2009, 17:30

HMSteinbach

Orthonormale Polynome - Beweis der Drei-Term-Rekursion (vollständige Induktion)

Hallo, liebes Forum,
als Neumitglied hoffe ich hier auf einen Lösungshinweis zu folgendem Problem:
Es geht um Datenreduktion / Ausgleichungsrechnung mittels orthonormaler Polynome. In dem Buch "Statistische und numerische Methoden der Datenanalyse" von Blobel/Lohrmann findet man hierzu eine Dreiterm-Rekursion der Form
$\begin{eqnarray*} \gamma_{j}\,\phi_{j}\,(x) \;=\; (\,x\,-\,\alpha_{j}\,)\,\phi_{j-1}\,(x)\;-\;\beta_{j}\,\phi_{j-2}\,(x) \end{eqnarray*}$
wobei
$\begin{eqnarray*} \phi_0(x)\,=\,b_{00} \end{eqnarray*}$
und
$\begin{eqnarray*} \phi_1(x)\,=\,b_{10}\,+\,b_{11}\cdot x \end{eqnarray*}$

Der Induktionsanfang für den Beweis mittels vollständiger Induktion ist klar. Beim Induktionsschritt jedoch schreiben die Autoren, daß man den nächsthöheren Polynomterm zunächst in der Form
$\begin{eqnarray*} \gamma_{j+1}\,\phi_{j+1}\,(x) \;=\; (\,x\,-\,\alpha_{j+1}\,)\,\phi_{j}\,(x)\;+\;\sum_{k=0}^{j-1}\,c_{j+1,k}\,\phi_k(x) \end{eqnarray*}$
darstellt und dann zeigt, daß sämtliche c_j+1,k} für k=0...(j-2) verschwinden und nur c_j+1,j-1 = -ß übrig bleibt.

Und hier stehe ich auf dem Schlauch und komme nicht weiter böse

. Meine Frage ist jetzt: wie kann man das zeigen ? Hat jemand eine Idee hierzu ?
Über eine Antwort würde ich mich sehr freuen,
vielen Dank im voraus,
HMSteinbach

02.08.2009, 19:16

Abakus

Auf diesen Beitrag antworten »

RE: Orthonormale Polynome - Beweis der Drei-Term-Rekursion (vollständige Induktion)

Zitat:

Original von HMSteinbach
Der Induktionsanfang für den Beweis mittels vollständiger Induktion ist klar. Beim Induktionsschritt jedoch schreiben die Autoren, daß man den nächsthöheren Polynomterm zunächst in der Form
$\begin{eqnarray*} \gamma_{j+1}\,\phi_{j+1}\,(x) \;=\; (\,x\,-\,\alpha_{j+1}\,)\,\phi_{j}\,(x)\;+\;\sum_{k=0}^{j-1}\,c_{j+1,k}\,\phi_k(x) \end{eqnarray*}$
darstellt und dann zeigt, daß sämtliche c_j+1,k} für k=0...(j-2) verschwinden und nur c_j+1,j-1 = -ß übrig bleibt.

Willkommen im Forum, HMSteinbach Wink

Die Darstellung funktioniert, weil die anderen Polynome eine Basis für den VR der Polynome bis zum Grad (j + 1) aufspannen, denke ich. Die Details für dieses Argument musst du natürlich dann noch genauer fassen, also wieso die Koeffizienten so gewählt werden können.

Wieso jetzt nur 2 Koeffizienten nicht verschwinden, kann nur an der IV und der Orthogonalität liegen. Dazu müsste man sich das zugrunde liegende Skalarprodukt anschauen (wie ist das definiert?), was ist genau die IV und wie lässt sich das einbringen?

Grüße Abakus smile

03.08.2009, 22:25

HMSteinbach

Auf diesen Beitrag antworten »

RE: Orthonormale Polynome - Beweis der Drei-Term-Rekursion (vollständige Induktion)
Hallo, Abakus,
vielen Dank für die Hinweise, die ganz plausibel klingen. Ich glaube aber, daß mein Verständnis da noch etwas hakt. Ich werde Morgen hierzu noch etwas schreiben, heute bin ich zu müd' (gähn).
Nochmals vielen Dank
HMSteinbach

04.08.2009, 04:57

WebFritzi

Auf diesen Beitrag antworten »

Vielleicht solltest du auch sagen, was überhaupt zu zeigen ist.

12.08.2009, 22:26

HMSteinbach

Auf diesen Beitrag antworten »

So, mit etwas Verspätung bin ich wieder da.
@WebFritzi: Zu zeigen ist die Gültigkeit der oben angeführten Drei-Term-Rekursion für die Entwicklung orthonormaler Polynome. Abakus hat ja schon darauf hingewiesen, daß durch die beiden Terme der rechten Seite der Vektorraum der Polynome bis zum Grad (j+1) aufgespannt wird. Das kann ich auch alles nachvollziehen, jedoch hakt es an folgender Stelle: Für den Induktionsschritt wird die Aussage hinzugezogen, daß( Gleichung A)

$\begin{eqnarray*} \gamma_{j+1}\,\phi_{j+1}(x)\,=\,(\, x \, -\, \alpha_{j+1}\,)\,\phi_{j}(x) \,+\,\sum_{k=0}^{j-1}\,c_{j+1,k}\,\phi_{k}(x) \end{eqnarray*}$

Dabei soll gezeigt werden, daß die

$\begin{eqnarray*} c_{j+1,k} \,=\, 0 \; {\rm fuer} \; k\,=\, 0\, \dots \, j-2 \end{eqnarray*}$

und somit nur der Term mit dem Polynom vom Grad "j-1" übrig bleibt.

Hierzu soll wird für jedes k = 0... (j-1) die obige Gleichung A für jedes x_i mit dem Term w_i Phi_k(x_i) multipliziert und über alle i Gleichungen summiert. Das ist auch richtig, da hier die zugrundegelegte Orthonormalitätsbedingung

$\begin{eqnarray*} \sum _{i=1}^n w_i\,\phi_k(x_i)\,\phi_l(x_i) \; = \; 0 \quad {\rm fuer} \;k\,\neq\,l \quad {\rm bzw.}\quad 1\quad {\rm fuer} \;k\,=\,l \end{eqnarray*}$

ausgenutzt wird und die Terme mit "\gamma_{j+1}" und "alpha_{j+1}"
in Gleichung A verschwinden. Für "k=j-1" paßt auch noch alles bestens,
jedoch für "k=0...j-2" bleiben doch immer die beiden Summanden

$\begin{eqnarray*} \sum_{i=1}^n\,w_i\,x_i\,\phi_j(x_i)\,\phi_{k}(x_i) \quad=\quad c_{j+1,k} \end{eqnarray*}$
übrig. Wenn die c_{j+1,k} Null sein sollen, muß die Produktsumme auf der linken Seite verschwinden - aber da stört mich der x-Term. Wie kann man zeigen, daß die linke Seite Null ist - oder bin ich hier auf dem Holzweg Hammer

?

Ich hoffe, mein Problem einigermaßen verständlich dargelegt zu haben. Auch wenn ich den Inhalt der Drei-term-Rekursion nicht anzweifle ( im Gegenteil: sie funktioniert in der Anwendung hervorragend), so möchte ich doch zumindest den beweis auf die Reihe bekommen. Über eine weitere Anregung würde ich mich sehr freuen,

HMSteinbach

Neue Frage »

Antworten »

Orthonormale Polynome - Beweis der Drei-Term-Rekursion (vollständige Induktion)

Verwandte Themen