Error-free computer solution of certain systems of linear equations

摘要

In this article we propose a procedure which generates the exact solution for the system Ax = b, where A is an integral nonsingular matrix and b is an integral vector, by improving the initial floating-point approximation to the solution. This procedure, based on an easily programmed method proposed by Aberth [1], first computes the approximate floating-point solution x* by using an available linear equation solving algorithm. Then it extracts the exact solution x from x* if the error in the approximation x* is sufficiently small. An a posteriori upper bound for the error of x* is derived when Gaussian Elimination with partial pivoting is used. Also, a computable upper bound for |det(A)|, which is an alternative to using Hadamard's inequality, is obtained as a byproduct of the Gaussian Elimination process.