Lösung nichtlineare Gleichung < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:06 Do 13.01.2005 | | Autor: | Joergi |
Hallo alle zusammen,
hier ist mal wieder eine unserer schönen Numerik- Aufgaben.
Ich hoffe ihr könnt mir weiterhelfen, denn ansonsten stehe ich echt auf dem Schlauch.
Aber seht selbst:
Sei [mm]f: \IR \to \IR[/mm] eine stetige Funktion und wir suchen eine Nullstelle von [mm]f[/mm]. Wir kennen zwei Werte [mm] a_0 < b_0[/mm] mit der Eigenschaft [mm] f(a_0) < 0[/mm] und[mm]f(b_0) > 0[/mm], wissen also, dass ein [mm]x^{\*} \in (a_0,b_0)[/mm] existieren muss mit [mm] f(x^{\*}) =0[/mm].
a.) Gegeben sei folgender Algorithmus:
[mm] \begin{matrix}
a = a_0; b = b_0; x = (a+b)/2;\\
while f(x) \not= 0 \{\\
if (f(x) < 0) a = x;\\
else b = x;\\
x = (a+b)/2;\\
\} \end{matrix}[/mm]
Zeige, dass die im Algorithmus iterativ veränderte Grösse [mm]x[/mm] gegen eine Nullstelle [mm]x^{\*}[/mm] konvergiert. Zeige, dass wenn man mit [mm]x_n [/mm] den im [mm]n[/mm]-ten Inerationsschritt [ [mm]n[/mm]-te Ausführung der while-Schleife] berechneten Wert [mm]x[/mm] bezeichnet, die Abschätzung [mm]|x_{n+1} - x^{\*}| \le 0.5|x_n - x^{\*}|[/mm] gilt.
b.) Wir versuchen den Algorithmus von a.) zu verbessern, indem wir die Berechnung von [mm]x[/mm] ändern: Wir bestimmen nun [mm]x[/mm] jeweils als die Nullstelle der Geraden, die die Punkte [mm](a,f(a)) [/mm] und [mm](b,f(b))[/mm] verbindet. Wir nehmen an, dass [mm] f \in C^2[/mm] und konvex ist, also [mm]f^{''}>0[/mm] auf dem Interval [mm][a_0,b_0][/mm]. Zeige, dass es dann nur eine Nullstelle in [mm][a_0,b_0][/mm] geben kann, die Folge der [mm]x_n[/mm] monoton wächst und gegen die Nullstelle konvergiert. Zeige weiter, dass [mm]x_{n+1} - x^{\*} = \vektor{1 - \bruch{x_n - b_0}{f(x_n) - f(b_0)} * \bruch{f(x_n) - f(x^{\*})}{x_n - x^{\*}}} * (x_n - x^{\*})[/mm].
[Ist [mm]f^"(x^{\*}) \not= 0[/mm], so wird sich im Falle der Konvergenz stets ab einem gewissen [mm]n[/mm] alles im rein konvexen oder rein konkaven Bereich von[mm]f[/mm] abspielen. Im konkaven Fall folgt dann analog die monoton fallende Konvergenz.]
c.) Zeige, dass im Fall von b.) die [mm] asymptotische[/mm] Fehlerreduktionsrate [mm]c[/mm], definiert durch [mm]c \equiv \limes_{n\rightarrow\infty} \bruch{|x_{n+1}-x^{\*}|}{|x_n-x^{\*}|}[/mm], gegeben ist durch [mm] c = 1-(b_0-x^{\*})f^{'}(x^{\*})/f(b_0)[/mm] und[mm] 0
d.) Wende mit MATLAB/MAPLE die Methoden aus a.) und b.) an, um die Nullstelle von [mm] f(x) \equiv 2 + ln(x) - 2sin(5x), x>0[/mm], zu finden. Gib die [mm]x_n[/mm] an. Ersetze im Algorithmus die Bedingung [mm] f(x) \not= 0[/mm] durch [mm]|f(x)|> \varepsilon[/mm]. Verwende [mm] \varepsilon = 10^{-10}, a_0 = 0.1[/mm] und [mm]b_0 = 5.0[/mm].
Ideenansatz folgt noch, aber leider habe ich zurzeit noch überhaupt keine Ahnung was ich mit dieser Aufgabe machen soll, denn ich verstehe nicht was das für ein Algorithmus sein soll.
So eine Schreibweise kenne ich nicht.
Es wäre schön, wenn mir jemand das zumindest schon mal erklären könnte, denn nur dann kann ich ja überhaupt irgendetwas machen.
Danke Rebekka und Jörg
|
|
| |
|
Hallo Rebekka und Jörg,
> Zeige, dass die im Algorithmus iterativ veränderte Grösse [mm]x[/mm]
> gegen eine Nullstelle [mm]x^{\*}[/mm] konvergiert. Zeige, dass wenn
> man mit [mm]x_n[/mm] den im [mm]n[/mm]-ten Inerationsschritt [ [mm]n[/mm]-te
> Ausführung der while-Schleife] berechneten Wert [mm]x[/mm]
> bezeichnet, die Abschätzung [mm]|x_{n+1} - x^{\*}| \le 0.5|x_n - x^{\*}|[/mm]
> gilt.
Ein Beispiel: f(x)=x a=-1 b=1.2
Die Nullstelle ist offensichtlich 0.
[mm]x_0=\bruch{a_0+b_0}{2}=0.1[/mm]
[mm] \Rightarrow a_1=-1 \wedge b_1=0.1[/mm]
[mm]x_1=\bruch{a_1+b_1}{2}=-0.45[/mm]
![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Konvergieren wird das bestimmt aber irgendwas stimmt nicht bei deiner Ungleichung?
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:37 Do 13.01.2005 | | Autor: | Joergi |
Hallo mathemaduenn,
erstmal herzlichen Dank dass Du uns weiterhilfst.
Also dein Beispiel kann ich nachvollziehen, aber die Ungleichung steht genau so auf unserem Aufgabenblatt.
Liebe Grüße
Rebekka
|
|
|
| |
|
Hallo Rebekka,
Dann ist wohl das Aufgabenblatt nicht ganz korrekt. Soll ja mal vorkommen. Beim Intervallhalbierungsverfahren/Bisektionsverfahren kann man nur die Intervalllänge betrachten. Der Abstand zur Nullstelle kann dabei variieren.
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:00 Fr 14.01.2005 | | Autor: | Joergi |
Hallo mathemaduenn,
leider sind die Übungen nicht wirklich an die Vorlesung angepasst. Könntest du mir daher vielleicht etwas zu Intervallhalbierungsverfahren/Bisektionsverfahren erklären.
Und es wäre sehr schön wenn du mir den Algorithmus der dort so seltsam aufgeschrieben ist erklären könntest. Mir ist diese Schreibweise nicht geläufig.
Ich glaube zwar, dass die Lösung relativ simpel sein muss, aber vielleicht macht mir auch nur diese Schreibweise zu schaffen...
Naja ich hoffe, ich nerve dich nicht. Ich würde diese Aufgabe gerne lösen, denn wir brachen die Punkte noch, nur bei mir scheint echt jemand auf der Leitung zu stehen.
Ich bin dir auf jedenfall für jede Hilfe dankbar.
Ich werde dann wohl mal die HiWi's ansprechen auf die Ungleichung.
Gruß Rebekka
|
|
|
| |
|
Hallo Rebekka,
Ich denke Mal der Algorithmus an sich wird anhand Paul's Beispielrechnung klar oder?
Was die Ungleichung angeht kannst Du ja versuchen folgendes zu betrachten:
1. Die Nullstelle liegt im Intervall [mm] [a_n,b_n]
[/mm]
2- Wie lang ist das Intervall?
3. Wie weit kann die Nst. also von [mm] a_n [/mm] oder [mm] b_n [/mm] entfernt sein?
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:22 Mo 17.01.2005 | | Autor: | Joergi |
Hallo mathemaduenn,
danke für deine Hilfe. Das Problem habe ich jetzt verstanden, aber weiter kommen wir trotz der geänderten Ungleichung dennoch nicht. Na ja.
Gruß Rebekka
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:33 Fr 14.01.2005 | | Autor: | Paulus |
Hallo alle
Warum soll das denn nicht stimmen?
Die Abfrage ist schon korrekt, und konvergieren tut das auch. Du musst nur die nächsten Werte berechnen:
[mm] $x_0=\bruch{a_0+b_0}{2}=0.1 \Rightarrow a_1=-1 \wedge b_1=0.1$
[/mm]
[mm] $x_1=\bruch{a_1+b_1}{2}=-0.45 \Rightarrow a_2=-0.45 \wedge b_2=0.1$
[/mm]
[mm] $x_2=\bruch{a_2+b_2}{2}=-0.175 \Rightarrow a_3=-0.175 \wedge b_3=0.1$
[/mm]
[mm] $x_3=\bruch{a_3+b_3}{2}=-0.0375 \Rightarrow a_4=-0.0375 \wedge b_4=0.1$
[/mm]
[mm] $x_4=\bruch{a_4+b_4}{2}=0.03125 \Rightarrow a_5=-0.0375 \wedge b_5=0.03125$
[/mm]
[mm] $x_5=\bruch{a_5+b_5}{2}=-0.003125 \Rightarrow a_6=-0.003125\wedge b_6=0.03125$
[/mm]
[mm] $x_6=\bruch{a_6+b_6}{2}=0.0140625 \Rightarrow a_7=-0.003125\wedge b_7=0.0140625$
[/mm]
[mm] $x_7=\bruch{a_7+b_7}{2}=0.00546875 \Rightarrow a_8=-0.003125\wedge b_8=0.00546875$
[/mm]
[mm] $x_8=\bruch{a_8+b_8}{2}=0.001171875 \Rightarrow a_9=-0.003125\wedge b_9=0.001171875$
[/mm]
[mm] $x_9=\bruch{a_9+b_9}{2}=-0.0009765625 \Rightarrow a_{10}=-0.0009765625\wedge b_{10}=0.001171875$
[/mm]
[mm] $x_{10}=\bruch{a_{10}+b_{10}}{2}=0.00009765625 \Rightarrow a_{10}=-0.0009765625\wedge b_{10}=0.00009765625$
[/mm]
[mm] $x_{11}=\bruch{a_{11}+b_{11}}{2}=-0.000439453125 \Rightarrow a_{12}=-0.000439453125\wedge b_{12}=0.00009765625$
[/mm]
...
...
Ich denke, jetzt sollte es klar sein! 
Mit lieben Grüssen
Paul
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:55 Fr 14.01.2005 | | Autor: | Joergi |
Hallo Paul,
erst einmal auch vielen Dank an dich, dass du mir weiterhilfst.
Jetzt habe ich auch verstanden, was das für ein Algorithmus sein soll. Dann werde ich mich mal an die erste Aufgabe setzen.
Stelle dann die Ergebnisse hier wieder rein.
Bis dann
Rebekka
|
|
|
| |
|
Hallo Paul,
Das Verfahren an sich stimmt schon. Aber wenn Du Dir die Beträge der berechneten [mm] x_i [/mm] anschaust wirst Du feststellen das die nicht immer um 0.5 kleiner sind als das vorangegangene [mm] x_{i-1}. [/mm] Selbiges würde aber die Abschätzung (für dieses Bsp.) aussagen.
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:50 So 16.01.2005 | | Autor: | Wurzelpi |
Hallo zusammen!
Also, zu a):
Der Algorithmus im Teil a) ist in C++ übersetzt.
D.h., so oder ein wenig anders könnte man ein kleines Programm zu diesem Algorithmus schreiben.
Die Abschätzung ist definitiv falsch und wurde von unserem Assistentnen geändert.
Es muss lauten:
[mm]|x-x^*|<= (b_0 -a_0)/2^{n+1}[/mm].
Dennoch habe ich weder einen vernünftigen Ansatz zu diesem Teil, noch zu einem anderen Aufgabenteil!
Ich hoffe, das wird sich noch ändern!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:25 Mo 17.01.2005 | | Autor: | Joergi |
Hallo Marcel,
danke nochmal für deine Mail.
Bist du inzwischen schlauer? Bei mir steht irgendwie ein Nilpferd auf der Leitung.
Ich krieg nichts von der Aufgabe auf die Reihe. Und das wo wir die Punkte brauchen. Na ja kannst dich ja mal melden, wenn du etwas hast.
Liebe Grüße
Rebekka
|
|
|
| |
|
Hallo,
Wenn ihr Ergebnisse aus vorangegangenen Aufgaben bentzen dürft ohne sie gezeigt zu haben könnt ihr euch ja mal die Formel aus b genauer anschauen.
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:46 Di 18.01.2005 | | Autor: | Wurzelpi |
Hallo!
Ja, da hat Mathemaduenn recht: Einfach b) betrachten, einpaar kleine Umformungen und fertig ist.
Danke!
Aber weder bei a), was mir völlig klar isr, noch bei b) komme ich weiter.
Vielleicht hat da noch jemand einen guten Tip.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:10 Di 18.01.2005 | | Autor: | Joergi |
Hallo ich schon wieder,
leider war ich noch mit Deutsch beschäftigt, aber jetzt hab ich wieder Zeit.
Also mir ist klar, dass ich [mm]x_{n+1} - x^{\*} = \vektor{1 - \bruch{x_n - b_0}{f(x_n) - f(b_0)} * \bruch{f(x_n) - f(x^{\*})}{x_n - x^{\*}}} * (x_n - x^{\*})[/mm]umforme, indem ich [mm](x_n - x^{\*})[/mm]auf die andere Seite bringe. Aber dann versagt es bei mir.
Ich weiß nicht wie ich dann auf[mm]c \equiv \limes_{n\rightarrow\infty} \bruch{|x_{n+1}-x^{\*}|}{|x_n-x^{\*}|}[/mm]komme.
Kann mir da jemand auf die Sprünge helfen?
Danke
Rebekka
|
|
|
| |
|
Hallo Rebekka,
[mm]x_{n+1} - x^{\*} = \vektor{1 - \bruch{x_n - b_0}{f(x_n) - f(b_0)} * \bruch{f(x_n) - f(x^{\*})}{x_n - x^{\*}}} * (x_n - x^{\*})[/mm]
[mm]\bruch{x_{n+1} - x^{\*}}{(x_n - x^{\*})} = \vektor{1 - \bruch{x_n - b_0}{f(x_n) - f(b_0)} * \bruch{f(x_n) - f(x^{\*})}{x_n - x^{\*}}}[/mm]
Jetzt solltest Du auf beiden seiten die Grenzübergänge machen. Dann steht links c und rechts kannst Du durch Rumrechnen mit den Grenzwerten den gewünschten Ausdruck erhalten. Dabei sind folgende Infos aus b nützlich:
[mm] x_n [/mm] konvergiert gegen die Nullstelle von f
d.h. [mm] \limes_{n\rightarrow\infty} x_n=x^{\*}
[/mm]
[mm] \limes_{n\rightarrow\infty} f(x_n)=0
[/mm]
Alles klar?
gruß
mathemaduenn
|
|
|
| |
|
Hi!
Mach´s nicht komplizierter, als es ist!
> Also
> [mm]x_{n+1} - x^{\*} = \vektor{1 - \bruch{x_n - b_0}{f(x_n) - f(b_0)} * \bruch{f(x_n) - f(x^{\*})}{x_n - x^{\*}}} * (x_n - x^{\*})[/mm]
>
>
> [mm]\bruch{x_{n+1} - x^{\*}}{(x_n - x^{\*})} = \vektor{1 - \bruch{x_n - b_0}{f(x_n) - f(b_0)} * \bruch{f(x_n) - f(x^{\*})}{x_n - x^{\*}}}[/mm]
>
> ist klar.
![[ok]](/images/smileys/ok.gif "[ok]")
> Dann weiter:
> [mm]\limes_{n\rightarrow\infty} \vektor{\bruch{x_{n+1} - x^{\*}}{(x_n - x^{\*})}} = \limes_{n\rightarrow\infty} \vektor{\vektor{1 - \bruch{x_n - b_0}{f(x_n) - f(b_0)} * \bruch{f(x_n) - f(x^{\*})}{x_n - x^{\*}}}}[/mm]
>
>
> und dann:
> [mm]c = 1- \limes_{n\rightarrow\infty} \vektor{\bruch{x_n - b_0}{f(x_n) - f(b_0)} * \bruch{f(x_n) - f(x^{\*})}{x_n - x^{\*}}}[/mm]
>
>
Da gilt [mm]x_n \to x^{\*}[/mm] und [mm]f(x_n) \to f(x^{\*}=0[/mm] :
>
[mm]c= 1- \bruch{b_0-x^{\*}}{f(b_0)}* \limes_{n\rightarrow\infty} \vektor{\bruch{f(x_n)-f(x^{\*})}{x_n-x^{\*}}}[/mm]
>
Und was ist [mm]\limes_{n\rightarrow\infty} \vektor{\bruch{f(x_n)-f(x^{\*})}{x_n-x^{\*}}}[/mm]?
Richtig: Der Differenzenquotient!!!! (das durch 0 habe ich übersehen)
Fertig.
|
|
|
| |
|
Hallo nochmal,
Hab doch noch ein Vorschlag zu b:
Mit f(a)<0 muß f(x)<0 gelten. Dies ist wohl das was zu zeigen wäre.
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Mi 19.01.2005 | | Autor: | Joergi |
Hy Wurzelpi, hier noch was zur Aufgabe 40:
a) [mm] \alpha*L^{T}Lx+A^{T}Ax=A^{T}b
[/mm]
[mm] \Rightarrow (\alpha*L^{T}L+A^{T}A)x=A^{T}b
[/mm]
[mm] \Rightarrow [/mm] x= [mm] (\alpha*L^{T}L+A^{T}A)^{-1}A^{T}b
[/mm]
[mm] \Rightarrow [/mm] x= [mm] (\alpha*I+A^{T}A)^{-1}A^{T}b [/mm] ist eindeutige Lösung sodass Kern(A) [mm] \cap [/mm] Kern(L) = {0}.
Ich denke, dass hier nach x gefragt ist und nicht nach b, besonders in Bezug auf Aufgabenteil b), zudem ist b ja auch immer gegeben, und warum sollte dieser Vektor gesucht werden!?Ansonsten musste ja nur nach b auflösen, aber meiner Meinung nach Blödsinn!
b) [mm] x_{\alpha}= (\alpha*I+A^{T}A)^{-1}A^{T}b [/mm] nach Aufg. 40a
= [mm] (VSU^{T}USV^{T}+\alpha*I)^{-1}*A^{T}*b, [/mm] da A = [mm] USV^{T} [/mm] und [mm] A^{T}A [/mm] = [mm] VSU^{T}, [/mm] also nur einsetzen!
= [mm] (VS^{2}V^{T}+\alpha*I)^{-1}*VSU^{T}b
[/mm]
= [mm] (V(S^{2}+\alpha*I)V^{T})^{-1}*VSU^{T}b
[/mm]
= [mm] V(S^{2}+\alpha*I))^{-1}*SU^{T}b
[/mm]
= [mm]\bruch{SU^{T}b}{S^{2}+\alpha*I}*V[/mm]
= [mm]\summe_{i=1}^{r}\bruch{\sigma_{i}*u_{i}^{T}b}{\sigma_{i}^{2}+\alpha*I}*v_{i}[/mm]
und damit die Behauptung!Beachte, in der Aufgabenstellung muss es [mm] u^{T} [/mm] heißen und nicht [mm] b^{T}, [/mm] auch ein Fehler, sonst geht es nämlich nicht!
So, über c) brüte ich noch, kommt aber bestimmt heute Abend noch, streng mich an!Ach ja, das ganze läuft unter dem Stichwort Tichonov-Regularisierung!
P.S.: Treff mich nachher noch mit Rebekka, dabei sollte noch was rumkommmen! Wenn Du mal Deine Lösungen als Pdf postest, wäre nett, besonders das mit Maple, denn ich hab das nicht und weiß auch garnicht damit umzugehen, gurke noch immer mit Derive rum (schäm), denn bis nachher
LG Jörg
|
|
|
| |
|
Hallo Jörg,
> a) [mm]\alpha*L^{T}Lx+A^{T}Ax=A^{T}b
[/mm]
> [mm]\Rightarrow (\alpha*L^{T}L+A^{T}A)x=A^{T}b
[/mm]
> [mm]\Rightarrow[/mm]
> x= [mm](\alpha*L^{T}L+A^{T}A)^{-1}A^{T}b
[/mm]
wieso existiert diese Inverse
> [mm]\Rightarrow[/mm] x= [mm](\alpha*I+A^{T}A)^{-1}A^{T}b[/mm] ist
> eindeutige Lösung sodass Kern(A) [mm]\cap[/mm] Kern(L) = {0}.
Das ist eine gdw. Beziehung wenn die Inverse existiert gilt das und wenns gilt existiert diese Inverse.
> b) [mm]x_{\alpha}= (\alpha*I+A^{T}A)^{-1}A^{T}b[/mm] nach Aufg.
> 40a
> = [mm](VSU^{T}USV^{T}+\alpha*I)^{-1}*A^{T}*b,[/mm] da A = [mm]USV^{T}[/mm]
> und [mm]A^{T}A[/mm] = [mm]VSU^{T},[/mm] also nur einsetzen!
> = [mm](VS^{2}V^{T}+\alpha*I)^{-1}*VSU^{T}b
[/mm]
> = [mm](V(S^{2}+\alpha*I)V^{T})^{-1}*VSU^{T}b
[/mm]
> = [mm]V(S^{2}+\alpha*I))^{-1}*SU^{T}b
[/mm]
> = [mm][mm]\bruch{SU^{T}b}{S^{2}+\alpha*I}*V[/mm]
[/mm]
Jetzt mal ehrlich Matrizen unterm Bruchstrich das sieht doch nicht schön aus
Und wieso darfst du die Matrizen vertauschen?
= [mm][mm]\summe_{i=1}^{r}\bruch{\sigma_{i}*u_{i}^{T}b}{\sigma_{i}^{2}+\alpha*I}*v_{i}[/mm]
[/mm]
> und damit die Behauptung!
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:04 Mi 19.01.2005 | | Autor: | Joergi |
Hallo zusammen,
wir sind zu der Überzeugung gekommen, dass man bei a) so vorgehen kann, da die Matrix symm. pos. def. ist.
Ein weiterer Aufgabenteil lautet nun:
Es sei[mm]r=n[/mm]. Für welche [mm] \alpha[/mm] ist [mm]cond_2( \alpha*I + A^{T}*A)
Wir haben uns dazu folgendes überlegt:
[mm]cond_2(A) = \vektor{A \\ \wurzel{ \alpha} *I} = ||\vektor{A \\ \wurzel{ \alpha} *I}||_2 * ||\vektor{A \\ \wurzel{ \alpha} *I}^{+}||_2[/mm].
[mm]\vektor{A \\ \wurzel{ \alpha} *I}^{T}*\vektor{A \\ \wurzel{ \alpha} *I} = \alpha*I + A^{T}*A = V((\Sigma)^2+ \alpha *I)V^{T}[/mm]
und daher [mm]||\vektor{A \\ \wurzel{ \alpha} *I}||_2 = \lambda_{max}^{1/2}(\Sigma^2+\alpha*I) = ((\sigma_1)^2 + \alpha)^{1/2}[/mm]
Weiter ist
[mm]\vektor{A \\ \wurzel{ \alpha} *I}^{+} = [(\vektor{A \\ \wurzel{ \alpha} *I})^{T}*\vektor{A \\ \wurzel{ \alpha} *I}]^{-1} * (\vektor{A \\ \wurzel{ \alpha} *I})^{T} = (\alpha*I + A^{T}*A)^{-1} (\vektor{A \\ \wurzel{ \alpha} *I})^{T}[/mm]
folglich ist
[mm] \vektor{A \\ \wurzel{ \alpha} *I}^{+} *[\vektor{A \\ \wurzel{ \alpha} *I}^{+}]^T = (\alpha*I + A^{T}*A)^{-1} = V(((\Sigma)^2+ \alpha *I))^{-1}V^{T}[/mm]
und damit
[mm]||(\vektor{A \\ \wurzel{ \alpha} *I})^{+}||_2 = \lambda_{max}^{1/2}[(\Sigma^2+\alpha*I) ^{-1}] = \bruch{1}{(\sigma_n^2+ \alpha)^{1/2}}[/mm].
Also insgesamt
[mm]cond_2(A) = (\bruch{\sigma_1^2 + \alpha}{\sigma_n^2 + \alpha})^{1/2}[/mm]
Wie können wir nun die [mm]cond_2(A^{T}A + \alpha *I)[/mm] berechnen wie oben?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:16 Mi 19.01.2005 | | Autor: | Wurzelpi |
Hi!
Bei Teil c) habt ihr meiner Meinung nach falsch angesetzt.
Das alpha spielt nur auf der linken Seite der Ungleichung eine Rolle.
[mm] cond_2(A) [/mm] ist nur der Quotient aus dem grössten und dem kleinsten Singulärwert.
Durch die Addition von alpha*Einheitsmatrix zu [mm] A^T*A [/mm] änderen sich die Eigenwerte von [mm] A^T*A [/mm] jeweil um alpha.
Ferner ist auch die [mm] cond_2(A)=Wurzel [/mm] aus [mm] cond_2(A^T*A).
[/mm]
Meiner Meinung nach, muss man die beiden Seiten irgendwie nach alpha auflösen, aber das gelingt mir icht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:02 Mi 19.01.2005 | | Autor: | Joergi |
Hy Wurzelpi!
Vielleicht könnte man ja auch so an das Problem rangehen!?
[mm]cond_2(A) = \bruch{\sigma_1}{\sigma_n}[/mm]. Zudem wissen wir aus Aufg. 25c):
[mm]cond_2(A^{T}A)=[cond_2(A)]^{2} = (\bruch{\sigma_1}{\sigma_n})^2[/mm].
Was ist aber jetzt [mm] cond_2(A^{T}A+ \alpha*I)????????? [/mm] Da hakt es noch, bleib aber dran!Für Ideen wäre ich immer zu haben 
Gruss Jörg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:51 Mi 19.01.2005 | | Autor: | Wurzelpi |
Hi!
Okay.
Wir haben ja schon mal die Kondition von [mm] A^T*A [/mm] und die Kondition von A in Verbindung gebracht.
Mit Aufgabe 25c) wissen wir, dass wir die Kondition von A als Quotient aus dem größten und den kleinsten Singuläwert darstellen können, also auch über die entsprechenden Eigenwerte (Def. der Singulärwerte).
Durch die Addition von einem Vielfachen der Einheitsmatrix vergößern wir wir die Eigenwerte von [mm] A^t*A [/mm] entsprechend.
Links steht also etwa: (lambda_max +alpha)/(lambda_min +alpha).
Das soll nun kleiner sein als die Wurzel von dem Kram nur ohne die alphas.
Leider habe ich es nicht geschafft, alpha zu isolieren.
ICh hoffe aber, dass der Ansatz einigermassen richtig ist!
Bis dann!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:40 Mi 19.01.2005 | | Autor: | Joergi |
Hy Wurzelpi,
angenommen das stimmt was Du da gepostet hast und ich hier keinen Blödsinn gemacht habe, dann könnte das so aussehen:
[mm]\bruch{\lambda_{max}+\alpha}{\lambda_{min}+\alpha}< \wurzel{\bruch{\lambda_{max}}{\lambda_{min}}[/mm].
[mm] \Rightarrow[/mm] [mm]\bruch{\lambda_{max}^{2}+2\alpha*\lambda_{max}+\alpha^{2}}{\lambda_{min}^{2}+2\alpha*\lambda_{min}+\alpha^{2}} - \bruch{\lambda_{max}}{\lambda_{min}} <0[/mm].
[mm] \Rightarrow[/mm] [mm]\lambda_{max}^{2}\lambda_{min}+2\alpha\lambda_{max}\lambda_{min}+ \alpha^{2}\lambda_{min}-\lambda_{min}^{2}\lambda_{max}-2\alpha\lambda_{max}\lambda_{min}-\alpha^{2}\lambda_{max}<0[/mm].
[mm] \Rightarrow[/mm] [mm]\lambda_{max}^{2}\lambda_{min}-\lambda_{min}^{2}\lambda_{max}+\alpha^{2}(\lambda_{min}-\lambda_{max})<0[/mm].
[mm] \Rightarrow[/mm] [mm]\alpha^{2}<\bruch{\lambda_{min}^{2}\lambda_{max}-\lambda_{max}^{2}\lambda_{min}}{\lambda_{min}-\lambda_{max}}[/mm].
[mm] \Rightarrow[/mm] [mm]\alpha^{2}<\lambda_{min}\lambda_{max}[/mm].
Da [mm]\alpha>0[/mm] laut Aufgabenstellung, kommt nur die Lösung [mm]\alpha=\wurzel{\lambda_{min}\lambda_{max}}[/mm] in Frage.
Schau mal drüber ob ich hier keinen Bockmist gemacht habe!
Gruss Jörg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:22 Mi 19.01.2005 | | Autor: | Wurzelpi |
Hallo Jörg!
Mit vereinten Kräften bekommen wir das nun raus.
Ich hing gleich beim 2. Schritt (schäm).
Egal.
Also:
Rechentechnisch alles okay bis auf den letzen Schritt.
Kleinster EW - grösster EW < 0!!!
Also dreht sich das Zeichen um.
Somit sollte gelten (Dein Schluss ist auch nicht richtig!):
Für alle alpha, die grösser als der Wurzel aus dem Produkt von grösstem und kleinstem EW, folgt die Beh.!
Dieses Produkt ist ja gerade auch wieder das Produkt des max und min Singuläwertes.
Ich hoffe, jetzt passt es!
War auch ne Menge Arbeit diese Woche!
|
|
|
| |
|
Hallo Jörg,Rebekka,
> [mm] \alpha*I [/mm] + [mm] A^{T}*A [/mm] = [mm] V((\Sigma)^2+ \alpha *I)V^{T}
[/mm]
Hier steht schon etwas sehr richtiges.
[mm] V((\Sigma)^2+ \alpha *I)V^{T} [/mm] ist ja eine Singulärwertzerlegung der Matrix [mm] \alpha*I [/mm] + [mm] A^{T}*A [/mm] (*) So könnt ihr die Kondition bestimmen. Wie man auf diese Gleichung kommt verlangt vielleicht noch 1/2 Zwischenschritte.
gruß
mathemaduenn
Edit: (*)
Natürlich nur wenn alpha entsprechend gewählt ist. Hier muß man wohl doch die Kondition ganz normal mittels
[mm] \wurzel{\bruch{\lambda_{max}(B^TB)}{\lambda_{min}(B^TB)}} [/mm] berechnen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:08 Do 20.01.2005 | | Autor: | Joergi |
Danke für deine Mühen.
Wir sehen dann mal weiter. Haben die Übung eben abgegeben.
Danke
Rebekka
|
|
|
|
![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]"){kind=small}
![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]"){kind=small}
![[lichtaufgegangen]](/images/smileys/lichtaufgegangen.gif "[lichtaufgegangen]"){kind=small}
![[anbet]](/images/smileys/anbet.gif "[anbet]"){kind=small}
