Interactive Educational Modules in
Scientific Computing

Convergence of Iterative Methods

This module uses the DFT to help in understanding the convergence rates of iterative methods for solving a system of linear equations. Iterative methods are often used for solving systems of linear equations Ax = b arising from discretization of differential equations. The convergence properties of such methods can be understood by considering the frequency spectrum of the residual bAx over successive iterations. In particular, some frequencies may be suppressed much more quickly than others. For example, some iterative methods suppress high-frequency components quickly (and thus are called “smoothers”), but their asymptotic convergence rate is determined by the much more slowly decaying low-frequency components. This module illustrates these phenomena in the context of a simple finite-difference approximation to the one-dimensional Laplace equation, u″ = 0.

The user begins by selecting the number of interior mesh points to use in the numerical solution of the Laplace equation. The upper graph displays an initial guess for the solution (blue dots), including the boundary conditions u(0) = 0 and u(1) = 0 (for this choice of boundary values, both the solution and the residual should converge to zero). Next the user selects an initial guess for the solution, either by clicking Specific Initial Guess, which cycles through a set of seven different initial guesses that illustrate properties of the different iterative methods, or by clicking Random Initial Guess, which generates a random initial guess for the solution, choosing a value between −1.5 and 1.5 at each interior mesh point. Finally, the user selects an iterative method from the menu provided. For the SOR method, the user can adjust the relaxation parameter ω using the slider. The theoretically optimal value of ω for the given number of mesh points is shown below the slider. The SOR method is implemented here using the “red-black” ordering, meaning in this case that on each iteration the solution components corresponding to the odd-numbered mesh points are updated before those for the even-numbered mesh points. Clicking Iterate carries out one iteration of the chosen iterative method for solving the linear system. After each iteration, the approximate solution in the upper graph is updated to show the new values, which should eventually converge to zero. The user can execute as many iterations of the method as desired; an iteration counter keeps track of the number of iterations, and the norm of the residual is displayed, so the user can compare different methods after the same number of iterations. Clicking Reset allows the user to select a different method for the same initial guess or to change the number of mesh points or starting values.

Throughout the iterations, the bottom graph shows the power spectrum (red dots) of the first half of the DFT of the values displayed in the top graph (interior mesh points only). The power spectrum of a sequence of complex values is computed by multiplying each value by its complex conjugate. For a sequence of real values, the power spectrum of the DFT is symmetric, so only the first half of the power spectrum need be displayed. The power spectrum represents the amount of energy present at each frequency. The tick labels on the horizontal axis show the wave numbers of selected frequencies; higher wave numbers correspond to higher frequencies. As the tick labels on the vertical axis suggest, the values of the power spectrum are shown on a log base 2 scale, with all values less than 2−5 lying on the horizontal axis.

As watching the power spectrum during iterations reveals, some of the iterative methods quickly reduce some frequencies in the residual, but then convergence bogs down as other frequencies decay very slowly. This observation, combined with the fact that the apparent frequency of a component of the residual depends on the coarseness of the mesh, motivates multigrid methods, in which the residual is transferred between grids of varying refinement in order to obtain maximum benefit from an iterative method's abililty to suppress various frequencies most quickly.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 11.5 and Computer Problem 12.14 on page 510.

Developers: Evan VanderZee and Michael Heath