Verständnisfragen f. Klausur

07.07.2008, 11:54

num

Verständnisfragen f. Klausur

Hallo,

ich schreibe morgen meine Klausur und habe noch einige Verständnisfragen.

Also das hier ist mehr oder weniger unser Skript: http://wwwmath1.uni-muenster.de:8000/num...WS04/skript.pdf

Auf Seite 59 steht unsere Definition der Potenzmethode, die ich aufgrund des Beispiels auch verstanden habe. Nun weiß ich aber, dass man mit der Potenzmethode auch den kleinsten Eigenwert berechnen kann, mir ist allerdings überhaupt nicht klar wie das geht.

Kennt jemand eine gute Seite, wo die QR-Zerlegung gut und mit Beispielen erklärt ist?

Wäre dankbar wenn mir jemand behilflich ist!

07.07.2008, 11:59

tigerbine

Auf diesen Beitrag antworten »

RE: Verständnisfragen MORGEN KLAUSUR!
Wie möchtest du die QR-Zerlegung bestimmen?

07.07.2008, 12:11

num

Auf diesen Beitrag antworten »

Wie meinst du das? Ich hab die leider noch nicht verstanden...

Mir ist gerade noch eine Frage eingefallen, die mir auch wie die erste wichtiger als die QR-Zerlegung ist.
Wir hatten folgende Aufgabe:
Geben Sie ein Fixpunktverfahren der Form $\begin{eqnarray*} x_{k+1} = g(x_k) \end{eqnarray*}$ an, das für alle
Startwerte $\begin{eqnarray*} x_0 \geq -1 \end{eqnarray*}$ gegen eine Lösung der Gleichung $\begin{eqnarray*} x^3-x-1 = 0 \end{eqnarray*}$ konvergiert.

Die Musterlösung sieh wie folgt aus:

Def. $\begin{eqnarray*} x^{k+1} = (1+3)^{1/3}=g(x_k) \end{eqnarray*}$
$\begin{eqnarray*} g'(x)=1/3 (1+x)^{-2/3} \end{eqnarray*}$
für $\begin{eqnarray*} x=0 \end{eqnarray*}$ ist | $\begin{eqnarray*} g'(x) \end{eqnarray*}$ | $\begin{eqnarray*} \leq 1/3 < 1 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ g kontrahierend in $\begin{eqnarray*} IR^+ \end{eqnarray*}$
Für $\begin{eqnarray*} x_0 \geq -1 \end{eqnarray*}$ ist $\begin{eqnarray*} x_1 \geq 0 \end{eqnarray*}$
für $\begin{eqnarray*} k \qeq 1 \end{eqnarray*}$ g: $\begin{eqnarray*} R^+ \to R^+ \end{eqnarray*}$
folgt mit dem Banachschen FPsatz $\begin{eqnarray*} x_k \end{eqnarray*}$ konv. gegen einen eind. FP

Das macht in meinen Augen auch alles Sinn. Ich versteh nur nicht, wieso ich dieses g(x) so bestimme. Ich hätte jetzt einfach z.B. das Newtonverfahren auf die gegebene Funktion angewendet und dann zeigen können, dass die Funktion (lokal) konv.

07.07.2008, 12:21

tigerbine

Auf diesen Beitrag antworten »

Nun mal in der Hektik nicht alles durcheinander.

QR-Zerlegung: Da gibt es doch verschiedene Methoden, die Matrizen zu bestimmen. Ich nenne einmal Gram-schmidt, Householder, Givens.
Bestimmung des kleinsten Eigenwertes mittels Potenzmethode
Fixpunktverfahren

Zu 3.

Wir haben eine Funktion f mit $\begin{eqnarray*} f(x)=x^3-x-1 \end{eqnarray*}$ . Die Nullstellen dieser Funktion sind Fixpunkte der Funktion $\begin{eqnarray*} g(x)=x^3-1 \end{eqnarray*}$ , wie man durch umstellen der Gleichung erkennt.

Deinen Iterartionsanfang kann ich nicht nachvollziehen, da dort nur eine Zahl steht, $\begin{eqnarray*} (1+3)^{\frac{1}{3}} \end{eqnarray*}$

Das Newtonverfahren hätte die Funktion f benutzt, du sollst aber das äquivalente Fixpunktproblem lösen.

07.07.2008, 12:33

num

Auf diesen Beitrag antworten »

QR-Zerlegung: Da gibt es doch verschiedene Methoden, die Matrizen zu bestimmen. Ich nenne einmal Gram-schmidt, Householder, Givens. <-- achso, wir hatten in der Vorlesung nur das Housholder-Verfahren

Bestimmung des kleinsten Eigenwertes mittels Potenzmethode <-- ist mir gerade klar geworden, ich schiebe quasi alle EW in den negativen Bereich, also als Bsp mal, wenn ich folgende Kreise habe.
$\begin{eqnarray*} K_1: M_1=5, r_1=4, K_2: M_2=4, r_2= 4, K_3: M_3=4, r_3=2, K_4: M_4=6, r_4=2 \end{eqnarray*}$
Dann wende ich die Potenzmethode auf B = A-10E an, wobei A meine gegebene Matrix ist.
Das Ergebnis ist dann c und $\begin{eqnarray*} \lambda_{min}=c+10 \end{eqnarray*}$

Wir haben eine Funktion f mit $\begin{eqnarray*} f(x)=x^3-x-1 \end{eqnarray*}$ . Die Nullstellen dieser Funktion sind Fixpunkte der Funktion $\begin{eqnarray*} g(x)=x^3-1 \end{eqnarray*}$ , wie man durch umstellen der Gleichung erkennt.

Deinen Iterartionsanfang kann ich nicht nachvollziehen, da dort nur eine Zahl steht, $\begin{eqnarray*} (1+3)^{\frac{1}{3}} \end{eqnarray*}$ <--- da hab ich mich wohl vertippt, richtig soll dort $\begin{eqnarray*} (1+x)^{\frac{1}{3}} \end{eqnarray*}$ stehen

Das Newtonverfahren hätte die Funktion f benutzt, du sollst aber das äquivalente Fixpunktproblem lösen. <-- ok danke

07.07.2008, 12:44

tigerbine

Auf diesen Beitrag antworten »

Householder
Nun kommt ein Postzusammenschnitt zum Thema Householder. Zu Punkt 3 geht es im nächsten Post.(-> hier )

Zitat:

Nun soll eine volle QR-Zerlegung bestimmt werden. Wieder hat A den Rang n. Es ist dann

$\begin{eqnarray*} A = QR \Leftrightarrow Q^{-1}A = R \Leftrightarrow Q^{T}A = R \end{eqnarray*}$

Ähnlich dem Prinzip beim Gaußalgorithmus ist es nun das Ziel die Matrix $\begin{eqnarray*} Q^T \end{eqnarray*}$ zu konstruieren, so dass $\begin{eqnarray*} Q^TA \end{eqnarray*}$ eine obere Dreiecksmatrix ist. Man schreibt:

$\begin{eqnarray*} Q^T = Q_l \cdot .... \cdot Q_1,\quad l:=\min\{m-1,n\} \end{eqnarray*}$

Dabei annulliert $\begin{eqnarray*} Q_j \end{eqnarray*}$ die Eintrage der j-ten Spalte unterhalb der Diagonalen.

Zitat:

Householder-Spiegelung (Definition)

$\begin{eqnarray*} H:=I_n - 2\cdot \underbrace{uu^T}_{Dyade}\quad \text{mit } u \in \mathbb R^n,~||u||_2=1 \end{eqnarray*}$

Konstruktion von u

x sei nun der Teil des Spaltenvektors von "A", den es zu annullieren gilt, zzgl. des Diagonalelements.

$\begin{eqnarray*} u:=x + \text{sign}(x_1)\cdot ||x||_2 \cdot e_1 \quad \text{(Bedingungen für die zu erzeugenden Nullen)} \end{eqnarray*}$

$\begin{eqnarray*} \beta:=\frac{2}{u^Tu} \quad \text{(Normierung)} \end{eqnarray*}$

$\begin{eqnarray*} H=I-\beta\cdot uu^T \end{eqnarray*}$

Eigenschaften der Matrix H

H ist symmetrisch, dies folgt direkt aus der Symmetrie von I und der Dyade.
H ist orthogonal, denn
$\begin{eqnarray*} H^TH = (I_n-2uu^T)^T(I_n-2uu^T) = I - 4uu^T + 4u\underbrace{(u^Tu)}_{1}u^T = I_n \end{eqnarray*}$
u ist ein Eigenvektor von H, denn
$\begin{eqnarray*} Hu = (I_n-2uu^T) u = u - 2u(u^Tu) = (-1) \cdot u \end{eqnarray*}$
Der Eigenraum von (-1) ist eindimensional.
H hat sonst nur noch den Eigenwert 1. Die Dimension seines Eigenraums ist (n-1). Da H symmetrisch und regulär ist, gibt es eine ONB aus Eigenvektoren von H, so dass H bzgl. dieser Diagonalagestalt hat .Sei v ein zu u orthogonaler Vektor. Dann gilt:
$\begin{eqnarray*} Hv = v - 2u\underbrace{u^Tv}_{0} = v \end{eqnarray*}$
H ist eine Spiegelung, denn
$\begin{eqnarray*} \det(H) = -1 \end{eqnarray*}$
Hx ist ein Vielfaches des ersten Einheitsvektors mit dem Faktor $\begin{eqnarray*} \alpha = - \text{sign}(x_1)||x||_2 \end{eqnarray*}$

Beweis:

Die Vektoren x und u unterscheiden sich nur im ersten Eintrag, d.h. es gilt $\begin{eqnarray*} u_j=x_j,~j=2,...,n \end{eqnarray*}$ . So kann man Dyade wie folgt schreiben:

$\begin{eqnarray*} U = \begin{pmatrix}u_1u_1 &u_1x_2 & \hdots & u_1x_n \\ x_2u_1 &x_2x_2 & \hdots & x_2x_n \\ \vdots & \vdots & \ddots & \vdots \\ x_nu_1 & x_nx_2 & \hdots & x_nx_n \end{pmatrix} \end{eqnarray*}$

Nun ist

$\begin{eqnarray*} Hx = (I-\beta uu^T)x = x - \frac{2}{u^Tu}\cdot Ux \end{eqnarray*}$ .

Für den Nenner des Faktors ß gilt:

$\begin{eqnarray*} u^Tu &&= \sum_{k=1}^n~u_k^2 = u_1^2 + \sum_{k=2}^n~x_k^2 \\ &&=\Bigl(x_1+\text{sign}(x_1)||x||_2\Bigr)^2 + \sum_{k=2}^n~x_k^2 \\&&= x_1^2 + 2x_1\cdot \text{sign}(x_1)||x||_2 +(\text{sign}(x_1)||x||_2)^2 + \sum_{k=2}^n~x_k^2 \\&& = 2\cdot \Bigl( ||x||_2^2+x_1 \cdot \text{sign}(x_1)||x||_2 \Bigr) \end{eqnarray*}$

Für den j-ten Eintrag des Vektors Ux gilt:

$\begin{eqnarray*} (Ux)_j = \sum_{k=1}^{n}~(u_ju_k)x_k \end{eqnarray*}$

Für j=1 gilt:

$\begin{eqnarray*} (Ux)_1&& = \sum_{k=1}^n~(u_1u_k)x_k = u_1 \cdot \Bigl(u_1x_1 + \sum_{k=2}^n~x_kx_k \Bigr)\\ &&=u_1 \cdot \Bigl((x_1 + \text{sign}(x_1)\cdot ||x||_2)x_1 +\sum_{k=2}^n~x_kx_k \Bigr) \\&& =u_1\cdot \Bigl( ||x||_2^2 + x_1 \cdot \text{sign}(x_1)||x||_2\Bigr) \end{eqnarray*}$

$\begin{eqnarray*} (Hx)_1&&=[(I-\beta\cdot uu^T)x]_1 = x_1-\beta\cdot (Ux)_1 \\&& = x_1 - \beta\cdot u_1\cdot \Bigl( ||x||_2^2 + x_1 \cdot \text{sign}(x_1)||x||_2\Bigr) \\&& = x_1 - u_1\\&& = -\text{sign}(x_1)||x||_2 \end{eqnarray*}$

Für j =2,...,n gilt:

$\begin{eqnarray*} (Ux)_1&& = \sum_{k=1}^n~(x_ju_k)x_k = \\&&=x_ju_1x_1 + \sum_{k=2}^n~(x_jx_k)x_k \\&&=x_ju_1x_1 + x_j\cdot \sum_{k=2}^n~(x_k)^2 = x_j\cdot (u_1x_1 + \sum_{k=2}^n~(x_k)^2) \\&&= x_j\cdot (x_1^2+x_1\cdot \text{sign}(x_1)||x||_2 + \sum_{k=2}^n~(x_k)^2) \\&& = x_j\cdot (||x||_2^2 + x_1\cdot \text{sign}(x_1)||x||_2) \end{eqnarray*}$

$\begin{eqnarray*} (Hx)_j=x_j -x_j = 0 \end{eqnarray*}$

Somit ist Hx ein Vielfaches des ersten Einheitsvektors mit obigem Faktor.

Zitat:

Wie hängen nun die eingangs erwähnten Matrizen $\begin{eqnarray*} Q_i \end{eqnarray*}$ und die Matrizen H zusammen? Mit entsprechenden Dimensionen gilt:

$\begin{eqnarray*} Q_i = \begin{pmatrix}\underbrace{I}_{(i-1) \times (i-1)} &\underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)}&\underbrace{H_i}_{(n+1-i)\times (n+1-i)} \end{pmatrix} \end{eqnarray*}$

Auch die Matrizen $\begin{eqnarray*} Q_i \end{eqnarray*}$ sind symmetrisch. Es gilt:

$\begin{eqnarray*} Q_i^T&&= \begin{pmatrix}\underbrace{I}_{(i-1) \times (i-1)} &\underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)}&\underbrace{H_i^T}_{(n+1-i)\times (n+1-i)} \end{pmatrix} \\&&=\begin{pmatrix}\underbrace{I}_{(i-1) \times (i-1)} &\underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)}&\underbrace{H_i}_{(n+1-i)\times (n+1-i)} \end{pmatrix} \\&&=Q_i \end{eqnarray*}$

Ebenso sind sie orthogonal:

$\begin{eqnarray*} Q_i^TQ_i &&= \begin{pmatrix}\underbrace{I^TI}_{(i-1) \times (i-1)} &\underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)}&\underbrace{H_i^TH_i}_{(n+1-i)\times (n+1-i)} \end{pmatrix} \\&&= I \end{eqnarray*}$

Und mit der Rechenregel für Blockdiagonalmatrizen folgt auch sofort:

$\begin{eqnarray*} \det(Q_i)=-1 \end{eqnarray*}$

Handelt es sich auch um eine Householder-Matrix? Dazu muss man nur einen Vektor $\begin{eqnarray*} \hat u_i \end{eqnarray*}$ finden mit:

$\begin{eqnarray*} Q_i = I - \frac{2}{\hat u_i^T \hat u_i} \cdot \hat u_i \hat u_i^T \end{eqnarray*}$

Wählt man nun:

$\begin{eqnarray*} (\hat u_i)^T = ( \underbrace{0}_{(i-1)},~\underbrace{u_i}_{(n+1-i)})^T \end{eqnarray*}$

Dann ist:

$\begin{eqnarray*} \frac{2}{\hat u_i^T \hat u_i} = \frac{2}{u_i^T u_i} \end{eqnarray*}$

$\begin{eqnarray*} \hat U_i = \begin{pmatrix} \underbrace{0}_{(i-1) \times (i-1)} & \underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)} &\underbrace{U_i}_{(n+1-i) \times (n+1-i)} \end{pmatrix} \end{eqnarray*}$

Damit ergibt:

$\begin{eqnarray*} I_n - \beta \cdot \hat U_i &&= \begin{pmatrix} \underbrace{I_{i-1}}_{(i-1) \times (i-1)} & \underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)} &\underbrace{I_{n+1-i}-\beta \cdot U_i}_{(n+1-i) \times (n+1-i)} \end{pmatrix} =\begin{pmatrix} \underbrace{I_{i-1}}_{(i-1) \times (i-1)} & \underbrace{0}_{(i-1) \times (n+1-i)}\\ \underbrace{0}_{(n+1-i) \times (i-1)} &\underbrace{H_i}_{(n+1-i) \times (n+1-i)} \end{pmatrix} \\ && = Q_i \end{eqnarray*}$

Somit sind die $\begin{eqnarray*} Q_i \end{eqnarray*}$ auch Householder-Matrizen.

Zitat:

Im Therorie Workshop wurden 3 Wege vorgestellt, eine (sie ist ja nicht eindeutig) QR-Zerlegung einer Matrix A zu bestimmen. Dies soll nun anhand der folgenden Matrix A geschehen. Bei den Berechnungen soll auf die Konstruktiven Formeln (im Gegensatz zu den Vorgehensweisen bei der Implementierung) zurückgegriffen werden.

$\begin{eqnarray*} A=\begin{pmatrix} 1&5&4 \\ -2&1&3 \\ 2&0&-2 \end{pmatrix} \end{eqnarray*}$

Zitat:

$\begin{eqnarray*} A^{(1)}=\begin{pmatrix} 1&5&4 \\ -2&1&3 \\ 2&0&-2 \end{pmatrix}\Rightarrow x^{(1)} = \begin{pmatrix}1\\-2\\2 \end{pmatrix} \end{eqnarray*}$

Somit ergibt sich:

$\begin{eqnarray*} u^{(1)} &&= \begin{pmatrix}1\\-2\\2 \end{pmatrix} + (+1) \cdot \sqrt{1^2+2^2+2^2} \cdot \begin{pmatrix}1\\0\\0 \end{pmatrix} \\&&= \begin{pmatrix}1\\-2\\2 \end{pmatrix} + 3 \cdot \begin{pmatrix}1\\0\\0 \end{pmatrix} = \begin{pmatrix}4\\-2\\2 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \beta^{(1)} = \frac{2}{(u^{(1)})^Tu^{(1)}} = \frac{2}{4^2+2^2+^2} = \frac{1}{12} \end{eqnarray*}$

$\begin{eqnarray*} U_1= u^{(1)}(u^{(1)})^T = \begin{pmatrix} 16&-8&8\\-8&4&-4\\8&-4&4 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} H_1 = I_3- \beta^{(1)} \cdot U =\frac{1}{3}\cdot \begin{pmatrix} -1&2&-2\\2&2&1\\-2&1&2 \end{pmatrix} = Q_1 \end{eqnarray*}$

Und somit erhält man schließlich:

$\begin{eqnarray*} Q_1 \cdot A^{(1)}&& = \frac{1}{3}\cdot \begin{pmatrix} -1&2&-2\\2&2&1\\-2&1&2 \end{pmatrix} \begin{pmatrix} 1&5&4 \\ -2&1&3 \\ 2&0&-2 \end{pmatrix} \\&&= \begin{pmatrix} -3&-1&2 \\ 0&4&4 \\ 0&-3&-3 \end{pmatrix} \end{eqnarray*}$

**************************************************
Nun geht es in Runde 2.

$\begin{eqnarray*} A^{(2)} = \begin{pmatrix}4&4 \\ -3&-3 \end{pmatrix} \Rightarrow x^{(2)} = \begin{pmatrix} 4 \\-3 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} u^{(2)} = \begin{pmatrix} 4 \\-3 \end{pmatrix} + (+1)\cdot \sqrt{4^2+3^2} \cdot \begin{pmatrix}1 \\ 0\end{pmatrix} = \begin{pmatrix}9 \\-3 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \beta^{(2)} = \frac{2}{9^2+3^2} = \frac{1}{45} \end{eqnarray*}$

$\begin{eqnarray*} U_2 = \begin{pmatrix} 81&-27 \\ -27 & 9 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} H_2= I_2 - \beta^{(2)}\cdot U_2 = \begin{pmatrix} -0.8& 0.6 \\ 0.6 & 0.8 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} Q_2 = \begin{pmatrix}1&0&0\\0&-0.8&0.6 \\ 0&0.6 & 0.8 \end{pmatrix} \end{eqnarray*}$

Und damit:

$\begin{eqnarray*} Q_2Q_1A^{(1)} &&=\begin{pmatrix}1&0&0\\0&-0.8&0.6 \\ 0&0.6 & 0.8 \end{pmatrix}\begin{pmatrix} -3&-1&2 \\ 0&4&4 \\ 0&-3&-3 \end{pmatrix}\\&& = \begin{pmatrix} -3&-1&2 \\ 0&-5&-5 \\ 0&0&0 \end{pmatrix} \end{eqnarray*}$

**************************************************

Somit ist die volle QR-Zerlegung fertig. Wir erhalten:

$\begin{eqnarray*} R = \begin{pmatrix} -3&-1&2 \\ 0&-5&-5 \\ 0&0&0 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} Q^{-1} = Q_2Q_1 = \frac{1}{3} \cdot \begin{pmatrix}1&0&0\\0&-0.8&0.6 \\ 0&0.6 & 0.8 \end{pmatrix}\begin{pmatrix} -1&2&-2\\2&2&1\\-2&1&2 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} Q &&=\frac{1}{3} \cdot \begin{pmatrix} -1&2&-2\\2&2&1\\-2&1&2 \end{pmatrix}\begin{pmatrix}1&0&0\\0&-0.8&0.6 \\ 0&0.6 & 0.8 \end{pmatrix} \\&&= \begin{pmatrix} -\frac{1}{3} & -\frac{14}{15} & -\frac{2}{15} \\ \frac{2}{3} & -\frac{1}{3} & \frac{2}{3} \\ -\frac{2}{3} & \frac{2}{15} & \frac{11}{15} \end{pmatrix} \end{eqnarray*}$

Es ist also:

$\begin{eqnarray*} A=QR \Leftrightarrow \begin{pmatrix} 1&5&4 \\ -2&1&3 \\ 2&0&-2 \end{pmatrix} = \begin{pmatrix} -\frac{1}{3} & -\frac{14}{15} & -\frac{2}{15} \\ \frac{2}{3} & -\frac{1}{3} & \frac{2}{3} \\ -\frac{2}{3} & \frac{2}{15} & \frac{11}{15} \end{pmatrix}\begin{pmatrix} -3&-1&2 \\ 0&-5&-5 \\ 0&0&0 \end{pmatrix} \end{eqnarray*}$

07.07.2008, 12:47

Sly

Auf diesen Beitrag antworten »

Zitat:

Original von num
Wie meinst du das? Ich hab die leider noch nicht verstanden...

Mir ist gerade noch eine Frage eingefallen, die mir auch wie die erste wichtiger als die QR-Zerlegung ist.
Wir hatten folgende Aufgabe:
Geben Sie ein Fixpunktverfahren der Form $\begin{eqnarray*} x_{k+1} = g(x_k) \end{eqnarray*}$ an, das für alle
Startwerte $\begin{eqnarray*} x_0 \geq -1 \end{eqnarray*}$ gegen eine Lösung der Gleichung $\begin{eqnarray*} x^3-x-1 = 0 \end{eqnarray*}$ konvergiert.

Die Musterlösung sieh wie folgt aus:

Def. $\begin{eqnarray*} x^{k+1} = (1+3)^{1/3}=g(x_k) \end{eqnarray*}$
$\begin{eqnarray*} g'(x)=1/3 (1+x)^{-2/3} \end{eqnarray*}$
für $\begin{eqnarray*} x=0 \end{eqnarray*}$ ist | $\begin{eqnarray*} g'(x) \end{eqnarray*}$ | $\begin{eqnarray*} \leq 1/3 < 1 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ g kontrahierend in $\begin{eqnarray*} IR^+ \end{eqnarray*}$
Für $\begin{eqnarray*} x_0 \geq -1 \end{eqnarray*}$ ist $\begin{eqnarray*} x_1 \geq 0 \end{eqnarray*}$
für $\begin{eqnarray*} k \qeq 1 \end{eqnarray*}$ g: $\begin{eqnarray*} R^+ \to R^+ \end{eqnarray*}$
folgt mit dem Banachschen FPsatz $\begin{eqnarray*} x_k \end{eqnarray*}$ konv. gegen einen eind. FP

Das macht in meinen Augen auch alles Sinn. Ich versteh nur nicht, wieso ich dieses g(x) so bestimme. Ich hätte jetzt einfach z.B. das Newtonverfahren auf die gegebene Funktion angewendet und dann zeigen können, dass die Funktion (lokal) konv.

lokal konvergiert, ja eben!

Wenn aber der Startwert beliebig größer als -1 gewählt werden kann, ist es unwahrscheinlich schwieriger zu zeigen, dass das dann auch konvergiert. (Und in diesem Beispiel würd ich das noch nicht mal unbedingt als sicher vermuten).

Man hat es ja auch am Freitag gesagt: Bei solchen Aufgaben mit den Ausdrücken so lange rumspielen, bis man eine Gleichung nach x stehen hat, auf die man dann den Banachschen Fixpunktsatz anwenden kann!

07.07.2008, 12:49

tigerbine

Auf diesen Beitrag antworten »

Iteration
Wie gesagt, f sieht so aus:

$\begin{eqnarray*} f(x)=x^3-x-1 \end{eqnarray*}$

Möchte man die Nullstellen berechnen, so macht man den Ansatz:

$\begin{eqnarray*} 0=x^3-x-1 \end{eqnarray*}$

Dies kann man nun ja mal umstellen. (Definitionsmengen beachten!)

$\begin{eqnarray*} x = x^3-1 \end{eqnarray*}$ oder $\begin{eqnarray*} x = \sqrt[3]{x+1} \end{eqnarray*}$

Nun gilt es eben zu Prüfen, ob für die daraus zu erhaltenen Iterationen die Voraussetzungen des banachschen Fixpunktsatzes erfüllt sind.

07.07.2008, 13:18

num

Auf diesen Beitrag antworten »

RE: Iteration
$\begin{eqnarray*} x = x^3-1=g(x) \end{eqnarray*}$ wäre für mich auch naheliegender gewesen
die "Rechnung müsste ja analog" sein
da $\begin{eqnarray*} g'(x)=3x^2 \end{eqnarray*}$
für $\begin{eqnarray*} x=0 \end{eqnarray*}$ ist | $\begin{eqnarray*} g'(x) \end{eqnarray*}$ | $\begin{eqnarray*} =0 < 1 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ g kontrahierend in $\begin{eqnarray*} IR^+ \end{eqnarray*}$
Für $\begin{eqnarray*} x_0 \geq -1 \end{eqnarray*}$ ist $\begin{eqnarray*} x_1 \geq 0 \end{eqnarray*}$ <-- überprüf ich das hier mittels g' oder mittels g? Ich tendiere zu g', bin mir aber nicht hunderprozentig sicher.
für $\begin{eqnarray*} k \geq 1 \end{eqnarray*}$ g: $\begin{eqnarray*} R^+ \to R^+ \end{eqnarray*}$
folgt mit dem Banachschen FPsatz $\begin{eqnarray*} x_k \end{eqnarray*}$ konv. gegen einen eind. FP

Danke euch! Ihr habt mir schon ganz gut weitergeholfen!
Sly, du scheinst ja auch die Vorlesung zu besuchen.
Was denkst du denn, was für die Klausur am wichtigsten is?
Kommt man mit LR-Zerlegung, Newtonverfahren ( da benötige ich ja $\begin{eqnarray*} (f'(x))^{-1}, es wird immer von invertierbar gesprochen. Wann ist eine Funktion denn invertierbar, sobald die Ableitung ungleich 0 ist?) \end{eqnarray*}$ , Gerschgorin, Lagrange-Interpolation, Potenzmethode schon gut voran?
Auf was würdest du noch achten?

07.07.2008, 14:26

tigerbine

Auf diesen Beitrag antworten »

RE: Iteration

Zitat:

Original von num

für $\begin{eqnarray*} x=0 \end{eqnarray*}$ ist | $\begin{eqnarray*} g'(x) \end{eqnarray*}$ | $\begin{eqnarray*} =0 < 1 \end{eqnarray*}$

Das ist von der Formulierung her doch sehr wüst. Wie lauten denn die Kriterien für Banach?

V ist ein Banachraum
$\begin{eqnarray*} \Phi:~X \to X \end{eqnarray*}$ ist eine Selbstabbildung,d.h. $\begin{eqnarray*} \text{Im}(\Phi) \subseteq X \end{eqnarray*}$
X ist eine abgeschlossene Teilmenge von V
$\begin{eqnarray*} \Phi:~X \to X \end{eqnarray*}$ ist eine Kontraktion

$\begin{eqnarray*} ||\Phi(x)-\Phi(y)|| \leq \kappa \cdot ||x-y|| \quad x,y \in X,~\kappa(0,1) \end{eqnarray*}$

Gut, 1 sollte mit $\begin{eqnarray*} V=\mathbb R \end{eqnarray*}$ erfüllt sein. Interessant wird es ja erst bei der Teilmenge X. Da ist mir euer Ansatz schon nicht klar. Erst soll für alle Startwerte $\begin{eqnarray*} x_0 \geq -1 \end{eqnarray*}$ argumentiert werden, dann wird $\begin{eqnarray*} X=\mathbb R^{+} \end{eqnarray*}$ gewählt. Imho ist das Intervall [-1,0] nicht leer.

$\begin{eqnarray*} g_1(x)=x^3-1,~g_1'(x)=3x^2 \end{eqnarray*}$

$\begin{eqnarray*} g_2(x)=\sqrt[3]{x+1},~g_2'(x)=\frac{1}{3} \cdot (x+1)^{-\frac{2}{3}} \end{eqnarray*}$

In Bildern sollte dann klar machen, warum man sich bei der Forderung "für alle" für Variante 2 entschieden hat.

07.07.2008, 19:03

Sly

Auf diesen Beitrag antworten »

RE: Iteration

Zitat:

Danke euch! Ihr habt mir schon ganz gut weitergeholfen!
Sly, du scheinst ja auch die Vorlesung zu besuchen.
Was denkst du denn, was für die Klausur am wichtigsten is?
Kommt man mit LR-Zerlegung, Newtonverfahren ( da benötige ich ja $\begin{eqnarray*} (f'(x))^{-1}) \end{eqnarray*}$ , es wird immer von invertierbar gesprochen. Wann ist eine Funktion denn invertierbar, sobald die Ableitung ungleich 0 ist?), Gerschgorin, Lagrange-Interpolation, Potenzmethode schon gut voran?
Auf was würdest du noch achten?

Ich schätze, das ist schonmal ein guter Ansatz.
Aber aufpassen: Nicht die Funktion ist in diesem Zusammenhang invertierbar, sondern die zugehörige Jacobi-Matrix der Nullstelle!

Ich würde mir aber auch mal Interpolation nach Newton und Neville anschauen. B-Splines sind wahrscheinlich eh zu schwierig, und die haben wir auch nur marginal angesprochen.
Fehlerrechnung würde ich aber auch nicht ignorieren! Also den Stoff des ersten Kapitels. Unvermeidbarer Fehler und so weiter. Und ich würde auch mal stumpf den Satz über die Fehlerabschätzung bei linearen Gleichungssystemen anschauen. In dem Zusammenhang sollte man auch wissen, wie man die Kondition einer Matrix ausrechnet usw.

Viel mehr kann ich leider auch nicht sagen ^^

09.07.2008, 09:54

num

Auf diesen Beitrag antworten »

Ich wollte euch nochmal danken! Gott