Solution of Linear Systems of Equations


A system of linear algebraic equations has the form

a[1,1] x[1] + a[1,2] x[2] + .... + a[1,N] x[N] = b[1]
a[2,1] x[1] + a[2,2] x[2] + .... + a[2,N] x[N] = b[2]
a[M,1] x[1] + a[M,2] x[2] + .... + a[M,N] x[N] = b[M]

where the a[i,j] and the b[i] are known. The x[j] are unknown and the purpose of solving the system is to find the x[j].

The system is often written in the form A x = b where A is an MxN matrix and x is an N-vector and b M-vectors.

Tutorials on Matrices

Solvability of the Linear System
Whether the solution is possible and the performance of the numerical solution methods all hinges on the nature of the matrix A.

Non-square matrix
If the matrix has more columns than rows (N>M) then there is a vector space of solutions (no unique solution); there are more unknowns than equations!
If the matrix has more rows than columns then the linear system is said to be "overdetermined". This can be confusing however. For example some of the equations may be linearly dependent or even simply repeated; for example if all the rows were the same then this does not help us determine a solution.
Often in an overdetermined system, there is no solution x that satisfies all the rows exactly but there are solutions x such that Ax-b is a vector of "small values" that are within working accuracy.

Square matrix (M=N)
If the matrix A has rows that can be formed from a linear combination of other rows then it is said to be singular. In this case the linear system either has no solution or no unique solution.
If the matrix A is nearly-singular (or ill-conditioned) then there will be a range of "numerical solutions" such that A x - b is within working numerical accuracy and a precise solution will be difficult to determine.The condition of the matrix is an important consideration and it is measured by the term Condition number or a matrix.
Otherwise the system has a well-defined unique solution.

Methods of Solution
There are two distinct approached to solving a system of equations; direct methods and iterative methods. In direct methods a finite series of operations are carried out (usually O(N^3)) and the solution is arrived at. The most well-known method of this type is Gaussian elimination. A more important method is LU factorisation followed by back-substitution in that it separates the computationally intensive 'factorisation' or 'decomposition' of the matrix (O(N^3)) from the solution of the matrix vector system (O(N^2)) and hence is a more versatile and practically useful method than Gaussian elimination.

Spreadsheet demonstration of Gaussian Elimination for solving a 3x3 System

Software carrying out LU factorisation and forward and back substitution is available on this site. A spreadsheet in Excel gives a very visible view of LU factorisation and forward and back substitution and this can be downloaded from LU.xlsm . In Matlab/Freemat/Ocave/Scilab, see LUfbsub.m . In FORTRAN, see LUFAC.FOR.

Another approach to solving linear systems of equations is through inverting the matrix. This is indeed probably the most obvious method. However, it is more their are usually less computationally costly methods for finding the solution of a linear system. In Matlab/Freemat/Scilab/Octave the inverse of a matrix can be found easily with the < a href=""inv method.

In Excel there is a MINVERSE function for finding the inverse of a matrix. However, it is reported to be limited to a maximum 52x52 dimension of matrix. A function VBA module MINVERSE.bas is included in the Excel spreadsheet and this will invert square matrices of any size.

Iterative methods involve a sequence of matrix-vector multiplications. Starting with an initial guess at the solution, each multiplication or iteration returns a new estimate of the solution and clearly takes O(N^2) operations. Hopefully the estimates get closer and closer to the solution so that after k iterations say a satisfactory solution is arrived at (after O(kN^2) operations).

Several Interactive Programs have become available, enabling users to carry out linear algebra without resorting to traditional programming languages. Leading examples of these are
Matlab (and its free clones; Scilab, Freemat and Octave) and Gauss. In Matlab, Scilab, Freemat and Octave, the tutorial Arrays - Matrices and Vectors shows how to set up and handle matrices, Matrix and Vector Arithmetic shows how to do basic matrix arithmetic and Solution of Linear Systems of Equations shows how to solve matrix-vector equations.

There are two widely-used general libraries on numerical methods: NAG (Numerical Algorithms Group) and IMSL (International Mathematics and Statistical Library).

LAPACK is a library of Linear Algebra routines that is available.

 [ ] [] [ ] [] [ ] [Fortran ] [ ]

[] [] [] [] []