W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


QR-Algorithmus

*** Shopping-Tipp: QR-Algorithmus

Der '''QR-Algorithmus''' ist ein Numerische Mathematik numerisches Verfahren zur Berechnung aller Eigenwerte und eventuell der Eigenvektoren einer quadratischen Matrix (Mathematik) Matrix. Das auch QR-Verfahren oder QR-Iteration genannte Verfahren basiert auf der QR-Zerlegung und wurde im Jahre 1961 unabhängig voneinander von J. G. F. Francis und V. N. Kublanovskaya eingeführt. Oft konvergieren die Iterierten aus diesem Algorithmus gegen die Schur-Zerlegung Schur-Form der Matrix. Das Verfahren ist recht aufwändig und damit auf heutigen Rechnern für Matrizen mit hunderttausenden Zeilen und Spalten nicht praktikabel. Zur effizienteren Umsetzung wird die Matrix in einem ersten Schritt mit Ähnlichkeitstransformationen (meist Givens-Rotationen von rechts und links) auf eine obere Hessenbergmatrix Hessenbergform gebracht.

QR-Algorithmus ohne Shifts
Der QR-Algorithmus ohne Shifts (auch unter dem Namen ''QR-Algorithmus in der Grundform'' bekannt), berechnet ausgehend von A_0=A\in\mathbb{C}^{n\times n} eine Folge von Matrizen A_i: # for i\in\mathbb{N}_0 do # Berechne die QR-Zerlegung von A_i: A_i=Q_iR_i # Berechne die neue Iterierte: A_{i+1}=R_iQ_i # end for Die Konvergenz dieses Algorithmus ist nicht immer gegeben und so existiert eine zweite Variante.

QR-Algorithmus mit Shifts
Meist wird zwecks Konvergenzgeschwindigkeit Konvergenzbeschleunigung bzw. um überhaupt Konvergenz (Mathematik) Konvergenz zu erreichen, mit spektralen Shifts \kappa_i gearbeitet: # for i\in\mathbb{N}_0 do # Berechne die QR-Zerlegung von A_i-\kappa_iI: A_i-\kappa_iI=Q_iR_i # Berechne die neue Iterierte: A_{i+1}=R_iQ_i+\kappa_iI # end for Der QR-Algorithmus ohne Shifts entspricht dem QR-Algorithmus mit Shifts identisch Null.

Ähnlichkeitstransformationen
Die im QR-Algorithmus berechneten Matrizen sind zueinander unitär ähnlich, da aufgrund von A_i-\kappa_iI=Q_iR_i\quad\Leftrightarrow\quad R_i=Q_i^H(A_i-\kappa_iI) A_{i+1}=R_iQ_i+\kappa_iI =Q_i^H(A_i-\kappa_iI)Q_i+\kappa_iI =Q_i^HA_iQ_i-\kappa_iQ_i^HQ_i+\kappa_iI =Q_i^HA_iQ_i gilt. Damit haben alle Matrizen A_i die selben Eigenwerte (mit der algebraischen und geometrischen Vielfachheit gezählt).

Wahl der Shifts, Konvergenz
Eine einfache aber nicht sehr effektive Wahl ist die Wahl von Shifts identisch Null. Die Iterierten A_i des resultierenden Algorithmus, des QR-Algorithmus in der Grundform, konvergieren im Wesentlichen, wenn alle Eigenwerte dem Betrage nach verschieden sind, gegen eine obere Dreiecksmatrix mit den Eigenwerten auf der Diagonalen. Konvergenz im Wesentlichen bedeutet, daß die Elemente des unteren Dreiecks von A_i gegen Null gehen und die Diagonalelemente gegen die Eigenwerte. Über die Elemente im oberen Dreieck wird also ''nichts'' ausgesagt. Werden die Shifts als das Matrixelement unten rechts der aktuellen Iterierten gewählt, also \kappa_i=a_{nn}^{(i)}, so konvergiert der Algorithmus unter geeigneten Umständen quadratisch oder sogar kubisch. Dieser Shift ist als Rayleigh-Quotienten-Shift bekannt, da er über die Inverse Iteration mit einem Rayleigh-Quotienten im Zusammenhang steht. Bei der Rechnung im Reellen (A\in\mathbb{R}^{n\times n}) möchte man die reelle Schur-Form berechnen und trotzdem mit konjugiert komplexen Eigenwerten arbeiten können. Dazu gibt es verschiedene Shift-Strategien. Eine Erweiterung von einfachen Shifts ist der nach James Hardy Wilkinson benannte Wilkinson-Shift. Für den Wilkinson-Shift wird der näher am letzten Matrixelement liegende Eigenwert der letzten 2\times 2 Hauptunterabschnittsmatrix \begin{pmatrix} a_{n-1,n-1}^{(i)} & a_{n-1,n}^{(i)} \\ a_{n,n-1}^{(i)} & a_{n,n}^{(i)} \end{pmatrix} verwendet. Kategorie:Numerische lineare Algebra ja:QR法 en:QR algorithm

*** Shopping-Tipp: QR-Algorithmus




[Der Artikel zu QR-Algorithmus stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels QR-Algorithmus zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite