.For any system of linear equations, the question concerning the errors in a solution obtained by a numerical method is not readily answered. A general discussion of the problems it raises is beyond the scope of this book. However, some sources of errors will be indicated below.
In many practical cases, the coefficients of the variables, and also the constants on the right-hand sides of the equations are obtained from observations of experiments or from other numerical calculations. They will have errors; and therefore, once the solution of a system has been found, it too will contain errors. In order to show how this kind of error is carried through calculations, we shall solve a simple example in two variables, assuming that the constants have errors at most as large as +/- 0.01. Consider the system:
.
Solving this system by Gauss elimination and back-substitution yields:
,
whence 3/2 y lies between 2.985 and 3.015, i.e., y lies between 1.990 and 2.010. From the first equation, we now obtain
,
so that x lies between 0.99 and 1.01.
If the coefficients and constants of the system were exact, its exact solution would be x = 1, y = 2. However, since the constants are not known exactly, it does not make sense to talk of an exact solution; all one can say is that 0.99 £ x £ 1.01 and 1.99 £ y £ 2.01.
In this example, the error in the solution is of the same order as that in the constants. Yet, in general, the errors in the solutions are greater than those in the constants.
Numerical methods for solving systems of linear equations involve large numbers of arithmetic operations. For example, the Gauss elimination of Step 11, according to Atkinson (1993), involves (n3 + 3n2 - n)/3 multiplications/divisions and (2n3 + 3n2 - 5n)/6 additions/subtractions in the case of a system with n unknowns.
Since round-off errors are propagated at each step of an algorithm, the growth of round-off errors can be such that, when n is large, a solution differs greatly from the true one.
In Gauss elimination, the buildup of round-off errors may be reduced by rearranging the equations so that the use of large multipliers in the elimination operations is avoided. The corresponding procedure is known as partial pivoting (or pivotal condensation). The general rule to follow involves: At each elimination stage, rearrange the rows of the augmented matrix so that the new pivot element is larger in absolute value than (or equal to) any element beneath it in its column.
A use of this rule ensures that the magnitudes of the multipliers, employed at each stage, are less or equal to unity. A simple example in 3 floating point arithmetic follows:
.
In the following tabular solution, the pivot elements are in bold print. (Note that the magnitude of all the multipliers is less than unity.)
.
If no pivoting is done, it may be verified that using three-digit floating point arithmetic yields the solution z = 2.93, y = 2.00 and x = 1.30. Since the true solution to 3S is z = 2.93, y = 1.96, and x=1.36, the solution obtained by partial pivoting is better than the one obtained without pivoting.
Certain systems of linear equations are such that their solutions are very sensitive to small changes (and therefore to errors) in their coefficients and constants. We give an example below in which 1 % changes in two coefficients change the solution by a factor of 10 or more. Such systems are said to be ill-conditioned. If a system is ill-conditioned, a solution obtained by a numerical method may differ greatly from the exact solution, even though great care is taken to keep round-off and other errors very small.
As an example, consider the system of equations:
which has the exact solution x =1, y = 2. Changing coefficients of the second equation by 1% and the constant of the first equation by 5% yields the system:
It is easily verified that the exact solution of this system is x = 11, y = -18.2. This solution differs greatly from the solution of the first system. Both these systems are said to be ill-conditioned.
If a system is ill-conditioned, then the usual procedure of checking a numerical solution by calculation of the residuals may not be valid. In order to see why this is so, suppose we have an approximation X to the true solution x. The vector of residuals r is then given by r = b - AX = A(x - X). Thus e = x - X satisfies the linear system Ae = r. In general, r will be a vector with small components. However, in an ill-conditioned system, even if the components of r are small so that it is `close' to 0, the solution of the linear system Ae = r could differ greatly from the solution of the system Ae = 0, namely 0. It then follows that X may be a poor approximation to x despite the residuals in r being small.
Obtaining accurate solutions to ill-conditioned linear systems can be difficult, and many tests have been proposed for determining whether or not a system is ill-conditioned. A simple introduction to this topic is given in the optional STEP 16.
1. Find the range of solutions for the following system, assuming that the maximum errors in the constants are as shown:
2. Solve the following systems by Gauss elimination:
a) 
b) 
c) 
3. Use 4D normalized floating point arithmetic to solve the fo1lowing system with and without partial pivoting. Compare your answers with the exact answer: x =1.000 x 1O0, y = 5.000 x 10-1:
4. Show that for a linear system of three unknowns, Gauss elimination requires three divisions, eight multiplications, and eight sub- tractions for the triangularization, and a further three divisions, three multiplications and three additions/subtractions for the backsubstitution.
5. Derive the general formulae in Section 2 for the numbers of required arithmetic operations.
6. Study the ill-conditioning example of Section 4 in the following ways:
a) Plot the lines of the first system on graph paper; then describe ill-conditioning in geometrical terms when only two unknowns are involved.
b) Insert the solution of the first system into the left-hand side of the second system. Does x=1, y=2 `look like a good solution to the second system? Comment!
c) Insert the solution of the second system into the left-hand side of the first system. Comment!
d) The system
is an example of ill-conditioning, due to T. S. Wilson. Insert the `solution' (6.0, -7.2, 2.9, -0.1 ) into the left-hand side. Would you claim this solution to be a good one? Next insert the solution (1.0,1.0,1.0,1.0). Comment on the dangers of laying claims!