WikiDer > Vandermonde-Matrix

In dem Lineare Algebra, eine Unterregion der Mathematik, ist ein Vandermonde-Matrix, benannt nach dem französischen Mathematiker des 18. Jahrhunderts Alexandre-Theophile Vandermonde, ein Matrix mit der Bedingung, dass jede Zeile in dieser Matrix aus a geometrische Folge muss existieren, d. h. a ${displaystyle mimen n}$-Matrix der Form:

${displaystyle V={ egin{bmatrix}1&alpha _{1}&alpha _{1}^{2}&dots &alpha _{1}^{n-1}/1&alpha _{2}&alpha _{2}^{2} &dots &alpha _{2}^{n-1}/1&alpha _{3}&alpha _{3}^{2}&dots &alpha _{3}^{n-1}/vdots &vdots &vdots &ddots &vdots /1&alpha _{m }&alpha _{m}^{2}&Punkte &alpha _{m}^{n-1}/end{bmatrix}}}$

oder

${Displaystil V_{i,j}=alpha_{i}^{j-1}}$

für alle Indizes ${Anzeigestil i}$ und ${Anzeigestil j}$.^[1] Einige Autoren verwenden die transponiert der obigen Matrix.

Eine Vandermonde-Matrix wird also vollständig durch die Zahlen bestimmt ${displaystyle alpha _{i}(i=1,2,ldots,n).}$

polynomielle Auswertung

Die Vandermonde-Matrix wird bei der Auswertung von a . diskutiert Polynom

${Anzeigestil v(x)=Summe _{i=0}^{n}v_{i}x^{i}}$

in mehreren Punkten ${displaystyle x_{0},x_{1},dots ,x_{m}}$.

Durch die Vandermonde-Matrix

${displaystyle V={ egin{bmatrix}1&x_{0}&x_{0}^{2}&dots &x_{0}^{n}/1&x_{1}&x_{1}^{2}&dots &x_{1}^{ n}/vdots &vdots &vdots &ddots &vdots /1&x_{m}&x_{m}^{2}&dots &x_{m}^{n}/end{bmatrix}}}$

zu multiplizieren mit dem Vektor

${displaystyle v=(v_{0},v_{1},Punkte,v_{n})}$

erhält man den Vektor mit den zu berechnenden Werten:

${Anzeigestil V,v=(v(x_{0}),v(x_{1}),ldots ,v(x_{m}))}$

Wenn die Punkte ${displaystyle x_{0},x_{1},dots ,x_{n-1}}$ das ${displaystyle n}$-das Wurzeln der Einheit sind, kommt dies auf die Berechnung der diskrete Fourier-Transformation von ${Anzeigestil v}$.

Interpolation eines Polynoms

Eng verwandt mit dem vorherigen Problem ist das der Interpolation von a Polynom: gegeben ${displaystyle n1}$ Mehrere Punkte ${Anzeigestil (x_{i},y_{i}),i=0,1,ldots,n,}$ bestimme das Polynom ${Anzeigestil p(x)}$ des Grad${displaystyle n}$ die durch die gegebenen Punkte geht; mit anderen Worten, worauf trifft das zu? ${displaystyle i=0,ldots,n}$

${displaystyle p(x_{i})=summe _{j=0}^{n}p_{j}x_{i}^{j}=y_{i}}$

An das Unbekannte Koeffizienten${displaystyle p_{0},p_{1},dots ,p_{n}}$ um einen zu finden muss man folgendes tun lineares Gleichungssystem lösen, geschrieben in Matrixnotation:

${displaystyle { egin{bmatrix}1&x_{0}&x_{0}^{2}&ldots &x_{0}^{n}/1&x_{1}&x_{1}^{2}&ldots &x_{1}^{n} /vdots &vdots &vdots &&vdots /1&x_{n}&x_{n}^{2}&ldots &x_{n}^{n}/end{bmatrix}}{ egin{bmatrix}p_{0}/p_{1}/vdots / p_{n}end{bmatrix}}={ egin{bmatrix}y_{0}/y_{1}/vdots /y_{n}end{bmatrix}}}$.

Die Koeffizientenmatrix dieses Systems ist eine Vandermonde-Matrix. Eine Vandermonde-Matrix ist jedoch schlecht konditioniert, wodurch große Abweichungen in den berechneten Werten auftreten können ${displaystyle p_{0},p_{1},ldots ,p_{n}}$ mit kleinen Änderungen in ${displaystyle y_{0},y_{1},ldots ,y_{n}}$.

Bestimmend

Das bestimmend von a Quadrat Vandermonde-Matrix ${displaystyle V_{n}}$ der Ordnung ${Anzeigestil n>1}$ ist:

${displaystyle V_{n}={ egin{vmatrix}1&x_{1}&x_{1}^{2}&ldots &x_{1}^{n-2}&x_{1}^{n-1}/1&x_{2} &x_{2}^{2}&ldots &x_{2}^{n-2}&x_{2}^{n-1}/vdots &vdots &vdots &ddots &vdots &vdots /1&x_{n}&x_{n}^{2}&ldots &x_{n}^{n-2}&x_{n}^{n-1}Ende{vmatrix}}}$

Die Anzahl der Variablen ${displaystyle x_{i}}$ in dieser Determinante ist ${displaystyle n}$.

Für diese Determinante gilt:

${displaystyle V_{n}=prod_{1leq i$

Es Beweis von diesem Gestell geht mit volle Einweisung durch die Anzahl der Variablen ${displaystyle n}$ in der Determinante.

Vor dem ${Anzeigestil n=2}$ die Behauptung ist richtig.

${displaystyle V_{2}={ egin{vmatrix}1&x_{1}/1&x_{2}end{vmatrix}}=x_{2}-x_{1}}$

Im Folgenden werden die Regeln für die fegen eine Determinante.

Angenommen, die Aussage ist für einige richtig ${displaystyle n}$, dann gilt:

${displaystyle V_{n 1}={ egin{vmatrix}1&x_{1}&x_{1}^{2}&ldots &x_{1}^{n-1}&x_{1}^{n}/1&x_{2}&x_ {2}^{2}&ldots &x_{2}^{n-1}&x_{2}^{n}/vdots &vdots &vdots &ddots &vdots &vdots /1&x_{n 1}&x_{n 1}^{2}&ldots &x_ {n 1}^{n-1}&x_{n 1}^{n}end{vmatrix}}={ egin{vmatrix}1&x_{1}&x_{1}^{2}&ldots &x_{1}^{n -1}&0/1&x_{2}&x_{2}^{2}&ldots &x_{2}^{n-1}&x_{2}^{n}-x_{2}^{n-1}x_{1 }/vdots &vdots &vdots &ddots &vdots &vdots /1&x_{n 1}&x_{n 1}^{2}&ldots &x_{n 1}^{n-1}&x_{n 1}^{n}-x_{n 1} ^{n-1}x_{1}end{vmatrix}}}$

Die zweite Determinante ergibt sich aus der ersten Determinante ${displaystyle x_{1}}$ mal die vorletzte Spalte, um die letzte Spalte zu subtrahieren. So von hinten nach vorne vorzugehen, ergibt sich immer ${displaystyle x_{1}}$ mal eine Spalte, um von der nächsten Spalte zu subtrahieren:

${displaystyle V_{n 1}={ egin{vmatrix}1&0&0&ldots &0&0/1&x_{2}-x_{1}&x_{2}^{2}-x_{2}x_{1}&ldots &x_{2}^{n -1}-x_{2}^{n-2}x_{1}&x_{2}^{n}-x_{2}^{n-1}x_{1}/vdots &vdots &vdots &ddots &vdots &vdots /1&x_ {n 1}-x_{1}&x_{n 1}^{2}-x_{n 1}x_{1}&ldots &x_{n 1}^{n-1}-x_{n 1}^{n- 2}x_{1}&x_{n 1}^{n}-x_{n 1}^{n-1}x_{1}Ende{vmatrix}}}$

Da in der ersten Zeile außer dem ersten Platz nur 0 steht, folgt:

${displaystyle V_{n 1}={ egin{vmatrix}x_{2}-x_{1}&x_{2}^{2}-x_{2}x_{1}&ldots &x_{2}^{n-1} -x_{2}^{n-2}x_{1}&x_{2}^{n}-x_{2}^{n-1}x_{1}/vdots &vdots &vdots &ddots &vdots &vdots /x_{n 1 }-x_{1}&x_{n 1}^{2}-x_{n 1}x_{1}&ldots &x_{n 1}^{n-1}-x_{n 1}^{n-2}x_ {1}&x_{n 1}^{n}-x_{n 1}^{n-1}x_{1}end{vmatrix}}}$

Aus jeder Zeile kann ein gemeinsamer Faktor entnommen werden:

${displaystyle V_{n 1}=(x_{2}-x_{1})ldots (x_{n 1}-x_{1}){ egin{vmatrix}1&x_{2}&ldots &x_{2}^{n- 2}&x_{2}^{n-1}/vdots &vdots &vdots &ddots &vdots /1&x_{n 1}&ldots &x_{n 1}^{n-2}&x_{n 1}^{n-1}end{vmatrix }}}$

Die verbleibende Determinante ist eine Vandermonde-Determinante der Ordnung ${displaystyle n}$, die nach der Induktionsannahme die richtige Form hat.