Diagonalisierung der Matrix - Weglassen kleiner Matrixelemente

8

Ich habe mich gefragt, ob es einen Satz gibt, der es mir ermöglicht, eine Obergrenze für den Fehler festzulegen, der durch das Weglassen kleiner Matrixelemente aus einer Matrix vor der Diagonalisierung entsteht.

Nehmen wir an, wir haben eine große Matrix, deren Matrixelemente zwischen $1$ und . Wenn ich vor der Diagonalisierung der Matrix alle Matrixelemente kleiner als auf würde, wie groß wäre der Fehler in den Eigenwerten und Eigenvektoren? $10^{-15}$ $10^{-10}$ $0$

Ist diese Implementierung abhängig?

eigensystem error-estimation ftiaronsem
quelle

was ist, wenn die Matrix innerhalb epsilon einer Matrix , die nicht diagonalisierbar ist

k20

6

Es gibt ein Untersuchungsgebiet, das als Eigenwert-Sensitivitätsanalyse oder Eigenwert-Störungsanalyse bekannt ist und es Ihnen ermöglicht, die Auswirkung kleiner Matrixstörungen auf die Eigenwerte und Eigenvektoren abzuschätzen. Die dafür verwendete Grundtechnik ist die Differenzierung der Eigenwertmatrixgleichung

A X = X Λ .

$AX = X\Lambda.$

Für Situationen, in denen die Eigenwerte der ursprünglichen Matrix alle unterschiedlich sind, hat das folgende Dokument eine sehr klare Ableitung und Ergebnisse:

Mike Giles. "Eine erweiterte Sammlung von Matrixableitungsergebnissen für die algorithmische Differenzierung im Vorwärts- und Rückwärtsmodus". https://people.maths.ox.ac.uk/gilesm/files/NA-08-01.pdf

Wenn die Eigenwerte nicht unterschiedlich sind, muss etwas mehr Sorgfalt angewendet werden. Siehe die folgende Präsentation und das folgende Papier .

Für den Sonderfall der symmetrischen Matrizen mit unterschiedlichen Eigenwerten, die einer kleinen Störung unterliegen , sind die Ergebnisse so einfach, dass ich sie hier reproduziere. Die Ableitung der Eigenwertmatrix lautet und die Ableitung der Eigenvektormatrix lautet wobei die Koeffizientenmatrix definiert ist als: $A=U \Lambda U^T$ $A \rightarrow A + dA$

d Λ = diag (U^{T} d A U),

$d\Lambda = \text{diag} (U^T dA U),$

d U = U C (d A),

$dU = UC(dA),$

C

$C$

C = {\begin{cases} \frac{u_{i}^{T} d A u_{j}}{λ_{j} - λ_{i}}, & i = j \\ 0, & i = j \end{cases}

$C = \begin{cases} \frac{u_i^T dA u_j}{\lambda_j - \lambda_i}, & i=j \\ 0, &i=j \end{cases}$

Das folgende Papier von Overton und Womersley enthält eine hervorragende Sensitivitätsanalyse für den symmetrischen Fall, einschließlich der zweiten Ableitungen.

Overton, Michael L. und Robert S. Womersley. "Zweite Ableitungen zur Optimierung der Eigenwerte symmetrischer Matrizen." SIAM Journal on Matrix Analysis and Applications 16.3 (1995): 697 & ndash; 718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf

Nick Alger
quelle

10

Es ist nicht implementierungsabhängig in dem Sinne, dass dies eine mathematische Operation ist, die an Ihrer Matrix ausgeführt wird. Es ist jedoch sehr viel Matrix -abhängigen.

$A=XDX^{-1}$ $E$ $X$

X^{- 1} (A + E) X = D + X^{- 1} E X .

$X^{-1}(A+E)X = D + X^{-1}EX.$

D

$D$

‖ E ‖ κ (X),

$\|E\| \kappa(X),$

‖ E ‖

$\|E\|$

κ (X)

$\kappa(X)$ ist die Bedingungsnummer der Matrix von Eigenvektoren.

Wenn Ihr Matrix ist normale (dh ) ist , dann ist unitär und , so dass diese in Ordnung ist. $A$ $AA^t=A^tA$ $X$ $\kappa(X)=1$

Wenn Ihre Matrix nicht normal ist, benötigen Sie das Konzept ihres Pseudospektrums, definiert als die Menge Eine äquivalente Definition, die einfacher zu berechnen ist, ist Es gibt eine gute Übersicht über Pseudospektren und ihre Eigenschaften in Pseudospektren von Matrizen von Trefethen (es enthält eine schöne Galerie von Matrizen, deren Pseudospektren viel größer als ihre Spektren sind: Man könnte denken, dass das Pseudospektrum eine Sammlung von kleinen

Λ_{ϵ} (EIN) = {z ∣ z ist ein Eigenwert von EIN + E. mit ‖ E. ‖ \leq ϵ}} .

$\Lambda_\epsilon(A) = \{z \mid z \text{ is an eigenvalue of $A+E$ with $\|E\| \leq \epsilon$} \}.$

Λ_{ϵ} (EIN) = {z ∣ ‖ (z ich - - EIN)^{- - 1} ‖ \geq ϵ^{- - 1}}} .

$\Lambda_\epsilon(A) = \{z \mid \|(zI-A)^{-1}\|\geq \epsilon^{-1} \}.$

ϵ

$\epsilon$ -große Scheiben um die Eigenwerte, aber das ist wirklich überhaupt nicht richtig). Im Allgemeinen kann man nicht einfach davon ausgehen, dass sich das Pseudospektrum gut verhält und die Störungen vernachlässigbar sind. Sie können jedoch berechnen und den resultierenden Fehler schätzen. Sie können das Pseudospektrum auch direkt berechnen.

κ (X)

$\kappa(X)$

In gewissem Sinne ist das Löschen kleiner Matrixelemente in Ordnung: Entweder spielen sie keine Rolle, und die neuen Ergebnisse sind genauso genau wie das Original, oder sie spielen eine Rolle, und Ihre ursprünglichen Ergebnisse sind genauso ungenau wie die neuen Ergebnisse.

Kirill
quelle

Vielen Dank für Ihre Antwort. Die fragliche Matrix wäre normal, was gut ist :). Könnten Sie die Aussage "vorausgesetzt, die Matrix X ändert sich nicht viel" etwas näher erläutern? Gibt es eine Möglichkeit, dies für normale Matrizen zu garantieren?

ftiaronsem

@ftiaronsem Ich denke, Sie können Links in der Antwort von Nick Alger folgen und die Änderung in bestimmen, indem Sie die Ableitung berechnen und abschätzen, wie groß sie sein kann. Der Punkt meiner Antwort ist wirklich, dass wenn die Matrix nicht als normal bekannt ist (Ihre Frage hat es nicht gesagt), dies wirklich nicht so einfach ist, wie man denkt.

X

$X$

d X

$dX$

Kirill

Diagonalisierung der Matrix - Weglassen kleiner Matrixelemente

Antworten: