Eigenvalue algorithm

Definition

Let $n \ge 1$ and let $\mathbb{K}$ be $\R$ or $\C$ . An eigenvalue algorithm is an algorithm that takes as input a matrix $A \in \mathbb{K}^{n \times n}$ (and, for iterative algorithms, a tolerance $\varepsilon > 0$ ) and returns:

numbers $\tilde\lambda_1, \dots, \tilde\lambda_k \in \C$ , with $1 \le k \le n$ , that approximate eigenvalues $\lambda_1, \dots, \lambda_k$ of $A$ , counted with algebraic multiplicity, to within the tolerance;
optionally, vectors $\tilde v_1, \dots, \tilde v_k$ that approximate corresponding eigenvectors or bases of invariant subspaces.

It computes all eigenvalues when $k = n$ , and some eigenvalues otherwise, for example those of largest modulus or those closest to a given shift.

Remarks

Example: the QR algorithm reduces $A$ to Hessenberg form and applies shifted QR steps until the matrix is nearly upper triangular. Its diagonal then approximates all $n$ eigenvalues, so it is an eigenvalue algorithm with $k = n$ . Non-example: an algorithm that only computes the coefficients of the characteristic polynomial does not return eigenvalues, so clause 1 fails. Finding the roots is a further step, and it is badly conditioned in general. The eigenvalues of a general matrix with $n \ge 5$ are not expressible by radicals in its entries. So every eigenvalue algorithm that works for all such matrices is iterative and stops at a tolerance. Accuracy is usually measured by backward error: the output should be the exact eigenvalues of a matrix $A + E$ with $\norm{E}$ small compared with $\norm{A}$ .

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Eigenvalue concept
Eigenvector concept
Matrix concept
Eigenvalue algorithm definition

Tag	`RBVCDV3GCY`
URI	`m2://RBVCDV3GCY`
Kind	definition
Writing	W0 stub
MSC	65F15, 15A18
Defines	Eigenvalue algorithm
Uses	Matrix, Eigenvalue, Eigenvector

Eigenvalue algorithm

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here