Text provided under a Creative Commons Attribution license, CC-BY. All code is made available under the FSF-approved MIT license. (c) Kyle T. Mandli

Note: This material largely follows the text “Numerical Linear Algebra” by Trefethen and Bau (SIAM, 1997) and is meant as a guide and supplement to the material presented there.

Iterative Methods¶

In this lecture we will consider a number of classical and more modern methods for solving sparse linear systems like those we found from our consideration of boundary value problems.

Motivation: Direct Methods¶

Gaussian elimination or other direct methods for solving linear systems of equations but are there other, better methods for solving these systems when there is structure that can be exploited?

For this lecture we will be considering an important type of linear system of equations that arise from discretizing the Poisson problem in one-dimension

How might you discretize the above ODE?

Following our finite difference discussion we can setup the following set of algebraic equations:

This forms the $i$th row of the matrix. See if you can write down this matrix in the form of $Ax = b$ ignoring the boundary conditions for now.

Computational Load¶

Now consider using Gaussian elimination on the above matrix. For good measure let us consider a 3D problem and discretize each dimension with a $m = 100$ leading to $100 \times 100 \times 100 = 10^6$ unknowns.

Gaussian Elimination - $\mathcal{O}(N^3)$ operations to solve, $(10^6)^3 = 10^{18}$ operations.

Suppose you have a machine that can perform 100 gigaflops (floating point operations per second):

Memory Load¶

What about memory?

We require $N^2$ to store entire array. In double precision floating point we would require 8-bytes per entry leading to

The situation really is not as bad as we are making it out to be as long as we take advantage of the sparse nature of the matrices. In fact for 1 dimensional problems direct methods can be reduced to $\mathcal{O}(N)$ in the case for a tridiagonal system. The situation is not so great for higher-dimensional problems however unless more structure can be leveraged. Examples of these types of solvers include fast Fourier methods such as fast Poisson solvers.

Jacobi and Gauss-Seidel¶

The Jacobi and Gauss-Seidel methods are simple approaches to introducing an iterative means for solving the problem $Ax = b$ when $A$ is sparse. Consider the general equation derived from the Poisson problem

If we rearrange this expression to solve for $U_i$ we have

For a direct method we would simultaneously find the values of $U_i$, $U_{i+1}$ and $U_{i-1}$ but instead consider the iterative scheme computes an update to the equation above by using the past iterate (values we already know)

Since this allows us to evaluate $U_i^{(k + 1)}$ without knowing the values of $U_{i+1}^{(k)} + U_{i-1}^{(k)}$ we directly evaluate this expression! This process is called Jacobi iteration. It can be shown that for this particular problem Jacobi iteration will converge from any initial guess $U^{(0)}$ although slowly.

Advantages

• Matrix $A$ is never stored or created

• Storage is optimal

• $\mathcal{O}(m)$ are required per iteration

Example¶

Let’s try to solve the problem before in the BVP section but use Jacobi iterations to replace the direct solve

A slight modification to the above leads also to the Gauss-Seidel method. Programmtically it is easy to see the modification but in the iteration above we now will have

Matrix Splitting Methods¶

One way to view Jacobi and Gauss-Seidel is as a splitting of the matrix $A$ so that

Then the system $A U = b$ can be viewed as

Viewing this instead as an iteration we have then

The goal then would be to pick $M$ and $N$ such that $M$ contains as much of $A$ as possible while remaining easier to solve than the original system.

The resulting update for each of these then becomes

where $G$ is called the iteration matrix and $c = M^{-1} b$. We also want

where $u$ is the true solution of the original $A u = b$, in other words $u$ is the fixed point of the iteration. Is this fixed point stable though? If the spectral radius $\rho(G) < 1$ we can show that in fact the iteration is stable.

For Jacobi the splitting is

(sticking to the Poisson problem). $M$ is now a diagonal matrix and easy to solve.

For Gauss-Seidel we have

Stopping Criteria¶

How many iterations should we perform? Let $E^{(k)}$ represent the error present at step $k$. If we want to reduce the error at the first step $E^{(0)}$ to order $\epsilon$ then we have

Under suitable assumption we can bound the error in the 2-norm as

Moving back to our estimate of the number of iterations we can combine our two expressions involving the error $E$ by taking $\Delta x \rightarrow 0$ which allows us to write

taking into account error convergence.

Picking $\epsilon$ is a bit tricky but one natural criteria to use would be $\epsilon = \mathcal{O}(\Delta x^2)$ since our original discretization was 2nd-order accurate. This leads to

This also allows us to estimate the total number of operations that need to be used.

For Jacobi we have the spectral radius of $G$ as

so that

where $m$ here is now the number of points used.

Combining this with the previous operation count per iteration we find that Jacobi would lead to $\mathcal{O}(m^3 \log m)$ work which is not very promising.

For two dimensions we have $\mathcal{O}(m^4 \log m)$ so even compared to Gaussian elimination this approach is not ideal.

What about Gauss-Seidel? Here the spectral radius is approximately

so that

which still does not lead to any advantage over direct solvers. It does show that Gauss-Seidel does actually converge faster due to the factor of 2 difference between $\rho_J$ and $\rho_{GS}$.

Successive Overrelaxation (SOR)¶

Well that’s a bit dissapointing isn’t it? These iterative schemes do not seem to be worth much but it turns out we can do better with a slight modification to Gauss-Seidel.

If you look at Gauss-Seidel iteration it turns out it moves $U$ in the correct direction to $u$ but is very conservative in the amount. If instead we do

where we get to pick $\omega$ we can do much better.

If $\omega = 1$ then we get back Gauss-Seidel.

If $\omega < 1$ we move even less and converges even more slowly (although is sometimes used for multigrid under the name underrelaxation).

If $\omega > 1$ then we move further than Gauss-Seidel suggests and any method where $\omega > 1$ is known as successive overrelaxation (SOR).

We can write this as a matrix splitting method as well. We can combine the two-step formula above to find

corresponding to a matrix splitting of

where $D$ is the diagonal of the matrix $A$, and $L$ and $U$ are the lower and upper triangular parts without the diagonal of $A$.

It can be shown that picking an $\omega$ such that $0 < \omega < 2$ the SOR method converges.

It turns out we can also find an optimal $\omega$ for a wide class of problems. For Poisson problems in any number of space dimensions for instance it can be shown that SOR method converges optimaly if

What about the number of iterations? We can follow the same tactic as before with the spectral radius of $G_{SOR}$ now

This leads to an iteration count of

an order of magnitude better than Gauss-Seidel alone!

Descent Methods¶

One special case of matrices are amenable to another powerful way to iterate to the solution. A matrix is said to be symmetric positive definite (SPD) if

As an example check that the matrix

is symmetric positive definite.

Now define a function $\phi: \mathbb R^m \rightarrow \mathbb R$ such that

This is a quadratic function in the variables $u_i$ and in the case where $m = 2$ forms a parabolic bowl. Since this is a quadratic function there is a unique minimum, $u^\ast$.

Lets see how approaching the problem like this helps us:

For the $m = 2$ case write the function $\phi(u)$ out.

What property of the matrix $A$ simplifies the expression above?

Symmetry! This implies that $A_{21} = A_{12}$ and the expression above simplifies to

Now write two expressions that when evaluated at $u^\ast$ are identically 0 that express that $u^\ast$ minimizes $\phi(u)$.

Since $u^\ast$ minimizes $\phi(u)$ we know that the first derivatives should be zero at the minimum:

Note that these equations can be rewritten as

The conclusion here then is that finding the minimum of $\phi$ is equivalent to solving the system $A u = f$! This is a common type of reformulation for many problems where it may be easier to treat a given equation as a minimization problem rather than directly solve it.

Note that this is not quite the matrix that we have been using for our Poisson problem so far which is actually symmetric negative definite although these same methods work as well. In this case we actually want to find the maximum of $\phi$ instead, other than that everything is the same.

Also note that if $A$ is indefinite then the eigenvalues of $A$ will change sign and instead of a stable minimum or maximum we have a saddle point which are much more difficult to handle (GMRES can for instance).

Method of Steepest Descent¶

So now we turn to finding the $u^\ast$ that minimizes the function $\phi(u)$. The simplest approach to this is called the method of steepest descent which finds the direction of the largest gradient of $\phi(u)$ and goes in that direction.

Mathematically we then have

where $\alpha^{(k)}$ will be the step size chosen in the direction we want to go.

We can find $\alpha$ by

i.e. the $\alpha$ that takes us just far enough so that if we went any further $\phi$ would increase.

This implies that $\alpha^{(k)} \geq 0$ and $\alpha^{(k)} = 0$ only if we are at the minimum of $\phi$. We can compute the gradient of $\phi$ as

where $r^{(k)}$ is the residual defined as

Looking back at the definition of $\alpha^{(k)}$ then leads to the conclusion that the $\alpha$ that would minimize the expression would be the one that satisfies

To find this note that

so that the derivative becomes

Setting this to zero than leads to

Convergence of Steepest Descent¶

What controls the convergence of steepest descent? It turns out that the shape of the parabolic bowl formed by $\phi$ is the major factor determining the convergence of steepest descent. For example, if $A$ is a scalar multiple of the identity than these ellipses are actually circles and steepest descent converges in $m$ steps. If $A$ does not lead to circles, the convergence is based on the ratio between the semi-major and semi-minor axis of the resulting ellipses $m$ dimensional ellipses. This is controlled by the smallest and largest eigenvalues of the matrix $A$ hence why steepest descent grows increasingly difficult as $m$ increases for the Poisson problem. Note that this also relates to the condition number of the matrix in the $\ell_2$ norm.

$A$-Conjugate Search Directions and Conjugate Gradient¶

An alternative to steepest descent is to choose a slightly different direction to descend down. Generalizing our step from above let the iterative scheme be

and as before we want to pick an $\alpha$ such that

leading again to the choice of $\alpha$ of

accept now we are also allowed to pick the search direction $p^{(k)}$.

Ways to choose $p^{(k)}$:

• One bad choice for $p$ would be orthogonal to $r$ since this would then be tangent to the level set (ellipse) of $\phi(u^{(k)})$ and would cause it to only increase so we want to make sure that $p^T r \neq 0$ (the inner-product).

• We also want to still move downwards so require that $\phi(u^{(k+1)}) < \phi(u^{(k)})$.

We know that $r^{(k)}$ is not always the best direction to go in but what might be better? We could head directly for the minimum but how do we do that without first knowing $u^\ast$?

It turns out when $m=2$ we can do this from any initial guess $u^{(0)}$ and initial direction $p^{(k)}$ we will arrive at the minimum in 2 steps if we choose the second search direction dependent on

In general if two vectors satisfy this property they are said to be $A$-conjugate.

Note that if $A = I$ then these two vectors would be orthogonal to each other and in this sense $A$-conjugacy is a natural extension from orthogonality and the simple case from before where the ellipses are circles to the case where we can have very distorted ellipses.

In fact the vector $p^{(0)}$ is tangent to the level set that $u^{(1)}$ lies on and therefore choosing $p^{(1)}$ so that it is $A$-conjugate to $p^{(0)}$ then always heads to the center of the ellipse.

In other words, once we know a tangent to one of the ellipses we can always choose a direction that minimizes in one of the dimensions of the search space. Choosing the $p^{(k)}$ iteratively this way forms the basis of the conjugate gradient method.

Now to generalize beyond $m = 2$ consider the $m=3$ case. As stated before we are now in a three-dimensional space where the level-sets are concentric ellipsoids. Taking a slice through this space will lead to an ellipse on the slice.

1. Start with an initial guess $u^{(0)}$ and choose a search direction $p^{(0)}$.

2. Minimize $\phi(u)$ in the direction $u^{(0)} + \alpha p^{(0)}$ resulting in the choice

   $$\alpha^{(0)} = \frac{(p^{(0)})^T p^{(0)}}{(p^{(0)})^T A p^{(0)}}$$

   (54)

   as we saw before. Now set $u^{(1)} = u^{(0)} + \alpha^{(0)} p^{(0)}$.

3. Choose $p^{(1)}$ to be $A$-conjugate to $p^{(0)}$. In this case there are an infinite set of vectors that are possible that satisfy $(p^{(1)})^T A p^{(0)} = 0$. Beyond requiring $p^{(1)}$ to be $A$-conjugate we also want it to be linearly-independent to $p^{(0)}$.

4. Again choose an $\alpha^{(1)}$ that minimizes the residual (again tangent to the level sets of $\phi$) in the direction $p^{(1)}$ and repeat the process

Preconditioning¶

One way to get around the difficulties with these types of methods due to the distortion of the ellipses (and consequently the conditioning of the matrix) is to precondition the matrix. The basic idea is that we take our original problem $A u = f$ and instead solve

Note that since we need to find the inverse of $M$, this matrix should be nice. A couple of illustrative examples may help to illustrate why this might be a good idea:

• If $M = A$ then we essentially have solved our problem already although that does not help us much

• If $M = \text{diag}(A)$, then $M^{-1}$ is easily computed and it turns out for some problems this can decrease the condition number of $M^{-1} A$ significantly. Note though that this is not actually helpful in the case of the Poisson problem.

• If $M$ is based on another iterative method used on $A$, for instance Gauss-Seidel, these can be effective general use preconditioners for many problems.

So the next question then becomes how to choose a preconditioner. This is usually very problem specific and a number of papers suggest strategies for particular problems.