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.