[WS] Lineare Gleichungssysteme 5 - Das CG-Verfahren

Neue Frage »

09.07.2007, 19:38	tigerbine	Auf diesen Beitrag antworten »
[WS] Lineare Gleichungssysteme 5 - Das CG-Verfahren Gliederung Das CG-Verfahren Der formale Algorithmus Satz über konjugierte Richtungen und Konvergenz Folgerung aus dem Algorithmus Der zu implementierende Algorithmus Eigenschaften einer SPD-Matrix Folgerungen 1 Folgerungen 2 Wann bricht der Algorithmus ab? Bezug zum Polynom p Schließen der Kette Beweis (1) Beweis (3) Beweis (4) Beweis (5) Beweis (6) Beweise (7a), (7b), (7) Beweis (8) Beweis (9) Beweis (10) Beweis (11) Beweis (12) Beweis (2) Beweis (2) - Was ist p(A)? Beweis (2) - Was ist \|\|B\|\|_A? Beweis (2) - Was ist das Spektrum von B? Beweis (2) - Was ist \|\|pA\|\|_A?
09.07.2007, 19:39	tigerbine	Auf diesen Beitrag antworten »
10. Das CG-Verfahren Nun sollen die Nachteile des Gradienten-Verfahrens beseitigt werden, indem man die Abstiegsrichtungen A-konjugiert wählt. Der Algorithmus lautet Algorithmus: $\begin{eqnarray} x_0&&=0 \qquad \qquad \quad \text{ (zweckmäßig)} \\r_0&&=b-Ax_0 \qquad \text{Residuum = neg. Gradient} \\p_0&& = r_0 \\\\ s_k&&=\frac{r_k^Tr_k}{p_k^TAp_k} \qquad \text{Lauflänge in Richtung }p_k \\ x_{k+1}&&=x_k+s_k\cdot p_k \quad \text{ Minimum in Richtung }p_k \\r_{k+1}&&=r_k-s_k\cdot Ap_k \quad \text{ neues Residuum } \\\\ &&\fbox{$\displaystyle \text{Prüfe, ob } r_{k+1} = 0 \text{, dann ist } x_{k+1} = x^ \Rightarrow \text{ENDE} $} \\\\\\t_k&&=\frac{r_{k+1}^Tr_{k+1}}{r_k^T\cdot r_k} \\ p_{k+1} &&= r_{k+1} + t_k\cdot p_k \text{ neue Abstiegsrichtung, A-konjugiert zu }p_k \end{eqnarray}$ Es wird sich am Ende Folgendes zeigen:* $\begin{eqnarray} \fbox{$\displaystyle \text{Das cg-Verfahren bricht nach spätestens } m \leq n \text{ Schritten ab, wobei m die Anzahl der versch. Eigenwerte von A ist} $} \end{eqnarray}$ Der entscheidende Gewinn ist hier also, dass man durch diese Wahl der Abstiegsrichtung nicht nur entlang einer Richtung, sondern gleich über den Krylow-Räum $\begin{eqnarray} \mathcal K_k(p_0, A)=\text{span}\{p^0, Ap_0,...,A^{k-1}p_0\} \end{eqnarray}$ minimiert. Aus den Eigenschaften der Krylow-Räume folgt dann die Eigenschaft, dass der Algorithmus theoretisch in $\begin{eqnarray} m \leq n \end{eqnarray}$ Schritten terminiert.
09.07.2007, 21:25	tigerbine	Auf diesen Beitrag antworten »
10a. Der formale Algorithmus $\begin{eqnarray} \text{Wähle } && x_0 \in \mathbb R^n \\r_0&&=b-Ax_0 \qquad \text{Residuum = neg. Gradient} \\p_0&& = r_0 \\\\ s_k&&=\frac{r_k^Tp_k}{(p_k)^TAp_k} \qquad \text{Lauflänge in Richtung }p_k \\ x_{k+1}&&=x_k+s_k\cdot p_k \quad \text{ Minimum in Richtung }p_k \\\\r_{k+1}&&=r_k-s_k\cdot Ap_k \quad \text{ neues Residuum } \\\\ &&\fbox{$\displaystyle \text{Prüfe, ob } r_{k+1} = 0 \text{, dann ist } x_{k+1} = x^ \Rightarrow \text{ENDE} $} \\\\ t_k&&=-~\frac{r_{k+1}^TAp_{k}}{(p_k)^TAp_k} \\ p_{k+1} &&= r_{k+1} + t_k\cdot p_k \text{ neue Abstiegsrichtung, A-konjugiert zu }p_k \\\\ k &&= 0,1,...,n-1 \end{eqnarray*}$
09.07.2007, 22:52	tigerbine	Auf diesen Beitrag antworten »
10b. Satz über konjugierte Richtungen und Konvergenz Seien n paarweise A-konjugierte Richtungen $\begin{eqnarray} p_o,...,p_{n-1} \end{eqnarray}$ gegeben (A sei SPD-Matrix). Wählt man diese Richtungen nacheinander im Abstiegsverfahren (also als $\begin{eqnarray} y_k \end{eqnarray}$ ) mit beliebigem $\begin{eqnarray} x_0 \end{eqnarray}$ , so minimiert $\begin{eqnarray} x_j \end{eqnarray}$ die Funktion f im Teilraum $\begin{eqnarray} \fbox{$ \displaystyle P_j:=\operatorname{span} \{p_0,...,p_{j-1}\} $} \end{eqnarray}$ $\begin{eqnarray} (p_j)^Tr_k = 0\quad\forall~0 \leq j < k \leq n \end{eqnarray}$ $\begin{eqnarray} Ax_n = b \end{eqnarray}$ Beweis: Seien die Richtungen nun A-konjugiert, das bedeutet es gilt $\begin{eqnarray} \langle p_i,p_j \rangle_A =p_i^TAp_j=0,~\forall i \neq j \end{eqnarray}$ . die Minimalität von f im Raum $\begin{eqnarray} P_j \end{eqnarray}$ ergibt sich direkt aus den Rechnungen im vorherigen Workshop. Egal wie man die Abstiegsrichtung wählte, so ergab sich die Rekursion: $\begin{eqnarray} x_k = x_{k-1} + s_{k-1}\cdot p_{k-1},\quad k \geq 1 \end{eqnarray}$ Man kann auch mehrere Schritte zurück gehen. So erhält man: $\begin{eqnarray} x_k = x_{j+1} + \sum_{r=j+1}^{k-1}~s_r\cdot p_r,\quad 0 \leq j < k \leq n \end{eqnarray}$ Es ist für beliebige Richtung $\begin{eqnarray} p_j \end{eqnarray}$ mit den Definitionen $\begin{eqnarray} (p_j)^Tr_{j+1} &&=(p_j)^T\Bigl(b-Ax_{j+1}\Bigr) = \\&&=(p_j)^T\Bigl(b-A(x_j+s_j\cdot p_j)\Bigr) = \\&&=(p_j)^T\Bigl(r_j- \frac{(p_j)^Tr_j}{(p_j)^TAp_j}\cdot Ap_j)\Bigr) = \\&&= (p_j)^Tr_j - (p_j)^Tr_j = \\&&=0 \\&& \forall ~0 \leq j \leq n-1 \end{eqnarray}$ Weiter folgt mit obiger Darstellung für $\begin{eqnarray} 0 \leq j < k \leq n \end{eqnarray}$ : $\begin{eqnarray} Ax_k-b &&= A\Bigl(x_{j+1} + \sum_{r=j+1}^{k-1}~s_r\cdot p_r\Bigr)-b = \\&&=Ax_{j+1} - b + \sum_{r=j+1}^{k-1}~s_r\cdot Ap_r \end{eqnarray}$ Multipliziert man diese Gleichung mit $\begin{eqnarray} (p_j)^T \end{eqnarray}$ , so folgt: $\begin{eqnarray} (p_j)^T(Ax_k-b) &&=(p_j)^T\left(Ax_{j+1} - b + \sum_{r=j+1}^{k-1}~s_r\cdot (p_j)^TAp_r\right) \\&& = -(p_j)^Tr_{j+1} + \sum_{r=j+1}^{k-1}~s_r\cdot (p_j)^TAp_r \\&& = 0 +0 =0 \end{eqnarray}$ Für k=n folgt daher: $\begin{eqnarray} (p_j)^T(Ax_n-b) = 0 \quad \forall~0 \leq j < n-1 \end{eqnarray}$ Da die Abstiegsrichtung $\begin{eqnarray} p_0,...,p_{n-1} \end{eqnarray}$ paarweise A-konjugiert sind, sind sie auch linear unabhängig. Damit ist die maximale Anzahl lin. unabhängiger Vektoren im $\begin{eqnarray} \mathbb R^n \end{eqnarray}$ erreicht. Der einzige Vektor der nun noch senkrecht auf allen stehen kann ist der Nullvektor. Somit muss gelten: $\begin{eqnarray} Ax_n =b \end{eqnarray}$ D.h. der Algorithmus konvergiert nach spätestens n Durchläufen.
09.07.2007, 23:03	tigerbine	Auf diesen Beitrag antworten »
10c. Folgerungen aus dem Algorithmus $\begin{eqnarray} \fbox{$\displaystyle (p_j)^TAp_k = 0,\quad j \neq k $} \end{eqnarray}$ D.h. die Abstiegsrichtungen sind A-konjugiert, bis der Algorithmus (10a) abbricht. Beweis: $\begin{eqnarray} \text{IA:~}(p_0)^TAp_1 && =(p_0)^TA( r_1 + t_{0}\cdot p_{0}) \\&&=(p_0)^TAr_{1} ~+~ t_{0}\cdot (p_0)^TAp_{0} \\&&=(p_0)^TAr_{1} ~-~\frac{(r_1)^TAp_{0}}{(p_{0})^TAp_{0}}\cdot (p_0)^TAp_{0}\\&&=(p_0)^TAr_{1} ~-~(r_1)^TAp_{0}\\&&=0 \end{eqnarray}$ _______________________________________________________________________ $\begin{eqnarray} \text{Bem. 1:} &&\text{ Ist richtig für allgemein } k =j-1 \\ \\ (p_{j-1})^TAp_j &&=(p_{j-1})^TAr_{j} ~-~\frac{(r_j)^TAp_{j-1}}{(p_{j-1})^TAp_{j-1}}\cdot (p_{j-1})^TAp_{j-1} \\&& = (p_{j-1})^TAr_{j} -(r_j)^TAp_{j-1} \\&&=0 \end{eqnarray}$ _______________________________________________________________________ $\begin{eqnarray} \text{IV:~}&& \text{Seien } p_0,...,p_{k-1} \text{ bereits paarweise zueinander A-konjugiert.} \end{eqnarray}$ _______________________________________________________________________ $\begin{eqnarray} \text{Bem. 2: } &&\text{Dann gilt nach (10b): } \\ &&(p_j)^Tr_q = 0 \qquad \forall~0 \leq j < q \leq k \\\\&&\text{Insbesondere gilt dann für q= k:} \\ &&(p_j)^Tr_k = 0 \qquad \forall ~0 \leq j < k \end{eqnarray}$ $\begin{eqnarray} &&\text{Damit folgt: } \\ &&\fbox{$\displaystyle (r_j)^Tr_k = 0 , \quad \forall~j=0,...,k-1 $} ~() \end{eqnarray}$ Beweis* $\begin{eqnarray} (r_j)^Tr_k &&= ~(p_j-t_{j-1}\cdot p_{j-1})r_k = \\&&=~(p_j)^Tr_k - t_{j-1} \cdot (p_{j-1})^Tr_k = \\&& = 0\\&&\forall~j=1,...,k-1 \\ \end{eqnarray}$ $\begin{eqnarray} \text{Für k=j ergibt sich: } \end{eqnarray}$ $\begin{eqnarray} (r_k)^Tr_k &&= ~(p_k-t_{k-1}\cdot p_{k-1})^Tr_k \\&&=~(p_k)^Tr_k - t_{k-1} \cdot (p_{k-1})^Tr_k = \\&& \stackrel{(10b)} = (p_k)^Tr_k \end{eqnarray}$ $\begin{eqnarray} \text{Daraus folgt:} \end{eqnarray}$ $\begin{eqnarray} s_k = \frac{(r_k)^Tp_k}{(p_k)^TAp_k} ~> ~0 \quad \text{falls } r_k \neq 0 \end{eqnarray}$ $\begin{eqnarray} \text{Und somit folgt auch noch: } \end{eqnarray}$ $\begin{eqnarray} (r_0)^Tr_k &&\stackrel{\text{Def}}= ~(p_0)^Tr_k = \\&&\stackrel{(10b)}=0 \end{eqnarray}$ _______________________________________________________________________ $\begin{eqnarray} \text{IS:~}&& \text{Sei also } r_k \neq 0 \text{. Mit Bem. 1 folgt für j=k-1: } \\&& (p_{k-1})^TAp_{k} = 0 \\\\ &&\text{Weiter gilt, da der Algorithmus noch nicht abgebrochen ist: }\\&& r_j \neq 0 ~\forall ~j=0,...,k \\\\&&\text{Mit Bem. 2 folgt: }\\ &&r_{j+1} = r_j - s_j\cdot Ap_j \Leftrightarrow Ap_j = \frac{r_j-r_{j+1}}{s_{j}} \\\\ &&\text{Somit folgt für } j=0,...,k-2: \end{eqnarray}$ $\begin{eqnarray} (p_j)^TAp_k &&= (p_j)^TA(r_k+t_{k-1}\cdot p_{k-1}) = \\&&=(p_j)^TAr_k + t_{k-1}\cdot (p_j)^TAp_{k-1} = \\&& = (r_k)^TAp_j + t_{k-1}\cdot (p_j)^TAp_{k-1} = \\&& = (r_k)^T (\frac{r_j-r_{j+1}}{s_{j}}) + + t_{k-1}\cdot (p_j)^TAp_{k-1} =\\&&=\frac{1}{s_{j}} \cdot (r_j^Tr_k-r_{j+1}^Tr_k) + t_{k-1}\cdot (p_j)^T Ap_{k-1} = \\&&\stackrel{(),\text{ IV}} =0 \\ &&\forall j=0,...,k-2 \end{eqnarray}$ $\begin{eqnarray} \fbox{$\displaystyle Ax_n=b $} \end{eqnarray}$ folgt aus (10b), d.h. das Verfahren konvergiert spätestens für $\begin{eqnarray} x_n \end{eqnarray*}$
09.07.2007, 23:07	tigerbine	Auf diesen Beitrag antworten »
10d. Der zu implementierende Algorithmus Der eingangs gepostete Algorithmus ergibt sich mit (10c) wie folgt $\begin{eqnarray} (r_k)^Tp_k = (r_k)^Tr_k \end{eqnarray}$ $\begin{eqnarray} \Rightarrow~s_k=\frac{(r_k)^Tp_k}{(p_k)^TAp_k}=\frac{(r_k)^Tr_k}{(p_k)^TAp_k} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow~\frac{1}{(p_k)^TAp_k}= \frac{s_k}{(r_k)^Tr_k} \end{eqnarray}$ $\begin{eqnarray} r_{k+1} = r_k-s_k\cdot Ap_k \end{eqnarray}$ $\begin{eqnarray} \Rightarrow -s_kAp_k = r_{k+1} - r_k \end{eqnarray}$ $\begin{eqnarray} t_k&&=-~\frac{(r_{k+1})^TAp_k}{(p_k)^TAp_k} = \\&&=-~ \frac{s_k \cdot (r_{k+1})^TAp_k}{(r_k)^Tr_k} = \\&&= \frac{(r_{k+1})^T(r_k+1-r_k)}{(r_k)^Tr_k} = \\&&=\frac{(r_{k+1})^Tr_{k+1}}{(r_k)^Tr_k} \end{eqnarray}$ Bei n Durchläufen benötigt man so $\begin{eqnarray} \mathcal O(n^3) \end{eqnarray}$ Operationen. Dass man es ggf. mit Weniger als n Durchläufen schafft, soll nun gezeigt werden. Identität des Residuums $\begin{eqnarray} \fbox{$\displaystyle r_{k+1}=b-Ax_{k+1}$} \end{eqnarray}$ Beweis: $\begin{eqnarray} \text{IA: }~r_0:=b-Ax_0 \end{eqnarray}$ $\begin{eqnarray} \text{IV: }~r_k =b - Ax_k \end{eqnarray}$ $\begin{eqnarray} \text{IS: }~r_{k+1}&& =r_k- s_k\cdot Ap_k \stackrel{IV}= b-Ax_k - s_k\cdot Ap_k=\\&&= b - A(x_k+s_k\cdot p_k)=b - Ax_{k+1} \end{eqnarray}$
Anzeige

10.07.2007, 03:16	tigerbine	Auf diesen Beitrag antworten »
10e. Eigenschaften einer SPD-Matrix $\begin{eqnarray} \text{Sei A }\in \mathbb R^{n \times n} \text{ eine SPD-Matrix. Dann gilt: } \end{eqnarray}$ --------------------------------------------------------------- $\begin{eqnarray} \text{A ist regulär} \end{eqnarray}$ $\begin{eqnarray} A = A^T \end{eqnarray}$ $\begin{eqnarray} x^TAx~>~0 \quad \forall~x \neq 0 \end{eqnarray}$ $\begin{eqnarray} \sigma(A) = \{\lambda_1,...,\lambda_m\} \subset \mathbb R,~m \leq n \end{eqnarray}$ $\begin{eqnarray} \xi_A(\lambda)=\prod_{j=1}^n~(\lambda-\lambda_j) \end{eqnarray}$ $\begin{eqnarray} \lambda_j ~> 0\quad~\forall ~j=1,...,n \end{eqnarray}$
10.07.2007, 03:38	tigerbine	Auf diesen Beitrag antworten »
10e1. Folgerungen 1 $\begin{eqnarray} &&\text{A ist SPD-Matrix mit obigen Eigenschaften, so kann man ein Polynom }\\ &&p \in \Pi_m \text{ wie folgt eindeutig definieren:} \end{eqnarray}$ ------------------------------------------------------- $\begin{eqnarray} && p(0):=1,~p(\lambda_1):= ... = p(\lambda_m):= 0 \\\\ && \Rightarrow p(x) = \sum_{j=1}^m~\alpha_j\cdot x^j \end{eqnarray}$ Es folgt daraus: $\begin{eqnarray} p(\lambda_j) = 0 \quad \forall ~j =1,...,m && \Leftrightarrow^{(1)} \max_{\lambda_\in \sigma(A)}~\|p(\lambda)\| = 0 \\\\&& \Leftrightarrow^{(2)} \|\|p(A)\|\|_A =0 \end{eqnarray}$
10.07.2007, 03:39	tigerbine	Auf diesen Beitrag antworten »
10e2. Folgerungen 2 $\begin{eqnarray} \text{Da A regulär ist, besitzt das LGS } Ax=b \text{ eine eindeutige Lösung }x^ \end{eqnarray}$ -------------------------------------------------------------------------------------------------- $\begin{eqnarray} x^* \text{ löst } Ax=b && \Leftrightarrow^{(3)} x^* \text{ minimiert } f(x) = \frac{1}{2}<x,Ax>-<b,x> \\&&\Leftrightarrow ^{(4)} x^* \text{ minimiert } f(x) = \frac{1}{2}e^TAe-\frac{1}{2}(x^)^Tb \quad \text{ mit } e:=x^-x \\&&\Leftrightarrow^{(5)} x^* \text { minimiert } \hat f(x) = e^TAe = \|\|e\|\|_A \quad \text{ mit } e:=x^-x \end{eqnarray}$
10.07.2007, 03:40	tigerbine	Auf diesen Beitrag antworten »
10f. Wann bricht der Algorithmus ab? Der Algorithmus bricht ab, wenn für ein minimales m für das Residuum gilt: $\begin{eqnarray} r_m=0 &&\Leftrightarrow b - Ax_m = 0 \\&&\Leftrightarrow x_m=x^ \\&&\Leftrightarrow e_m=0 \\&&\Leftrightarrow \|\|e_m\|\|_A=0 \end{eqnarray}$ Die entscheidende Äquivalenzkette* $\begin{eqnarray} r_m=0 &&\Leftrightarrow^{(6)} p_m = 0 \\ &&\Leftrightarrow^{(7)} \forall~k \geq m \text{ gilt : } \operatorname{dim}~\Bigl( \operatorname{span}\{r_0,...,r_k\}\Bigr) =\operatorname{dim}~\Bigl( \operatorname{span}\{r_0,...,r_{m-1}\}\Bigr) = m \\ &&\Leftrightarrow^{(8)} \forall~k \geq m \text{ gilt : } \operatorname{dim}~\mathcal K \Bigl(A, p_0,k+1\Bigr) :=\operatorname{dim}~\Bigl( \operatorname{span}\{p_0,Ap_0,...,A^kp_0\}\Bigr) = m \end{eqnarray}$ Residuen-Raum $\begin{eqnarray} R_k:=\operatorname\{r_0,...,r_{k-1} \} \end{eqnarray}$ Raum der Abstiegsrichtungen $\begin{eqnarray} P_k:=\operatorname\{p_0,...,p_{k-1} \} \end{eqnarray}$ Krylov-Raum Der Raum $\begin{eqnarray} \mathcal K \Bigl(A, p_0,k+1\Bigr) \end{eqnarray}$ heißt Krylov-Raum. Kennen wir seine maximale Dimension, so wissen wir nach wie vielen Schritten das Verfahren spätestens abbricht. Es gilt des weitern: $\begin{eqnarray} \operatorname{span}\{r_0,...,r_k\} =^{(7a)} \operatorname{span}\{p_0,...,p_k\} \Leftrightarrow R_{k+1} = P_{k+1} \end{eqnarray}$ $\begin{eqnarray} \operatorname{span}\{r_0,...,r_k\} =^{(7b)} \operatorname{span}\{p_0,Ap_0,...,A^kp_0\} \Leftrightarrow R_{k+1} = \mathcal K \Bigl(A, p_0,k+1\Bigr) \end{eqnarray}$ $\begin{eqnarray} \mathcal K \Bigl(A, p_0,k+1 \Bigr) =^{(9)} \operatorname{span}\{Ae_0,...,A^{k+1}e_0\} \end{eqnarray}$ Es gilt offensichtlicht: $\begin{eqnarray} \mathcal K \Bigl(A, p_0,0\Bigr) \subseteq \mathcal K \Bigl(A, p_0,1\Bigr) \subseteq ... \subseteq \mathcal K \Bigl(A, p_0,k+1\Bigr) \end{eqnarray}$
10.07.2007, 03:40	tigerbine	Auf diesen Beitrag antworten »
10g. Bezug zum Polynom p Für die Iterierten $\begin{eqnarray} e_k \end{eqnarray}$ gilt: $\begin{eqnarray} (e_{k+1}-e_0) \in^{(10)} K \Bigl(A, p_0,k+1\Bigr) =\operatorname{span}\{Ae_0,...,A^{k+1}e_0\} \end{eqnarray}$ Somit lassen sie sich als Linearkombination wie folgt darstellen: $\begin{eqnarray} (e_{k+1}-e_0) = \sum_{j=1}^{k+1}~c_j\cdot A^je_0 \end{eqnarray}$ Für die Iterierten $\begin{eqnarray} e_k \end{eqnarray}$ ergibt sich daher: $\begin{eqnarray} e_{k+1}&&=\sum_{j=1}^{k+1}~c_j\cdot A^je_0 +e_0 \\&&=\sum_{j=0}^{k+1}~c_j\cdot A^je_0, \quad \text{mit } c_0:=1 \\&&=\Bigl[\sum_{j=0}^{k+1}~c_j\cdot A^j\Bigr]\cdot e_0 \end{eqnarray}$ Allgemein bedeutet das: $\begin{eqnarray} \fbox{$ \displaystyle e_j=p(A) \cdot e_0 ,\quad p \in \Pi_j,\quad p(0)=1, \quad j=0,1,... $} \end{eqnarray}$ Für das Residuum folgt dann: $\begin{eqnarray} r_j&&= Ae_j\\&&= p(A) \cdot Ae_0 \\&&=p(A) \cdot Ar_0 ,\quad p \in \Pi_j,\quad p(0)=1, \quad j=0,1,... \end{eqnarray}$
10.07.2007, 03:40	tigerbine	Auf diesen Beitrag antworten »
10h. Schließen der Kette Als Folgerung des vorherigen Post ergibt sich $\begin{eqnarray} \|\|e_k\|\|= 0 \Leftrightarrow^{(11)} \|\|p(A)e_0\|\| = 0 \end{eqnarray}$ Nun muss nur noch gezeigt werden, dass gilt: $\begin{eqnarray} \|\|p(A)\|\|_A= 0 \Rightarrow^{(12)} \|\|p(A)e_0\|\| = 0 \end{eqnarray}$ Und es wurde somit folgendes gezeigt: $\begin{eqnarray} \text{A hat m versch. Eigenwerte } &&\Rightarrow \text{ Der Krylov-Raum hat die max. Dimension m}\\&& \Leftrightarrow \text{Das Verfahren konvergiert nach max. m Schritten} \end{eqnarray}$
12.07.2007, 05:16	tigerbine	Auf diesen Beitrag antworten »
Beweis (1) Behauptung (1): $\begin{eqnarray} p(\lambda_j) = 0 \quad \forall ~j =1,...,m && \Leftrightarrow^{(1)} \max_{\lambda_\in \sigma(A)}~\|p(\lambda)\| = 0 \end{eqnarray}$ Beweis: $\begin{eqnarray} \Rightarrow: \end{eqnarray}$ offensichtlich $\begin{eqnarray} \Leftarrow: \end{eqnarray}$ Angenommen es gäbe einen Eigenwert mit $\begin{eqnarray} p(\lambda_j) \neq 0 \end{eqnarray}$ . Dann wäre $\begin{eqnarray} \|p(\lambda_j)\| >0 \end{eqnarray}$ , was im Widerspruch zu $\begin{eqnarray} \max_{\lambda_\in \sigma(A)}~\|p(\lambda)\| = 0 \end{eqnarray}$ steht.
12.07.2007, 05:29	tigerbine	Auf diesen Beitrag antworten »
Beweis (3) Behauptung (3): $\begin{eqnarray} x^ \text{ löst } Ax=b && \Leftrightarrow^{(3)} x^* \text{ minimiert } f(x) = \frac{1}{2}<x,Ax>-<b,x> \end{eqnarray}$ Beweis:* Sieha (8a)
12.07.2007, 05:31	tigerbine	Auf diesen Beitrag antworten »
Beweis (4) Behauptung (4): $\begin{eqnarray} &&x^ \text{ minimiert } f(x) = \frac{1}{2}<x,Ax>-<b,x> \\\Leftrightarrow ^{(4)}&& x^* \text{ minimiert } f(x) = \frac{1}{2}e^TAe-\frac{1}{2}(x^)^Tb \quad \text{ mit } e:=x^-x \end{eqnarray}$ Beweis:* Siehe (8b)
12.07.2007, 05:43	tigerbine	Auf diesen Beitrag antworten »
Beweis (5) Behauptung (5): $\begin{eqnarray} &&x^ \text{ minimiert } f(x) = \frac{1}{2}e^TAe-\frac{1}{2}(x^)^Tb \quad \text{ mit } e:=x^-x \\\Leftrightarrow^{(5)} &&x^* \text { minimiert } \hat f(x) = e^TAe = \|\|e\|\|_A \quad \text{ mit } e:=x^-x \end{eqnarray}$ Beweis: Siehe (8c)
12.07.2007, 05:43	tigerbine	Auf diesen Beitrag antworten »
Beweis (6) Behauptung (6): $\begin{eqnarray} r_m=0 &&\Leftrightarrow^{(6)} p_m = 0 \end{eqnarray}$ Beweis: Dabei darf $\begin{eqnarray} r_{m-1} \neq 0 \end{eqnarray}$ angenommen werden, da sonst der Algorithmus schon abgebrochen worden wäre. $\begin{eqnarray} \Rightarrow: \end{eqnarray}$ $\begin{eqnarray} r_m = 0 \quad \Rightarrow \quad p_m&&:=r_m + \frac{(r_m)^Tr_m}{(r_{m-1})^Tr_{m-1}}\cdot p_{m-1} =\\&&= 0+0=\\&&=0 \end{eqnarray}$ $\begin{eqnarray} \Leftarrow: \end{eqnarray}$ $\begin{eqnarray} p_m=0 \quad \Rightarrow \quad 0 &&=r_m +\frac{(r_m)^Tr_{m}}{(r_{m-1})^Tr_{m-1}}\cdot p_{m-1} \\ \\&&\text{Wegen } p_{m-1} \perp r_{m} \text{ folgt (beide Seiten mit } p_{m-1}^T \text{ multiplizieren):} \\ \\&&\frac{(r_m)^Tr_{m}}{(r_{m-1})^Tr_{m-1}} \stackrel{!}=0 ~\Rightarrow r_m=0 \end{eqnarray}$
12.07.2007, 05:44	tigerbine	Auf diesen Beitrag antworten »
Beweise (7a), (7b), (7) Behauptung (7a): $\begin{eqnarray} \operatorname{span}\{r_0,...,r_k\} =^{(7a)} \operatorname{span}\{p_0,...,p_k\} \Leftrightarrow R_{k+1} = P_{k+1} \end{eqnarray}$ Beweis: $\begin{eqnarray} \text{IA: }&& k=0,~p_0 = r_0 \text{ laut Algorithmus} \end{eqnarray}$ $\begin{eqnarray} \text{IV:}&&\text{Sei die Behauptung richtig für (k-1).} \end{eqnarray}$ $\begin{eqnarray} \text{IS: }&& \text{Sei } v\in \text{span}\{r_0,...,r_k \}. \text{ Dann gibt es eine Darstellung von v als Linearkombination dieser Vektoren}\\&&v = a_0\cdot r_0 + ...+a_{k-1}\cdot r_{k-1} + a_r\cdot r_k \\\\&& \text{Nach IV gilt span}\{ r_0,...,r_{k-1}\} = \text{span}\{p_0,...,p_{k-1}\}. \text{Somit gibt es Koeffizienten }b_i, i=0,...,k-1 \text{ mit: }\\&& v=b_0\cdot p_0 + ... + b_{k-1}\cdot p_{k-1} + a_k\cdot r_k \\\\&&\text{Laut Algorithmus gilt } p_k=r_k+t\cdot p_{k-1} \Leftrightarrow r_k=p_k-t\cdot p_{k-1}. \text{ Damit folgt: } \\&& v = b_0\cdot p_0+...+b_{k-1}\cdot p_{k-1} + a_k\cdot r_k \\&& v=b_0\cdot p_0 + ...+b_{k-1}\cdot p_{k-1} + a_k\cdot (p_k - t\cdot p_{k-1}) \\ && v=b_0\cdot p_0 + ...+(b_{k-1}-t\cdot a_k)\cdot p_{k-1} + a_k\cdot p_k \\\\&&\text{Damit gilt }v\in \text{ span} \{p_0,...,p_k\} \text{. Aus Dimensionsgründen folgt die Behauptung.} \end{eqnarray}$ Die Residuen sind paarweise orthogonal und die Abstiegsrichtungen paarweise A-konjugiert. Daher sind auch jeweils paarweise linear unabängig. Vergleiche (10c) Behauptung (7b): $\begin{eqnarray} \operatorname{span}\{r_0,...,r_k\} =^{(7b)} \operatorname{span}\{p_0,Ap_0,...,A^kp_0\} \Leftrightarrow R_{k+1} = \mathcal K \Bigl(A, p_0,k+1\Bigr) \end{eqnarray}$ Beweis: $\begin{eqnarray} {IA: }&& j=0,~r_0=p_0 \end{eqnarray}$ $\begin{eqnarray} {IV: }&& \text{Sei die Behauptung richtig für (k-1). Es gilt also } \\&& R_k = \mathcal K \Bigl(A, p_0,k\Bigr) \end{eqnarray}$ $\begin{eqnarray} {IS: }&& \text{Wegen (10c - Residuen sind orthogonal) gilt: }\quad r_k \in ~R_{k+1} \setminus R_k\\&& \text{mit der IV folgt: }\quad r_k \notin \mathcal K(A, p_0,k) \\ \\&&\text{Mit (7a) und der IV folgt: } \quad r_{k-1},~p_{k-1} \in \mathcal K(A, p_0,k) \\&&\text{Damit folgt: } \quad Ap_{k-1} \in \mathcal K(A,p_0,k+1) \\ \\ &&\text{Laut Algorithmus gilt: } \quad r_k=r_{k-1}-s_{k-1} \cdot Ap_{k-1} \\&&\text{Also gilt: }\quad r_k \in \mathcal K(A,p_0,k+1) \\\\&&\text{Insgesamt gilt also: } \quad r_k \in~\mathcal K(A,p_0,k+1) \setminus \mathcal K(A,p_0,k) \\&&\text{Und somit: } \quad R_{k+1} = \mathcal K(A,p_0,k+1) \end{eqnarray}$ Die letzte Argumentation teilt sich in 2 Fälle. Entweder die Räume haben sich nicht vergrößert, dann sind sie nach IV identisch. Wenn sie sich vergrößern, dann folgt aus Dimensionsgründen, dass sie übereinstimmen. Das wirft die Frage auf, wann sich die Dimension der Räume nicht mehr erhöht. Behauptung (7): $\begin{eqnarray} p_m = 0 &&\Leftrightarrow^{(7)} \forall~k \geq m \text{ gilt : } \operatorname{dim}~\Bigl( \operatorname{span}\{r_0,...,r_k\}\Bigr) =\operatorname{dim}~\Bigl( \operatorname{span}\{r_0,...,r_{m-1}\}\Bigr) = m \end{eqnarray}$ Beweis: $\begin{eqnarray} \Rightarrow: \end{eqnarray}$ $\begin{eqnarray} p_m = 0 \Leftrightarrow^{(6)} r_m=0. \text{ Somit folgt: } \end{eqnarray}$ $\begin{eqnarray} r_{m+1} = r_m - s_k \cdot Ap_m = 0 \end{eqnarray}$ $\begin{eqnarray} p_{m+1} = r_{m+1} + t_k \cdot p_m = 0 \end{eqnarray}$ $\begin{eqnarray} \text{Damit folgt: } r_k = p_k = 0 \quad \forall ~k \geq m \end{eqnarray}$ Da m bzgl. der Eigenschaft $\begin{eqnarray} r_m = 0 \end{eqnarray}$ minimal ist (siehe 10f) und die Residuuen bis dahin paarweise orthogonal sind, folgt die Behauptung. $\begin{eqnarray} \Leftarrow: \end{eqnarray}$ Die Residuen sind paarweise orthogonal. Der einzige Vektor, bei dem sich dann die Dimension nicht mehr erhöht ist der Nullvektor. Somit muss gelten $\begin{eqnarray} r_m=0 \end{eqnarray}$ , Damit folgt aus (6) die Behauptung.
12.07.2007, 05:45	tigerbine	Auf diesen Beitrag antworten »
Beweis (8) Behauptung (8): $\begin{eqnarray} && \forall~k \geq m \text{ gilt : } \operatorname{dim}~\Bigl( \operatorname{span}\{r_0,...,r_k\}\Bigr) =\operatorname{dim}~\Bigl( \operatorname{span}\{r_0,...,r_{m-1}\}\Bigr) = m \\&& \Leftrightarrow^{(8)} \\ &&\forall~k \geq m \text{ gilt : } \operatorname{dim}~K \Bigl(A, p_0,k+1\Bigr) :=\operatorname{dim}~\Bigl( \operatorname{span}\{p_0,Ap_0,...,A^kp_0\}\Bigr) = m \end{eqnarray}$ Beweis: $\begin{eqnarray} \text{Folgt direkt aus (7b): }R_{k+1} = \mathcal K \Bigl(A, p_0,k+1\Bigr) \end{eqnarray}$
12.07.2007, 05:45	tigerbine	Auf diesen Beitrag antworten »
Beweis (9) Behauptung (9): $\begin{eqnarray} K \Bigl(A, p_0,k+1\Bigr) =^{(9)} \operatorname{span}\{Ae_0,...,A^{k+1}e_0\} \end{eqnarray}$ Beweis: $\begin{eqnarray} \text{Nach Definition im Algorithmus und in (10e) gilt: } \end{eqnarray}$ $\begin{eqnarray} p_0=r_0=b-Ax_0 = Ax^-Ax_0 = A(x^-x_0) = Ae_0 \end{eqnarray}$ $\begin{eqnarray} \text{Somit folgt: } \end{eqnarray}$ $\begin{eqnarray} K \Bigl(A, p_0,k+1\Bigr):=\operatorname\{ p_0,Ap_0,...,A^kp_0\} = \operatorname{span}\{Ae_0,...,A^{k+1}e_0\} \end{eqnarray}$
12.07.2007, 05:46	tigerbine	Auf diesen Beitrag antworten »
Beweis (10) Behauptung (10): $\begin{eqnarray} (e_{k+1}-e_0) \in^{(10)} K \Bigl(A, p_0,k+1\Bigr) =\operatorname{span}\{Ae_0,...,A^{k+1}e_0\} \end{eqnarray}$ Beweis: Laut Algorithmus gilt: $\begin{eqnarray} x_{k+1} = x_k + s_k\cdot p_k \end{eqnarray}$ Dies kann man auch zu $\begin{eqnarray} x_0 \end{eqnarray}$ zurückführen (Induktionsbeweis): $\begin{eqnarray} x_{k+1} = x_0 + \sum_{i=0}^k~s_i\cdot p_i \end{eqnarray}$ Stellt man dies nun um, so erhalt man: $\begin{eqnarray} x_{k+1} - x_0 = \sum_{i=0}^k~s_i\cdot p_i \end{eqnarray}$ Mit der Definition von $\begin{eqnarray} e_k \end{eqnarray}$ folgt: $\begin{eqnarray} (x^-e_{k+1}) -(x^- e_0) = \sum_{i=0}^k~s_i\cdot p_i \end{eqnarray}$ $\begin{eqnarray} (e_{k+1} - e_{0}) = - \sum_{i=0}^k~s_i\cdot p_i \quad \in P_{k+1} \end{eqnarray}$ Mit (7b), (9) folgt dann: $\begin{eqnarray} (e_{k+1}-e_0) \in \mathcal K(A,p_0,k+1) = ~\operatorname{span}\{Ae_0,...,A^{k+1}e_0\} \end{eqnarray}$
12.07.2007, 05:47	tigerbine	Auf diesen Beitrag antworten »
Beweis (11) Behauptung (11): $\begin{eqnarray} \|\|e_k\|\|= 0 \Leftrightarrow^{(11)} \|\|p(A)e_0\|\| = 0 \end{eqnarray}$ Beweis: Wegen (10) gilt: $\begin{eqnarray} (e_k-e_0) \in \operatorname{span}\{Ae_0,...,A^{k+1}e_0\} \end{eqnarray}$ Somit ist der Term als Linearkombination wie folgt darstellbar: $\begin{eqnarray} (e_k-e_0) = \sum_{i=0}^k~\hat c_i \cdot A^ie_0 \end{eqnarray}$ Umstellen liefert: $\begin{eqnarray} e_k = \sum_{i=0}^k~ c_i \cdot A^ie_0 = \Bigl[c_k\cdot (A)^k + ...+ c_1\cdot A + c_0 \cdot I \Bigr]\cdot e_0 \end{eqnarray}$ Somit gibt es ein Polynom $\begin{eqnarray} p \in \Pi_k \end{eqnarray}$ mit: $\begin{eqnarray} e_k=p(A)\cdot e_0 \end{eqnarray}$ Damit folgt die Behauptung
12.07.2007, 05:48	tigerbine	Auf diesen Beitrag antworten »
Beweis (12) Behauptung (12): $\begin{eqnarray} \|\|p(A)\|\|_A= 0 \Rightarrow^{(12)} \|\|p(A)e_0\|\|_A = 0 \end{eqnarray}$ Beweis: es ist $\begin{eqnarray} B:=p(A) \end{eqnarray}$ wieder eine Matrix. Laut dem [Workshop-Lineare Gleichungssysteme 1] gilt: $\begin{eqnarray} \|\|p(A)e_0\|\| \leq \|\|p(A)\|\|_A\cdot \|\|e_0\|\|_A \end{eqnarray}$ Es gilt hier i.A. $\begin{eqnarray} e_0 = x^-x_0 \neq 0 \end{eqnarray}$ , sonst hätte man mit x_0 schon die gesuchte Lösung gefunden. Gilt nun also: $\begin{eqnarray} \|\|p(A)\|\|=0 \end{eqnarray}$ So folgt wegen der Normeigenschaft: $\begin{eqnarray} 0 \leq\|\|p(A)e_0\|\|_A \end{eqnarray*}$ die Behauptung.
13.07.2007, 01:21	tigerbine	Auf diesen Beitrag antworten »
Beweis (2) Erfolgt über mehrere Post. ******************************************** Sei $\begin{eqnarray} A \in \mathbb R^{n \times n} \end{eqnarray}$ eine SPD-Matrix. Dann besitzt diese nur reelle positive Eigenwerte, d.h. das charakteristische Polynom zerfällt über $\begin{eqnarray} \mathbb R \end{eqnarray}$ in Linearfaktoren. Dabei bezeichnen nun $\begin{eqnarray} m \leq n \end{eqnarray}$ die Anzahl der verschiedenen Eigenwerte von A. Aus der Regularität von A folgt, dass 0 kein Eigenwert ist. Es gilt: Spektrum von A $\begin{eqnarray} \sigma(A) = \{\lambda_1,...,\lambda_m\} \end{eqnarray}$ A-Vektor-Norm $\begin{eqnarray} \|\|x\|\|_A := \sqrt{<x,x>_A} = \sqrt{x^TAx} \end{eqnarray}$ induzierte Matrixnorm $\begin{eqnarray} \|\|M\|\|_A &&= \sup_{\|\|x\|\|_A=1} \|\|Mx\|\|_A = \sup_{x^TAx=1}~\sqrt{(Mx)^TA(Mx)} \\ &&= \max_{\|\|x\|\|_A=1} \|\|Mx\|\|_A =\max_{x^TAx=1}~\sqrt{(Mx)^TA(Mx)}= \end{eqnarray}$ Wir konstruieren nun ein Polynom $\begin{eqnarray} p \in \Pi_m \end{eqnarray}$ aus folgenden (m+1)-Interpolalationsbedingungen. Aus dem [Workshop - Polynominterpolation] wissen wir, dass p eindeutig exisitiert. $\begin{eqnarray} \fbox{$\displaystyle p(0) =1,~p(\lambda_1) = ... = p(\lambda_2) = 0 \quad \Rightarrow p(X) = \sum_{j=1}^m~\alpha_j\cdot X^j $} \end{eqnarray}$
13.07.2007, 01:23	tigerbine	Auf diesen Beitrag antworten »
Beweis (2) - Was ist p(A)? Was passiert, wenn man A in p einsetzt? $\begin{eqnarray} \fbox{$\displaystyle p(A) = \alpha_m\cdot A^m + ... + \alpha_1\cdot A + \alpha_0 \cdot I =:B$} \end{eqnarray}$ Das ist wiederum eine Matrix aus dem $\begin{eqnarray} \mathbb R^{n \times n} \end{eqnarray}$ , die mit B bezeichnet werden soll. Welche Eigenschaften hat B? $\begin{eqnarray} B:=p(A) \end{eqnarray}$ $\begin{eqnarray} A^T= A \Rightarrow B^T=p(A^T) = p(A) = B \end{eqnarray}$ $\begin{eqnarray} B^TB =BB = BB^T \end{eqnarray}$ , d.h. B ist normal. $\begin{eqnarray} AB = A\cdot p(A) = p(A) \cdot A = BA \end{eqnarray}$ , d.h. A und B sind vertauschbar $\begin{eqnarray} \Rightarrow \end{eqnarray}$ A, B sind simultan diagonalisierbar, d.h. es gibt eine orthogonale Matrix $\begin{eqnarray} Q \in \mathbb R^{n \times n} \end{eqnarray}$ mit $\begin{eqnarray} AQ = QD_A,~D_A=\text{diag}(\lambda_1,..,\lambda_n) \end{eqnarray}$ $\begin{eqnarray} BQ = QD_B,~D_B=\text{diag}(\mu,..,\mu_n) \end{eqnarray}$
13.07.2007, 01:24	tigerbine	Auf diesen Beitrag antworten »
Beweis (2) - Was ist \|\|B\|\|_A ? Die induzierte Matrixnorm wurde bereits definiert. Dabei beachte man, dass aus Kompaktheitsgründen $\begin{eqnarray} \sup \end{eqnarray}$ durch $\begin{eqnarray} \max \end{eqnarray}$ ersetzt werden kann. $\begin{eqnarray} \|\|B\|\|_A&&=\max_{\|\|x\|\|_A}~\|\|Bx\|\|_A \\&&= \max_{x^TAx=1}~\|\sqrt{(Bx)^TA(Bx)} \end{eqnarray}$ Da die Spalten von Q eine ONB bilden, kann man jeden Vektor x als Linearkombination dieser ausdrücken: $\begin{eqnarray} x = \sum_{j_1}^n~\beta_j\cdot q_j \end{eqnarray}$ Mit dem Wissen $\begin{eqnarray} (q_k)^Tq_j = \begin{cases} 0 & k \neq j \\ 1 &k=j \end{cases} \end{eqnarray}$ folgt: $\begin{eqnarray} Ax = QD_AQ^Tx = \sum_{j=1}^n~(\lambda_j \cdot\beta_j)\cdot q_j \end{eqnarray}$ $\begin{eqnarray} Bx = QD_BQ^Tx = \sum_{k=1}^n~(\mu_k \cdot\beta_k)\cdot q_j \end{eqnarray}$ Daraus ergibt sich die folgende Darstellung: $\begin{eqnarray} (Bx)^TA(Bx) &&=(Bx)^TQD_AQ^T(QD_BQ^Tx) =\\&&=(Bx)^TQD_A(Q^TQ)D_BQ^Tx=\\&&= (Bx)^TQD_AD_BQ^Tx = \\&&= \Bigl(\sum_{k=1}^{n}~(\mu_k\cdot \beta_k) \cdot q_k \Bigr)^T \cdot \Bigl( \sum_{j=1}^{n}~(\lambda_j \cdot\mu_j \cdot \beta_j )\cdot q_j\Bigr) = \\ &&=\sum_{j=1}^{n}~\lambda_j\cdot (\mu_j)^2\cdot (\beta_j)^2 = \\&&\text{Substituiere } c_j:=\|\beta_j\|^2\cdot \lambda_j\\&&=\sum_{j=1}^{n}~c_j \|\mu_j\|^2 \end{eqnarray}$ $\begin{eqnarray} x^TAx = 1 \Leftrightarrow && \Bigl(\sum_{k=1}^n~\beta_k\cdot q_k \Bigr)^T \cdot \Bigl(\sum_{j=1} ^n \lambda_j \cdot \beta_j \cdot q_j \Bigr) = 1\\&& \sum_{j=1}^n~\lambda_j \cdot (\beta_j )^2 = 1\\&& \sum_{j=1}^n~c_j = 1 \end{eqnarray}$ Da A eine SPD-Matrix ist, gilt $\begin{eqnarray} c_j:=\lambda_j \cdot (\beta_j )^2 \geq 0 \end{eqnarray}$ . Damit ergibt sich: $\begin{eqnarray} \|\|B\|\|_A &&= \max_{\|\|x\|\|_A=1}~\sqrt{(Bx)^TA(Bx)} = \\ &&= \max_{\sum_{j=1}^n~c_j = 1 \atop c_j \leq 0}~\sqrt{\sum_{j=1}^{n}~c_j \|\mu_j\|^2} = \\&& \max_{j}~\|\mu_j\| \end{eqnarray}$ Also letztendlich gilt: $\begin{eqnarray} \fbox{$\displaystyle \|B\|\|_A =\max_{j}\|\mu_j\| \quad \text{ ,mit } \sigma(B) = \{ \mu_1,...,\mu_n \}$} \end{eqnarray}$
13.07.2007, 01:25	tigerbine	Auf diesen Beitrag antworten »
Beweis (2) - Was ist das Spektrum von B? Behauptung: $\begin{eqnarray} \fbox{$\displaystyle \sigma\Bigl(p(A)\Bigr) = p\Bigl( \sigma(A) \Bigr) $} \end{eqnarray}$ Beweis -Teil 1: $\begin{eqnarray} \sigma\Bigl(p(A)\Bigr) \supseteq p\Bigl( \sigma(A) \Bigr) \end{eqnarray}$ Sei x ein Eigenvektor von A zum Eigenwert $\begin{eqnarray} \lambda_r \in \sigma(A) \end{eqnarray}$ . Dann gilt wegen $\begin{eqnarray} Ax = \lambda_r x \end{eqnarray}$ : $\begin{eqnarray} p(A)\cdot x = \sum_{j=0}^m~\alpha_j\cdot A^jx =\sum_{j=0}^m~\alpha_j\cdot \lambda_r^j\cdot x = p(\lambda_r) \cdot x \end{eqnarray}$ $\begin{eqnarray} \Rightarrow p(\lambda_r) \in \sigma\Bigl(p(A)\Bigr)\quad \forall~ r = 1,..,n \end{eqnarray}$ Beweis -Teil 2: $\begin{eqnarray} \sigma\Bigl(p(A)\Bigr) \subseteq p\Bigl( \sigma(A) \Bigr) \end{eqnarray}$ Da das char. Polynom von A über IR in Linearfaktoren zerfällt, ist A trigonalisierbar (Schur-Zerlegung R): $\begin{eqnarray} R =Q^TAQ \end{eqnarray}$ Setzt man nun R in das Polynom p ein, so folgt wegen $\begin{eqnarray} Q^T=Q^{-1} \end{eqnarray}$ $\begin{eqnarray} p(R) &&= \sum_{j=0}^m~\alpha_j\cdot R^m = \\&&= \sum_{j=0}^m ~\alpha_j \cdot (Q^TAQ)^m = \\&&=\sum_{j=0}^m ~\alpha_j \cdot Q^TA^mQ = \\ &&=Q^Tp(A)Q \end{eqnarray}$ Somit sind $\begin{eqnarray} p(R) \end{eqnarray}$ und $\begin{eqnarray} p(A) \end{eqnarray}$ ähnliche Matrizen und besitzen das gleiche Spektrum. Nun sind die Diagonaleinträge von R das Spektrum von A. Damit ergibt sich für die Diagonale von $\begin{eqnarray} R^m \end{eqnarray}$ (nachrechnen): $\begin{eqnarray} \operatorname{diag}(R^m) = (\operatorname{diag}(R))^m \end{eqnarray}$ Es ist dann also $\begin{eqnarray} p(R) \end{eqnarray}$ eine obere Dreiecksmatrix mit: $\begin{eqnarray} \sigma\Bigl(p(R)\Bigr)=\operatorname{diag}\Bigl(p(R)\Bigr) = \{p(\lambda_1),...,p(\lambda_n)\} = p\Bigl(\sigma(A) \Bigr) \end{eqnarray}$
13.07.2007, 01:26	tigerbine	Auf diesen Beitrag antworten »
Beweis (2) - Was ist \|\|p(A)\|\|_A? Mit den letzten beiden Antworten folgt nun also: $\begin{eqnarray} \|\|p(A)\|\|_A = \max_{\lambda \in \sigma(A)}~\|p(\lambda)\| \end{eqnarray}$ Wenn wir uns nun an die Konstruktion von p erinnern, dann folgt: $\begin{eqnarray} \fbox{$\displaystyle \|\|p(A)\|\|_A = \max_{\lambda \in \sigma(A)}~\|p(\lambda)\| = 0 $} \end{eqnarray}$
16.08.2007, 14:00	tigerbine	Auf diesen Beitrag antworten »
Ausblick Bislang haben wir immer den Fall Ax=b für reguläres A betrachtet. Was passiert nun, wenn A singulär ist? Was wenn A nicht quadratisch ist? Mehr dazu im Wokshop lineare Ausgleichprobleme

Neue Frage »

Antworten »

[WS] Lineare Gleichungssysteme 5 - Das CG-Verfahren

Verwandte Themen