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.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
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.
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 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 Matrix Inversion.xlsm 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).
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.