Mathematical Methods (10/24.539)

VI. Numerical Solution of Algebraic Equations

Introduction

The solution of linear systems of algebraic equations is an important subject of linear algebra, and the computational considerations needed for computer implementation are usually treated in some detail in introductory numerical methods courses. We have already touched briefly upon this subject (see Section III - Overview of Linear Algebra), and most students have had some introduction to computer implementation in other courses (numerical methods, heat transfer, etc.). Thus, this section of notes simply represents a quick review or overview of the subject - it is not intended as a complete treatise on this topic. Students with little or no background in this area are referred to one of many good numerical methods texts that treat the subject in more detail.

The numerical solution of large systems of algebraic equations is a direct consequence of the Finite Difference method for solving ODEs or PDEs. Recall that the goal in these techniques is to break the continuous differential equation into a coupled set of algebraic difference equations for each finite volume or node in the system. When one has only a single independent variable (the ODE case), this process can easily lead to several hundred simultaneous equations that need to be solved. For multiple independent variables (the PDE case), systems with hundreds of thousands of equations are common. Thus, in general, we need to be able to solve large systems of linear equations of the form as part of the solution algorithm for general Finite Difference methods.

There are two general schemes for solving linear systems: Direct Elimination Methods and Iterative Methods. All the direct methods are, in some sense, based on the standard Gauss Elimination technique, which systematically applies row operations to transform the original system of equations into a form that is easier to solve. In particular, this section of notes overviews an algorithm for implementation of the basic Gauss Elimination scheme and it also highlights the LU Decomposition method which, although functionally equivalent to the Gauss Elimination method, does provide some additional flexibility for computer implementation. Thus, the LU decomposition method is often the preferred direct solution method for low to medium sized systems (usually less than 200-300 equations).

For large systems, iterative methods (instead of direct elimination methods) are almost always used. This switch is required from accuracy considerations (related to round-off errors), from memory limitations for physical storage of the equation constants, from considerations for treating nonlinear problems, and from overall efficiency concerns. There are several specific iterative schemes that are in common use, but most methods build upon the base Gauss Seidel method, usually with some acceleration scheme to help convergence. Thus, our focus in this brief overview is on the basic Gauss Seidel scheme and on the use of Successive Over Relaxation (SOR) to help accelerate convergence.

Our brief overview of direct and iterative schemes for computer solution of large systems of equations is broken into the following subsections:

10/24.539 Lecture Notes by Dr. J. R. White, UMass-Lowell (updated August 1998).

Return to Online Courses