a  priori Error Bounds

Theorem 8.4.1 (Gershgorin)   For $A=[a_{ij}]\in \hbox{{\sf I}\kern-.4em\hbox{\sf C}}^{n\times n}$, let

$$\begin{eqnarray*}r_i & = & \sum _{\stackrel{j=1}{_{j\not= i}}}^n\vert a_{ij}\ver... ...rel{i=1}{_{i\not= j}}}^n\vert a_{ij}\vert,\quad j=1,2,\ldots ,n. \end{eqnarray*}$$

Then

(a)

each eigenvalue lies in the union of discs $\vert z-a_{ii}\vert\leq r_i,\quad i=1,2,\ldots ,n$,

(b)

each eigenvalue lies in the union of discs $\vert z-a_{jj}\vert\leq c_j,\quad j=1,2,\ldots ,n$,

(c)

if the union of m of either of these sets of discs is disjoint from the remainder of that set, then this union of m discs contains just m eigenvalues of A (counting multiplicities).

Proof.  

(a)

For any eigenvalue $\lambda$ of A and corresponding eigenvector $\mbox{\boldmath$\space x $ }$, we have $A\mbox{\boldmath$\space x $ } =\lambda \mbox{\boldmath$\space x $ }$. Writing this in component form and rearranging we find

$$(\lambda -a_{ii})x_i=\sum _{\stackrel{j=1}{_{j\not= i}}}^na_{ij}x_j,\quad i=1,2,\ldots ,n.$$

Now choose the particular value of i for which $\vert x_i\vert=\stackrel{\max }{_k}\vert x_k\vert$, then

$$\vert\lambda -a_{ii}\vert=\left\vert\sum _{\stackrel{j=1}{_{j... ...leq \sum_{\stackrel{j=1}{_{j\not= i}}}^n\vert a_{ij}\vert=r_i.$$

The result follows, since the choice of eigenvalue was arbitrary.

(b)

This follows by applying (a) to A^T.

(c)

Consider the family of matrices A(t)=D+tB, where D is the diagonal part of A and B is the rest. Each eigenvalue lies in the union of discs $\vert z-a_{ii}\vert\leq tr_i, \quad i=1,2,\ldots ,n$. As t runs from 0 to 1, A(t) goes from D to A. The coefficients of the characteristic equation are polynomials in t and the roots (i.e. the eigenvalues of A) are continuous functions of the coefficients and hence of t.
When t=0, the discs are just points, each corresponding to an eigenvalue; as t increases, two of the discs intersect, and the eigenvalues must stay within the union, since otherwise they would have to move discontinuously in order to go into another non-intersecting disc. Thus, each intersection brings with it just one eigenvalue.

This concludes the proof.

Corollary 8.4.2   With the hypotheses of the theorem

$$\rho (A)\leq \left\Vert \kern.05em A \kern.05em \right\Vert _... ...rho (A)\leq \left\Vert \kern.05em A \kern.05em \right\Vert _1.$$

Proof.   $\vert a_{ii}+(z-a_{ii})\vert\leq \vert a_{ii}\vert+\vert z-a_{ii}\vert$, so $\vert z\vert\leq \vert a_{ii}\vert+r_i\leq \left\Vert \kern.05em A \kern.05em \right\Vert _{\infty }$, etc.Example.   $A=\left[ \begin{array}{rrr}i & 0 & \frac{1}{2}\\ 0 & 4 & 1\\ 0 & 2 & 5\end{array} \right]$.

The eigenvalues lie in the union of $\vert z-i\vert\leq \frac{1}{2},~ \vert z-4\vert\leq 1,~ \vert z-5\vert\leq 2$.

The characteristic equation is actually

$$(\lambda -i)\{ (\lambda -4)(\lambda -5)-2\} =0,$$

giving the eigenvalues as i,3,6. The corollary gives $\rho (A)\leq 7$.

We consider the effect of a small perturbation of A into $A+\epsilon B$ upon the eigenvalues of A, where A and B are made comparable in size by scaling them so that the moduli of their maximum elements are bounded by 1. We assume that A is nondefective, with right and left eigenvectors $\mbox{\boldmath$\space x $ } _1,\mbox{\boldmath$\space x $ } _2,\ldots ,\mbox{\boldmath$\space x $ } _n$ and $\mbox{\boldmath$\space y $ }^T _1,\mbox{\boldmath$\space y $ } ^T _2,\ldots ,\mbox{\boldmath$\space y $ }^T _n$, both sets of which are linearly independent, and which are scaled so that $\left\Vert \kern.05em \mbox{\boldmath$\space x $ } _i \kern.05em \right\Vert _2=\left\Vert \kern.05em \mbox{\boldmath$\space y $ } _i \kern.05em \right\Vert _2=1$ for $i=1,2,\ldots ,n$.

Let $s_i=\mbox{\boldmath$\space y $ } _i^T\mbox{\boldmath$\space x $ } _i$, so that, with the help of the Schwarz inequality,

$$\vert s_i\vert=\left\vert\mbox{\boldmath$ y $ } _i^T\mbox{\bo... ...rn.05em \mbox{\boldmath$ y $ } _i \kern.05em \right\Vert _2=1.$$

Let $\beta _{ij}=\mbox{\boldmath$\space y $ } _i^TB\mbox{\boldmath$\space x $ } _j=\mbox{\boldmath$\space y $ } _i^T(B\mbox{\boldmath$\space x $ } _j)$. Then, using the Schwarz inequality again,

$$\vert\beta _{ij}\vert\leq \left\Vert \kern.05em \mbox{\boldma... ...2\leq \left\Vert \kern.05em B \kern.05em \right\Vert _2\leq n,$$

where the last result is from exercise 36.

Let $X=[\mbox{\boldmath$\space x $ } _1,\mbox{\boldmath$\space x $ } _2,\ldots ,\mbox{\boldmath$\space x $ } _n]$, then $X^{-1}=\left[ \frac{\mbox{\boldmath$\space y $ } _1^T}{s_1},\frac{\mbox{\boldma... ...y $ } _2^T}{s_2},\ldots \frac{\mbox{\boldmath$\space y $ } _n^T}{s_n}\right] ^T$, since $X^{-1}X=\left[ \frac{\mbox{\boldmath$\space y $ } _i^T\mbox{\boldmath$ x $ } _j}{s_i}\right] =[\delta _{ij}]=I$, using the biorthogonality property. Now

$$X^{-1}(A+\epsilon B)X=\, {\rm diag}\, [\lambda _i]+\epsilon ... ... [\lambda _i]+\epsilon \left[ \frac{\beta _{ij}}{s_i}\right] .$$

Gershgorin gives the discs containing the eigenvalues of $X^{-1}(A+\epsilon B)X$ and hence of $A+\epsilon B$ as

$$\left\vert z-\left( \lambda _i+\epsilon \frac{\beta _{ii}}{s_... ...}{s_i}\right\vert \leq \frac{n(n-1)\epsilon }{\vert s_i\vert}.$$

The condition of the ith eigenvalue clearly depends on |s_i|; if this is small, it suggests that the calculation of $\lambda _i$ is ill-conditioned.

Lemma 8.4.3   Let $\Lambda =\, {\rm diag}\, [\lambda _i]\in \hbox{{\sf I}\kern-.4em\hbox{\sf C}}^{n\times n}$. Then $\left\Vert \kern.05em \Lambda \kern.05em \right\Vert _2=\stackrel{\max }{_i}\vert\lambda _i\vert$.

Proof.   $\left\Vert \kern.05em \Lambda \kern.05em \right\Vert _2^2=\rho (\Lambda ^*\Lamb... ...rm diag}\, [\vert\lambda _i\vert^2]=\stackrel{\max }{_i}\vert\lambda _i\vert^2$.

Theorem 8.4.4   Let $A,B\in\hbox{{\sf I}\kern-.4em\hbox{\sf C}}^{n\times n}$ and A be nondefective, with eigenvalues $\lambda _i,~ i=1,2,\ldots ,n$. If $\lambda$ is an eigenvalue of $A+\epsilon B$, where $\epsilon$ is a positive scalar, then for some i

$$\vert\lambda _i-\lambda \vert\leq \epsilon \kappa _2(A)\left\Vert \kern.05em B \kern.05em \right\Vert _2,$$

where $\kappa _2(A)$ is the spectral condition number of A.

Proof.  Let X be the matrix whose columns are the eigenvectors of A. Then if $\lambda \not= \lambda _i$

$$\begin{eqnarray*}0 & = & \det [A+\epsilon B-\lambda I]\\ & = & \det [X^{-1}]\de... ..._i-\lambda )^{-1}]]\det [\, {\rm diag}\, [\lambda _i-\lambda ]]. \end{eqnarray*}$$

This implies that $\epsilon X^{-1}BX\, {\rm diag}\, [(\lambda _i-\lambda )^{-1}]$has an eigenvalue -1, so

$$\left\Vert \kern.05em \epsilon X^{-1}BX\, {\rm diag}\, [(\lam... ...n X^{-1}BX\, {\rm diag}\, [(\lambda _i-\lambda )^{-1}])\geq 1,$$

which implies that

$$\begin{eqnarray*}\epsilon \left\Vert \kern.05em X^{-1} \kern.05em \right\Vert _2... ...n \kappa _2(A)\left\Vert \kern.05em B \kern.05em \right\Vert _2. \end{eqnarray*}$$

Since the case when $\lambda =\lambda _i$ also satisfies this inequality, it is true in that case also.If A is Hermitian, we can scale X to be unitary and so $\kappa _2(A)=1$, which shows that an Hermitian matrix is as well-conditioned as possible for the eigenvalue problem also.