3
$\begingroup$

For any iteration method from A=M-N, e.g.,

$$ Mx_{k+1}=Nx_{k}+b,\quad k=0,1,... $$

we know that it converges iff $\rho(M^{-1}N)<1$. And when it converges, there exists a concept called asymtotic convergence rate $R = -\ln(\rho M^{-1}N)$. So, we usually call $\rho$ the convergence factor.

I also heard that a concept called contraction factor of the iteration method. What is the contraction factor?

$\endgroup$
7
$\begingroup$

These concepts are related. Let $A = M - N$ and consider the iteration $$ M x_{k+1} = N x_k + b. $$ We can write this as a mapping $\Phi : \mathbb{R}^n \to \mathbb{R}^n$ defined by $$ \Phi(y) = M^{-1}(N y + b), $$ and so $x_{k+1} = \Phi(x_k)$. $\Phi$ is called a contraction mapping if there exists a constant $0 \leq L < 1$ (called the Lipschitz constant, or contraction factor) such that $$ \| \Phi(y) - \Phi(z) \| \leq L \| y - z \|. $$ Intuitively speaking, this means that the mapping $\Phi$ takes any two vectors and moves them closer together. Note that \begin{align} \Phi(y) - \Phi(z) &= M^{-1}(Ny + b) - M^{-1}(Nz + b) \\ &= M^{-1}N(y - z), \tag{$\ast$} \end{align} and so we have that $L = \|M^{-1} N\|$.

Now, let's relate this to the convergence of the iterative method. Let $x$ be the solution to $Ax = b$. Notice that $x$ is a fixed point of this iteration: \begin{align} \Phi(x) &= M^{-1}(Nx + b)\\ &= M^{-1}((M-A)x + b) \\ &= (I - M^{-1}A)x + M^{-1} b \\ &= x. \end{align}

Combining this fact with equation ($\ast$), we have \begin{align} M^{-1}N(x_{k} - x) &= \Phi(x_k) - \Phi(x) \\ &= x_{k+1} - x, \end{align} and therefore, defining the error of the method at step $k$ to be $e_k = x_{k}-x$, we have the following recurrence for the errors: $$ e_{k+1} = M^{-1}N e_k. \tag{$\ast\ast$} $$ So, we certainly have that $$ \|e_{k+1}\| \leq \| M^{-1} N \| \| e_k \| = L \| e_k \|, $$ relating the convergence of the iteration to the contraction factor of the mapping.

In your question, you mention the spectral radius of the operator $M^{-1}N$. The condition $\rho(M^{-1}N)$ indeed is necessary and sufficient for convergence of the iteration, which can be seen by applying the power sequence theorem for the spectral radius to equation ($\ast\ast$).

$\endgroup$
  • 1
    $\begingroup$ Get it! Thanks Prof. Will for your detailed answers and I understand it. $\endgroup$ – sunshine Nov 21 '19 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.