QR algorithm - Revision history

BattyBot: Fixed CS1 errors: extra text: edition and general fixes

2025-04-24T04:59:45Z

Fixed CS1 errors: extra text: edition and general fixes

← Previous revision		Revision as of 04:59, 24 April 2025
Line 10:		Line 10:
	Under certain conditions,<ref name="golubvanloan">{{cite book \|last1=Golub \|first1=G. H. \|last2=Van Loan \|first2=C. F. \|title=Matrix Computations \|edition=3rd \|publisher=Johns Hopkins University Press \|location=Baltimore \|year=1996 \|isbn=0-8018-5414-8 }}</ref> the matrices ''A''<sub>''k''</sub> converge to a triangular matrix, the [[Schur form]] of ''A''. 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,{{citation needed\|date=July 2020}} but the [[Gershgorin circle theorem]] provides a bound on the error.		Under certain conditions,<ref name="golubvanloan">{{cite book \|last1=Golub \|first1=G. H. \|last2=Van Loan \|first2=C. F. \|title=Matrix Computations \|edition=3rd \|publisher=Johns Hopkins University Press \|location=Baltimore \|year=1996 \|isbn=0-8018-5414-8 }}</ref> the matrices ''A''<sub>''k''</sub> converge to a triangular matrix, the [[Schur form]] of ''A''. 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,{{citation needed\|date=July 2020}} but the [[Gershgorin circle theorem]] provides a bound on the error.

	If the matrices converge, then the eigenvalues along the diagonal will appear according to their geometric multiplicity. To guarantee convergence, A must be a symmetric matrix, and for all non zero eigenvalues <math>\lambda</math> there must not be a corresponding eigenvalue <math>-\lambda</math> <ref>{{Cite book \|last=Holmes \|first=Mark H. \|title=Introduction to scientific computing and data analysis \|date=2023 \|publisher=Springer \|isbn=978-3-031-22429-4 \|edition=Second ~~Edition~~ \|series=Texts in computational science and engineering \|location=Cham}}</ref>. Due to the fact that a single QR iteration has a cost of <math>\mathcal{O}(n^3)</math> and the convergence is linear, the standard QR algorithm is extremely expensive to compute, especially considering it is not guaranteed to converge <ref>{{Cite book \|last=Golub \|first=Gene H. \|title=Matrix computations \|last2=Van Loan \|first2=Charles F. \|date=2013 \|publisher=The Johns Hopkins University Press \|isbn=978-1-4214-0794-4 \|edition=Fourth ~~edition~~ \|series=Johns Hopkins studies in the mathematical sciences \|location=Baltimore}}</ref>.		If the matrices converge, then the eigenvalues along the diagonal will appear according to their geometric multiplicity. To guarantee convergence, A must be a symmetric matrix, and for all non zero eigenvalues <math>\lambda</math> there must not be a corresponding eigenvalue <math>-\lambda</math>.<ref>{{Cite book \|last=Holmes \|first=Mark H. \|title=Introduction to scientific computing and data analysis \|date=2023 \|publisher=Springer \|isbn=978-3-031-22429-4 \|edition=Second \|series=Texts in computational science and engineering \|location=Cham}}</ref> Due to the fact that a single QR iteration has a cost of <math>\mathcal{O}(n^3)</math> and the convergence is linear, the standard QR algorithm is extremely expensive to compute, especially considering it is not guaranteed to converge.<ref>{{Cite book \|last=Golub \|first=Gene H. \|title=Matrix computations \|last2=Van Loan \|first2=Charles F. \|date=2013 \|publisher=The Johns Hopkins University Press \|isbn=978-1-4214-0794-4 \|edition=Fourth \|series=Johns Hopkins studies in the mathematical sciences \|location=Baltimore}}</ref>

	===Using Hessenberg form===		===Using Hessenberg form===
Line 26:		Line 26:
	# Pick a shift <math>\mu</math> and subtract it from all diagonal elements, producing the matrix <math> A - \mu I </math>. A basic strategy is to use <math> \mu = a_{n,n} </math>, but there are more refined strategies that would further accelerate convergence. The idea is that <math> \mu </math> should be close to an eigenvalue, since making this shift will accelerate convergence to that eigenvalue.		# Pick a shift <math>\mu</math> and subtract it from all diagonal elements, producing the matrix <math> A - \mu I </math>. A basic strategy is to use <math> \mu = a_{n,n} </math>, but there are more refined strategies that would further accelerate convergence. The idea is that <math> \mu </math> should be close to an eigenvalue, since making this shift will accelerate convergence to that eigenvalue.
	# Perform a sequence of [[Givens rotation]]s <math> G_1, G_2, \dots, G_{n-1} </math> on <math> A - \mu I </math>, where <math> G_i </math> acts on rows <math>i</math> and <math>i+1</math>, and <math> G_i </math> is chosen to zero out position <math>(i+1,i)</math> of <math> G_{i-1} \dotsb G_1 (A - \mu I) </math>. This produces the upper triangular matrix <math> R = G_{n-1} \dotsb G_1 (A - \mu I) </math>. The orthogonal factor <math> Q </math> would be <math> G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, but it is neither necessary nor efficient to produce that explicitly.		# Perform a sequence of [[Givens rotation]]s <math> G_1, G_2, \dots, G_{n-1} </math> on <math> A - \mu I </math>, where <math> G_i </math> acts on rows <math>i</math> and <math>i+1</math>, and <math> G_i </math> is chosen to zero out position <math>(i+1,i)</math> of <math> G_{i-1} \dotsb G_1 (A - \mu I) </math>. This produces the upper triangular matrix <math> R = G_{n-1} \dotsb G_1 (A - \mu I) </math>. The orthogonal factor <math> Q </math> would be <math> G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, but it is neither necessary nor efficient to produce that explicitly.
	# Now multiply <math> R </math> by the Givens matrices <math> G_1^\mathrm{T} </math>, <math> G_2^\mathrm{T} </math>, …, <math> G_{n-1}^\mathrm{T} </math> on the right, where <math> G_i^\mathrm{T} </math> instead acts on columns <math>i</math> and <math> i+1 </math>. This produces the matrix <math> RQ = R G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, which is again on Hessenberg form.		# Now multiply <math> R </math> by the Givens matrices <math> G_1^\mathrm{T} </math>, <math> G_2^\mathrm{T} </math>, ..., <math> G_{n-1}^\mathrm{T} </math> on the right, where <math> G_i^\mathrm{T} </math> instead acts on columns <math>i</math> and <math> i+1 </math>. This produces the matrix <math> RQ = R G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, which is again on Hessenberg form.
	# Finally undo the shift by adding <math> \mu </math> to all diagonal entries. The result is <math> A' = RQ + \mu I </math>. Since <math>Q</math> commutes with <math>I</math>, we have that <math> A' = Q^\mathrm{T} (A-\mu I) Q + \mu I = Q^\mathrm{T} A Q </math>.		# Finally undo the shift by adding <math> \mu </math> to all diagonal entries. The result is <math> A' = RQ + \mu I </math>. Since <math>Q</math> commutes with <math>I</math>, we have that <math> A' = Q^\mathrm{T} (A-\mu I) Q + \mu I = Q^\mathrm{T} A Q </math>.
	The purpose of the shift is to change which Givens rotations are chosen.		The purpose of the shift is to change which Givens rotations are chosen.

Daurum: Added a paragraph explaining some properties of the convergence of the standard form of the QR algorithm

2025-04-23T11:07:53Z

Added a paragraph explaining some properties of the convergence of the standard form of the QR algorithm

← Previous revision		Revision as of 11:07, 23 April 2025
Line 9:		Line 9:

	Under certain conditions,<ref name="golubvanloan">{{cite book \|last1=Golub \|first1=G. H. \|last2=Van Loan \|first2=C. F. \|title=Matrix Computations \|edition=3rd \|publisher=Johns Hopkins University Press \|location=Baltimore \|year=1996 \|isbn=0-8018-5414-8 }}</ref> the matrices ''A''<sub>''k''</sub> converge to a triangular matrix, the [[Schur form]] of ''A''. 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,{{citation needed\|date=July 2020}} but the [[Gershgorin circle theorem]] provides a bound on the error.		Under certain conditions,<ref name="golubvanloan">{{cite book \|last1=Golub \|first1=G. H. \|last2=Van Loan \|first2=C. F. \|title=Matrix Computations \|edition=3rd \|publisher=Johns Hopkins University Press \|location=Baltimore \|year=1996 \|isbn=0-8018-5414-8 }}</ref> the matrices ''A''<sub>''k''</sub> converge to a triangular matrix, the [[Schur form]] of ''A''. 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,{{citation needed\|date=July 2020}} but the [[Gershgorin circle theorem]] provides a bound on the error.

			If the matrices converge, then the eigenvalues along the diagonal will appear according to their geometric multiplicity. To guarantee convergence, A must be a symmetric matrix, and for all non zero eigenvalues <math>\lambda</math> there must not be a corresponding eigenvalue <math>-\lambda</math> <ref>{{Cite book \|last=Holmes \|first=Mark H. \|title=Introduction to scientific computing and data analysis \|date=2023 \|publisher=Springer \|isbn=978-3-031-22429-4 \|edition=Second Edition \|series=Texts in computational science and engineering \|location=Cham}}</ref>. Due to the fact that a single QR iteration has a cost of <math>\mathcal{O}(n^3)</math> and the convergence is linear, the standard QR algorithm is extremely expensive to compute, especially considering it is not guaranteed to converge <ref>{{Cite book \|last=Golub \|first=Gene H. \|title=Matrix computations \|last2=Van Loan \|first2=Charles F. \|date=2013 \|publisher=The Johns Hopkins University Press \|isbn=978-1-4214-0794-4 \|edition=Fourth edition \|series=Johns Hopkins studies in the mathematical sciences \|location=Baltimore}}</ref>.

	===Using Hessenberg form===		===Using Hessenberg form===

Ophyrius: Reverted 1 edit by 210.212.2.165 (talk) to last revision by Ererer333

2025-04-19T08:42:10Z

Reverted 1 edit by 210.212.2.165 (talk) to last revision by Ererer333

← Previous revision		Revision as of 08:42, 19 April 2025
Line 129:		Line 129:

	===Renaming proposal===		===Renaming proposal===
	Since in the modern implicit version of the procedure no [[QR decomposition]]s are explicitly performed, some authors, for instance Watkins,<ref>{{cite book \|last=Watkins \|first=David S. \|title=The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods \|publisher=SIAM \|location=Philadelphia, PA \|year=2007 \|isbn=978-0-89871-641-2 }}</ref> suggested changing its name to ''Francis ~~algorithmhe~~ term ''Francis QR step''.		Since in the modern implicit version of the procedure no [[QR decomposition]]s are explicitly performed, some authors, for instance Watkins,<ref>{{cite book \|last=Watkins \|first=David S. \|title=The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods \|publisher=SIAM \|location=Philadelphia, PA \|year=2007 \|isbn=978-0-89871-641-2 }}</ref> suggested changing its name to ''Francis algorithm''. [[Gene H. Golub\|Golub]] and [[Charles F. Van Loan\|Van Loan]] use the term ''Francis QR step''.

	== Interpretation and convergence ==		== Interpretation and convergence ==

210.212.2.165: /* The implicit QR algorithm */

2025-04-19T08:25:46Z

The implicit QR algorithm

← Previous revision		Revision as of 08:25, 19 April 2025
Line 129:		Line 129:

	===Renaming proposal===		===Renaming proposal===
	Since in the modern implicit version of the procedure no [[QR decomposition]]s are explicitly performed, some authors, for instance Watkins,<ref>{{cite book \|last=Watkins \|first=David S. \|title=The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods \|publisher=SIAM \|location=Philadelphia, PA \|year=2007 \|isbn=978-0-89871-641-2 }}</ref> suggested changing its name to ''Francis ~~algorithm''. [[Gene H. Golub\|Golub]] and [[Charles F. Van Loan\|Van Loan]] use the~~ term ''Francis QR step''.		Since in the modern implicit version of the procedure no [[QR decomposition]]s are explicitly performed, some authors, for instance Watkins,<ref>{{cite book \|last=Watkins \|first=David S. \|title=The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods \|publisher=SIAM \|location=Philadelphia, PA \|year=2007 \|isbn=978-0-89871-641-2 }}</ref> suggested changing its name to ''Francis algorithmhe term ''Francis QR step''.

	== Interpretation and convergence ==		== Interpretation and convergence ==

Ererer333: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-02-08T09:43:39Z

Link suggestions feature: 3 links added.

← Previous revision		Revision as of 09:43, 8 February 2025
Line 18:		Line 18:
	If a Hessenberg matrix <math>A</math> has element <math> a_{k,k-1} = 0 </math> for some <math>k</math>, i.e., if one of the elements just below the diagonal is in fact zero, then it decomposes into blocks whose eigenproblems may be solved separately; an eigenvalue is either an eigenvalue of the submatrix of the first <math>k-1</math> rows and columns, or an eigenvalue of the submatrix of remaining rows and columns. The purpose of the QR iteration step is to shrink one of these <math>a_{k,k-1}</math> elements so that effectively a small block along the diagonal is split off from the bulk of the matrix. In the case of a real eigenvalue that is usually the <math> 1 \times 1 </math> block in the lower right corner (in which case element <math> a_{nn} </math> holds that eigenvalue), whereas in the case of a pair of conjugate complex eigenvalues it is the <math> 2 \times 2 </math> block in the lower right corner.		If a Hessenberg matrix <math>A</math> has element <math> a_{k,k-1} = 0 </math> for some <math>k</math>, i.e., if one of the elements just below the diagonal is in fact zero, then it decomposes into blocks whose eigenproblems may be solved separately; an eigenvalue is either an eigenvalue of the submatrix of the first <math>k-1</math> rows and columns, or an eigenvalue of the submatrix of remaining rows and columns. The purpose of the QR iteration step is to shrink one of these <math>a_{k,k-1}</math> elements so that effectively a small block along the diagonal is split off from the bulk of the matrix. In the case of a real eigenvalue that is usually the <math> 1 \times 1 </math> block in the lower right corner (in which case element <math> a_{nn} </math> holds that eigenvalue), whereas in the case of a pair of conjugate complex eigenvalues it is the <math> 2 \times 2 </math> block in the lower right corner.

	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.{{clarify\|date=June 2012}}		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.{{clarify\|date=June 2012}}

	====A single iteration with explicit shift====		====A single iteration with explicit shift====
Line 132:		Line 132:

	== Interpretation and convergence ==		== Interpretation and convergence ==
	The QR algorithm can be seen as a more sophisticated variation of the basic [[Power iteration\|"power" eigenvalue algorithm]]. Recall that the power algorithm repeatedly multiplies ''A'' times a single vector, normalizing after each iteration. The vector converges to an 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.		The QR algorithm can be seen as a more sophisticated variation of the basic [[Power iteration\|"power" eigenvalue algorithm]]. Recall that the power algorithm repeatedly multiplies ''A'' times a single vector, normalizing after each iteration. The vector converges to an 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.

	== History ==		== History ==
Line 140:		Line 140:

	== Other variants ==		== Other variants ==
	One variant of the ''QR algorithm'', ''the Golub-Kahan-Reinsch'' algorithm starts with reducing a general matrix into a bidiagonal one.<ref>Bochkanov Sergey Anatolyevich. ALGLIB User Guide - General Matrix operations - Singular value decomposition . ALGLIB Project. 2010-12-11. URL:[http://www.alglib.net/matrixops/general/svd.php] Accessed: 2010-12-11. (Archived by WebCite at https://www.webcitation.org/5utO4iSnR?url=http://www.alglib.net/matrixops/general/svd.php</ref> This variant of the ''QR algorithm'' for the computation of [[singular values]] was first described by {{harvtxt\|Golub\|Kahan\|1965}}. The [[LAPACK]] subroutine [http://www.netlib.org/lapack/double/dbdsqr.f DBDSQR] implements this iterative method, with some modifications to cover the case where the singular values are very small {{harv\|Demmel\|Kahan\|1990}}. Together with a first step using Householder reflections and, if appropriate, [[QR decomposition]], this forms the [http://www.netlib.org/lapack/double/dgesvd.f DGESVD] routine for the computation of the [[singular value decomposition]]. The QR algorithm can also be implemented in infinite dimensions with corresponding convergence results.<ref>{{cite journal \|first1=Percy \|last1=Deift \|first2=Luenchau C. \|last2=Li \|first3=Carlos \|last3=Tomei\|title=Toda flows with infinitely many variables \|journal=Journal of Functional Analysis \|volume=64 \| number=3\| pages=358–402 \|year=1985 \|doi=10.1016/0022-1236(85)90065-5\|doi-access=free }}</ref><ref>{{cite journal \|first1=Matthew J. \|last1=Colbrook \|first2=Anders C.\|last2=Hansen\|title=On the infinite-dimensional QR algorithm \|journal=Numerische Mathematik \|volume=143 \| number=1\| pages=17–83 \|year=2019 \|doi=10.1007/s00211-019-01047-5\|arxiv=2011.08172\|doi-access=free }}</ref>		One variant of the ''QR algorithm'', ''the Golub-Kahan-Reinsch'' algorithm starts with reducing a general matrix into a bidiagonal one.<ref>Bochkanov Sergey Anatolyevich. ALGLIB User Guide - General Matrix operations - Singular value decomposition . ALGLIB Project. 2010-12-11. URL:[http://www.alglib.net/matrixops/general/svd.php] Accessed: 2010-12-11. (Archived by WebCite at https://www.webcitation.org/5utO4iSnR?url=http://www.alglib.net/matrixops/general/svd.php</ref> This variant of the ''QR algorithm'' for the computation of [[singular values]] was first described by {{harvtxt\|Golub\|Kahan\|1965}}. The [[LAPACK]] subroutine [http://www.netlib.org/lapack/double/dbdsqr.f DBDSQR] implements this [[iterative method]], with some modifications to cover the case where the singular values are very small {{harv\|Demmel\|Kahan\|1990}}. Together with a first step using Householder reflections and, if appropriate, [[QR decomposition]], this forms the [http://www.netlib.org/lapack/double/dgesvd.f DGESVD] routine for the computation of the [[singular value decomposition]]. The QR algorithm can also be implemented in infinite dimensions with corresponding convergence results.<ref>{{cite journal \|first1=Percy \|last1=Deift \|first2=Luenchau C. \|last2=Li \|first3=Carlos \|last3=Tomei\|title=Toda flows with infinitely many variables \|journal=Journal of Functional Analysis \|volume=64 \| number=3\| pages=358–402 \|year=1985 \|doi=10.1016/0022-1236(85)90065-5\|doi-access=free }}</ref><ref>{{cite journal \|first1=Matthew J. \|last1=Colbrook \|first2=Anders C.\|last2=Hansen\|title=On the infinite-dimensional QR algorithm \|journal=Numerische Mathematik \|volume=143 \| number=1\| pages=17–83 \|year=2019 \|doi=10.1007/s00211-019-01047-5\|arxiv=2011.08172\|doi-access=free }}</ref>

	== References ==		== References ==

Arjayay: Duplicate word reworded

2024-12-02T13:55:46Z

Duplicate word reworded

← Previous revision		Revision as of 13:55, 2 December 2024
Line 37:		Line 37:
	\end{bmatrix}		\end{bmatrix}
	</math>		</math>
	where the <math>I</math> in the upper left corner is an <math> (n-1) \times (n-1) </math> identity matrix, and the two scalars <math> c = \cos\theta </math> and <math> s = \sin\theta </math> are determined by what rotation angle <math> \theta </math> is appropriate for zeroing out position <math>(i+1,i)</math>. It is not necessary to exhibit <math> \theta </math>; the factors <math> c </math> and <math> s </math> can be determined directly from elements in the matrix <math> G_i </math> should act on. Nor is it necessary to produce the whole matrix; multiplication (from the left) by <math> G_i </math> only affects rows <math> i </math> and <math> i+1 </math>, so it it easier to just update those two rows in place. Likewise, for the Step 3 multiplication by <math> G_i^\mathrm{T} </math> from the right, it is sufficient to remember <math>i</math>, <math>c</math>, and <math>s</math>.		where the <math>I</math> in the upper left corner is an <math> (n-1) \times (n-1) </math> identity matrix, and the two scalars <math> c = \cos\theta </math> and <math> s = \sin\theta </math> are determined by what rotation angle <math> \theta </math> is appropriate for zeroing out position <math>(i+1,i)</math>. It is not necessary to exhibit <math> \theta </math>; the factors <math> c </math> and <math> s </math> can be determined directly from elements in the matrix <math> G_i </math> should act on. Nor is it necessary to produce the whole matrix; multiplication (from the left) by <math> G_i </math> only affects rows <math> i </math> and <math> i+1 </math>, so it is easier to just update those two rows in place. Likewise, for the Step 3 multiplication by <math> G_i^\mathrm{T} </math> from the right, it is sufficient to remember <math>i</math>, <math>c</math>, and <math>s</math>.

	If using the simple <math> \mu = a_{n,n} </math> strategy, then at the beginning of Step 2 we have a matrix		If using the simple <math> \mu = a_{n,n} </math> strategy, then at the beginning of Step 2 we have a matrix

37.198.120.181: /* A single iteration with explicit shift */ Typo.

2024-12-02T10:55:01Z

A single iteration with explicit shift: Typo.

← Previous revision		Revision as of 10:55, 2 December 2024
Line 99:		Line 99:
	\times & \times & \times & \times & \times \\		\times & \times & \times & \times & \times \\
	0 & \times & \times & \times & \times \\		0 & \times & \times & \times & \times \\
	0 & 0 & \times & \times & ~~c h_{n-1,n}~~ \\		0 & 0 & \times & \times & \times \\
	0 & 0 & 0 & -s^2 h_{n-1,n} & cs h_{n-1,n}		0 & 0 & 0 & -s^2 h_{n-1,n} & cs h_{n-1,n}
	\end{pmatrix}		\end{pmatrix}

37.198.120.181: /* A single iteration with explicit shift */ Showing how steps affect the matrix form.

2024-12-02T10:52:38Z

A single iteration with explicit shift: Showing how steps affect the matrix form.

@@ Line 21: / Line 21: @@
 ====A single iteration with explicit shift====
-The steps of a QR iteration on a real Hessenberg matrix <math>A</math> with explicit shift are:
+The steps of a QR iteration with explicit shift on a real Hessenberg matrix <math>A</math> are:
 # Pick a shift <math>\mu</math> and subtract it from all diagonal elements, producing the matrix <math> A - \mu I </math>. A basic strategy is to use <math> \mu = a_{n,n} </math>, but there are more refined strategies that would further accelerate convergence. The idea is that <math> \mu </math> should be close to an eigenvalue, since making this shift will accelerate convergence to that eigenvalue.
 # Perform a sequence of [[Givens rotation]]s <math> G_1, G_2, \dots, G_{n-1} </math> on <math> A - \mu I </math>, where <math> G_i </math> acts on rows <math>i</math> and <math>i+1</math>, and <math> G_i </math> is chosen to zero out position <math>(i+1,i)</math> of <math> G_{i-1} \dotsb G_1 (A - \mu I) </math>. This produces the upper triangular matrix <math> R = G_{n-1} \dotsb G_1 (A - \mu I) </math>. The orthogonal factor <math> Q </math> would be <math> G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, but it is neither necessary nor efficient to produce that explicitly.
 # Now multiply <math> R </math> by the Givens matrices <math> G_1^\mathrm{T} </math>, <math> G_2^\mathrm{T} </math>, …, <math> G_{n-1}^\mathrm{T} </math> on the right, where <math> G_i^\mathrm{T} </math> instead acts on columns <math>i</math> and <math> i+1 </math>. This produces the matrix <math> RQ = R G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, which is again on Hessenberg form.
 # Finally undo the shift by adding <math> \mu </math> to all diagonal entries. The result is <math> A' = RQ + \mu I </math>. Since <math>Q</math> commutes with <math>I</math>, we have that <math> A' = Q^\mathrm{T} (A-\mu I) Q + \mu I = Q^\mathrm{T} A Q </math>.
 == Visualization ==

37.198.120.181: /* Iteration phase */ New subsection "A single iteration with explicit shift"

2024-12-02T08:33:28Z

Iteration phase: New subsection "A single iteration with explicit shift"

← Previous revision		Revision as of 08:33, 2 December 2024
Line 19:		Line 19:

	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.{{clarify\|date=June 2012}}		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.{{clarify\|date=June 2012}}

			====A single iteration with explicit shift====
			The steps of a QR iteration on a real Hessenberg matrix <math>A</math> with explicit shift are:
			# Pick a shift <math>\mu</math> and subtract it from all diagonal elements, producing the matrix <math> A - \mu I </math>. A basic strategy is to use <math> \mu = a_{n,n} </math>, but there are more refined strategies that would further accelerate convergence. The idea is that <math> \mu </math> should be close to an eigenvalue, since making this shift will accelerate convergence to that eigenvalue.
			# Perform a sequence of [[Givens rotation]]s <math> G_1, G_2, \dots, G_{n-1} </math> on <math> A - \mu I </math>, where <math> G_i </math> acts on rows <math>i</math> and <math>i+1</math>, and <math> G_i </math> is chosen to zero out position <math>(i+1,i)</math> of <math> G_{i-1} \dotsb G_1 (A - \mu I) </math>. This produces the upper triangular matrix <math> R = G_{n-1} \dotsb G_1 (A - \mu I) </math>. The orthogonal factor <math> Q </math> would be <math> G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, but it is neither necessary nor efficient to produce that explicitly.
			# Now multiply <math> R </math> by the Givens matrices <math> G_1^\mathrm{T} </math>, <math> G_2^\mathrm{T} </math>, …, <math> G_{n-1}^\mathrm{T} </math> on the right, where <math> G_i^\mathrm{T} </math> instead acts on columns <math>i</math> and <math> i+1 </math>. This produces the matrix <math> RQ = R G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, which is again on Hessenberg form.
			# Finally undo the shift by adding <math> \mu </math> to all diagonal entries. The result is <math> A' = RQ + \mu I </math>. Since <math>Q</math> commutes with <math>I</math>, we have that <math> A' = Q^\mathrm{T} (A-\mu I) Q + \mu I = Q^\mathrm{T} A Q </math>.

	== Visualization ==		== Visualization ==

130.243.94.123: /* Iteration phase */ Wrote lead-in to the iteration phase.

2024-10-29T12:49:32Z

Iteration phase: Wrote lead-in to the iteration phase.

← Previous revision		Revision as of 12:49, 29 October 2024
Line 16:		Line 16:

	===Iteration phase===		===Iteration phase===
			If a Hessenberg matrix <math>A</math> has element <math> a_{k,k-1} = 0 </math> for some <math>k</math>, i.e., if one of the elements just below the diagonal is in fact zero, then it decomposes into blocks whose eigenproblems may be solved separately; an eigenvalue is either an eigenvalue of the submatrix of the first <math>k-1</math> rows and columns, or an eigenvalue of the submatrix of remaining rows and columns. The purpose of the QR iteration step is to shrink one of these <math>a_{k,k-1}</math> elements so that effectively a small block along the diagonal is split off from the bulk of the matrix. In the case of a real eigenvalue that is usually the <math> 1 \times 1 </math> block in the lower right corner (in which case element <math> a_{nn} </math> holds that eigenvalue), whereas in the case of a pair of conjugate complex eigenvalues it is the <math> 2 \times 2 </math> block in the lower right corner.

	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.{{clarify\|date=June 2012}}		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.{{clarify\|date=June 2012}}