Solving Linear Equations using Iterative Improvement

Greg Fee, CECM, SFU



A square system of linear equations with integer coefficients
may be represented in matrix form by the matrix equation  
 A.x = b,  where  
 A  is an n by n matrix of integers,  
 b  is a column vector of integers and  
 x  is a column vector of unknowns.
If the determinant of the matrix  A  is non-zero,
then the solution is unique. An approxiamte solution may found by
performing an LU decomposition of the matrix  A  using
floating-point arithmetic.  If the condition number is small
we can find an approximate floating-point solution,
then we can find a higher precision solution by applying
iterative improvement to our current approximation.
A modified continued-fraction algorithm can recover
the exact rational number solution.