Kondition und Eigenwerte < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:39 Sa 26.04.2014 | | Autor: | Khaine |
Hallo zusammen,
Ich bräuchte Hilfe/Ideen für kleinere Beweise bezüglich des Zusammenhangs der Kondition einer Matrix den den Betragsgrößten und -kleinsten Eigenwert. Zunächst soll gezeigt werden, dass für beliebige Matrixnormen gilt
cond(A) >= |EW_max / EW_min|.
Eigentlich weiß ich nur cond(A) = [mm] ||A||*||A^T|| [/mm] und mir ist nicht wirklich klar wie man da die EW rein bringen kann. Könnt ihr mir helfen? Dann würde ich versuchen die übrigen Aussagen erstmal alleine zu zeigen und dann konkreter zu fragen.
Vielen Dank schonmal (Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:11 Sa 26.04.2014 | | Autor: | DieAcht |
Hallo Khaine und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
> Ich bräuchte Hilfe/Ideen für kleinere Beweise bezüglich
> des Zusammenhangs der Kondition einer Matrix den den
> Betragsgrößten und -kleinsten Eigenwert. Zunächst soll
> gezeigt werden, dass für beliebige Matrixnormen gilt
> cond(A) >= |EW_max / EW_min|.
Ich empfehle dir auch die anderen Teilaufgaben zu posten,
denn in der Regel benutzt man diese für die jeweiligen
anderen Teilaufgaben.
> Eigentlich weiß ich nur cond(A) = [mm]||A||*||A^T||[/mm]
Das stimmt nur dann, wenn $A$ orthogonal ist!
Für eine reguläre Matrix $A$ definieren wir die Kondition als
[mm] \kappa(A):=\|A\|*\|A^{-1}\|.
[/mm]
> und mir ist nicht wirklich klar wie man da die EW rein bringen kann.
Es gilt:
[mm] \|A\|_2=\sqrt{\lambda_{\max}}.
[/mm]
> Könnt ihr mir helfen? Dann würde ich versuchen die
> übrigen Aussagen erstmal alleine zu zeigen und dann
> konkreter zu fragen.
Alle Normen in [mm] \IR^n, [/mm] wobei [mm] n\in\IN, [/mm] sind äquivalent.
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:20 So 27.04.2014 | | Autor: | Khaine |
> Für eine reguläre Matrix [mm]A[/mm] definieren wir die Kondition
> als
>
> [mm]\kappa(A):=\|A\|*\|A^{-1}\|.[/mm]
Richtig, das war auch ein blöder Tippfehler von mir. Die inverse war natürlich gemeint.
> Es gilt:
>
> [mm]\|A\|_2=\sqrt{\lambda_{\max}}.[/mm]
An der Stelle hast du dann die Spektralnorm verwendet oder? Soweit war ich nämlich auch schon und dann kommt man ja auf die Gleichheit. Zu zeigen wäre ja dann noch, dass der Term für alle anderen Normen größer wird. Und auch hier wüsste ich nicht wie
Edit:Wobei stimmt ja gar nicht, man landet bei Wurzel des Verhältnis der EW. Und da der Quotient größer 1 ist schätzt man die Wurzel einfach mit dem Betrag ab?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:04 So 27.04.2014 | | Autor: | DieAcht |
> > Für eine reguläre Matrix [mm]A[/mm] definieren wir die Kondition
> > als
> >
> > [mm]\kappa(A):=\|A\|*\|A^{-1}\|.[/mm]
> Richtig, das war auch ein blöder Tippfehler von mir. Die
> inverse war natürlich gemeint.
>
> > Es gilt:
> >
> > [mm]\|A\|_2=\sqrt{\lambda_{\max}}.[/mm]
> An der Stelle hast du dann die Spektralnorm verwendet
> oder?
Ja.
> Soweit war ich nämlich auch schon und dann kommt man
> ja auf die Gleichheit. Zu zeigen wäre ja dann noch, dass
> der Term für alle anderen Normen größer wird. Und auch
> hier wüsste ich nicht wie
Es gilt für eine reguläre Matrix $A$ folgende Eigenschaft:
[mm] 1\le\kappa_2(A)\le\kappa_{F}(A)\le n\kappa_{\infty}(A).
[/mm]
> Edit:Wobei stimmt ja gar nicht, man landet bei Wurzel des
> Verhältnis der EW. Und da der Quotient größer 1 ist
> schätzt man die Wurzel einfach mit dem Betrag ab?
Das verstehe ich nicht ganz. Ich empfehle dir auch mal die
komplette Aufgabenstellung zu posten. Was für Eigenschaften
besitzt etwa die Matrix $A$? Bei deiner Fragestellung ist
nicht einmal die Regularität von $A$ vorausgesetzt!
Ihr wisst bestimmt auch schon folgendes:
[mm] \|A\|_2=\sqrt{\lambda_{\text{max}}(A^T*A)}.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:38 So 27.04.2014 | | Autor: | Khaine |
| Aufgabe | | Sei A regulär. Zeigen sie mit einer zu einer Vektornorm verträglichen Matrixnorm das cond(A) >= |EW_max(A)/EW_min(A)| gilt. |
Ok dann das ganze jetzt mal Ordentlich (sorry war heute morgen noch ein bisschen vom Feiern erschöpft ) Leider weiß ich nicht ganz genau, was in der Vorlesung alles rankam da ich verhindert war, sich der Dozent nicht wirklich an das vorhandene Skript gehalten hat und ich mir erst Dienstag eine Mitschrift besorgen kann. Trotzdem bin ich optimistisch das wir das zusammen hinkriegen :) Danke an dieser Stelle schon mal für deine Hilfe.
Aktuell scheint das mein bester Ansatz zu sein.
cond(A) = ||A||*||A^-1|| = [mm] \wurzel{EW_{max}(A^T*A)}*\wurzel{EW_{max}(A^-1^T*A^-1)} [/mm] = = [mm] \wurzel{EW_{max}(A^T*A)}*\wurzel{EW_{max}((A*A^T)^-1)} [/mm] = [mm] \wurzel(EW_{max}(A^T*A)/EW_{min}(A*A^T))
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:32 So 27.04.2014 | | Autor: | DieAcht |
> Sei A regulär. Zeigen sie mit einer zu einer Vektornorm
> verträglichen Matrixnorm das cond(A) >=
> |EW_max(A)/EW_min(A)| gilt.
Das passt nun.
> cond(A) = ||A||*||A^-1|| =
> [mm]\wurzel{EW_{max}(A^T*A)}*\wurzel{EW_{max}(A^-1^T*A^-1)}[/mm] = =
> [mm]\wurzel{EW_{max}(A^T*A)}*\wurzel{EW_{max}((A*A^T)^-1)}[/mm] =
> [mm]\wurzel(EW_{max}(A^T*A)/EW_{min}(A*A^T))[/mm]
Du hast einen schweren Fehler begangen. Seien [mm] $A\$ [/mm] und [mm] $B\$
[/mm]
regulär, dann ist das Produkt auch regulär und es gilt:
[mm] (A*B)^{-1}=B^{-1}*A^{-1}.
[/mm]
Auf Grund der Aufgabenstellung würde ich folgendes benutzen:
Sei [mm] A\in K^{n\times n} [/mm] eine reguläre Matrix über einem Körper $K$.
Sei [mm] \lambda [/mm] Eigenwert von $A$, dann ist [mm] \lambda\not=0 [/mm] und [mm] \lambda^{-1} [/mm] ist Eigen-
wert von [mm] A^{-1}.
[/mm]
Der Beweis dazu ist ziemlich einfach. Sei $x$ Eigenvektor zum
Eigenwert [mm] \lambda, [/mm] dann gilt:
[mm] $Ax=\lambda [/mm] x$
[mm] \Longleftrightarrow
[/mm]
[mm] $x=\lambda A^{-1}x$
[/mm]
[mm] \Longleftrightarrow
[/mm]
[mm] $\lambda^{-1}x=A^{-1}x$
[/mm]
[mm] \Longleftrightarrow
[/mm]
[mm] \lambda^{-1} [/mm] ist Eigenwert von [mm] A^{-1},
[/mm]
wobei
[mm] \lambda\not=0
[/mm]
aus der zweiten Gleichung folgt (Wieso?).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:23 So 27.04.2014 | | Autor: | Khaine |
> Sei [mm]A\in K^{n\times n}[/mm] eine reguläre Matrix über einem
> Körper [mm]K[/mm].
> Sei [mm]\lambda[/mm] Eigenwert von [mm]A[/mm], dann ist [mm]\lambda\not=0[/mm] und
> [mm]\lambda^{-1}[/mm] ist Eigen-
> wert von [mm]A^{-1}.[/mm]
Das ist mir klar, das wollte ich in meiner Rechnung ja auch benutzen und braucht meiner Meinung nach auch nicht bewiesen zu werden.
> > cond(A) = ||A||*||A^-1|| =
> > [mm]\wurzel{EW_{max}(A^T*A)}*\wurzel{EW_{max}(A^-1^T*A^-1)}[/mm] = =
> > [mm]\wurzel{EW_{max}(A^T*A)}*\wurzel{EW_{max}((A*A^T)^-1)}[/mm] =
> > [mm]\wurzel(EW_{max}(A^T*A)/EW_{min}(A*A^T))[/mm]
>
> Du hast einen schweren Fehler begangen. Seien [mm]A\[/mm] und [mm]B\[/mm]
> regulär, dann ist das Produkt auch regulär und es gilt:
>
> [mm](A*B)^{-1}=B^{-1}*A^{-1}.[/mm]
Auch das ist klar, ich sehe gerade aber auch nicht, wo ich das falsch gemacht habe. Ich hab doch beim "rausziehen" der Invertierung die Reihenfolge vertauscht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:25 So 27.04.2014 | | Autor: | DieAcht |
Ich habe mich verlesen, sorry.
Ich würde zur Übersicht anfangen mit
[mm] \kappa_{2}^{2}(A)=\ldots,
[/mm]
denn damit hat man die Wurzel los. 
Jetzt musst du mir noch erklären wie du am Ende auf Minimum
kommst. Beachte dazu vielleicht auch nochmal
[mm] $1\le\kappa_2(A)\le\kappa_{F}(A)\le n\kappa_{\infty}(A)$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:13 So 27.04.2014 | | Autor: | Khaine |
So sehr stört mich die Wurzel jetzt nicht, aber könnte man natürlich machen, je nach dem wie aufwändig das ganze noch wird, irgendwie hab ich das Gefühl, dass ich noch relativ weit vom Ziel entfernt bin.
Deine Frage bezüglich des Minimums ist jetzt nicht ganz eindeutig. Auf das EW_min in der Formel komme ich, weil der maximale Eigenwert von der Matrix B^-1 1/EW_min von B ist (nach der Regel die du ja auch schon geschrieben hast). Oder meinst du das so, dass bisher die Rechnung korrekt ist und ich jetzt begünden soll, dass das für alle anderen Normen größer wird? Das sieht man dann doch an der zweiten Umformung $ [mm] \wurzel{EW_{max}(A^T\cdot{}A)}\cdot{}\wurzel{EW_{max}(A^-1^T\cdot{}A^-1)} [/mm] $, wenn die Spektralnorm immer am kleinsten ist wird das Produkt natürlich für alle anderen Normen größer.
Aber selbst wenn das alles jetzt so stimmen sollte muss ich ja immer noch die Wurzel und die [mm] A^T [/mm] loswerden.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:42 Mo 28.04.2014 | | Autor: | DieAcht |
Ich glaube, dass du nun durcheinander gekommen bist. Das
liegt aber auch daran, dass du am Anfang nicht die Eigen-
schaften von $A$ dazugeschrieben hast und im folgenden ich
dir dennoch probiert habe "allgemein" zu helfen. Es kommt
nämlich immer darauf an welche Eigenschaften $A$ besitzt
und welche Voraussetzung du schon kennst.
Ist $A$ regulär, dann gilt:
[mm] \kappa(A)\ge\left|\frac{\lambda_{\text{max}}(A)}{\lambda_{\text{min}}(A)}\right|.
[/mm]
Ist [mm] $A\in\IR^{m\times n}$ [/mm] mit [mm] $m\ge [/mm] n$ und [mm] $\DeclareMathOperator{\Rang}{Rang(A)}=n$, [/mm] dann gilt:
[mm] \kappa_2(A^T*A)=\frac{\lambda_{\text{max}}(A^T*A)}{\lambda_{\text{min}}(A^T*A)}.
[/mm]
Ist $A$ regulär und symmetrisch, dann gilt:
[mm] \kappa_2(A)=\left|\frac{\lambda_{\text{max}}(A)}{\lambda_{\text{min}}(A)}\right|.
[/mm]
Ist $A$ nicht symmetrisch, dann ist im Allgemeinen
[mm] \left|\frac{\lambda_{\text{max}}(A)}{\lambda_{\text{min}}(A)}\right|
[/mm]
ein schlechtes Konditionsmaß.
Ist $A$ regulär, dann gilt:
[mm] 1\le\kappa_2(A)\le\kappa_{F}(A)\le n\kappa_{\infty}(A).
[/mm]
Viele benutzen auch die Konvention
[mm] \kappa(A)=\kappa_2(A),
[/mm]
wobei ich diese Konvention nicht "gut" finde.
Ich hoffe, dass das erstmal reicht, denn mehr fällt mir
gerade ehrlich gesagt auch nicht ein. Falls du mehr wissen
willst, dann müsste ich nochmal genauer nachgucken. Es
soll dir nur klar machen, dass die Eigenschaften von $A$
sehr wichtig sind!
Kommen wir nun zurück zu deiner Aufgabe:
| Aufgabe | Sei A regulär. Zeigen Sie mit einer zu einer Vektornorm verträglichen Matrixnorm das gilt:
[mm] \kappa(A)\ge\left|\frac{\lambda_{\text{max}}(A)}{\lambda_{\text{min}}(A)}\right|. [/mm] |
Zunächst gilt offenbar durch die Voraussetzung:
[mm] \|Ax\|\le\|A\|\|x\| [/mm] für alle [mm] x\in\IR^n.
[/mm]
Nun wollen wir die Behauptung zeigen. Es gilt:
[mm] \kappa(A):=\|A\|*\|A^{-1}\|.
[/mm]
Der erste Faktor ist klar. Wir betrachten den zweiten Faktor:
[mm] \|A^{-1}\|=\max_{y\in\IR^n\setminus\{0\}}\frac{\|A^{-1}y\|}{\|y\|}\overset{y=Ax}{=}\max_{x\in\IR^n\setminus\{0\}}\frac{\|x\|}{\|Ax\|}=\max_{\|x|\|=1}\frac{1}{\|Ax\|}=\left(\min_{\|x\|=1}\|Ax\|\right)^{-1}.
[/mm]
Somit erhalten wir:
[mm] \kappa(A):=\|A\|*\|A^{-1}\|=\frac{\max_{\|x\|=1}\|Ax\|}{\min_{\|x\|=1}\|Ax\|}.
[/mm]
Ist dir nun klar, weshalb die Behauptung folgt?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:33 Mo 28.04.2014 | | Autor: | Khaine |
Danke nochmal für die ausführliche Antwort und deine Geduld.
> Es soll dir nur klar machen, dass die Eigenschaften von [mm]A[/mm]
> sehr wichtig sind!
Ist es spätestens jetzt, tut mir Leid das der Anfang so unspezifisch war.
> Ist [mm]A\in\IR^{m\times n}[/mm] mit [mm]m\ge n[/mm] und
> [mm]\DeclareMathOperator{\Rang}{Rang(A)}=n[/mm], dann gilt:
>
> [mm]\kappa_2(A^T*A)=\frac{\lambda_{\text{max}}(A^T*A)}{\lambda_{\text{min}}(A^T*A)}.[/mm]
>
> Ist [mm]A[/mm] regulär und symmetrisch, dann gilt:
>
> [mm]\kappa_2(A)=\left|\frac{\lambda_{\text{max}}(A)}{\lambda_{\text{min}}(A)}\right|.[/mm]
Das sind nebenbei erwähnt die anderen beiden Behauptungen die ich noch zeigen muss, wobei ich bei der letzteren glaube ich eine Idee hab wie das mit meiner Rechnung von oben gehen könnte. Aber jetzt erst den Teil 1) schaffen.
> Somit erhalten wir:
>
> [mm]\kappa(A):=\|A\|*\|A^{-1}\|=\frac{\max_{\|x\|=1}\|Ax\|}{\min_{\|x\|=1}\|Ax\|}.[/mm]
>
> Ist dir nun klar, weshalb die Behauptung folgt?
Soweit konnte ich dir folgen. Meine Idee war dann als nächstes "Verträglichkeitsungleichung" zu benutzen, wobei ja die Einschränkung ||x|| = 1 besteht.
Damit käme ich dann auf [mm]\kappa(A) <= \frac{max ||A||}{min ||A||}.[/mm] Aber so wirklich froh bin ich damit selbst nicht, insbesondere da ich ja Zähler und Nenner nach oben abschätze und dann der Bruch ja eigentlich alles mögliche machen kann. (Ich muss vllt dazu noch sagen dass ich eine kleine Pause im Studium eingelegt hatte und mich jetzt erst wieder an diese Art Aufgaben gewöhnen muss, sorry wenn ich mich da etwas doof anstelle)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:07 Mo 28.04.2014 | | Autor: | DieAcht |
Deine Argumentation deiner Abschätzung verstehe ich nicht.
Wir benötigen eine Abschätzung nach unten und nicht nach
oben! Dennoch gebe ich dir hiermit noch einen Tipp.
Sei [mm] x\in\IC^n\setminus\{0\} [/mm] Eigenvektor zum Eigenwert [mm] \lambda\in\IC [/mm] einer Matrix [mm] A\in\IC^{n\times n}, [/mm] d.h.
[mm] $Ax=\lambda [/mm] x$,
dann gilt mit der zugehörigen Vektornorm [mm] \|*\|\colon\IC^n\to\IR_{\ge 0}
[/mm]
[mm] \|A\|\ge\frac{\|Ax\|}{\|x\|}=\frac{|\lambda|\|x\|}{\|x\|}=|\lambda|.
[/mm]
Mit anderen Worten:
[mm] \|A\|\ge\max\{|\lambda|\mid\lambda\text{ ist Eigenwert von }A\},
[/mm]
wobei natürlich
[mm] \lambda\in\IC.
[/mm]
Alles klar?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:09 Mo 28.04.2014 | | Autor: | DieAcht |
> > Ist [mm]A[/mm] regulär und symmetrisch, dann gilt:
> >
> >
> [mm]\kappa_2(A)=\left|\frac{\lambda_{\text{max}}(A)}{\lambda_{\text{min}}(A)}\right|.[/mm]
Vielleicht mal kurz die Idee:
[mm] \kappa_2(A):=\|A\|_2*\|A^{-1}\|_2=\max_{x\not=0}\frac{\|Ax\|_2}{\|x\|_2}*\min_{x\not=0}\frac{\|Ax\|_2}{\|x\|_2}=\sqrt{\lambda_{\text{max}}(A^T*A)}*\frac{1}{\sqrt{\lambda_{\text{min}}(A^T*A)}}.
[/mm]
Entschuldige meine Notation weiter oben. Die Wurzeln aus
den Eigenwerten von
[mm] A^T*A
[/mm]
nennt man Singulärwerte von $A$, sodass es natürlich besser
ist am Ende folgende Notation zu benutzen:
[mm] \sqrt{\lambda_{\text{max}}(A^T*A)}*\frac{1}{\sqrt{\lambda_{\text{min}}(A^T*A)}}=\left|\frac{\sigma_{\text{max}}(A)}{\sigma_{\text{min}}(A)}\right|.
[/mm]
Die andere Aufgabe solltest du nun schaffen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:35 Mo 28.04.2014 | | Autor: | Khaine |
Okay, ich denke die beiden Teile mit regulären Matrizen hab ich jetzt hinbekommen. Bleibt noch $ [mm] A\in\IR^{m\times n} [/mm] $ mit $ [mm] m\ge [/mm] n $ und $ [mm] \DeclareMathOperator{\Rang}{Rang(A)}=n [/mm] $. Dann ist [mm] $A^T*A$ [/mm] doch aus [mm] $R^{m \times m} [/mm] $, aber mit Rang n oder? Und wenn eine Matrix nicht den vollen Rang hat muss die 0 doch ein EW sein, aber dann wäre der Ausdruck ja nicht definiert.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:32 Mo 28.04.2014 | | Autor: | Khaine |
.
> > Dann ist [mm]A^T*A[/mm] doch aus [mm]R^{m \times m} [/mm],
>
> Nein. ![[notok]](/images/smileys/notok.gif "[notok]")
>
> Es gilt:
>
> [mm]A\in\IR^{m\times n}[/mm]
>
> [mm]\Rightarrow A^T\in\IR^{n\times m}[/mm]
>
> [mm]\Rightarrow A^TA\in\IR^{n\times n}.[/mm]
Ahh fuck, schon wieder so richtig blöder Fehler :(
> Damit ist [mm]B:=A^TA[/mm] eine quadratische Matrix mit vollem
> Rang. Was heißt das nun für unsere Matrix [mm]B[/mm] und wie kannst du
> das nun benutzen um die Aufgabe zu lösen?
Das heißt sie ist regulär und symmetrisch, daher kann ich das Ergebnis der anderen Teilaufgabe verwenden. Danke dir, damit sollte jetzt alles zusammenpassen und ich warte gespannt auf die folgenden Aufgaben, die dann hoffentlich etwas besser klappen.
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
