Content deleted Content added
Line 30:
== The implicit QR algorithm ==
In modern computational practice, the QR algorithm is performed in an implicit version which makes the use of multiple shifts easier to introduce.<ref name="golubvanloan" /> The matrix is first brought to upper Hessenberg form <math>A_0=QAQ^{\mathsf{T}}</math> as in the explicit version; then, at each step, the first column of <math>A_k</math> is transformed via a small-size Householder similarity transformation to the first column of <math>p(A_k)</math> {{Clarify}} (or <math>p(A_k)e_1</math>), where <math>p(A_k)</math>, of degree <math>r</math>, is the polynomial that defines the shifting strategy (often <math>p(x)=(x-\lambda)(x-\bar\lambda)</math>, where <math>\lambda</math> and <math>\bar\lambda</math> are the two eigenvalues of the trailing <math>2 \times 2</math> principal submatrix of <math>A_k</math>, the so-called ''implicit double-shift''). Then successive Householder transformations of size <math>r+1</math> are performed in order to return the working matrix <math>A_k</math> 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 <math>A_k</math> is sufficiently small.
===Renaming proposal===
| |||