Result verification for eigenvectors and eigenvalues.

*(English)*Zbl 0813.65077
Herzberger, Jürgen, Topics in validated computations. Proceedings of the IMACS-GAMM international workshop, Oldenburg, Germany, 30 August - 3 September 1993. Amsterdam: Elsevier. Stud. Comput. Math. 5, 209-276 (1994).

We quote substantially from the introduction:

The paper is addressed to the matrix eigenproblem for \(n \times n\) matrices \(A\) and to related topics such as the generalized eigenproblem, the singular value problem and the inverse eigenvalue problem. Mainly, the considerations are restricted to the case of real eigenvalues \(\lambda^*\) and real eigenvectors \(x^*\). The following problems are considered:

1. Find an interval \([\lambda]\) which contains at least one (or exactly one) real eigenvalue \(\lambda^*\) of \(A\). In particular, find \([\lambda]\) such that the bounds \(\underline\lambda\), \(\overline \lambda\) of \([\lambda]\) differ only in the last few digits. (In this case their common leading digits coincide with those of \(\lambda^*\). This aspect is particularly important if one wants to control rounding errors when approximating \(\lambda^*\) on a computer.)

2. Find interval enclosures \([\lambda]_ i\) simultaneously for all real eigenvalues \(\lambda_ i\) of \(A\).

3. Find an interval vector \([x]\) which contains at least one (or exactly one) eigenvector \(x^*\) associated with an eigenvalue \(\lambda^*\). (Again tight bounds \(\underline x\), \(\overline x\) are required in order to gurantee digits of \(x^*.)\)

4. Find the interval quantities in 1.–3. when \(A\) is replaced by an interval matrix \([A] \in M_{nn} (I(\mathbb{R}))\). In this case \([\lambda]\) means an interval which contains for each \(A \in [A]\) at least one (or exactly one) eigenvalue of \(A\); furthermore, \([x]\) means an interval vector with the following property: for any \(\lambda^* \in [\lambda]\) and any \(A \in [A]\) for which \(\lambda^*\) is an eigenvalue, the vector \([x]\) contains at least one (or exactly one) eigenvector of \(A\) associated with \(\lambda^*\).

In detail, the arrangement of the contents is as follows. Sections 2-4 are concerned with preliminaries (notations and auxiliary results), quadratic systems, and some (classical) existence theorems for eigenvalues \(\lambda^*\) and corresponding eigenvectors \(x^*\) (yielding also estimates for \(\lambda^*\) and \(x^*)\). In Sec. 5, a method for general matrices \(A\) with simple, double or nearly double eigenvalues is presented, whereas, in Sec. 6, for the case of symmetric \(A\) also multiple eigenvalues and clusters of eigenvalues are admitted.

In Sec. 7, the generalized eigenproblem is considered, and, in Sec. 8, a method is derived in order to verify and enclose singular values and singular vectors. In Sec. 9, an inverse eigenvalue problem is described for which the methods of Secs. 5-6 apply. Sec. 10 terminates with a brief sketch on additional topics in result verification for eigenpairs and with biographical remarks. The paper includes 9 examples and a list of 144 references.

For the entire collection see [Zbl 0803.00016].

The paper is addressed to the matrix eigenproblem for \(n \times n\) matrices \(A\) and to related topics such as the generalized eigenproblem, the singular value problem and the inverse eigenvalue problem. Mainly, the considerations are restricted to the case of real eigenvalues \(\lambda^*\) and real eigenvectors \(x^*\). The following problems are considered:

1. Find an interval \([\lambda]\) which contains at least one (or exactly one) real eigenvalue \(\lambda^*\) of \(A\). In particular, find \([\lambda]\) such that the bounds \(\underline\lambda\), \(\overline \lambda\) of \([\lambda]\) differ only in the last few digits. (In this case their common leading digits coincide with those of \(\lambda^*\). This aspect is particularly important if one wants to control rounding errors when approximating \(\lambda^*\) on a computer.)

2. Find interval enclosures \([\lambda]_ i\) simultaneously for all real eigenvalues \(\lambda_ i\) of \(A\).

3. Find an interval vector \([x]\) which contains at least one (or exactly one) eigenvector \(x^*\) associated with an eigenvalue \(\lambda^*\). (Again tight bounds \(\underline x\), \(\overline x\) are required in order to gurantee digits of \(x^*.)\)

4. Find the interval quantities in 1.–3. when \(A\) is replaced by an interval matrix \([A] \in M_{nn} (I(\mathbb{R}))\). In this case \([\lambda]\) means an interval which contains for each \(A \in [A]\) at least one (or exactly one) eigenvalue of \(A\); furthermore, \([x]\) means an interval vector with the following property: for any \(\lambda^* \in [\lambda]\) and any \(A \in [A]\) for which \(\lambda^*\) is an eigenvalue, the vector \([x]\) contains at least one (or exactly one) eigenvector of \(A\) associated with \(\lambda^*\).

In detail, the arrangement of the contents is as follows. Sections 2-4 are concerned with preliminaries (notations and auxiliary results), quadratic systems, and some (classical) existence theorems for eigenvalues \(\lambda^*\) and corresponding eigenvectors \(x^*\) (yielding also estimates for \(\lambda^*\) and \(x^*)\). In Sec. 5, a method for general matrices \(A\) with simple, double or nearly double eigenvalues is presented, whereas, in Sec. 6, for the case of symmetric \(A\) also multiple eigenvalues and clusters of eigenvalues are admitted.

In Sec. 7, the generalized eigenproblem is considered, and, in Sec. 8, a method is derived in order to verify and enclose singular values and singular vectors. In Sec. 9, an inverse eigenvalue problem is described for which the methods of Secs. 5-6 apply. Sec. 10 terminates with a brief sketch on additional topics in result verification for eigenpairs and with biographical remarks. The paper includes 9 examples and a list of 144 references.

For the entire collection see [Zbl 0803.00016].

Reviewer: M.Kracht (Düsseldorf)

##### MSC:

65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |

65G30 | Interval and finite arithmetic |