LGS mit Vandermondematrix - wozu?

26.04.2011, 18:49	Erlkoenig	Auf diesen Beitrag antworten »
LGS mit Vandermondematrix - wozu? Liebe Leser, für ein Seminar soll ich einen speziellen Algorithmus zur Lösung von LGS der Form $\begin{eqnarray} V^Ty=b \end{eqnarray}$ erläutern, wobei $\begin{eqnarray} V \end{eqnarray}$ die Vandermonde-Matrix ist, gegeben durch: $\begin{eqnarray} V=\begin{pmatrix} 1 & 1 & \dots & 1 \\<br /> x_0 & x_1 & \dots & x_n \\<br /> x_0^2 & x_1^2 & \dots & x_n^2 \\<br /> \vdots & \vdots & \vdots & \vdots \\<br /> x_0^n & x_1^n & \dots & x_n^n<br /> \end{pmatrix} \in \mathbb{R}^{n+1,n+1} \end{eqnarray}$ . Damit kann man dann ein Polynom interpolieren, indem man für $\begin{eqnarray} x_{0 \dots n} \end{eqnarray}$ die Stützstellen einsetzt, und für $\begin{eqnarray} b_{0 \dots n} \end{eqnarray}$ die Werte an den Stützstellen. Allerdings gibt es da noch einen Algorithmus, mit dem man LGS der Form $\begin{eqnarray} Vy=b \end{eqnarray}$ lösen kann, aber mir ist nicht gelungen herauszufinden, was das bringt. Beides gesehen im Buch Gene H. Golub, Charles F. Van Loan - Matrix computations, ab Seite 183. Kann mir jemand ein Stichwort liefern, wozu das gut ist und idealerweise, wo ich es nachlesen kann? Vielen Dank im Voraus!
26.04.2011, 20:22	tigerbine	Auf diesen Beitrag antworten »
RE: LGS mit Vandermondematrix - wozu? Würde weitergehen ins Kapitel FFT und mir die Gestalt der dortigen Matrix anschauen. Da stehen in den Zeilen immer die gleichen Potenzen von Einheitswurzeln. Wie in V. Mehr weiß ich dazu aber auch nicht.
28.04.2011, 09:20	Erlkoenig	Auf diesen Beitrag antworten »
Hm, eigentlich ist der FFT-Algorithmus "abgeschlossen", wüsste jetzt nicht wo man da das V braucht - außerdem enthält V reelle Zahlen, und die Matrix für die FFT besteht aus komplexen Zahlen, und die FFT läuft in O(n log n), und dieser Algorithmus für die Vandermonde-Matrix in O(n^2), also scheint mir dessen Einsatz an dieser Stelle nicht allzu sinnvoll...
28.04.2011, 12:16	tigerbine	Auf diesen Beitrag antworten »
Mehr kann ich dir leider nicht sagen. Mir ist Vandermonde nur bei der Polynominterpolation begegnet und selbst da eher als theoretisches Objekt [Determinante, reguläres LGS]. Wenn mir noch was begegnet, poste ich es. Würdest du dich nach dem Seminar melden?
28.04.2011, 14:44	Erlkoenig	Auf diesen Beitrag antworten »
Ich habe mittlerweile herausgefunden, dass diese Art Algorithmus "Pereyra-Björck-Algorithmus" heißt, und das Problem $\begin{eqnarray} Vx=b \end{eqnarray*}$ "appears naturally and has to be solved, in many applications. Some important examples are interpolation, construction of spline functions, approximation of linear functionals, etc." [1]. Wie man nun damit etwas interpoliert, weiß wohl niemand so genau. 1: Ake Björck; Victor Pereyra - Solution of Vandermonde systems of equations

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »