Iterative Solvers in a Nutshell

April 12, 2008

Iterative Solvers in a Nutshell

Filed under: Uncategorized — secr @ pm

Basic concepts of iterative algorithms for elliptic PDEs can be compressed to the following remarks:

1. Continuous and discrete equations

(a) Given a PDE $Lu = v$ with Dirichlet boundary conditions, $L$ an linear elliptic differential operator, we wish to find the solution $u$ .

(b) The solution can be written formally as $u = L^{-1} v$ . $L^{-1}$ is a linear elliptic integral operator, given by $L^{-1} v(x) = \int G(y-x) \, v(y) \, dy$ , the convolution of the right hand side with some Green’s function of $L$ .

(c) $L$ and $v$ can be discretized (somehow) as $A$ (a matrix) and $b$ (a vector). The goal is to find the discretized version $x$ of $u$ , given by $A x = b$ .

(d) The formal solution of the discretized problem is $x = A^{-1} b$ . But inverting $A$ directly would be to expensive, that’s where the iterative solver springs into action.

2. The iterative solver

(a) The goal is to build an iteration $x_{i+1} = f(x_i, b)$ that converges against the solution $x = A^{-1} b$ .

(b) While $i$ increases, we wish that the error in $x = x_i$ ,

$e_i = x_i - x$ ,

decreases and finally reaches 0. We’ll never know the value of $e_i$ because $x$ is unknown. But that doesn’t matter as long as the error in $Ax_i = b$ ,

$r_i = b - A x_i$

is known. The name of $e_i$ is simply “the error” while $r_i$ is called “the residual”.

(c) The relation between the error and the residual is $- A e_i = r_i$ , i.e. $e_i$ scales with $r_i$ . The “anisotropic” scaling-factor is $A^{-1}$ .

(d) The relation between the exact solution and the residual is $x = x_i + A^{-1} r_i$ . If we replace $A^{-1}$ with an approximation $B$ , we’ll get an approximation of $x$ :

$x_{i+1} = x_i + B r_i$ .

I would frame this equation now if I could, because it defines $f(x_i, b)$ , the iterator that’ll hopefully converge against $x$ .

(e) To be sure that it does, $||e_i||$ has to approach 0 for $i \rightarrow \infty$ . The related proof is always done by induction, i.e. $e_{i+1}$ has to be related to $e_i$ . Note that our iteration $x_{i+1} = x_i + B r_i$ can be rewritten as $x_{i+1} = x_i - B A e_i$ (can be simply done with (c)), so that $e_{i+1} = x_{i+1} - x = x_i - B A e_i - x$ . So eventually

$e_{i+1} = (I - B A) e_i$ .

To conclude whether $x_i$ approaches $x$ , we have to make sure that $||e_i||$ approaches 0. The key is the following relation between $||e_{i+1}||$ and the spectral radius of $I - BA$ :

$||e_{i+1}|| \leq \rho(I-BA) ||e_i||$ .

You’ll see it if you expand $e_{i+1} = (I - B A) e_i$ in the Eigenbase of $I-BA$ . The conclusion is:

If $\rho(I - BA) < 1$ then convergence.

Like this:

Be the first to like this post.

o_O

April 12, 2008

Iterative Solvers in a Nutshell

Like this:

Recent Posts

Pages

Follow “o_O”