Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 31
Текст из файла (страница 31)
Also,for these solutions (with r calculated in double precision), using just thetion algorithm 4.4.A of thesolutionscalculatesubstitu-4.6BACKWARD ERROR ANALYSIS AND ITERATIVE IMPROVEMENT1774.6 BACKWARD ERROR ANALYSIS AND ITERATIVEIMPROVEMENTIn the preceding Sec. 4.5, we used the condition number(4.43)of the coefficient matrix A of the linear system Ax = b as an x-independent quantity in estimating the error of an approximate solution.
Tosummarize: The condition number (4.43) provides a measure of howreliably the relative residualof an approximate solutionreflects the relative errorof the approximate solution. Thecondition number is therefore a measure of how well we can hope todistinguish a “good” (approximate) solution from a “bad” one by lookingat the residual error.It is clearly quite difficult to calculate the condition number for agiven matrix even if the matrix norm can be calculated relatively easily,since one must know A-1. At times, cond(A ) can be estimated with the aidof the following theorem, which might also help to explain further thesignificance of the condition number.Theorem 4.8 For any invertible n × n matrix A and any matrix norm,the condition number of A indicates the relative distance of A fromthe nearest noninvertible n × n matrix.
Specifically,A complete proof of this theorem is beyond the scope of this book (butsee Exercise 4.6-5). We only show thati.e., that for any noninvertible n × n matrix B,(4.44)Indeed, if B is not invertible, then by Theorem 4.4, there is a nonzeron-vector x such that Bx = 0. But thenusing (4.38), and sincewe can divide byto obtain (4.44).The argument just given establishes the following useful corollary.178MATRICES AND SYSTEMS OF LINEAR EQUATIONSCorollary If A is invertible and B is a matrix such thatthen B is invertible.To give an example, we find for the matrixof Example 4.5 thatsince the matrixhas max-norm.we get that cond(A) > 100.
A different= 0.02. Hence, sinceexample is provided by invertible triangular matrices. If A is triangular, weknow from Theorem 4.6 that all diagonal entries of A are nonzero, andthat replacing any diagonal entry of A by 0 makes A noninvertible.Consequently, if A is triangular, thenis not invertible, and.The condition number also plays a role in the analysis of a furthercomplication in solving linear systems.
If the linear system Ax = b derivesfrom a practical problem, we must expect the coefficients of this system tobe subject to error, either because they result from other calculations orfrom physical measurement, or even only because of roundoff resultingfrom the conversion to a binary representation during read-in. Hence,assuming for the moment that the right side is accurate, we are, in fact,solving the linear system(4.45)instead of Ax = b, where, the matrix E containing the errorsin the coefficients. Even if all calculations are carried out exactly, we stillcompute only the solution of (4.45) rather than the solution x of Ax = b.Now, we have x = A-1 b; hence, assuming that (4.45) has a solution,Therefore, withHence4.6BACKWARD ERROR ANALYSIS AND ITERATIVE IMPROVEMENT179giving the final result(4.46)relative toIn words, the change in the solution fromcan be aslarge as cond(A) times the relative change ||E||/||A|| in the coefficientmatrix.
If the coefficients of the linear system Ax = b are known to beaccurate only to about 10-5 (relative to the size of A) andthen there is no point in calculating the solution to a relative accuracybetter than 10t - s .Example 4.7 Consider once more the linear system (4.30) in Example 4.5. We foundearlier that cond(A ) = 100 for its coefficient matrix A. By (4.46), a 1 percent change inthe coefficients of the system could therefore change its solution drastically.
Indeed, a 1percent change (in the right direction) produces the linear systemwhich has no solution at all, for the coefficient matrix now fails to be invertible.The preceding analysis can be put to good use in gauging the effect ofround-off errors incurred during elimination and back-substitution on theaccuracy of the computed solution with the aid of backward error analysis.In this, we will make use of the terminology and notation introduced inSec. 1.3.Theorem 4.9 Suppose that, in order to obtain a factorization PLU forthe nth order matrix A and, from this, the solution of the linear systemAx = b, we use Algorithms 4.2 and 4.4, but employ floating pointarithmetic with unit roundoff u < 0.01, getting the computed factorsand the computed solutionThen satisfies exactly theperturbed equation(4.47)(4.48)withandHere, we denote by |B| the matrix obtained from B = (bij) by replacing all its entries by their absolute value,Also, we writefor two matrices B and C in case B and C are of the same order andfor all i and j180MATRICES AND SYSTEMS OF LINEAR EQUATIONSThe theorem states that if n is not “too large” and ifis aboutthe size of |A|, then we can account for the errors in the computed solutionby adjustments in the equations of the same order of magnitude as are thechanges we had to make merely to get the equations into the machine.
Inother words, the error in the computed solution caused by the use offloating-point arithmetic is then no worse than the error we had to acceptfrom the outset because we were forced to round the entries of A tofloating-point numbers.Of course, should the matrixbe much larger than |A|, then theerrors in the computedmay be much larger than those due to theconversion of the problem to machine floating-point numbers.
Note thatone could actually calculate the matrix(at some expense) and go tohigher-precision arithmetic in case the resulting bound on the perturbationmatrix E exceeds the tolerance to which the entries of A are known to beaccurate. But more important, since the pivot order may materially affectwe draw from Theorem 4.9 the important conclusionthe size ofthat a pivoting strategy should try to keep the matrixsmall.We now indicate the simple proof of Theorem 4.9, using the notationand terms introduced in Sec. 1.3. First, we deal with the interchanges made(as recorded in the permutation matrix P) by applying Algorithm 4.2without interchanges to the matrix A' := P-1 A (as we did in Sec. 4.4).Thus, we compute the interesting entries of the factors L and U accordingto (4.23) byConsequently, by Sec. 1.3, especially by comparison of (1.12) with (1.13),the entriesandof the factors andas computed in floating-pointarithmetic satisfy the perturbed equationswithHere, each stands for some number of the form< u, theunit roundoff.
To simplify these equations, we next observe that for anysuch number and for any r, there existsso thatas long as u < 0.01. This shows that4.6BACKWARD ERROR ANALYSIS AND ITERATIVE IMPROVEMENT181and therefore(4.49)with(4.50)andThis shows that the computed factors andfor A' are the exactfactors for a perturbed matrix A' + F, with the error matrix F of the orderof the roundoff in the entries of A, provided the matrixis not muchlarger than |A|.The computational steps used in Algorithm 4.4, i.e., in the solvingphase, are rather similar to those above. One can, therefore, show in thesame way that the computed vector satisfies exactly the perturbedlower-triangular systemwithwhile the computed solutionsatisfies exactly the perturbed linear systemWe conclude that the computed solution satisfiesBut nowwherewhich proves the theorem.The bound (4.48) is conservative.
If partial pivoting is used, then thebound(4.50a)is often much more realistic. In any event, such a bound gives some insightinto the effect of the precision used in the calculations on the accuracy ofthe computed solution. For we get, for example, from (4.46) and (4.50),that the error of the computed solution relative to the size of this solutionis usually bounded as follows:(4.51)Quite loosely, the linear system Ax = b is often called ill-conditioned ifcond(A) is “large.” Somewhat more to the point, one should say that thelinear system is ill-conditioned with respect to the precision used if cond(A)is about 1/u, for then, by (4.51), a computed solution might well bear noresemblance to the (exact) solution of the system.182MATRICES AND SYSTEMS OF LINEAR EQUATIONSExample 4.8 Consider the linear system(4.52)We attempt to solve this system by the elimination Algorithm 4.2, using two-decimaldigit floating-point arithmetic and scaled partial pivoting.
The pivoting order turns outto be pT = [1 2 3], and the final content of the working array isContinuing the calculations, we find by back-substitution the approximate solutionThe residual isIn fact, the solution isso that thecomputed solutionis in error in the first significant digit.The max-norm for the coefficient matrix A of this system isthe matrixFurther,is noninvertible (its first column is 0.7 times its second column)0.012.
Hence we get from Theorem 4.8 thatThis system is therefore very ill-conditioned with respect to the precision used, and thevery large error in the computed solution is not surprising.Next, we repeat the calculations, using three-decimal-digit floating-point arithmeticthis time. Sincewe still do not expect a very accurate computed solution.After Algorithm 4.2, the working matrix has the content(4.53)and back-substitution gives the computed solutioni.e., we get the(exact) solution, even though the system is still somewhat ill-conditioned with respect tothe precision used.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
