Eigenwert-Algorithmen

Eigenwert-Algorithmen berechnen die Eigenwerte und Eigenvektoren einer Matrix iterativ, da für Matrizen, die größer als vier mal vier sind, keine endliche Formel existieren kann.

Definition

Ein Eigenwert-Algorithmus ist ein iteratives numerisches Verfahren zur Annäherung der Eigenwerte und optional der Eigenvektoren einer Matrix, da die Eigenwerte Wurzeln des charakteristischen Polynoms sind und im Allgemeinen nicht in endlich vielen arithmetischen Operationen gefunden werden können.

Scope

Dieses Thema behandelt die Potenz- und inverse Iteration, die Reduktion auf die Hessenberg- oder Tridiagonalform, den QR-Algorithmus mit Shifts und spezialisierte Methoden für das symmetrische Eigenwertproblem, zusammen mit der Störungstheorie, die die Empfindlichkeit der berechneten Eigenwerte regelt.

Core questions

• Warum muss die allgemeine Eigenwertberechnung iterativ und nicht direkt sein?
• Wie konvergiert der verschobene QR-Algorithmus zur Schur-Form, und warum ist eine vorherige Reduktion auf die Hessenberg-Form für die Effizienz unerlässlich?
• Was macht das symmetrische Eigenwertproblem besser konditioniert und für spezialisierte Algorithmen zugänglich?
• Wie empfindlich reagieren Eigenwerte auf Störungen, und wie hängt dies von der Nicht-Normalität der Matrix ab?

Key theories

Der QR-Algorithmus

Wiederholtes Faktorisieren einer Matrix als QR und Rekombinieren als RQ, mit gut gewählten Shifts und einer vorherigen Hessenberg-Reduktion, treibt die Matrix in eine obere Dreiecksform (Schur-Form), deren Diagonale die Eigenwerte enthält; es ist die Standardmethode für das dichte Eigenwertproblem.

Potenz- und inverse Iteration

Die wiederholte Multiplikation mit der Matrix konvergiert zum dominanten Eigenvektor, während die inverse Iteration mit einem Shift den Eigenwert nahe dem Shift anvisiert; diese bilden die Grundlage sowohl klassischer Methoden als auch moderner Eigenvektorverfeinerungen.

Eigenwert-Störungstheorie

Das Bauer-Fike-Theorem und verwandte Ergebnisse begrenzen, wie stark sich Eigenwerte unter Störungen verschieben; für symmetrische (normale) Matrizen sind Eigenwerte perfekt konditioniert, während sie für stark nicht-normale Matrizen extrem empfindlich sein können.

Mechanisms

Eine dichte Matrix wird zunächst durch orthogonale Ähnlichkeitstransformationen auf die obere Hessenberg-Form (im symmetrischen Fall tridiagonal) reduziert, was die Eigenwerte erhält und jeden QR-Schritt kostengünstig macht. Die verschobene QR-Iteration deflatiert dann konvergierte Eigenwerte einzeln oder paarweise vom unteren Ende der Matrix. Bei symmetrischen Problemen nutzen Divide-and-Conquer- und MRRR-Algorithmen die Struktur aus, um Eigenwerte und Eigenvektoren genau und parallel zu berechnen.

Clinical relevance

Eigenwertberechnungen bestimmen Schwingungsmoden und Eigenfrequenzen im Bau- und Maschinenbau, die Stabilität dynamischer Systeme und Regelkreise, Energieniveaus in der Quantenchemie und -physik sowie die spektralen Methoden, die hinter Graphenpartitionierung, PageRank und Hauptkomponentenanalyse stehen.

History

Der QR-Algorithmus wurde um 1961 unabhängig voneinander von John Francis und Vera Kublanovskaya eingeführt und entwickelte sich mit der Hinzufügung von Shifts und der Hessenberg-Reduktion zur dominierenden Methode für das dichte Eigenwertproblem; Wilkinsons Analyse etablierte seine Zuverlässigkeit und die Störungstheorie, die seine Genauigkeit erklärt.

Key figures

• James H. Wilkinson
• John G. F. Francis
• Vera Kublanovskaya
• Beresford Parlett

Seminal works

• trefethen1997
• golub2013
• wilkinson1965

Frequently asked questions

Warum können Eigenwerte nicht durch eine direkte Formel wie eine lineare Lösung berechnet werden?

Eigenwerte sind Wurzeln des charakteristischen Polynoms, und nach dem Satz von Abel haben Polynome fünften Grades oder höher keine allgemeine Radikalformel, daher muss die Eigenwertberechnung für Matrizen, die größer als vier mal vier sind, iterativ erfolgen.

Sind Eigenwerte immer gut konditioniert?

Für symmetrische und andere normale Matrizen sind Eigenwerte perfekt konditioniert, aber für stark nicht-normale Matrizen können sie sehr empfindlich auf Störungen reagieren, weshalb das Spektrum allein das Verhalten solcher Matrizen möglicherweise nicht vollständig erfasst.