Ctrl+K

Das QR-Verfahren

Voraussetzungen

  • Programmier-Grundlagen

  • Matrizen-Grundlagen inklusive Eigenwerte

Lerninhalte

  • Berechnung von Eigenwerten mithilfe der QR-Zerlegung (Diagonalisierung)

Das QR-Verfahren#

Folgender iterativer Algorithmus liegt dem sogenanneten QR-Verfahren zur Berechnung der Eigenwerte einer Matrix zugrunde:

  1. Setze \(A^{(0))}=A\)

  2. Berechne \(Q^{(k)}\) und \(R^{(k)}\), so dass

    \[ A^{(k)}=Q^{(k)}R^{(k)} \hspace{1cm} \text{ für alle } k=0,1,... \]

  3. Setze \(A^{(k+1)}=R^{(k)}Q^{(k)}\)

Aufgabe 1 - Implementieren Sie den QR-Algorithmus#

Schreiben Sie eine Funktion, die dieses Verfahren implementiert, um die Eigenwerte einer Matrix zu berechnen. Brechen Sie die Iteration ab, sobald eine maximale Anzahl an Iterationen erreicht wurde oder die relative Änderung \(\frac{\|diag(A^{(k)}) - diag(A^{(k-1)})\|}{\|diag(A^{(k)})\|}\) eine vom Benutzer vorgegebene Toleranz unterschreitet.

%%file my_eig.m
function E = my_eig(A, maxiter, tol)
% Find a few eigenvalues and eigenvectors of a matrix
%
%   E = my_eig(A, maxiter, tol) returns a a column vector E containing the eigenvalues of 
%   a square matrix A. The entries are sorted from largest to smallest magnitude
%
% Internally, an implementation of the QR algorithm is used.
%
%   maxiter is the maximum number of iterations
%   tol is a user defined tolerance. The iteration stops if norm(A - Aprev)/norm(A) falls below this threshold

% INSERT CODE HERE

Hinweis

Verwenden Sie für die Berechnung der QR-Zerlegung die Matlab/Octave-Funktion qr.

Überprüfen Sie ob Ihre Funktion die Testfälle in test_my_eig.m besteht:

moxunit_runtests test_my_eig.m;

Aufgabe 2 - Testen Sie Ihre Funktion von Hand#

Berechnen Sie die Eigenwerte der Matrix

\[\begin{split} \Phi = \begin{bmatrix} 2 & -\frac{1}{2} & 0 & -\frac{1}{2} \\ 0 & 4 & 0 & 2 \\ - \frac{1}{2} & 0 & 6 & \frac{1}{2} \\ 0 & 0 & 1 & 9 \end{bmatrix} \end{split}\]

mit der Matlab/Octave-Funktion eig und vergleichen Sie das Ergebnis mit der Ausgabe Ihrer Funktion my_eig.

Contents