QR algorithm

QR algorithm

In numerical linear algebra, the QR algorithm is an eigenvalue algorithm; that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR transformation was developed in 1961 by John G.F. Francis (England) and by Vera N. Kublanovskaya (USSR), working independently. [J.G.F. Francis, "The QR Transformation, I" (part 1) , "The Computer Journal", vol. 4, no. 3, pages 265-271 (1961) [http://comjnl.oxfordjournals.org/cgi/content/abstract/4/3/265 online at oxfordjournals.org] ;
"The QR Transformation, II" (part 2), "The Computer Journal", vol. 4, no. 4, pages 332-345 (1962) [http://comjnl.oxfordjournals.org/cgi/content/abstract/4/4/332 online at oxfordjournals.org] .

Vera N. Kublanovskaya, "On some algorithms for the solution of the complete eigenvalue problem," "USSR Computational Mathematics and Mathematical Physics", vol. 3, pages 637–657 (1961). Also published in: "Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki", vol.1, no. 4, pages 555–570 (1961).

For biographical information about John G.F. Francis, see “Notes” in Wikipedia article “Eigenvalue, eigenvector and eigenspace”. For biographical information about Vera Kublanovskaya, see Wikipedia article “Vera Kublanovskaya”.] The basic idea is to perform a QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the other order, and iterate.

The practical QR algorithm

Formally, let "A" be the matrix of which we want to compute the eigenvalues, and let "A"0:="A". At the "k"-th step (starting with "k" = 0), we write "A""k" as the product of an orthogonal matrix "Q""k" and a upper triangular matrix "R""k" and we form "A""k"+1 = "R""k""Q""k". Note that: A_{k+1} = R_k Q_k = Q_k^T Q_k R_k Q_k = Q_k^T A_k Q_k = Q_k^{-1} A_k Q_k, so all the "A""k" are similar and hence they have the same eigenvalues. The algorithm is numerically stable because it proceeds by "orthogonal" similarity transforms.

Under certain conditions [Golub, G. H. and Van Loan, C. F.: Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996, ISBN 0-8018-5414-8.] , the matrices "A""k" converge to a triangular matrix. The eigenvalues of a triangular matrix are listed on the diagonal, and the eigenvalue problem is solved. In testing for convergence it is impractical to require exact zeros, but the Gershgorin circle theorem provides a bound on the error.

In this crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix "A" to upper Hessenberg form (which costs egin{matrix}frac{5}{3}end{matrix} n^3 + O(n^2) using Householder reduction) with a finite sequence of orthogonal similarity transforms, much like a QR decomposition. Determining the QR decomposition of an upper Hessenberg matrix costs 6 n^2 + O(n).

If the original matrix is symmetric, then the upper Hessenberg matrix is also symmetric and thus tridiagonal, and so are all the "A""k". This procedure costs egin{matrix}frac{2}{3}end{matrix} n^3 + O(n^2) using Householder reduction. Determining the QR decomposition of a tridiagonal matrix costs O(n).

The rate of convergence depends on the separation between eigenvalues, so a practical algorithm will use shifts, either explicit or implicit, to increase separation and accelerate convergence. A typical symmetric QR algorithm isolates each eigenvalue (then reduces the size of the matrix) with only one or two iterations, making it efficient as well as robust.

The implicit QR algorithm

In modern computational practice [Golub and Van Loan, chapter 7] , the QR algorithm is performed in an implicit version which makes the use of multiple shifts easier to introduce. The matrix is first brought to upper Hessenberg form A_0=QAQ^T as in the explicit version; then, at each step, the first column of A_k is transformed via a small-size Householder similarity transformation to the first column of p(A_k)e_1, where p(A_k), of degree r, is the polynomial that defines the shifting strategy (often p(x)=(x-lambda)(x-arlambda), where lambda and arlambda are the two eigenvalues of the trailing 2 imes 2 principal submatrix of A_k, the so-called "implicit double-shift"). Then successive Householder transformation of size r+1 are performed in order to return the working matrix A_k to upper Hessenberg form. This operation is known as "bulge chasing", due to the peculiar shape of the non-zero entries of the matrix along the steps of the algorithm. As in the first version, deflation is performed as soon as one of the sub-diagonal entries of A_k is sufficiently small.

Renaming proposal

Since in the modern implicit version of the procedure no QR decompositions are explicitly performed, some authors, for instance Watkins [Watkins, David S.: The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM, Philadelphia, PA, USA, 2007, ISBN 0898716411, 9780898716412] , suggested changing its name to "Francis algorithm". Golub and Van Loan use the term "Francis QR step".

Interpretation and convergence

The QR algorithm can be seen as a more sophisticated variation of the basic 'power' eigenvalue algorithm. Recall that the power algorithm repeatedly multiplies "A" times a single vector, normalizing after each iteration. The vector converges to the eigenvector of the largest eigenvalue. Instead, the QR algorithm works with a complete basis of vectors, using QR decomposition to renormalize (and orthogonalize). For a symmetric matrix "A", upon convergence, "AQ" = "QΛ", where "Λ" is the diagonal matrix of eigenvalues to which "A" converged, and where "Q" is a composite of all the orthogonal similarity transforms required to get there. Thus the columns of "Q" are the eigenvectors.

External links

*
* [http://www.math.umn.edu/~olver/aims_/qr.pdf Prof. Peter Olver's notes on orthogonal bases and the workings of the QR algorithm]

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Algorithm design — is a specific method to create a mathematical process in solving problems. Applied algorithm design is algorithm engineering.Algorithm design is identified and incorporated into many solution theories of operation research, such as dynamic… …   Wikipedia

  • Algorithm engineering — is a combination of theoretical algorithm design with real world data. By taking an algorithm and combining it with a hardware device connected to the real world, you are able to more accurately verify and validate the algorithm results and… …   Wikipedia

  • algorithm — UK US /ˈælgərɪðəm/ noun [C] IT ► a set of mathematical instructions that must be followed in a fixed order, and that, especially if given to a computer, will help to calculate an answer to a mathematical problem: a computer/mathematical/search… …   Financial and business terms

  • algorithm — n. a precise rule (or set of rules) specifying how to solve some problem; a set of procedures guaranteed to find the solution to a problem. Syn: algorithmic rule, algorithmic program [WordNet 1.5 +PJC] …   The Collaborative International Dictionary of English

  • algorithm — [al′gə rith΄əm] n. [altered (after ARITHMETIC) < ALGORISM] 1. Math. a) any systematic method of solving a certain kind of problem b) the repetitive calculations used in finding the greatest common divisor of two numbers: called in full… …   English World dictionary

  • Algorithm Builder — ist eine Entwicklungsumgebung für AVR Mikrocontroller, basierend auf einer graphischen Makro Assembler Sprache. Der gesamte Programmablauf wird in graphischer Form als Flussdiagramm eingegeben. Es lässt sich mit einzelnen Anweisungen direkt auf… …   Deutsch Wikipedia

  • Algorithm —   [engl.], Algorithmus.   …   Universal-Lexikon

  • algorithm — (n.) 1690s, from Fr. algorithme, refashioned (under mistaken connection with Gk. arithmos number ) from O.Fr. algorisme the Arabic numeral system (13c.), from M.L. algorismus, a mangled transliteration of Arabic al Khwarizmi native of Khwarazm,… …   Etymology dictionary

  • algorithm — ► NOUN ▪ a process or set of rules used in calculations or other problem solving operations. DERIVATIVES algorithmic adjective. ORIGIN Latin algorismus, from an Arabic word meaning the man of Kw rizm , referring to a 9th century mathematician …   English terms dictionary

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”