[Numerik I] - Übung 6 *

Neue Frage »

05.01.2009, 00:49

tigerbine

Auf diesen Beitrag antworten »

Aufgaben - Teil 6

Determinante der Vandermonde-Matrix
Vandermonde-Matrix und Polynominterpolation
Begleitmatrix eines Polynoms
Berechnung und Auswertung eines Interpolationspolynoms

05.01.2009, 00:50

tigerbine

Auf diesen Beitrag antworten »

6.1 Determinante der Vandermonde-Matrix
Vorab mache man sich mit den Rechenregeln für Matrizen vertraut. Entscheidend sind

Addititon/Subtraktion eines Spaltenvielfachen von einer Spalte ändert den Wert der Determinante nicht
Laplacescher Entwicklungssatz
Ausklammern eines Faktors einer Zeile

Der Übersichtlichkeit wegen sei n=4. Der Beweis funktioniert allgemein genauso.

$\begin{eqnarray*} \begin{vmatrix} 1 & x_1 & x_1^2 & x_1^3 \\ 1 & x_2 & x_2^2 & x_2^3 \\ 1 & x_3 & x_3^2 & x_3^3 \\ 1 & x_4 & x_4^2 & x_4^3\end{vmatrix} && \stackrel{a}=\begin{vmatrix} 1 & x_1-x_1 & x_1^2-x_1x_1 & x_1^3-x_1^2x_1 \\ 1 & x_2-x_1 & x_2^2-x_2x_1 & x_2^3-x_2^2x_1 \\ 1 & x_3-x_1 & x_3^2-x_3x_1 & x_3^3-x_3^2x_1 \\ 1 & x_4-x_1 & x_4^2-x_4x_1 & x_4^3-x_4^2x_1\end{vmatrix}\\ \\ && = \begin{vmatrix} 1 & 0 & 0 & 0 \\ 1 & (x_2-x_1) & x_2(x_2-x_1) & x_2^2(x_2-x_1) \\ 1 & (x_3-x_1) & x_3(x_3-x_1) & x_3^2(x_3-x_1) \\ 1 & (x_4-x_1) & x_4(x_4-x_1) & x_4^2(x_4-x_1) \end{vmatrix} \\ && \stackrel{b}= (-1)^{1+1} \begin{vmatrix} (x_2-x_1) & x_2(x_2-x_1) & x_2^2(x_2-x_1) \\ (x_3-x_1) & x_3(x_3-x_1) & x_3^2(x_3-x_1) \\ (x_4-x_1) & x_4(x_4-x_1) & x_4^2(x_4-x_1) \end{vmatrix} \\&& \stackrel{c} = (x_2-x_1)(x_3-x_1)(x_4-x_1) \begin{vmatrix} 1& x_2 & x_2^2\\ 1 & x_3& x_3^2 \\ 1 & x_4 & x_4^2 \end{vmatrix} \\&&\stackrel{a} =(x_2-x_1)(x_3-x_1)(x_4-x_1) \begin{vmatrix} 1& 0 & 0\\ 1 & x_3-x_2& x_3(x_3-x_2) \\ 1 & x_4-x_2 & x_4(x_4-x_2) \end{vmatrix} \\ && \stackrel{b} = (x_2-x_1)(x_3-x_1)(x_4-x_1) \begin{vmatrix} x_3-x_2& x_3(x_3-x_2) \\ x_4-x_2 & x_4(x_4-x_2) \end{vmatrix} \\ && \stackrel{c} =(x_2-x_1)(x_3-x_1)(x_4-x_1)(x_3-x_2)(x_4-x_2) \begin{vmatrix}1& x_3 \\ 1 & x_4 \end{vmatrix} \\ \\ \\ && = (x_2-x_1)(x_3-x_1)(x_4-x_1)(x_3-x_2)(x_4-x_2)(x_4-x_3) \end{eqnarray*}$

05.01.2009, 00:53

tigerbine

Auf diesen Beitrag antworten »

6.2 Vandermonde Matrix und Polynominterpolation
Damit ein IP vom Grad kleiner gleich n-1 die Langrange Interpolationsbedingung erfüllt muss gelten:

$\begin{eqnarray*} \sum_{j=0}^{n-1}~a_0 \cdot x_i^j = y_i,~\forall i \in \{1,...,n\} \end{eqnarray*}$

Notiert man diese Forderungen in Form eines LGS, so erhält man Ma=y, wobei M die Gestalt einer Vandermonde Matrix hat. Sind die Knoten paarweise verschieden, so ist die Determinante (siehe 6.1) von 0 verschieden und somit die Matrix regulär. Das LGS besitzt eine eindeutige Lösung a und somit ist auch das interpolierende Polynom eindeutig.

05.01.2009, 00:54

tigerbine

Auf diesen Beitrag antworten »

6.3 Begleitmatrix eines Polynoms
Teilaufgabe a

Notieren wir uns zunächst einmal die zu berechnende Determinante:

$\begin{eqnarray*} \text{char}(P)= \begin{vmatrix} x & 0 &0 & \hdots & a_0 \\ -1 & x & \hdots & 0 & a_1 \\ 0 & -1 & \ddots & \vdots& a_2\\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & \hdots & 0 & -1 & x+a_{n-1} \end{vmatrix} = ... \end{eqnarray*}$

Entwickeln wir sie nach der ersten Zeile, so erhält man:

$\begin{eqnarray*} ...= (-1)^{1+1}\cdot x \underbrace{\begin{vmatrix} x & \hdots & 0 & a_1 \\ -1 & \ddots & \vdots& a_2\\ \vdots & \ddots & 0 & \vdots \\ 0 & \hdots & -1 & x+a_{n-1} \end{vmatrix}}_{\hat P} + (-1)^{1+n}\cdot a_0 \underbrace{\begin{vmatrix} -1 & x & \hdots & 0 \\ 0 & -1 & \ddots & \vdots\\ \vdots & \ddots & \ddots & \vdots \\ 0 & \hdots & 0 & -1 \end{vmatrix}}_{(n-1)} =... \end{eqnarray*}$

Die zweite Matrix ist eine obere Dreiecksmatrix mit (-1) auf der Diagonale. Die erste Matrix ist von der gleichen Gestalt wie die ursprüngliche Matrix, nur um 1 in der Länger kleiner. Somit folgt der Beweis durch Induktion. Für n=1 ist die Behauptung offensichtlich korrekt:

$\begin{eqnarray*} \begin{vmatrix} x+a_0 \end{vmatrix} = x+a_0 = p_1(x) \end{eqnarray*}$

Sei nun die Behauptung richtig für n-1, so folgt:

$\begin{eqnarray*} \text{char}(P)=x \cdot \text{char}(\hat P) + (-1)^{n-1} \cdot a_0 \cdot (-1)^{n-1} = x \cdot (\sum_{k=1}^{n-1}~a_k x^{k-1}+x^{n-1})+a_0 =p(x) \end{eqnarray*}$

Teilaufgabe b

Um die Behauptung zu zeigen, löst man ein äquivalentes Problem. So kann man auf bekannte Matrizen zurückgreifen

$\begin{eqnarray*} VPV^{-1} = D \Leftrightarrow VP = DV \end{eqnarray*}$

Dabei gilt laut Aufgabenstellung:

$\begin{eqnarray*} D=\begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots \\ & & & \lambda_n\end{pmatrix}, V=\begin{pmatrix} 1& \lambda_1 & \hdots & \lambda_1^{n-1}\\ 1& \lambda_2 & \hdots & \lambda_2^{n-1}\\ \vdots & & & \\ 1& \lambda_{n} & \hdots & \lambda_{n}^{n-1} \end{pmatrix}, P=\begin{pmatrix} 0& 0 & \hdots & -a_0\\ 1& 0 & \hdots & -a_1\\ \vdots & \ddots& & \\ 0& \hdots & 1& -a_{n-1} \end{pmatrix} \end{eqnarray*}$

Die Gleichheit der ersten Spalten sei anhand eines Beispiels illustriert:

$\begin{eqnarray*} \begin{pmatrix} 1& \lambda_1 & \hdots & \lambda_1^{n-1}\\ 1& \lambda_2 & \hdots & \lambda_2^{n-1}\\ \vdots & & & \\ 1& \lambda_{n} & \hdots & \lambda_{n}^{n-1} \end{pmatrix}\begin{pmatrix}0\\1\\0 \\ \vdots \\ 0 \end{pmatrix} = \begin{pmatrix} \lambda_1\\ \lambda_2 \\ \vdots \\ \lambda_n \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots \\ & & & \lambda_n\end{pmatrix} \begin{pmatrix} 1\\1 \\ \vdots \\1 \end{pmatrix} = \begin{pmatrix} \lambda_1\\ \lambda_2 \\ \vdots \\ \lambda_n \end{pmatrix} \end{eqnarray*}$

Für Gleichhiet die letzte Spalte benötigen wir das wissen, dass die $\begin{eqnarray*} \lambda \end{eqnarray*}$ die Nullstellen und die $\begin{eqnarray*} a \end{eqnarray*}$ die Koeffizienten von p sind. Somit ergibt sich:

$\begin{eqnarray*} \begin{pmatrix} 1& \lambda_1 & \hdots & \lambda_1^{n-1}\\ 1& \lambda_2 & \hdots & \lambda_2^{n-1}\\ \vdots & & & \\ 1& \lambda_{n} & \hdots & \lambda_{n}^{n-1} \end{pmatrix}\begin{pmatrix}-a_0\\-a_1\\ -a_2 \\ \vdots \\ -a_{n-1} \end{pmatrix} = \begin{pmatrix} -p(\lambda_1)+ \lambda_1^n\\ -p(\lambda_2)+ \lambda_2^n \\ \vdots \\ -p(\lambda_n) + \lambda_n^n \end{pmatrix} = \begin{pmatrix} \lambda_1^n\\ \lambda_2^n \\ \vdots \\ \lambda_n^n \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots \\ & & & \lambda_n\end{pmatrix} \begin{pmatrix} \lambda_1^{n-1}\\ \lambda_2^{n-1} \\ \vdots \\ \lambda_n^{n-1} \end{pmatrix} =\begin{pmatrix} \lambda_1^n\\ \lambda_2^n \\ \vdots \\ \lambda_n^n \end{pmatrix} \end{eqnarray*}$

Teilaufgabe c

Da die Koeffizienten nicht explizit bekannt sind, kann man keine Aussage darüber Treffen, wie die Kreise genau aussehen und ob es disjunkte "Gruppen" gibt. Man kann aber den Satz von Gerschgorin auf $\begin{eqnarray*} P \end{eqnarray*}$ und $\begin{eqnarray*} P^T \end{eqnarray*}$ anwenden.

$\begin{eqnarray*} \lambda_i \in \cup_{j=1}^n~K_j \end{eqnarray*}$

$\begin{eqnarray*} K_1=\{z \in \mathbb C ~|~|z| \leq |a_0|\} \end{eqnarray*}$

$\begin{eqnarray*} K_j=\{z \in \mathbb C ~|~|z| \leq 1+|-a_j|\},~j=2,...,n-1 \end{eqnarray*}$

$\begin{eqnarray*} K_{n}=\{z \in \mathbb C ~|~|z+a_{n-1}| \leq 1 \} \end{eqnarray*}$

Für die transponierte Matrix ergibt sich:

$\begin{eqnarray*} \lambda_i \in \cup_{j=1}^n~\hat K_j \end{eqnarray*}$

$\begin{eqnarray*} \hat K_j=\{z \in \mathbb C ~|~|z| \leq 1\},~j=1,...,n-1 \end{eqnarray*}$

$\begin{eqnarray*} \hat K_{n}=\{z \in \mathbb C ~|~|z+a_{n-1}| \leq \sum_{k=1}^{n-2}|-a_k| \} \end{eqnarray*}$

Alternativ kann man die gröbere Abschätzung (Link) verwenden.

$\begin{eqnarray*} \rho(A) \leq \|A\|_M \end{eqnarray*}$

05.01.2009, 00:55

tigerbine

Auf diesen Beitrag antworten »

6.4 Berechnung und Auswerten eines IPS

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:

Es wird ein Interpolationspolynom in 3 Darstellungen berechnet.
 
Beachte: Der Datensatz hat die Form
         Knoten:           x_0,...,x_n
         Funktionswerte:   y_0,...,y_n
 
Bitte die Daten homogen eingeben!
 
Knotenpunkte eingeben:   [0,1,2,3]
Funktionswerte eingeben: [1,2,0,1]
 
--------------------------------------------------------------------------------------------
 
Lagrange-Darstellung  
===============================================================================================
                               [x - 1] [x - 2] [x - 3] 
y_ 0 * L_ 0(x) =      1 *    -------------------------------------------------------------------
                               [0 - 1] [0 - 2] [0 - 3] 

                      1
               =   -----------  *  [x - 1] [x - 2] [x - 3] 
                     -6


                               [x - 0] [x - 2] [x - 3] 
y_ 1 * L_ 1(x) =      2 *    -------------------------------------------------------------------
                               [1 - 0] [1 - 2] [1 - 3] 

                      2
               =   -----------  *  [x - 0] [x - 2] [x - 3] 
                      2


                               [x - 0] [x - 1] [x - 3] 
y_ 2 * L_ 2(x) =      0 *    -------------------------------------------------------------------
                               [2 - 0] [2 - 1] [2 - 3] 

                      0
               =   -----------  *  [x - 0] [x - 1] [x - 3] 
                     -2


                               [x - 0] [x - 1] [x - 2] 
y_ 3 * L_ 3(x) =      1 *    -------------------------------------------------------------------
                               [3 - 0] [3 - 1] [3 - 2] 

                      1
               =   -----------  *  [x - 0] [x - 1] [x - 2] 
                      6


 
Weiter mit beliebiger Taste
 
Newton-Darstellung  
===============================================================================================
 
Dividierte Differenzen Schema
-----------------------------
 
DD =
         0    1.0000    1.0000   -1.5000    1.0000
    1.0000    2.0000   -2.0000    1.5000         0
    2.0000         0    1.0000         0         0
    3.0000    1.0000         0         0         0
 
Interpolationspolynom
---------------------
 
p_ 3(x)= 
 
         +    1 
         +    1 * [x - 0]   
         -  1.5 * [x - 0] [x - 1]   
         +    1 * [x - 0] [x - 1] [x - 2]   
 
Weiter mit beliebiger Taste
 
Monom-Darstellung  
===============================================================================================
 
p_ 3(x)= 
 
     + 1 * x^0     + 4.5 * x^1     - 4.5 * x^2     + 1 * x^3

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

Neville Schema  - Funktionswerte bei 1.5 
=====================================
 
NW =
         0    1.0000    2.5000    1.3750    1.0000
    1.0000    2.0000    1.0000    0.6250         0
    2.0000         0   -0.5000         0         0
    3.0000    1.0000         0         0         0

31.01.2009, 00:06

tigerbine

Auf diesen Beitrag antworten »

Hier geht es weiter: [Numerik I] - Blatt 7

Neue Frage »

Antworten »

[Numerik I] - Übung 6 *

Verwandte Themen