Analysis of Convergence

As usual, we are concerned with the solution of the equation

$$A\mbox{\boldmath$ x $ } =\mbox{\boldmath$ f $ } .$$ (4.1)

We start by splitting A into N-P, so that (7.1) can be written

$$N\mbox{\boldmath$ x $ } =P\mbox{\boldmath$ x $ } +\mbox{\boldmath$ f $ } ,$$ (4.2)

which, given $\mbox{\boldmath$\space x $ } _0$, defines the iteration

$$N\mbox{\boldmath$ x $ } _{m+1} =P\mbox{\boldmath$ x $ } _m+\mbox{\boldmath$ f $ } ,\quad m=0,1,\ldots .$$ (4.3)

We can solve this at each iteration, provided that N is nonsingular; the choice of splitting depends on

1.

Ease of solution. There is no point in splitting if (7.3) is just as hard to solve as (7.1), so we look for N to be something easy, e.g., a diagonal matrix.

2.

Convergence of the iteration. Does it converge, and if it does, how quickly?

Subtracting (7.3) from (7.2) and putting $\mbox{\boldmath$\space x $ } _m-\mbox{\boldmath$\space x $ } =\mbox{\boldmath$\space e $ } _m$ for $m=0,1,\ldots$, we find

$$N\mbox{\boldmath$ e $ } _{m+1}=P\mbox{\boldmath$ e $ } _m,$$

or

$$\mbox{\boldmath$ e $ } _{m+1}=M\mbox{\boldmath$ e $ } _m,$$

where M=N^-1P is the iteration matrix for this splitting. Repeated application of the iteration gives

$$\mbox{\boldmath$ e $ } _m=M^m\mbox{\boldmath$ e $ } _0.$$ (4.4)

Thus the error converges to zero, and hence $\mbox{\boldmath$\space x $ } _m$ converges to $\mbox{\boldmath$\space x $ }$, if M is a convergent matrix.

To examine the rate of convergence, we start with the case when M is nondefective. Let $\{ \mbox{\boldmath$\space u $ } _1,\mbox{\boldmath$\space u $ } _2,\ldots ,\mbox{\boldmath$\space u $ } _n\}$ be a set of linearly independent eigenvalues of M, and let $\mbox{\boldmath$\space e $ } _0=\sum _{i=1}^na_i\mbox{\boldmath$\space u $ } _i$. Then

$$\mbox{\boldmath$ e $ } _m=M^m\mbox{\boldmath$ e $ } _0=\sum _... ... $ } _i=\sum _{i=1}^na_i\lambda _i^m\mbox{\boldmath$ u $ } _i,$$

where $\lambda _1, \lambda _2,\ldots ,\lambda _n$ are the corresponding eigenvalues of M. Suppose they are ordered so that

$$\rho (M)=\vert\lambda _1\vert>\vert\lambda _i\vert, \quad i=2,3,\ldots ,n .$$

Then

$$\mbox{\boldmath$ e $ } _m=\lambda _1^m\{ a_1\mbox{\boldmath$ ... ...{\lambda _i}{\lambda _1}\right)^m\mbox{\boldmath$ u $ } _i\} .$$

For large m, the first term dominates, so the error is ultimately reduced by a factor of $\vert\lambda _1\vert=\rho (M)$ by each iteration. We call this the asymptotic convergence factor.

To reduce the error by a factor of 10^-m,  m>0 we will need kiterations, where k must satisfy $\rho ^k(M)\leq 10^{-m}$, so that $k\geq \frac{m}{-\log _{10}\rho (M)}=\frac{m}{R}$, say, where

$$R=-\log _{10}\rho (M)$$

is the asymptotic conergence rate. The bigger the rate, the smaller the number of iterations required to improve the accuracy by a given amount.

If M is defective, we have to proceed differently. Taking vector induced norms of (7.4) we obtain

$$\begin{eqnarray*}\left\Vert \kern.05em \mbox{\boldmath$ e $ } _m \kern.05em \rig... ...Vert \kern.05em \mbox{\boldmath$ e $ } _0 \kern.05em \right\Vert \end{eqnarray*}$$

for some norm. Thus the error bound in some norm is reduced by a factor $\rho (M)$, and we can still regard this as the asymptotic convergence factor and define R as before.