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.

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).

Software

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.

[mathematics.me.uk] [computing.me.uk] [engineering.me.uk] [physics.me.uk] [statistics.me.uk]