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]
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.
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]
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.
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. LU factorisation
followed by back-substitution is a related method.
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 Gauss.
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]