Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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?
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$).
