You are here

Iterative Methods for Solving Ax = b

Author(s): 
David M. Strong

Information for Instructors

This module comprises two tutorials with associated exercises and a Java applet to do the necessary computations and display the results graphically.  We explore three different iterative methods, that is, methods that are intended to generate successive approximations to the exact solution of a linear system of equations.

David Strong is Assistant Professor of Mathematics at Pepperdine University.

Iterative methods are important in solving many of today’s real world problems, so it is important that your first exposure to these methods be as positive and simple, as well as informative and educational, as possible. With this in mind, the main purpose of the tutorials and applet is to allow easy visualization and experimentation.

In more detail, here are the primary features of the applet:

  • The applet allows for clear and simple visualization of what each iterative method is doing, in particular, how properties of the matrix affect the convergence (or non-convergence) of each method. Repeatedly zooming-in on the converging approximations will help you literally to see that iterative methods don’t normally find a solution exactly -- rather each iteration gives you a better approximation, and you have to decide how good is good enough.

  • The applet allows you easily and quickly to do as many iterations as you want, without the practically impossible burden of doing more than a few iterations by hand with a calculator. Many of the exercises take advantage of this and allow you to explore a variety of basic ideas and considerations arising in iterative solution of linear systems that would otherwise be impossible to do.

  • The applet allows for a simple comparison of three iterative methods, including a comparison of their rates of convergence

  • The applet is designed for easy use and is free. In particular, there is virtually no learning curve and there is no software, calculator, etc. for you to purchase. The only requirement is a computer with an Internet connection and the Java Plug-in, which is free and easy to install.

You will see that the applet deals only with 2 x 2 sytems, i.e., two linear equations in two unknowns. In the real world, we would never use an iterative method to solve such a small sytem, or even to solve substantially larger (e.g., 64 x 64, 512 x 512, etc.) systems. In my own image processing research I typically deal with (sparse) systems of 65536 (2562) or 262144 (5122) equations in the same number of variables. We generally don't use any of the three methods (Jacobi, Gauss-Seidel, SOR) discussed in the module, although some of their basic ideas are found in any iterative method. Still, these methods are very straightforward, which makes them relatively easy to understand, and that is why they are your first taste of iterative methods for solving linear systems.

Furthermore, the 2 x 2 case (as opposed to 3 x 3 or larger systems) makes it easier to visualize the results of these methods, which I think you will find valuable. With this said, the tutorial and its experimentation and visualization are good introductions to iterative methods for solving Ax = b. However, you should consider further treatment of these topics in a numerical analysis or numerical linear algebra course. In particular, you will learn in such a course that some of the simple and elegant results seen in the 2 x 2 case are no longer true when dealing with larger systems.

Published July, 2005
© David M. Strong 2003 - 2005
All Rights Reserved

 

David M. Strong, "Iterative Methods for Solving [i]Ax[/i] = [i]b[/i]," Convergence (July 2005)