Transcription of The QR Algorithm - ETH Z
{{id}} {{{paragraph}}}
Example: confidence
The QR Algorithm - ETH Z
Chapter 4. The QR Algorithm The QR Algorithm computes a Schur decomposition of a matrix. It is certainly one of the most important Algorithm in eigenvalue computations [9]. However, it is applied to dense (or: full) matrices only. The QR Algorithm consists of two separate stages. First, by means of a similarity transformation, the original matrix is transformed in a finite number of steps to Hessenberg form or in the Hermitian/symmetric case to real tridiagonal form. This first stage of the Algorithm prepares its second stage, the actual QR iterations that are applied to the Hessenberg or tridiagonal matrix. The overall complexity (number of floating points) of the Algorithm is O(n3 ), which we will see is not entirely trivial to obtain.
64 CHAPTER4. THEQRALGORITHM Algorithm 4.1 Basic QR algorithm 1: Let A∈Cn×n.This algorithm computes an upper triangular matrix Tand a unitary matrix Usuch that A= UTU∗ is the Schur decomposition of A. 2: Set A0:= Aand U0 = I. 3: for k= 1,2,...do 4: Ak−1 =: QkRk; /* QR factorization */ 5: Ak:= RkQk; 6: Uk:= Uk−1Qk; /* Update transformation matrix */ 7: end for 8: …
Loading..
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: