Eigenvalue algorithm - Revision history

OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-26T04:25:11Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 04:25, 26 May 2025
Line 47:		Line 47:
	For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.		For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.

	The condition number for the problem of finding the eigenspace of a normal matrix {{math\|''A''}} corresponding to an eigenvalue {{math\|''λ''}} has been shown to be inversely proportional to the minimum distance between {{math\|''λ''}} and the other distinct eigenvalues of {{math\|''A''}}.<ref>{{Citation \| author = S.C. Eisenstat \| author2 = I.C.F. Ipsen \| title = Relative Perturbation Results for Eigenvalues and Eigenvectors of Diagonalisable Matrices \| journal = BIT \| volume = 38 \| issue = 3 \| pages = 502–9 \| year = 1998 \| doi=10.1007/bf02510256\| s2cid = 119886389 \| url = http://www.lib.ncsu.edu/resolver/1840.4/286 }}</ref> In particular, the eigenspace problem for normal matrices is well-conditioned for isolated eigenvalues. When eigenvalues are not isolated, the best that can be hoped for is to identify the span of all eigenvectors of nearby eigenvalues.		The condition number for the problem of finding the eigenspace of a normal matrix {{math\|''A''}} corresponding to an eigenvalue {{math\|''λ''}} has been shown to be inversely proportional to the minimum distance between {{math\|''λ''}} and the other distinct eigenvalues of {{math\|''A''}}.<ref>{{Citation \| author = S.C. Eisenstat \| author2 = I.C.F. Ipsen \| title = Relative Perturbation Results for Eigenvalues and Eigenvectors of Diagonalisable Matrices \| journal = BIT \| volume = 38 \| issue = 3 \| pages = 502–9 \| year = 1998 \| doi=10.1007/bf02510256\| s2cid = 119886389 \| url = http://www.lib.ncsu.edu/resolver/1840.4/286 \| url-access = subscription }}</ref> In particular, the eigenspace problem for normal matrices is well-conditioned for isolated eigenvalues. When eigenvalues are not isolated, the best that can be hoped for is to identify the span of all eigenvectors of nearby eigenvalues.

	==Algorithms==		==Algorithms==
Line 373:		Line 373:
	\| jstor =		\| jstor =
	\| issn =		\| issn =
	\| doi = 10.1137/0612005}}		\| doi = 10.1137/0612005\| url-access = subscription
			}}

	{{Numerical linear algebra}}		{{Numerical linear algebra}}

Dmoore5556: /* Iterative algorithms */ adjust a wikilink

2025-05-18T00:21:02Z

Iterative algorithms: adjust a wikilink

← Previous revision		Revision as of 00:21, 18 May 2025
Line 174:		Line 174:
	\| [[Folded spectrum method]] \|\| real symmetric \|\| eigenpair with value closest to ''μ'' \|\| \|\| \|\| align="left" \| Preconditioned inverse iteration applied to {{math\|(''A'' − ''μI'')<sup>2</sup>}}		\| [[Folded spectrum method]] \|\| real symmetric \|\| eigenpair with value closest to ''μ'' \|\| \|\| \|\| align="left" \| Preconditioned inverse iteration applied to {{math\|(''A'' − ''μI'')<sup>2</sup>}}
	\|-		\|-
	\| [[~~MRRR\|~~MRRR algorithm]]<ref>{{Citation		\| [[MRRR algorithm]]<ref>{{Citation
	\| last1=Dhillon		\| last1=Dhillon
	\| first1=Inderjit S.		\| first1=Inderjit S.

Redav: /* Eigenvalues and eigenvectors */ real.l => real. {typo}

2025-03-13T01:55:12Z

Eigenvalues and eigenvectors: real.l => real. {typo}

← Previous revision		Revision as of 01:55, 13 March 2025
Line 8:		Line 8:
	:<math>\left(A - \lambda I\right)^k {\mathbf v} = 0,</math>		:<math>\left(A - \lambda I\right)^k {\mathbf v} = 0,</math>

	where {{math\|'''v'''}} is a nonzero {{math\|''n'' × 1}} column vector, {{math\|''I''}} is the {{math\|''n'' × ''n''}} [[identity matrix]], {{math\|''k''}} is a positive integer, and both {{math\|''λ''}} and {{math\|'''v'''}} are allowed to be complex even when {{math\|''A''}} is real.l When {{math\|1=''k'' = 1}}, the vector is called simply an ''[[eigenvector]]'', and the pair is called an ''eigenpair''. In this case, {{math\|1=''A'''''v''' = ''λ'''''v'''}}. Any eigenvalue {{math\|''λ''}} of {{math\|''A''}} has ordinary<ref group="note">The term "ordinary" is used here only to emphasize the distinction between "eigenvector" and "generalized eigenvector".</ref> eigenvectors associated to it, for if {{math\|''k''}} is the smallest integer such that {{math\|1=(''A'' − ''λI'')<sup>''k''</sup> '''v''' = 0}} for a generalized eigenvector {{math\|'''v'''}}, then {{math\|1=(''A'' − ''λI'')<sup>''k''−1</sup> '''v'''}} is an ordinary eigenvector. The value {{math\|''k''}} can always be taken as less than or equal to {{math\|''n''}}. In particular, {{math\|1=(''A'' − ''λI'')<sup>''n''</sup> '''v''' = 0}} for all generalized eigenvectors {{math\|'''v'''}} associated with {{math\|''λ''}}.		where {{math\|'''v'''}} is a nonzero {{math\|''n'' × 1}} column vector, {{math\|''I''}} is the {{math\|''n'' × ''n''}} [[identity matrix]], {{math\|''k''}} is a positive integer, and both {{math\|''λ''}} and {{math\|'''v'''}} are allowed to be complex even when {{math\|''A''}} is real. When {{math\|1=''k'' = 1}}, the vector is called simply an ''[[eigenvector]]'', and the pair is called an ''eigenpair''. In this case, {{math\|1=''A'''''v''' = ''λ'''''v'''}}. Any eigenvalue {{math\|''λ''}} of {{math\|''A''}} has ordinary<ref group="note">The term "ordinary" is used here only to emphasize the distinction between "eigenvector" and "generalized eigenvector".</ref> eigenvectors associated to it, for if {{math\|''k''}} is the smallest integer such that {{math\|1=(''A'' − ''λI'')<sup>''k''</sup> '''v''' = 0}} for a generalized eigenvector {{math\|'''v'''}}, then {{math\|1=(''A'' − ''λI'')<sup>''k''−1</sup> '''v'''}} is an ordinary eigenvector. The value {{math\|''k''}} can always be taken as less than or equal to {{math\|''n''}}. In particular, {{math\|1=(''A'' − ''λI'')<sup>''n''</sup> '''v''' = 0}} for all generalized eigenvectors {{math\|'''v'''}} associated with {{math\|''λ''}}.

	For each eigenvalue {{math\|λ}} of {{math\|''A''}}, the [[kernel (matrix)\|kernel]] {{math\|ker(''A'' − ''λI'')}} consists of all eigenvectors associated with {{math\|''λ''}} (along with 0), called the ''[[eigenspace]]'' of {{math\|''λ''}}, while the vector space {{math\|ker((''A'' − ''λI'')<sup>''n''</sup>)}} consists of all generalized eigenvectors, and is called the ''[[generalized eigenspace]]''. The ''[[geometric multiplicity]]'' of {{math\|''λ''}} is the dimension of its eigenspace. The ''[[algebraic multiplicity]]'' of {{math\|''λ''}} is the dimension of its generalized eigenspace. The latter terminology is justified by the equation		For each eigenvalue {{math\|λ}} of {{math\|''A''}}, the [[kernel (matrix)\|kernel]] {{math\|ker(''A'' − ''λI'')}} consists of all eigenvectors associated with {{math\|''λ''}} (along with 0), called the ''[[eigenspace]]'' of {{math\|''λ''}}, while the vector space {{math\|ker((''A'' − ''λI'')<sup>''n''</sup>)}} consists of all generalized eigenvectors, and is called the ''[[generalized eigenspace]]''. The ''[[geometric multiplicity]]'' of {{math\|''λ''}} is the dimension of its eigenspace. The ''[[algebraic multiplicity]]'' of {{math\|''λ''}} is the dimension of its generalized eigenspace. The latter terminology is justified by the equation

2001:67C:10EC:578C:8000:0:0:E0E: /* Algorithms */

2025-02-25T12:02:14Z

Algorithms

← Previous revision		Revision as of 12:02, 25 February 2025
Line 51:		Line 51:
	==Algorithms==		==Algorithms==

	The most reliable and most widely used algorithm for computing eigenvalues is [[John G. F. Francis]]' [[QR algorithm]], considered one of the top ten algorithms of 20th century.<ref name="t10">{{cite journal \|last1=J. Dongarra and F. Sullivan \|title=Top ten algorithms of the century \|journal=Computing in Science and Engineering \|date=2000 \|volume=2 \|page=22-23\|doi=10.1109/MCISE.2000.814652 }}</ref>		The most reliable and most widely used algorithm for computing eigenvalues is [[John G. F. Francis]]' and [[Vera N. Kublanovskaya]]'s [[QR algorithm]], considered one of the top ten algorithms of 20th century.<ref name="t10">{{cite journal \|last1=J. Dongarra and F. Sullivan \|title=Top ten algorithms of the century \|journal=Computing in Science and Engineering \|date=2000 \|volume=2 \|page=22-23\|doi=10.1109/MCISE.2000.814652 }}</ref>

	Any monic polynomial is the characteristic polynomial of its [[companion matrix]]. Therefore, a general algorithm for finding eigenvalues could also be used to find the roots of polynomials. The [[Abel–Ruffini theorem]] shows that any such algorithm for dimensions greater than 4 must either be infinite, or involve functions of greater complexity than elementary arithmetic operations and fractional powers. For this reason algorithms that exactly calculate eigenvalues in a finite number of steps only exist for a few special classes of matrices. For general matrices, algorithms are [[Iterative method\|iterative]], producing better approximate solutions with each iteration.		Any monic polynomial is the characteristic polynomial of its [[companion matrix]]. Therefore, a general algorithm for finding eigenvalues could also be used to find the roots of polynomials. The [[Abel–Ruffini theorem]] shows that any such algorithm for dimensions greater than 4 must either be infinite, or involve functions of greater complexity than elementary arithmetic operations and fractional powers. For this reason algorithms that exactly calculate eigenvalues in a finite number of steps only exist for a few special classes of matrices. For general matrices, algorithms are [[Iterative method\|iterative]], producing better approximate solutions with each iteration.

Citation bot: Added pages. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Numerical linear algebra | #UCB_Category 80/123

2024-12-21T05:54:48Z

Added pages. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Numerical linear algebra | #UCB_Category 80/123

← Previous revision		Revision as of 05:54, 21 December 2024
Line 204:		Line 204:
	\| journal=Proceedings of the 40th International Conference on Machine Learning		\| journal=Proceedings of the 40th International Conference on Machine Learning
	\| year=2023		\| year=2023
			\| pages=7513–7532
	\| url=https://proceedings.mlr.press/v202/delattre23a.html		\| url=https://proceedings.mlr.press/v202/delattre23a.html
	}}</ref> \|\| general \|\| Eigenpair with largest eigenvalue \|\| \|\| super-linear \|\| align="left" \|Repeatedly computes the Gram product and rescales, deterministically.		}}</ref> \|\| general \|\| Eigenpair with largest eigenvalue \|\| \|\| super-linear \|\| align="left" \|Repeatedly computes the Gram product and rescales, deterministically.

FrescoBot: Bot: link syntax

2024-08-18T17:55:46Z

Bot: link syntax

← Previous revision		Revision as of 17:55, 18 August 2024
Line 43:		Line 43:
	Any problem of numeric calculation can be viewed as the evaluation of some function {{math\|''f''}} for some input {{math\|''x''}}. The [[condition number]] {{math\|''κ''(''f'', ''x'')}} of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base-10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best-case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well-conditioned. However, the problem of finding the roots of a polynomial can be [[Wilkinson's polynomial\|very ill-conditioned]]. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill-conditioned even when the problem is not.		Any problem of numeric calculation can be viewed as the evaluation of some function {{math\|''f''}} for some input {{math\|''x''}}. The [[condition number]] {{math\|''κ''(''f'', ''x'')}} of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base-10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best-case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well-conditioned. However, the problem of finding the roots of a polynomial can be [[Wilkinson's polynomial\|very ill-conditioned]]. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill-conditioned even when the problem is not.

	For the problem of solving the linear equation {{math\|1=''A'''''v''' = '''b'''}} where {{math\|''A''}} is invertible, the [[Condition number#Matrices\|matrix condition number]] {{math\|1=''κ''(''A''<sup>−1</sup>, '''b''')}} is given by {{math\|1={{!!}}''A''{{!!}}<sub>op</sub>{{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub>}}, where {{nowrap\|{{!!}} {{!!}}<sub>op</sub>}} is the [[operator norm]] subordinate to the normal [[Norm (mathematics)#Euclidean norm\|Euclidean norm]] on {{math\|'''C'''<sup>''n''</sup>}}. Since this number is independent of {{math\|'''b'''}} and is the same for {{math\|''A''}} and {{math\|''A''<sup>−1</sup>}}, it is usually just called the condition number {{math\|''κ''(''A'')}} of the matrix {{math\|''A''}}. This value {{math\|''κ''(''A'')}} is also the absolute value of the ratio of the largest [[~~Singular_value\|~~singular value]] of {{math\|''A''}} to its smallest. If {{math\|''A''}} is [[Unitary matrix\|unitary]], then {{math\|1={{!!}}''A''{{!!}}<sub>op</sub> = {{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub> = 1}}, so {{math\|1=''κ''(''A'') = 1}}. For general matrices, the operator norm is often difficult to calculate. For this reason, other [[matrix norms]] are commonly used to estimate the condition number.		For the problem of solving the linear equation {{math\|1=''A'''''v''' = '''b'''}} where {{math\|''A''}} is invertible, the [[Condition number#Matrices\|matrix condition number]] {{math\|1=''κ''(''A''<sup>−1</sup>, '''b''')}} is given by {{math\|1={{!!}}''A''{{!!}}<sub>op</sub>{{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub>}}, where {{nowrap\|{{!!}} {{!!}}<sub>op</sub>}} is the [[operator norm]] subordinate to the normal [[Norm (mathematics)#Euclidean norm\|Euclidean norm]] on {{math\|'''C'''<sup>''n''</sup>}}. Since this number is independent of {{math\|'''b'''}} and is the same for {{math\|''A''}} and {{math\|''A''<sup>−1</sup>}}, it is usually just called the condition number {{math\|''κ''(''A'')}} of the matrix {{math\|''A''}}. This value {{math\|''κ''(''A'')}} is also the absolute value of the ratio of the largest [[singular value]] of {{math\|''A''}} to its smallest. If {{math\|''A''}} is [[Unitary matrix\|unitary]], then {{math\|1={{!!}}''A''{{!!}}<sub>op</sub> = {{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub> = 1}}, so {{math\|1=''κ''(''A'') = 1}}. For general matrices, the operator norm is often difficult to calculate. For this reason, other [[matrix norms]] are commonly used to estimate the condition number.

	For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.		For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.

164.73.163.20: corrected mistake in condition number definition: it's the ratio of the largest sigular value of A to the smallest. }it said "eigenvalue" instead of "singular value"

2024-07-24T12:52:52Z

corrected mistake in condition number definition: it's the ratio of the largest sigular value of A to the smallest. }it said "eigenvalue" instead of "singular value"

← Previous revision		Revision as of 12:52, 24 July 2024
Line 8:		Line 8:
	:<math>\left(A - \lambda I\right)^k {\mathbf v} = 0,</math>		:<math>\left(A - \lambda I\right)^k {\mathbf v} = 0,</math>

	where {{math\|'''v'''}} is a nonzero {{math\|''n'' × 1}} column vector, {{math\|''I''}} is the {{math\|''n'' × ''n''}} [[identity matrix]], {{math\|''k''}} is a positive integer, and both {{math\|''λ''}} and {{math\|'''v'''}} are allowed to be complex even when {{math\|''A''}} is real. When {{math\|1=''k'' = 1}}, the vector is called simply an ''[[eigenvector]]'', and the pair is called an ''eigenpair''. In this case, {{math\|1=''A'''''v''' = ''λ'''''v'''}}. Any eigenvalue {{math\|''λ''}} of {{math\|''A''}} has ordinary<ref group="note">The term "ordinary" is used here only to emphasize the distinction between "eigenvector" and "generalized eigenvector".</ref> eigenvectors associated to it, for if {{math\|''k''}} is the smallest integer such that {{math\|1=(''A'' − ''λI'')<sup>''k''</sup> '''v''' = 0}} for a generalized eigenvector {{math\|'''v'''}}, then {{math\|1=(''A'' − ''λI'')<sup>''k''−1</sup> '''v'''}} is an ordinary eigenvector. The value {{math\|''k''}} can always be taken as less than or equal to {{math\|''n''}}. In particular, {{math\|1=(''A'' − ''λI'')<sup>''n''</sup> '''v''' = 0}} for all generalized eigenvectors {{math\|'''v'''}} associated with {{math\|''λ''}}.		where {{math\|'''v'''}} is a nonzero {{math\|''n'' × 1}} column vector, {{math\|''I''}} is the {{math\|''n'' × ''n''}} [[identity matrix]], {{math\|''k''}} is a positive integer, and both {{math\|''λ''}} and {{math\|'''v'''}} are allowed to be complex even when {{math\|''A''}} is real.l When {{math\|1=''k'' = 1}}, the vector is called simply an ''[[eigenvector]]'', and the pair is called an ''eigenpair''. In this case, {{math\|1=''A'''''v''' = ''λ'''''v'''}}. Any eigenvalue {{math\|''λ''}} of {{math\|''A''}} has ordinary<ref group="note">The term "ordinary" is used here only to emphasize the distinction between "eigenvector" and "generalized eigenvector".</ref> eigenvectors associated to it, for if {{math\|''k''}} is the smallest integer such that {{math\|1=(''A'' − ''λI'')<sup>''k''</sup> '''v''' = 0}} for a generalized eigenvector {{math\|'''v'''}}, then {{math\|1=(''A'' − ''λI'')<sup>''k''−1</sup> '''v'''}} is an ordinary eigenvector. The value {{math\|''k''}} can always be taken as less than or equal to {{math\|''n''}}. In particular, {{math\|1=(''A'' − ''λI'')<sup>''n''</sup> '''v''' = 0}} for all generalized eigenvectors {{math\|'''v'''}} associated with {{math\|''λ''}}.

	For each eigenvalue {{math\|λ}} of {{math\|''A''}}, the [[kernel (matrix)\|kernel]] {{math\|ker(''A'' − ''λI'')}} consists of all eigenvectors associated with {{math\|''λ''}} (along with 0), called the ''[[eigenspace]]'' of {{math\|''λ''}}, while the vector space {{math\|ker((''A'' − ''λI'')<sup>''n''</sup>)}} consists of all generalized eigenvectors, and is called the ''[[generalized eigenspace]]''. The ''[[geometric multiplicity]]'' of {{math\|''λ''}} is the dimension of its eigenspace. The ''[[algebraic multiplicity]]'' of {{math\|''λ''}} is the dimension of its generalized eigenspace. The latter terminology is justified by the equation		For each eigenvalue {{math\|λ}} of {{math\|''A''}}, the [[kernel (matrix)\|kernel]] {{math\|ker(''A'' − ''λI'')}} consists of all eigenvectors associated with {{math\|''λ''}} (along with 0), called the ''[[eigenspace]]'' of {{math\|''λ''}}, while the vector space {{math\|ker((''A'' − ''λI'')<sup>''n''</sup>)}} consists of all generalized eigenvectors, and is called the ''[[generalized eigenspace]]''. The ''[[geometric multiplicity]]'' of {{math\|''λ''}} is the dimension of its eigenspace. The ''[[algebraic multiplicity]]'' of {{math\|''λ''}} is the dimension of its generalized eigenspace. The latter terminology is justified by the equation
Line 43:		Line 43:
	Any problem of numeric calculation can be viewed as the evaluation of some function {{math\|''f''}} for some input {{math\|''x''}}. The [[condition number]] {{math\|''κ''(''f'', ''x'')}} of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base-10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best-case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well-conditioned. However, the problem of finding the roots of a polynomial can be [[Wilkinson's polynomial\|very ill-conditioned]]. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill-conditioned even when the problem is not.		Any problem of numeric calculation can be viewed as the evaluation of some function {{math\|''f''}} for some input {{math\|''x''}}. The [[condition number]] {{math\|''κ''(''f'', ''x'')}} of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base-10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best-case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well-conditioned. However, the problem of finding the roots of a polynomial can be [[Wilkinson's polynomial\|very ill-conditioned]]. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill-conditioned even when the problem is not.

	For the problem of solving the linear equation {{math\|1=''A'''''v''' = '''b'''}} where {{math\|''A''}} is invertible, the [[Condition number#Matrices\|matrix condition number]] {{math\|1=''κ''(''A''<sup>−1</sup>, '''b''')}} is given by {{math\|1={{!!}}''A''{{!!}}<sub>op</sub>{{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub>}}, where {{nowrap\|{{!!}} {{!!}}<sub>op</sub>}} is the [[operator norm]] subordinate to the normal [[Norm (mathematics)#Euclidean norm\|Euclidean norm]] on {{math\|'''C'''<sup>''n''</sup>}}. Since this number is independent of {{math\|'''b'''}} and is the same for {{math\|''A''}} and {{math\|''A''<sup>−1</sup>}}, it is usually just called the condition number {{math\|''κ''(''A'')}} of the matrix {{math\|''A''}}. This value {{math\|''κ''(''A'')}} is also the absolute value of the ratio of the largest ~~eigenvalue~~ of {{math\|''A''}} to its smallest. If {{math\|''A''}} is [[Unitary matrix\|unitary]], then {{math\|1={{!!}}''A''{{!!}}<sub>op</sub> = {{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub> = 1}}, so {{math\|1=''κ''(''A'') = 1}}. For general matrices, the operator norm is often difficult to calculate. For this reason, other [[matrix norms]] are commonly used to estimate the condition number.		For the problem of solving the linear equation {{math\|1=''A'''''v''' = '''b'''}} where {{math\|''A''}} is invertible, the [[Condition number#Matrices\|matrix condition number]] {{math\|1=''κ''(''A''<sup>−1</sup>, '''b''')}} is given by {{math\|1={{!!}}''A''{{!!}}<sub>op</sub>{{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub>}}, where {{nowrap\|{{!!}} {{!!}}<sub>op</sub>}} is the [[operator norm]] subordinate to the normal [[Norm (mathematics)#Euclidean norm\|Euclidean norm]] on {{math\|'''C'''<sup>''n''</sup>}}. Since this number is independent of {{math\|'''b'''}} and is the same for {{math\|''A''}} and {{math\|''A''<sup>−1</sup>}}, it is usually just called the condition number {{math\|''κ''(''A'')}} of the matrix {{math\|''A''}}. This value {{math\|''κ''(''A'')}} is also the absolute value of the ratio of the largest [[Singular_value\|singular value]] of {{math\|''A''}} to its smallest. If {{math\|''A''}} is [[Unitary matrix\|unitary]], then {{math\|1={{!!}}''A''{{!!}}<sub>op</sub> = {{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub> = 1}}, so {{math\|1=''κ''(''A'') = 1}}. For general matrices, the operator norm is often difficult to calculate. For this reason, other [[matrix norms]] are commonly used to estimate the condition number.

	For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.		For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.

Suslindisambiguator: /* Algorithms */ added author link for Robert Charles Thompson

2024-03-21T04:41:14Z

Algorithms: added author link for Robert Charles Thompson

← Previous revision		Revision as of 04:41, 21 March 2024
Line 63:		Line 63:
	If an eigenvalue algorithm does not produce eigenvectors, a common practice is to use an inverse iteration based algorithm with {{math\|''μ''}} set to a close approximation to the eigenvalue. This will quickly converge to the eigenvector of the closest eigenvalue to {{math\|''μ''}}. For small matrices, an alternative is to look at the column space of the product of {{math\|''A'' − ''λ''{{'}}''I''}} for each of the other eigenvalues {{math\|''λ''{{'}}}}.		If an eigenvalue algorithm does not produce eigenvectors, a common practice is to use an inverse iteration based algorithm with {{math\|''μ''}} set to a close approximation to the eigenvalue. This will quickly converge to the eigenvector of the closest eigenvalue to {{math\|''μ''}}. For small matrices, an alternative is to look at the column space of the product of {{math\|''A'' − ''λ''{{'}}''I''}} for each of the other eigenvalues {{math\|''λ''{{'}}}}.

	A formula for the norm of unit eigenvector components of normal matrices was discovered by Robert Thompson in 1966 and rediscovered independently by several others.<ref>{{cite journal \|last1=Thompson \|first1=R. C. \|title=Principal submatrices of normal and Hermitian matrices \|journal=Illinois Journal of Mathematics \|date=June 1966 \|volume=10 \|issue=2 \|pages=296–308 \|doi=10.1215/ijm/1256055111 \|doi-access=free }}</ref><ref>{{cite journal \|author1=Peter Nylen \|author2=Tin-Yau Tam \|author3=Frank Uhlig \|title=On the eigenvalues of principal submatrices of normal, hermitian and symmetric matrices \|journal=Linear and Multilinear Algebra \|date=1993 \|volume=36 \|issue=1 \|pages=69–78 \|doi=10.1080/03081089308818276}}</ref><ref>{{cite journal \|vauthors=Bebiano N, Furtado S, da Providência J \|title=On the eigenvalues of principal submatrices of J-normal matrices \|journal=Linear Algebra and Its Applications \|date=2011 \|volume=435 \|issue=12 \|pages=3101–3114 \|doi=10.1016/j.laa.2011.05.033 \|doi-access=free }}</ref><ref>{{cite journal \| vauthors=Forrester PJ, Zhang J \| arxiv=1905.05314 \| title=Corank-1 projections and the randomised Horn problem \| journal=Tunisian Journal of Mathematics \| year=2021 \| volume=3 \| pages=55–73 \| doi=10.2140/tunis.2021.3.55 \| s2cid=153312446 }}</ref><ref>{{cite journal \| vauthors= Denton PB, Parke SJ, Tao T, Zhang X \| arxiv=1908.03795 \| title=Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra \| journal=Bulletin of the American Mathematical Society \| year=2021 \| volume=59 \| page=1 \| doi=10.1090/bull/1722 \| s2cid=213918682 }}</ref>		A formula for the norm of unit eigenvector components of normal matrices was discovered by Robert Thompson in 1966 and rediscovered independently by several others.<ref>{{cite journal \|last1=Thompson \|first1=R. C. \|author-link=Robert Charles Thompson \|title=Principal submatrices of normal and Hermitian matrices \|journal=Illinois Journal of Mathematics \|date=June 1966 \|volume=10 \|issue=2 \|pages=296–308 \|doi=10.1215/ijm/1256055111 \|doi-access=free }}</ref><ref>{{cite journal \|author1=Peter Nylen \|author2=Tin-Yau Tam \|author3=Frank Uhlig \|title=On the eigenvalues of principal submatrices of normal, hermitian and symmetric matrices \|journal=Linear and Multilinear Algebra \|date=1993 \|volume=36 \|issue=1 \|pages=69–78 \|doi=10.1080/03081089308818276}}</ref><ref>{{cite journal \|vauthors=Bebiano N, Furtado S, da Providência J \|title=On the eigenvalues of principal submatrices of J-normal matrices \|journal=Linear Algebra and Its Applications \|date=2011 \|volume=435 \|issue=12 \|pages=3101–3114 \|doi=10.1016/j.laa.2011.05.033 \|doi-access=free }}</ref><ref>{{cite journal \| vauthors=Forrester PJ, Zhang J \| arxiv=1905.05314 \| title=Corank-1 projections and the randomised Horn problem \| journal=Tunisian Journal of Mathematics \| year=2021 \| volume=3 \| pages=55–73 \| doi=10.2140/tunis.2021.3.55 \| s2cid=153312446 }}</ref><ref>{{cite journal \| vauthors= Denton PB, Parke SJ, Tao T, Zhang X \| arxiv=1908.03795 \| title=Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra \| journal=Bulletin of the American Mathematical Society \| year=2021 \| volume=59 \| page=1 \| doi=10.1090/bull/1722 \| s2cid=213918682 }}</ref>
	If {{math\|''A''}} is an <math display="inline"> n \times n</math> normal matrix with eigenvalues {{math\|''λ''<sub>''i''</sub>(''A'')}} and corresponding unit eigenvectors {{math\|'''v'''<sub>''i''</sub>}} whose component entries are {{math\|''v''<sub>''i,j''</sub>}}, let {{math\|''A''<sub>''j''</sub>}} be the <math display="inline"> n - 1 \times n - 1</math> matrix obtained by removing the {{math\|''i''}}-th row and column from {{math\|''A''}}, and let {{math\|''λ''<sub>''k''</sub>(''A''<sub>''j''</sub>)}} be its {{math\|''k''}}-th eigenvalue. Then		If {{math\|''A''}} is an <math display="inline"> n \times n</math> normal matrix with eigenvalues {{math\|''λ''<sub>''i''</sub>(''A'')}} and corresponding unit eigenvectors {{math\|'''v'''<sub>''i''</sub>}} whose component entries are {{math\|''v''<sub>''i,j''</sub>}}, let {{math\|''A''<sub>''j''</sub>}} be the <math display="inline"> n - 1 \times n - 1</math> matrix obtained by removing the {{math\|''i''}}-th row and column from {{math\|''A''}}, and let {{math\|''λ''<sub>''k''</sub>(''A''<sub>''j''</sub>)}} be its {{math\|''k''}}-th eigenvalue. Then
	<math display="block"> \|v_{i,j}\|^2 \prod_{k=1,k\ne i}^n (\lambda_i(A) - \lambda_k(A)) = \prod_{k=1}^{n-1}(\lambda_i(A) - \lambda_k(A_j))</math>		<math display="block"> \|v_{i,j}\|^2 \prod_{k=1,k\ne i}^n (\lambda_i(A) - \lambda_k(A)) = \prod_{k=1}^{n-1}(\lambda_i(A) - \lambda_k(A_j))</math>

176.114.201.5: Changed "3×3 matrices" to "Symmetric 3×3 matrices"

2024-02-12T12:04:23Z

Changed "3×3 matrices" to "Symmetric 3×3 matrices"

← Previous revision		Revision as of 12:04, 12 February 2024
Line 272:		Line 272:
	In both matrices, the columns are multiples of each other, so either column can be used. Thus, {{math\|(1, −2)}} can be taken as an eigenvector associated with the eigenvalue -2, and {{math\|(3, −1)}} as an eigenvector associated with the eigenvalue 3, as can be verified by multiplying them by {{math\|''A''}}.		In both matrices, the columns are multiples of each other, so either column can be used. Thus, {{math\|(1, −2)}} can be taken as an eigenvector associated with the eigenvalue -2, and {{math\|(3, −1)}} as an eigenvector associated with the eigenvalue 3, as can be verified by multiplying them by {{math\|''A''}}.

	===3×3 matrices===		===Symmetric 3×3 matrices===

	The characteristic equation of a symmetric 3×3 matrix {{math\|''A''}} is:		The characteristic equation of a symmetric 3×3 matrix {{math\|''A''}} is:

Citation bot: Add: pages, doi, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1195/1612

2023-12-11T02:54:21Z

Add: pages, doi, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1195/1612

← Previous revision		Revision as of 02:54, 11 December 2023
Line 51:		Line 51:
	==Algorithms==		==Algorithms==

	The most reliable and most widely used algorithm for computing eigenvalues is [[John G. F. Francis]]' [[QR algorithm]], considered one of the top ten algorithms of 20th century.<ref name="t10">{{cite journal \|last1=J. Dongarra and F. Sullivan \|title=Top ten algorithms of the century \|journal=Computing in Science and Engineering \|date=2000 \|volume=2 \|page=22-23}}</ref>		The most reliable and most widely used algorithm for computing eigenvalues is [[John G. F. Francis]]' [[QR algorithm]], considered one of the top ten algorithms of 20th century.<ref name="t10">{{cite journal \|last1=J. Dongarra and F. Sullivan \|title=Top ten algorithms of the century \|journal=Computing in Science and Engineering \|date=2000 \|volume=2 \|page=22-23\|doi=10.1109/MCISE.2000.814652 }}</ref>

	Any monic polynomial is the characteristic polynomial of its [[companion matrix]]. Therefore, a general algorithm for finding eigenvalues could also be used to find the roots of polynomials. The [[Abel–Ruffini theorem]] shows that any such algorithm for dimensions greater than 4 must either be infinite, or involve functions of greater complexity than elementary arithmetic operations and fractional powers. For this reason algorithms that exactly calculate eigenvalues in a finite number of steps only exist for a few special classes of matrices. For general matrices, algorithms are [[Iterative method\|iterative]], producing better approximate solutions with each iteration.		Any monic polynomial is the characteristic polynomial of its [[companion matrix]]. Therefore, a general algorithm for finding eigenvalues could also be used to find the roots of polynomials. The [[Abel–Ruffini theorem]] shows that any such algorithm for dimensions greater than 4 must either be infinite, or involve functions of greater complexity than elementary arithmetic operations and fractional powers. For this reason algorithms that exactly calculate eigenvalues in a finite number of steps only exist for a few special classes of matrices. For general matrices, algorithms are [[Iterative method\|iterative]], producing better approximate solutions with each iteration.
Line 108:		Line 108:
	\|}		\|}

	For symmetric tridiagonal eigenvalue problems all eigenvalues (without eigenvectors) can be computed numerically in time O(n log(n)), using bisection on the characteristic polynomial.<ref name=CoakleyRokhlin>{{Citation \|last=Coakley\|first=Ed S. \|title=A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices. \|journal=[[Applied and Computational Harmonic Analysis]] \|volume=34 \|issue=3 \|date=May 2013 \|~~page~~=379–414 \|doi=10.1016/j.acha.2012.06.003\|doi-access= }}</ref>		For symmetric tridiagonal eigenvalue problems all eigenvalues (without eigenvectors) can be computed numerically in time O(n log(n)), using bisection on the characteristic polynomial.<ref name=CoakleyRokhlin>{{Citation \|last=Coakley\|first=Ed S. \|title=A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices. \|journal=[[Applied and Computational Harmonic Analysis]] \|volume=34 \|issue=3 \|date=May 2013 \|pages=379–414 \|doi=10.1016/j.acha.2012.06.003\|doi-access= }}</ref>

	==Iterative algorithms==		==Iterative algorithms==
Line 193:		Line 193:
	\|-		\|-
	\| [[Gram iteration]]<ref>{{Citation		\| [[Gram iteration]]<ref>{{Citation
	\| ~~last~~=Delattre		\| last1=Delattre
	\| ~~first~~=B.		\| first1=B.
	\| last2=Barthélemy		\| last2=Barthélemy
	\| first2=Q.		\| first2=Q.

← Previous revision		Revision as of 17:55, 18 August 2024
Line 43:		Line 43:
	Any problem of numeric calculation can be viewed as the evaluation of some function {{math\|''f''}} for some input {{math\|''x''}}. The [[condition number]] {{math\|''κ''(''f'', ''x'')}} of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base-10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best-case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well-conditioned. However, the problem of finding the roots of a polynomial can be [[Wilkinson's polynomial\|very ill-conditioned]]. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill-conditioned even when the problem is not.		Any problem of numeric calculation can be viewed as the evaluation of some function {{math\|''f''}} for some input {{math\|''x''}}. The [[condition number]] {{math\|''κ''(''f'', ''x'')}} of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base-10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best-case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well-conditioned. However, the problem of finding the roots of a polynomial can be [[Wilkinson's polynomial\|very ill-conditioned]]. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill-conditioned even when the problem is not.

	For the problem of solving the linear equation {{math\|1=''A'''''v''' = '''b'''}} where {{math\|''A''}} is invertible, the [[Condition number#Matrices\|matrix condition number]] {{math\|1=''κ''(''A''<sup>−1</sup>, '''b''')}} is given by {{math\|1={{!!}}''A''{{!!}}<sub>op</sub>{{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub>}}, where {{nowrap\|{{!!}} {{!!}}<sub>op</sub>}} is the [[operator norm]] subordinate to the normal [[Norm (mathematics)#Euclidean norm\|Euclidean norm]] on {{math\|'''C'''<sup>''n''</sup>}}. Since this number is independent of {{math\|'''b'''}} and is the same for {{math\|''A''}} and {{math\|''A''<sup>−1</sup>}}, it is usually just called the condition number {{math\|''κ''(''A'')}} of the matrix {{math\|''A''}}. This value {{math\|''κ''(''A'')}} is also the absolute value of the ratio of the largest [[~~Singular_value\|~~singular value]] of {{math\|''A''}} to its smallest. If {{math\|''A''}} is [[Unitary matrix\|unitary]], then {{math\|1={{!!}}''A''{{!!}}<sub>op</sub> = {{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub> = 1}}, so {{math\|1=''κ''(''A'') = 1}}. For general matrices, the operator norm is often difficult to calculate. For this reason, other [[matrix norms]] are commonly used to estimate the condition number.		For the problem of solving the linear equation {{math\|1=''A'''''v''' = '''b'''}} where {{math\|''A''}} is invertible, the [[Condition number#Matrices\|matrix condition number]] {{math\|1=''κ''(''A''<sup>−1</sup>, '''b''')}} is given by {{math\|1={{!!}}''A''{{!!}}<sub>op</sub>{{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub>}}, where {{nowrap\|{{!!}} {{!!}}<sub>op</sub>}} is the [[operator norm]] subordinate to the normal [[Norm (mathematics)#Euclidean norm\|Euclidean norm]] on {{math\|'''C'''<sup>''n''</sup>}}. Since this number is independent of {{math\|'''b'''}} and is the same for {{math\|''A''}} and {{math\|''A''<sup>−1</sup>}}, it is usually just called the condition number {{math\|''κ''(''A'')}} of the matrix {{math\|''A''}}. This value {{math\|''κ''(''A'')}} is also the absolute value of the ratio of the largest [[singular value]] of {{math\|''A''}} to its smallest. If {{math\|''A''}} is [[Unitary matrix\|unitary]], then {{math\|1={{!!}}''A''{{!!}}<sub>op</sub> = {{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub> = 1}}, so {{math\|1=''κ''(''A'') = 1}}. For general matrices, the operator norm is often difficult to calculate. For this reason, other [[matrix norms]] are commonly used to estimate the condition number.

	For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.		For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.

← Previous revision		Revision as of 12:52, 24 July 2024
Line 8:		Line 8:
	:<math>\left(A - \lambda I\right)^k {\mathbf v} = 0,</math>		:<math>\left(A - \lambda I\right)^k {\mathbf v} = 0,</math>

	where {{math\|'''v'''}} is a nonzero {{math\|''n'' × 1}} column vector, {{math\|''I''}} is the {{math\|''n'' × ''n''}} [[identity matrix]], {{math\|''k''}} is a positive integer, and both {{math\|''λ''}} and {{math\|'''v'''}} are allowed to be complex even when {{math\|''A''}} is real. When {{math\|1=''k'' = 1}}, the vector is called simply an ''[[eigenvector]]'', and the pair is called an ''eigenpair''. In this case, {{math\|1=''A'''''v''' = ''λ'''''v'''}}. Any eigenvalue {{math\|''λ''}} of {{math\|''A''}} has ordinary<ref group="note">The term "ordinary" is used here only to emphasize the distinction between "eigenvector" and "generalized eigenvector".</ref> eigenvectors associated to it, for if {{math\|''k''}} is the smallest integer such that {{math\|1=(''A'' − ''λI'')<sup>''k''</sup> '''v''' = 0}} for a generalized eigenvector {{math\|'''v'''}}, then {{math\|1=(''A'' − ''λI'')<sup>''k''−1</sup> '''v'''}} is an ordinary eigenvector. The value {{math\|''k''}} can always be taken as less than or equal to {{math\|''n''}}. In particular, {{math\|1=(''A'' − ''λI'')<sup>''n''</sup> '''v''' = 0}} for all generalized eigenvectors {{math\|'''v'''}} associated with {{math\|''λ''}}.		where {{math\|'''v'''}} is a nonzero {{math\|''n'' × 1}} column vector, {{math\|''I''}} is the {{math\|''n'' × ''n''}} [[identity matrix]], {{math\|''k''}} is a positive integer, and both {{math\|''λ''}} and {{math\|'''v'''}} are allowed to be complex even when {{math\|''A''}} is real.l When {{math\|1=''k'' = 1}}, the vector is called simply an ''[[eigenvector]]'', and the pair is called an ''eigenpair''. In this case, {{math\|1=''A'''''v''' = ''λ'''''v'''}}. Any eigenvalue {{math\|''λ''}} of {{math\|''A''}} has ordinary<ref group="note">The term "ordinary" is used here only to emphasize the distinction between "eigenvector" and "generalized eigenvector".</ref> eigenvectors associated to it, for if {{math\|''k''}} is the smallest integer such that {{math\|1=(''A'' − ''λI'')<sup>''k''</sup> '''v''' = 0}} for a generalized eigenvector {{math\|'''v'''}}, then {{math\|1=(''A'' − ''λI'')<sup>''k''−1</sup> '''v'''}} is an ordinary eigenvector. The value {{math\|''k''}} can always be taken as less than or equal to {{math\|''n''}}. In particular, {{math\|1=(''A'' − ''λI'')<sup>''n''</sup> '''v''' = 0}} for all generalized eigenvectors {{math\|'''v'''}} associated with {{math\|''λ''}}.

	For each eigenvalue {{math\|λ}} of {{math\|''A''}}, the [[kernel (matrix)\|kernel]] {{math\|ker(''A'' − ''λI'')}} consists of all eigenvectors associated with {{math\|''λ''}} (along with 0), called the ''[[eigenspace]]'' of {{math\|''λ''}}, while the vector space {{math\|ker((''A'' − ''λI'')<sup>''n''</sup>)}} consists of all generalized eigenvectors, and is called the ''[[generalized eigenspace]]''. The ''[[geometric multiplicity]]'' of {{math\|''λ''}} is the dimension of its eigenspace. The ''[[algebraic multiplicity]]'' of {{math\|''λ''}} is the dimension of its generalized eigenspace. The latter terminology is justified by the equation		For each eigenvalue {{math\|λ}} of {{math\|''A''}}, the [[kernel (matrix)\|kernel]] {{math\|ker(''A'' − ''λI'')}} consists of all eigenvectors associated with {{math\|''λ''}} (along with 0), called the ''[[eigenspace]]'' of {{math\|''λ''}}, while the vector space {{math\|ker((''A'' − ''λI'')<sup>''n''</sup>)}} consists of all generalized eigenvectors, and is called the ''[[generalized eigenspace]]''. The ''[[geometric multiplicity]]'' of {{math\|''λ''}} is the dimension of its eigenspace. The ''[[algebraic multiplicity]]'' of {{math\|''λ''}} is the dimension of its generalized eigenspace. The latter terminology is justified by the equation
Line 43:		Line 43:
	Any problem of numeric calculation can be viewed as the evaluation of some function {{math\|''f''}} for some input {{math\|''x''}}. The [[condition number]] {{math\|''κ''(''f'', ''x'')}} of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base-10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best-case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well-conditioned. However, the problem of finding the roots of a polynomial can be [[Wilkinson's polynomial\|very ill-conditioned]]. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill-conditioned even when the problem is not.		Any problem of numeric calculation can be viewed as the evaluation of some function {{math\|''f''}} for some input {{math\|''x''}}. The [[condition number]] {{math\|''κ''(''f'', ''x'')}} of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base-10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best-case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well-conditioned. However, the problem of finding the roots of a polynomial can be [[Wilkinson's polynomial\|very ill-conditioned]]. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill-conditioned even when the problem is not.

	For the problem of solving the linear equation {{math\|1=''A'''''v''' = '''b'''}} where {{math\|''A''}} is invertible, the [[Condition number#Matrices\|matrix condition number]] {{math\|1=''κ''(''A''<sup>−1</sup>, '''b''')}} is given by {{math\|1={{!!}}''A''{{!!}}<sub>op</sub>{{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub>}}, where {{nowrap\|{{!!}} {{!!}}<sub>op</sub>}} is the [[operator norm]] subordinate to the normal [[Norm (mathematics)#Euclidean norm\|Euclidean norm]] on {{math\|'''C'''<sup>''n''</sup>}}. Since this number is independent of {{math\|'''b'''}} and is the same for {{math\|''A''}} and {{math\|''A''<sup>−1</sup>}}, it is usually just called the condition number {{math\|''κ''(''A'')}} of the matrix {{math\|''A''}}. This value {{math\|''κ''(''A'')}} is also the absolute value of the ratio of the largest ~~eigenvalue~~ of {{math\|''A''}} to its smallest. If {{math\|''A''}} is [[Unitary matrix\|unitary]], then {{math\|1={{!!}}''A''{{!!}}<sub>op</sub> = {{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub> = 1}}, so {{math\|1=''κ''(''A'') = 1}}. For general matrices, the operator norm is often difficult to calculate. For this reason, other [[matrix norms]] are commonly used to estimate the condition number.		For the problem of solving the linear equation {{math\|1=''A'''''v''' = '''b'''}} where {{math\|''A''}} is invertible, the [[Condition number#Matrices\|matrix condition number]] {{math\|1=''κ''(''A''<sup>−1</sup>, '''b''')}} is given by {{math\|1={{!!}}''A''{{!!}}<sub>op</sub>{{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub>}}, where {{nowrap\|{{!!}} {{!!}}<sub>op</sub>}} is the [[operator norm]] subordinate to the normal [[Norm (mathematics)#Euclidean norm\|Euclidean norm]] on {{math\|'''C'''<sup>''n''</sup>}}. Since this number is independent of {{math\|'''b'''}} and is the same for {{math\|''A''}} and {{math\|''A''<sup>−1</sup>}}, it is usually just called the condition number {{math\|''κ''(''A'')}} of the matrix {{math\|''A''}}. This value {{math\|''κ''(''A'')}} is also the absolute value of the ratio of the largest [[Singular_value\|singular value]] of {{math\|''A''}} to its smallest. If {{math\|''A''}} is [[Unitary matrix\|unitary]], then {{math\|1={{!!}}''A''{{!!}}<sub>op</sub> = {{!!}}''A''<sup>−1</sup>{{!!}}<sub>op</sub> = 1}}, so {{math\|1=''κ''(''A'') = 1}}. For general matrices, the operator norm is often difficult to calculate. For this reason, other [[matrix norms]] are commonly used to estimate the condition number.

	For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.		For the eigenvalue problem, [[Bauer–Fike theorem\|Bauer and Fike proved]] that if {{math\|''λ''}} is an eigenvalue for a [[Diagonalizable matrix\|diagonalizable]] {{math\|''n'' × ''n''}} matrix {{math\|''A''}} with [[eigenvector matrix]] {{math\|''V''}}, then the absolute error in calculating {{math\|''λ''}} is bounded by the product of {{math\|''κ''(''V'')}} and the absolute error in {{math\|''A''}}.<ref>{{Citation \| author = F. L. Bauer \| author2 = C. T. Fike \| title = Norms and exclusion theorems \| journal = Numer. Math. \| volume = 2 \| pages = 137–141 \| year = 1960 \| doi=10.1007/bf01386217\| s2cid = 121278235 }}</ref> [[Bauer-Fike theorem#Corollary\|As a result]], the condition number for finding {{math\|''λ''}} is {{math\|1=''κ''(''λ'', ''A'') = ''κ''(''V'') = {{!!}}''V'' {{!!}}<sub>op</sub> {{!!}}''V'' <sup>−1</sup>{{!!}}<sub>op</sub>}}. If {{math\|''A''}} is normal, then {{math\|''V''}} is unitary, and {{math\|1=''κ''(''λ'', ''A'') = 1}}. Thus the eigenvalue problem for all normal matrices is well-conditioned.

← Previous revision		Revision as of 04:41, 21 March 2024
Line 63:		Line 63:
	If an eigenvalue algorithm does not produce eigenvectors, a common practice is to use an inverse iteration based algorithm with {{math\|''μ''}} set to a close approximation to the eigenvalue. This will quickly converge to the eigenvector of the closest eigenvalue to {{math\|''μ''}}. For small matrices, an alternative is to look at the column space of the product of {{math\|''A'' − ''λ''{{'}}''I''}} for each of the other eigenvalues {{math\|''λ''{{'}}}}.		If an eigenvalue algorithm does not produce eigenvectors, a common practice is to use an inverse iteration based algorithm with {{math\|''μ''}} set to a close approximation to the eigenvalue. This will quickly converge to the eigenvector of the closest eigenvalue to {{math\|''μ''}}. For small matrices, an alternative is to look at the column space of the product of {{math\|''A'' − ''λ''{{'}}''I''}} for each of the other eigenvalues {{math\|''λ''{{'}}}}.

	A formula for the norm of unit eigenvector components of normal matrices was discovered by Robert Thompson in 1966 and rediscovered independently by several others.<ref>{{cite journal \|last1=Thompson \|first1=R. C. \|title=Principal submatrices of normal and Hermitian matrices \|journal=Illinois Journal of Mathematics \|date=June 1966 \|volume=10 \|issue=2 \|pages=296–308 \|doi=10.1215/ijm/1256055111 \|doi-access=free }}</ref><ref>{{cite journal \|author1=Peter Nylen \|author2=Tin-Yau Tam \|author3=Frank Uhlig \|title=On the eigenvalues of principal submatrices of normal, hermitian and symmetric matrices \|journal=Linear and Multilinear Algebra \|date=1993 \|volume=36 \|issue=1 \|pages=69–78 \|doi=10.1080/03081089308818276}}</ref><ref>{{cite journal \|vauthors=Bebiano N, Furtado S, da Providência J \|title=On the eigenvalues of principal submatrices of J-normal matrices \|journal=Linear Algebra and Its Applications \|date=2011 \|volume=435 \|issue=12 \|pages=3101–3114 \|doi=10.1016/j.laa.2011.05.033 \|doi-access=free }}</ref><ref>{{cite journal \| vauthors=Forrester PJ, Zhang J \| arxiv=1905.05314 \| title=Corank-1 projections and the randomised Horn problem \| journal=Tunisian Journal of Mathematics \| year=2021 \| volume=3 \| pages=55–73 \| doi=10.2140/tunis.2021.3.55 \| s2cid=153312446 }}</ref><ref>{{cite journal \| vauthors= Denton PB, Parke SJ, Tao T, Zhang X \| arxiv=1908.03795 \| title=Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra \| journal=Bulletin of the American Mathematical Society \| year=2021 \| volume=59 \| page=1 \| doi=10.1090/bull/1722 \| s2cid=213918682 }}</ref>		A formula for the norm of unit eigenvector components of normal matrices was discovered by Robert Thompson in 1966 and rediscovered independently by several others.<ref>{{cite journal \|last1=Thompson \|first1=R. C. \|author-link=Robert Charles Thompson \|title=Principal submatrices of normal and Hermitian matrices \|journal=Illinois Journal of Mathematics \|date=June 1966 \|volume=10 \|issue=2 \|pages=296–308 \|doi=10.1215/ijm/1256055111 \|doi-access=free }}</ref><ref>{{cite journal \|author1=Peter Nylen \|author2=Tin-Yau Tam \|author3=Frank Uhlig \|title=On the eigenvalues of principal submatrices of normal, hermitian and symmetric matrices \|journal=Linear and Multilinear Algebra \|date=1993 \|volume=36 \|issue=1 \|pages=69–78 \|doi=10.1080/03081089308818276}}</ref><ref>{{cite journal \|vauthors=Bebiano N, Furtado S, da Providência J \|title=On the eigenvalues of principal submatrices of J-normal matrices \|journal=Linear Algebra and Its Applications \|date=2011 \|volume=435 \|issue=12 \|pages=3101–3114 \|doi=10.1016/j.laa.2011.05.033 \|doi-access=free }}</ref><ref>{{cite journal \| vauthors=Forrester PJ, Zhang J \| arxiv=1905.05314 \| title=Corank-1 projections and the randomised Horn problem \| journal=Tunisian Journal of Mathematics \| year=2021 \| volume=3 \| pages=55–73 \| doi=10.2140/tunis.2021.3.55 \| s2cid=153312446 }}</ref><ref>{{cite journal \| vauthors= Denton PB, Parke SJ, Tao T, Zhang X \| arxiv=1908.03795 \| title=Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra \| journal=Bulletin of the American Mathematical Society \| year=2021 \| volume=59 \| page=1 \| doi=10.1090/bull/1722 \| s2cid=213918682 }}</ref>
	If {{math\|''A''}} is an <math display="inline"> n \times n</math> normal matrix with eigenvalues {{math\|''λ''<sub>''i''</sub>(''A'')}} and corresponding unit eigenvectors {{math\|'''v'''<sub>''i''</sub>}} whose component entries are {{math\|''v''<sub>''i,j''</sub>}}, let {{math\|''A''<sub>''j''</sub>}} be the <math display="inline"> n - 1 \times n - 1</math> matrix obtained by removing the {{math\|''i''}}-th row and column from {{math\|''A''}}, and let {{math\|''λ''<sub>''k''</sub>(''A''<sub>''j''</sub>)}} be its {{math\|''k''}}-th eigenvalue. Then		If {{math\|''A''}} is an <math display="inline"> n \times n</math> normal matrix with eigenvalues {{math\|''λ''<sub>''i''</sub>(''A'')}} and corresponding unit eigenvectors {{math\|'''v'''<sub>''i''</sub>}} whose component entries are {{math\|''v''<sub>''i,j''</sub>}}, let {{math\|''A''<sub>''j''</sub>}} be the <math display="inline"> n - 1 \times n - 1</math> matrix obtained by removing the {{math\|''i''}}-th row and column from {{math\|''A''}}, and let {{math\|''λ''<sub>''k''</sub>(''A''<sub>''j''</sub>)}} be its {{math\|''k''}}-th eigenvalue. Then
	<math display="block"> \|v_{i,j}\|^2 \prod_{k=1,k\ne i}^n (\lambda_i(A) - \lambda_k(A)) = \prod_{k=1}^{n-1}(\lambda_i(A) - \lambda_k(A_j))</math>		<math display="block"> \|v_{i,j}\|^2 \prod_{k=1,k\ne i}^n (\lambda_i(A) - \lambda_k(A)) = \prod_{k=1}^{n-1}(\lambda_i(A) - \lambda_k(A_j))</math>