Maß für die Invertierbarkeit einer Matrix

[egonmarkin]

Hallo

Bekanntlich ist eine Matrix invertierbar, wenn ihre Determinante
ungleich Null ist.

Wenn ich auf dem Computer mit Real-Zahlen arbeite, dann bekomme ich
nicht problemlos die Aussage, ob
eine Zahl Null ist oder nicht, sondern, dass di Zahl eventuell sehr,
sehr klein ist. Mittels der Determinante kann ich also nicht testen,
ob eine wie auch immer numerisch erhaltene Matrix invertierbar ist
oder es wäre, wenn der Computer keine numrischen Fehler machen würde.

Das führt mich zur - sehr praxisrelevanten - Frage, "wie gut" eine
Matrix invertierbar ist, also ein Maß dafür finden. Die Determinante
zu nehmen, scheidet offensichtlich aus.

Fruß
E.M.

[karl]

Post by egonmarkin
Hallo
Bekanntlich ist eine Matrix invertierbar, wenn ihre Determinante
ungleich Null ist.
Wenn ich auf dem Computer mit Real-Zahlen arbeite, dann bekomme ich
nicht problemlos die Aussage, ob
eine Zahl Null ist oder nicht, sondern, dass di Zahl eventuell sehr,
sehr klein ist. Mittels der Determinante kann ich also nicht testen,
ob eine wie auch immer numerisch erhaltene Matrix invertierbar ist
oder es wäre, wenn der Computer keine numrischen Fehler machen würde.
Das führt mich zur - sehr praxisrelevanten - Frage, "wie gut" eine
Matrix invertierbar ist, also ein Maß dafür finden. Die Determinante
zu nehmen, scheidet offensichtlich aus.
Fruß
E.M.

Vielleicht hilft Dir das:

http://en.wikipedia.org/wiki/Condition_number
ciao

Karl

[egonmarkin]

Post by karl

Post by egonmarkin
Hallo
Bekanntlich ist eine Matrix invertierbar, wenn ihre Determinante
ungleich Null ist.
Wenn ich auf dem Computer mit Real-Zahlen arbeite, dann bekomme ich
nicht problemlos die Aussage, ob
eine Zahl Null ist oder nicht, sondern, dass di Zahl eventuell sehr,
sehr klein ist. Mittels der Determinante kann ich also nicht testen,
ob eine wie auch immer numerisch erhaltene Matrix invertierbar ist
oder es wäre, wenn der Computer keine numrischen Fehler machen würde.
Das führt mich zur - sehr praxisrelevanten - Frage, "wie gut" eine
Matrix invertierbar ist, also ein Maß dafür finden. Die Determinante
zu nehmen, scheidet offensichtlich aus.
Fruß
E.M.

http://en.wikipedia.org/wiki/Condition_number
ciao
Karl- Zitierten Text ausblenden -
- Zitierten Text anzeigen -

Hallo Karl,

vielen Dank für den Tipp.

Ich bin fündig geworden im Internet. Aber ich habe gleich neue
Fragen...

Die Konditionszahl ist das Produkt der Norm der Matrix mit der Norm
der inversen Matrix.
Welche Norm ist denn gemeint?

Ergeben vielleicht glücklicherweise alle Normen dasselbe Ergebnis?

Komme ich bei der Berechnung der Konditionszahl darum herum, die
Matrix zu invertieren?

Und last not least: Wie wird die Konditionszahl denn verkostet? Ich
meine, ist eine Konditionszahl von 100 "klein" oder "gross" ? Was ist
die Schwelle zur exzellenten, guten, schlechten, ganz schlechten und
miserablen Konditioniertheit? Oder unterschieden sich die diese
Schwellen, je nachdem, sie gross (=wieviele Zeilen/Spaltan) die Matrix
hat?

Gruß und Dank

e.m

[karl]

Post by egonmarkin
Ich bin fündig geworden im Internet. Aber ich habe gleich neue
Fragen...

Das mußt Du Dir selber erarbeiten oder jemand anders antwortet. Ich
bin kein Numerikfachmann.

Ciao

Karl

[Bastian Erdnuess]

In Matlab sind zwei Funktionen zur Berechnung der Konditionszahl
vorhanden (ich glaube cond und rcond oder so). Eine von den beiden
Funktionen ist sehr schnell, da sie nicht die tatsächliche
Konditionszahl berechnet, sondern ein Schätzung dafür angibt, die als
ein Maß der Invertierbarkeit ausreichen sollte. Vielleicht findest du
den Algorithmus dazu im Octave Projekt im Internet.

Man nimmt in der Regel so weit ich weiß die Spektralnorm. Aber
wahrscheinlich ist das Ergebnis mit anderen Normen qualitativ ähnlich.

Nimmst du den Logarithmus von der Konditionszahl, dann hast du in etwa
die Anzahl an signifikanten Stellen, die du bei der Invertierung
verlierst. (Logarithmus entsprechend des Zahlensystems, in dem du
rechnest. Also wahrscheinlich 2 oder 10.)

Eine Konditionszahl von 100 ist also noch erträglich. Da verlierst du
nur 2 Stellen. Kritisch wirds so bei 10^15, da bleibt dann fast nix
mehr übrig, je nach Datentyp.

[JCH]

"egonmarkin" <***@gmx.de> schrieb im Newsbeitrag news:***@q2g2000cwa.googlegroups.com...
On 9 Feb., 09:59, karl <***@nononet.com> wrote:

[...]

Und last not least: Wie wird die Konditionszahl denn verkostet? Ich
meine, ist eine Konditionszahl von 100 "klein" oder "gross" ? Was ist
die Schwelle zur exzellenten, guten, schlechten, ganz schlechten und
miserablen Konditioniertheit? Oder unterschieden sich die diese
Schwellen, je nachdem, sie gross (=wieviele Zeilen/Spaltan) die Matrix
hat?
Siehe hierzu auch:
http://de.wikipedia.org/wiki/Hilbert-Matrix

Beispiel:
http://home.arcor.de/janch/janch/_news/20070209-hilbert/

[Christopher Creutzig]

Post by egonmarkin
Die Konditionszahl ist das Produkt der Norm der Matrix mit der Norm
der inversen Matrix.
Welche Norm ist denn gemeint?

Zu jeder Norm gibt es eine Konditionszahl der Matrix. Aber je nach
Größe der Matrizen kann man eine Zahl M angeben, so dass die Normen sich
höchstens um diesen Faktor unterscheiden. Das ist ein klassisches
Ergebnis der Analysis/Topologie: Auf dem R^n (und auch dem C^n) sind
alle Normen äquivalent.

Post by egonmarkin
Komme ich bei der Berechnung der Konditionszahl darum herum, die
Matrix zu invertieren?

Nicht, wenn Du die Konditionszahl wirklich ausrechnen willst, nein.

Post by egonmarkin
Und last not least: Wie wird die Konditionszahl denn verkostet? Ich

Ganz, ganz grob gesagt kannst Du beim Invertieren eine Matrix mit
Konditionszahl 2^n davon ausgehen, dass die letzten n Dezimalstellen im
Ergebnis einfach nur Rundungsmüll sind. Wie gesagt: Nur als erste Näherung.

Aber mal so ganz allgemein gesagt: Wer numerisch Matrizen invertiert,
macht etwas falsch. Wozu sollte man das tun wollen? Zu allen
Anwendungen, die mir einfallen, gibt es stabilere und meistens auch noch
schnellere Alternativen. Außer zum erechnen der Konditionszahl, aber
auch das ist nur ein theoretisches Konstrukt, welches in einer
„Anwendung“ (tolles Wort, bei dem keiner so genau weiß, was es
eigentlich bedeutet, zumindest wenn es jemand anders benutzt) wohl kaum
jemals auftauchen wird.


Gruß,
Christopher

[egonmarkin]

Post by Christopher Creutzig

Post by egonmarkin
Die Konditionszahl ist das Produkt der Norm der Matrix mit der Norm
der inversen Matrix.
Welche Norm ist denn gemeint?

Zu jeder Norm gibt es eine Konditionszahl der Matrix. Aber je nach
Größe der Matrizen kann man eine Zahl M angeben, so dass die Normen sich
höchstens um diesen Faktor unterscheiden. Das ist ein klassisches
Ergebnis der Analysis/Topologie: Auf dem R^n (und auch dem C^n) sind
alle Normen äquivalent.

Post by egonmarkin
Komme ich bei der Berechnung der Konditionszahl darum herum, die
Matrix zu invertieren?

Nicht, wenn Du die Konditionszahl wirklich ausrechnen willst, nein.

Post by egonmarkin
Und last not least: Wie wird die Konditionszahl denn verkostet? Ich

Ganz, ganz grob gesagt kannst Du beim Invertieren eine Matrix mit
Konditionszahl 2^n davon ausgehen, dass die letzten n Dezimalstellen im
Ergebnis einfach nur Rundungsmüll sind. Wie gesagt: Nur als erste Näherung.
Aber mal so ganz allgemein gesagt: Wer numerisch Matrizen invertiert,
macht etwas falsch. Wozu sollte man das tun wollen? Zu allen
Anwendungen, die mir einfallen, gibt es stabilere und meistens auch noch
schnellere Alternativen. Außer zum erechnen der Konditionszahl, aber
auch das ist nur ein theoretisches Konstrukt, welches in einer
,,Anwendung" (tolles Wort, bei dem keiner so genau weiß, was es
eigentlich bedeutet, zumindest wenn es jemand anders benutzt) wohl kaum
jemals auftauchen wird.
Gruß,
Christopher

Hallo,

ich sage mal allen, wie ich weiter gekommen bin.

Bei einer quadratischen Matrix, die nur Diagonalelemente hat, kann man
die Invertierbarkeit ja prüfen, indem man schaut, ob alle
Diagonalelement ungleich Null sind.

Die qualtiative Aussage "es ist so oder nicht" kann man sozusagen
quantifizieren, indem man den Quotienten aus dem kleinsten und den
groessten Diagolalelement betrachtet.

Dieses Verfahren wird in der Praxis angewendet, etwa in der Robotik,
wenn man durch Untersuchung der Jacobimatrix oder ähnlich
aussagefähiger Matrizen feststellen will, ob man sich in Arbeitsraum
nahe einer sogenannten Singularität des Arbeitsraumes befindet.

Nun sind nicht alle quadratischen Matrizen Diagonalmatrizen. Man kann
aber jede Matrix mittels SVD in das Produkt dreier Matrizen zerlegen.
Die mittlere Matrix ist eine Diagonalmatrix, die äußeren Matrizen
brauchen in diesem Zusammenhang nicht beachtet zu werden. Man testet
einfach die mittlere Matrix, und erhält die gesuchte "quantitative
Aussage".

Gruß
EM

[Peter Niessen]

Post by egonmarkin
Dieses Verfahren wird in der Praxis angewendet, etwa in der Robotik,
wenn man durch Untersuchung der Jacobimatrix oder ähnlich
aussagefähiger Matrizen feststellen will, ob man sich in Arbeitsraum
nahe einer sogenannten Singularität des Arbeitsraumes befindet.

Was ist denn eine Singularität des Arbeitsraumes?
Kannst du da mal ein Beispiel aus der Robotik nennen?

[egonmarkin]

Post by Peter Niessen

Post by egonmarkin
Dieses Verfahren wird in der Praxis angewendet, etwa in der Robotik,
wenn man durch Untersuchung der Jacobimatrix oder ähnlich
aussagefähiger Matrizen feststellen will, ob man sich in Arbeitsraum
nahe einer sogenannten Singularität des Arbeitsraumes befindet.

Was ist denn eine Singularität des Arbeitsraumes?
Kannst du da mal ein Beispiel aus der Robotik nennen?
--
Mit freundlichen Grüssen
Peter Nießen

Hallo Herr Nießen,

bei Parallelkinematiken oder Seriellen Robotern fragt man sich
natürlich, wie sich die Orientierung des Werkzeuges(serielle
Kinematik) oder die Orientierung des Roboters (Parallelkinematik)
differentiell ändert, wenn man differentiell Parameter der Gelenke
ändert (typisch bei bei Seriellkinematiken, etwa Winkeländerungen)
oder Beinlängen ändert (typisch bei Parallelkinematiken wie Stewart
Platform).

So ein Robotet kann an einigen Stellen des Arbeitsraumes Freiheiten
verlieren (er kann nich nicht mehr bewegen wie sonst), oder er hat
keinen Halt mehr (wird ungewollterweise beweglich). Das ist eine
Singularität.

Gruß
Egon Markin

[Peter Niessen]

Post by egonmarkin

Post by Peter Niessen

Post by egonmarkin
Dieses Verfahren wird in der Praxis angewendet, etwa in der Robotik,
wenn man durch Untersuchung der Jacobimatrix oder ähnlich
aussagefähiger Matrizen feststellen will, ob man sich in Arbeitsraum
nahe einer sogenannten Singularität des Arbeitsraumes befindet.

Was ist denn eine Singularität des Arbeitsraumes?
Kannst du da mal ein Beispiel aus der Robotik nennen?
--
Mit freundlichen Grüssen
Peter Nießen

Hallo Herr Nießen,
bei Parallelkinematiken oder Seriellen Robotern fragt man sich
natürlich, wie sich die Orientierung des Werkzeuges(serielle
Kinematik) oder die Orientierung des Roboters (Parallelkinematik)
differentiell ändert, wenn man differentiell Parameter der Gelenke
ändert (typisch bei bei Seriellkinematiken, etwa Winkeländerungen)
oder Beinlängen ändert (typisch bei Parallelkinematiken wie Stewart
Platform).
So ein Robotet kann an einigen Stellen des Arbeitsraumes Freiheiten
verlieren (er kann nich nicht mehr bewegen wie sonst), oder er hat
keinen Halt mehr (wird ungewollterweise beweglich). Das ist eine
Singularität.

Danke für die Erläuterung.

[Roland Franzius]

Post by egonmarkin
Hallo
Bekanntlich ist eine Matrix invertierbar, wenn ihre Determinante
ungleich Null ist.
Wenn ich auf dem Computer mit Real-Zahlen arbeite, dann bekomme ich
nicht problemlos die Aussage, ob
eine Zahl Null ist oder nicht, sondern, dass di Zahl eventuell sehr,
sehr klein ist. Mittels der Determinante kann ich also nicht testen,
ob eine wie auch immer numerisch erhaltene Matrix invertierbar ist
oder es wäre, wenn der Computer keine numrischen Fehler machen würde.
Das führt mich zur - sehr praxisrelevanten - Frage, "wie gut" eine
Matrix invertierbar ist, also ein Maß dafür finden. Die Determinante
zu nehmen, scheidet offensichtlich aus.

Eine Matrix A ist mit linearen Methoden numerisch instabil invertierbar,
wenn zwei oder mehrere Eigenwerte e_k im Vergleich zur Numerikpräzision
eps und dem Spektralradius r(A) dicht beieinander liegen.

|e_i-e_k|/r(A) ~ 1

Dann bildet man nämlich nicht das charakteristische Polynom

det (A- k Id) =0 sondern det(A - (k Id + sum dk_i Z_i) =0
und löst für die Inverse nicht

B.A = Id sondern B.A = (sum dk_i Z_i) Id

wobei dk_i Rundungsfehler und Z_i eine Basis der nxn-Matrizen sind.

Es gibt Formeln für die 2. Ableitungen von Determinanten und Eigenwerten
von Matrizen für die Taylorentwicklung. Man muß dann versuchen, die
Basis Z_k so zu transformieren, dass das gestörte charakteristische
Polynom faktorisiert in die in dk linearen und die vergleichbar großen
quadratischen Terme für die nahezu entarteten Unterräume.

[Roland Franzius]

Post by egonmarkin
Hallo
Bekanntlich ist eine Matrix invertierbar, wenn ihre Determinante
ungleich Null ist.
Wenn ich auf dem Computer mit Real-Zahlen arbeite, dann bekomme ich
nicht problemlos die Aussage, ob
eine Zahl Null ist oder nicht, sondern, dass di Zahl eventuell sehr,
sehr klein ist. Mittels der Determinante kann ich also nicht testen,
ob eine wie auch immer numerisch erhaltene Matrix invertierbar ist
oder es wäre, wenn der Computer keine numrischen Fehler machen würde.
Das führt mich zur - sehr praxisrelevanten - Frage, "wie gut" eine
Matrix invertierbar ist, also ein Maß dafür finden. Die Determinante
zu nehmen, scheidet offensichtlich aus.

Eine Matrix A ist mit linearen Methoden numerisch instabil invertierbar,
wenn zwei oder mehrere Eigenwerte e_k im Vergleich zur Numerikpräzision
eps und dem Spektralradius r(A) dicht beieinander liegen.

|e_i-e_k|/r(A) ~ eps

Dann bildet man nämlich nicht das charakteristische Polynom

det (A- k Id) =0 sondern det(A - (k Id + sum dk_i Z_i) =0
und löst für die Inverse nicht

B.A = Id sondern B.A = (sum dk_i Z_i) Id

wobei dk_i Rundungsfehler und Z_i eine Basis der nxn-Matrizen sind.

Es gibt Formeln für die 2. Ableitungen von Determinanten und Eigenwerten
von Matrizen für die Taylorentwicklung. Man muß dann versuchen, die
Basis Z_k so zu transformieren, dass das gestörte charakteristische
Polynom faktorisiert in die in dk linearen und die vergleichbar großen
quadratischen Terme für die nahezu entarteten Unterräume.

[Alois Steindl]

Post by Roland Franzius
Eine Matrix A ist mit linearen Methoden numerisch instabil
invertierbar, wenn zwei oder mehrere Eigenwerte e_k im Vergleich zur
Numerikpräzision eps und dem Spektralradius r(A) dicht beieinander
liegen.
|e_i-e_k|/r(A) ~ eps
Dann bildet man nämlich nicht das charakteristische Polynom
det (A- k Id) =0 sondern det(A - (k Id + sum dk_i Z_i) =0
und löst für die Inverse nicht
B.A = Id sondern B.A = (sum dk_i Z_i) Id
wobei dk_i Rundungsfehler und Z_i eine Basis der nxn-Matrizen sind.
Es gibt Formeln für die 2. Ableitungen von Determinanten und
Eigenwerten von Matrizen für die Taylorentwicklung. Man muß dann
versuchen, die Basis Z_k so zu transformieren, dass das gestörte
charakteristische Polynom faktorisiert in die in dk linearen und die
vergleichbar großen quadratischen Terme für die nahezu
entarteten Unterräume.

Hallo,
davon abgesehen, dass das Invertieren der Matrix selten eine gute Idee
ist, aber verwechselst du hier nicht die Probleme?
Klarerweise lassen sich die Eigenvektoren nur sehr ungenau berechnen,
wenn die zugehörigen Eigenwerte nahe beisammen liegen. Aber wie
weit sollte das beim Lösen von linearen Gleichungssystemen eine
Rolle spielen, wenn nicht gerade Nulleigenwerte vorliegen?
So ist zB. die Matrix
| 1 1 |
A = | |
| 0 1 |
ohne Probleme invertierbar, auch wenn man sie ein wenig stört.

Alois

[Roland Franzius]

Post by egonmarkin

Post by Roland Franzius
Eine Matrix A ist mit linearen Methoden numerisch instabil
invertierbar, wenn zwei oder mehrere Eigenwerte e_k im Vergleich zur
Numerikpräzision eps und dem Spektralradius r(A) dicht beieinander
liegen.
|e_i-e_k|/r(A) ~ eps
Dann bildet man nämlich nicht das charakteristische Polynom
det (A- k Id) =0 sondern det(A - (k Id + sum dk_i Z_i) =0
und löst für die Inverse nicht
B.A = Id sondern B.A = (sum dk_i Z_i) Id
wobei dk_i Rundungsfehler und Z_i eine Basis der nxn-Matrizen sind.
Es gibt Formeln für die 2. Ableitungen von Determinanten und
Eigenwerten von Matrizen für die Taylorentwicklung. Man muß dann
versuchen, die Basis Z_k so zu transformieren, dass das gestörte
charakteristische Polynom faktorisiert in die in dk linearen und die
vergleichbar großen quadratischen Terme für die nahezu
entarteten Unterräume.

Hallo,
davon abgesehen, dass das Invertieren der Matrix selten eine gute Idee
ist, aber verwechselst du hier nicht die Probleme?
Klarerweise lassen sich die Eigenvektoren nur sehr ungenau berechnen,
wenn die zugehörigen Eigenwerte nahe beisammen liegen. Aber wie
weit sollte das beim Lösen von linearen Gleichungssystemen eine
Rolle spielen, wenn nicht gerade Nulleigenwerte vorliegen?

Das ist aber der Punkt: Bei der näheren Betrachtung des Problems legt
man den entarteten Teilraum auf den Nullpunkt

Post by egonmarkin
So ist zB. die Matrix
| 1 1 |
A = | |
| 0 1 |
ohne Probleme invertierbar, auch wenn man sie ein wenig stört.

2x2 oder Entartung kompatibel mit der gewählten Basis ist nicht das
Problem.

Es geht auch bei dieser Betrachtung weniger um das Invertieren an sich
als darum, zu verstehen, wieso Probleme in der Lösung von
Gleichungssystemen nahe Entartungspunkten der Eigenwertverteilung
auftreten und wie man das durch geeignete Transformationen, Verschieben
in den Nullpunkt, Diagonalisierung der Taylorentwicklung ab 2. Ordnung
für Eigenwertgruppen nahe 0 und Eigenvektoren in den Griff bekommen kann.

[JCH]

Post by egonmarkin

Post by Roland Franzius
Eine Matrix A ist mit linearen Methoden numerisch instabil
invertierbar, wenn zwei oder mehrere Eigenwerte e_k im Vergleich zur
Numerikpräzision eps und dem Spektralradius r(A) dicht beieinander
liegen.
|e_i-e_k|/r(A) ~ eps
Dann bildet man nämlich nicht das charakteristische Polynom
det (A- k Id) =0 sondern det(A - (k Id + sum dk_i Z_i) =0
und löst für die Inverse nicht
B.A = Id sondern B.A = (sum dk_i Z_i) Id
wobei dk_i Rundungsfehler und Z_i eine Basis der nxn-Matrizen sind.
Es gibt Formeln für die 2. Ableitungen von Determinanten und
Eigenwerten von Matrizen für die Taylorentwicklung. Man muß dann
versuchen, die Basis Z_k so zu transformieren, dass das gestörte
charakteristische Polynom faktorisiert in die in dk linearen und die
vergleichbar großen quadratischen Terme für die nahezu
entarteten Unterräume.

Hallo,
davon abgesehen, dass das Invertieren der Matrix selten eine gute Idee
ist, aber verwechselst du hier nicht die Probleme? Klarerweise lassen
sich die Eigenvektoren nur sehr ungenau berechnen,
wenn die zugehörigen Eigenwerte nahe beisammen liegen. Aber wie
weit sollte das beim Lösen von linearen Gleichungssystemen eine
Rolle spielen, wenn nicht gerade Nulleigenwerte vorliegen?

Das ist aber der Punkt: Bei der näheren Betrachtung des Problems legt man
den entarteten Teilraum auf den Nullpunkt

Post by egonmarkin
So ist zB. die Matrix
| 1 1 |
A = | |
| 0 1 |
ohne Probleme invertierbar, auch wenn man sie ein wenig stört.

2x2 oder Entartung kompatibel mit der gewählten Basis ist nicht das
Problem.
Es geht auch bei dieser Betrachtung weniger um das Invertieren an sich als
darum, zu verstehen, wieso Probleme in der Lösung von Gleichungssystemen
nahe Entartungspunkten der Eigenwertverteilung auftreten und wie man das
durch geeignete Transformationen, Verschieben in den Nullpunkt,
Diagonalisierung der Taylorentwicklung ab 2. Ordnung für Eigenwertgruppen
nahe 0 und Eigenvektoren in den Griff bekommen kann.

Hast Du mal z.B. 3 lineare 'Problemgleichungen' A*x=b, die zu lösen ein
Problem darstellen sollen?