SVDFEI.HTM

SVD Erklaerungen von HGFei (zur Vorlesung im WS 0203, Angew.Math. f. LAK)

"UNDER CONSTRUCTION!!!"      11. Nov. 2002 

SVD Routine in MATLAB:  Ergebnis von "help"

-----------------------------------------------------  EIGENWERT ROUTINE ------
EIG Eigenvalues and eigenvectors.
E = EIG(X) is a vector containing the eigenvalues of a square
matrix X.

[V,D] = EIG(X) produces a diagonal matrix D of eigenvalues and a
full matrix V whose columns are the corresponding eigenvectors so
that X*V = V*D. 

IST KLARERWEISE äquivalent zu (da ja inv(V) = V' =: U) 

              X =   V * D * V'  , d.h. bzgl. der ONB  (Spalten von)

V hat die Abbildung  x  >>  X * x  DIAGONAL-GESTALT!!   

[V,D] = EIG(X,'nobalance') performs the computation with balancing
disabled, which sometimes gives more accurate results for certain
problems with unusual scaling. If X is symmetric, EIG(X,'nobalance')
is ignored since X is already balanced.

Etc. etc., See also CONDEIG, EIGS.
 

HELP ERGEBNIS zum Befehl SVD:  SINGULÄRWERT ZERLEGUNG

SVD Singular value decomposition.
[U,S,V] = SVD(X) produces a diagonal matrix S, of the same
dimension as X and with nonnegative diagonal elements in
decreasing order, and unitary matrices U and V so that
                                           X = U*S*V'.                             

S = SVD(X) returns a vector containing the singular values.

[U,S,V] = SVD(X,0) produces the "economy size"
decomposition. If X is m-by-n with m > n, then only the
first n columns of U are computed and S is n-by-n.

See also SVDS, GSVD.

PINV Pseudoinverse. (Moore-Penrose inverse)

X = PINV(A) produces a matrix X of the same dimensions
as A' so that A*X*A = A, X*A*X = X and A*X and X*A
are Hermitian. The computation is based on SVD(A) and any
singular values less than a tolerance are treated as zero.
The default tolerance is MAX(SIZE(A)) * NORM(A) * EPS.

PINV(A,TOL) uses the tolerance TOL instead of the default.

See also RANK.

PRAKTISCHE Anwendungen

Folgerung: Projektion auf den Spaltenraum:  Psp =  A *  pinv(A);  Projektion auf den Zeilenraum:   PZ =  A' * pinv(A') . 

Sind die Spalten von A linear unabhängig gilt:    Psp  ==   A *  inv(A'*A) * A' 

Sind die Spalten von A ein Erz.System f. R^m (schreibe S = A*A')   pinv(A) =  A' * inv(A*A') =    [ inv(A*A') * A ]' =  ( d.h  B = inv(S)*Aerlaubt die Identität so zu schreiben: Id =  A*B', d.h. man kann jeden Vektor darstellen, indem man mithilfe von B (dualer frame) Koeffizienten bildet, die geeignet sind, den Vektor als Lin.Komb. der Spalten von A darzustellen (und zwar sind das genau die "minimal norm" Koeffizienten).   . 

Einfacher Anwendungsfall: Regressionsgerade (viele Werte, dazu "Ausgleichsgerade"), plots etc. werden in einem eigenen File  (derzeit nur Platzhalter "under construction") dargeboten.

Sobald die (nichtneg.) Singulärwerte einer bel. rechteckigen Matrix bekannt sind, kann auch ihre Operatornorm bestimmt werden, d.h. der maximale Quotient zwischen "input" und "output" des entsprechenden "linearen Systems":  x  >>  A*x ,  und zwar ist das gerade der kleinste Singularwert. Wenn die Matrix  A  quadratisch  ist, und die SVD   A =  U * S * V'  hat, gilt natürlich     inv(A) =  V * inv( S) * U' .  Die Singulärwerte von inv(A) sind also  genau die Kehrwerte der Sing.Werte von   A  selber. Also ist die Operatornorm von  inv(A)  gerade  1/s_n , also der Kehrwert des kleinsten Sing.Wertes von   A .

Formale Definition der "Norm einer (beschränkten) linearen Abbildung" (lineare Abb. zwischen endlichdim. Vektorräumen sind immer beschränkt):

sup   || Ax || / || x || ,   wobei das supremum über alle vom Nullvektor verschiedenen Vektoren genommen wird. Da die lineare Abbildung aber auch mit skalarer Multiplikation verträglich ist,  kann man auch vom "Durchmesser" des Bildes der Einheitskugel (d.h. aller Vektoren von Norm kleiner oder gleich 1)  unter der Abbildung   x >>  A*x  sprechen.

Die Konditionszahl  einer invertierbaren Matrix wird definiert als  das Produkt aus der Norm von  A  und der Norm von  inv(A) , ergibt sich also als der Quotient  s1/sn (des größten SV, dividiert durch den kleinsten) .

MATLAB-Befehle dazu:  [U,S,V] = svd(A);  sv = diag(S);  oder gleich nur  sv = svd(A);  und:   cA = cond(A);  

Der Begriff der  KONDITIONSZAHL  ist dann wichtig, wenn man aus der Existenz einer Näherungslösung  x1  mit  A*x1 = b1  aus der Größe des relativen Fehlers zwischen den rechten Seiten  (b bzw. b1) auf die (schlimmst mögliche) Abweichung von  x1 zur "wahren Lösung"  x  schließen will. [2-Zeilen Abschätzung]. 

 Ist  A  eine symmetrische Matrix hat relle Eigenwerte. Wenn der "maximal größte" isoliert ist, dann ist die einfache "Vektoriteration" ein gute Methode, um den entsprechenden Eigenvektoren zu bestimmen:  Schritte:  Anwenden der Matrix, dann normieren des Vektors, dann wieder Anwenden der

Weitere Hinweise auf die SVD:

Bedeutung der Singulärwerte:

a)  Es sind genau die Quadratwurzeln aus den Eigenwerten zu  AA'  bzw.  A'A (diese haben ja die gleichen Eigenwerte):

Begründung:  Wenn     A =  U * S * V'  gilt, dann ist  A'  =  V * S' * U', also  A*A' =  U * (S * S') * U' , wobei die quadr. Diagonalmatrix S*S' genau die von Null verschiedenen Eigenwerte   s_1^2,... s_r^2  hat (r = Rank(A)).

Wenn man "input Vektoren"  x  (normierte) würfelt, dann spiegelt die Verteilung der Längen der Vektoren  Ax genau die Verteilung der Singulärwerte wider (! Histogramm). 

Wenn die Matrix   A  normal ist, sincd nach Def. die Matrizen  A*A'   und  A'*A und somit wird aus der SVD ein DIAGONALISIERUNG der Matrix A.  Beachte, dass auch z.B.  unitäre Matrizen diese Eigenschaft haben (dort ist es aber besonders leicht   eine SVD herzustellen, denn eine unitäre Abbildung bewahrt bekanntlich Winkel, also Orthogonalität, und daher werden Orthonormalsysteme immer in ONS abgebildet). Die Singulärwerte einer unitären Matrix sind also alle konstant gleich  1 , also ist auch die Kinditionszahl einer unitären Marix gleich EINS. Das ist auch dirket aus der Definition klar, denn mit  A  ist Sauch  inv(A)   unitär. Aber jede isometrische Abbildung hat natürlich auch Norm Eins!

SVD  und Approximation einer Matrix durch einen Operator (d.h. einer Matrix) durch eine Matrix von geringerem Rang: Kurz gesagt, wie kann man die Spalten eines Vektors, die einen  r-dimensionalen Raum aufspannen, gut durch Elemente eines s-dimensionalen Teilraumes aufspannen: man nehme die ersten  Eigenvektoren zu  AA' !!  (d.h. die Eigenvektoren, die zu den  s  größten Eigenwerten von  AA'  gehören!

PINV mit SCHWELLWERT (threshold):

Mit Hilfe der  PINV  werden (ohne Ansehen der Größe) alle nicht-verschwindenden Singulärwerte invertiert. Das ist analytisch zwar "nett", in der Praxis kommt man aber in das Problem, dass einerseits manchmal nicht klar ist, ob ein Wert nur durch numerische Ungenauigkeiten so aussieht, als wäre er ungleich Null (aber besser so zu behandeln wäre). Andererseits kommt man (praktisch gesprochen) in die Situation "beliebig hohe Kosten" in Kauf zu nehmen, um eine noch so geringe Verbesserung der Approximation eines Vektors  b (rechte Seite von  A*x = b)  zu erzielen. Wie im praktischen Leben wird man das aber meist nicht für wünschenswert halten, und nur in besonderen Fällen "extreme Kosten" in Kauf nehmen, d.h. Koeffizientenvektoren von größerer Länge akzeptieren um eine bessere Approximation zu bekommen. Man bedenke auch, dass im Falle einer schlechten Kondition ( s_r  ist sehr klein, z.B.) ein sehr kleiner Fehler auf der rechten Seite zu einem (um den Faktor  1/s_r vergrößerten) Fehler in der Wahl des Vektors x  führt. Vor allem dann, wenn es sich um "verrauschte" Daten handelt, wird man darauf gerne verzichten, und lieber nur die "relativ großen" Singulärwerte invertieren.   Der  Befehl (MATLAB)      x ´=  pinv(A,0.001) * b   bestimmt eine solche Pseudo-Inverse, wobei die Singulärwerte  kleiner als  der Schwellwert  0.001  als NULL betrachtet werden und daher NICHT invertiert werden.

Klarerweise ergibt sich durch diese Methode ein gewisse Stabilisierung (geringere Empfindlichkeit des Ergebnisses bzgl. kleiner Störungen, d.h. man hat eine robustere Methode, da dafür aber im Falle von "idealen Daten" nicht ganz so exakt ist).

Dieser Ansatz kann auch benutzt werden, um den  "approximativen Rang"  einer Familie von Vektoren zu bestimmen, d.h. die Dimension (= s) eines Teilraums, der stabil (!)  von einer gegebenen Kollektion von Vektoren aufgespannt werden. 

Zurück  zur Vorlesungs Homepage  (Stand vom 12.Nov.2002, HGFei)