The condition number of a square nonsingular matrix is defined by which is also the condition number associated with solving the linear system . A matrix with a large condition number is said to be ill-conditioned.
The condition number can be measured with any -norm, so to be precise we typically specify the norm being used, i.e. , .
If is singular, we can define by convention.
Let be the solution of and be the solution of the perturbed problem . Let be the absolute error in output. Then we have so Now we want to see how the relative error in output is related to the relative error in input :
where we used
Then
Therefore, if we know the relative error in input, then we can use the condition number of the system to obtain an upper bound for the relative error of our computed solution (output).
The residual vector of approximate solution for the linear system is defined as . In the perturbed matrix problem described above, we have
Therefore, equation (1) can also be written as
If we define relative residual as , we can see that small relative residual implies small relative error in approximate solution only if is well-conditioned ( is small).
When we use Gaussian elimination with partial pivoting to compute the solution for the linear system and obtain an approximate solution , the residual vector satisfies:
where is backward error in (which is defined by ), is a coefficient related to and is machine epsilon.
Typically is small with partial pivoting, but can be arbitrarily large without pivoting.
Therefore, Gaussian elimination with partial pivoting yields small relative residual regardless of conditioning of the system.
For more details, see Gaussian Elimination & Roundoff Error.
Suppose we apply Gaussian elimination with partial pivoting and back substitution to the linear system and obtain a computed solution . If the entries in and are accurate to decimal digits, and , then the elements of the solution vector will be accurate to about decimal digits.
For a proof of this rule of thumb, please see Fundamentals of Matrix Computations by David S. Watkins.
Example: How many accurate decimal digits in the solution can we expect to obtain if we solve a linear system where using Gaussian elimination with partial pivoting, assuming we are using IEEE double precision and the inputs are accurate to machine precision?
In IEEE double precision, , which means the entries in and are accurate to decimal digits.
Then, using the rule of thumb, we know the entries in will be accurate to about decimal digits.