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.

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.

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 ] [ ]

[] [] [] [] []