Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 32
Текст из файла (страница 32)
This becomes evident when we change the right side of (4.52) toUsing the factorization (4.53), we calculate by Algorithm 4.4 the (approximate) solutionarithmetic), which has residual(still using three-decimal-digit floating-point. The exact solution ishenceour computed solution has about 10 percent error, which is compatible with (4.51).As this example shows, a large condition number relative to theprecision used may lead to a relatively large error in the computed solutionbut is not guaranteed to do so.4.6BACKWARD ERROR ANALYSIS AND ITERATIVE IMPROVEMENT183Whether or not a given linear system is ill-conditioned with respect tothe precision used can be conveniently ascertained [even without knowledge of cond(A)] during iterative improvement, which we now discuss.Withthe (unknown) error in the approximate solutionforAx = b, we found in Sec.
4.5 that(4.54)whereis the computable residual for. Here we have, then,a linear system whose solution is the error e and whose coefficient matrixagrees with the coefficient matrix of the original system. Ifis obtainedby the elimination Algorithm 4.2, we can solve (4.54) rather quickly by thesubstitution Algorithm 4.4.
Letbe the (approximate) solution for (4.54)will, in general, not agree with e. But at the veryso computed. Thenleast,should give an indication of the size of e. Ifwe conclude that the first s decimal places ofprobably agree with thoseof x. We would then also expectto be that accurate an approximationto e. Hence we expectto be a better approximation to x than isWe can now, if necessary,compute the new residualand solve (4.54) again to obtain anew correctionand a new approximationto x.
Thenumber of places in agreement in the successive approximationsas well as an examination of the successive residuals, shouldgive an indication of the accuracy of these approximate solutions. Onenormally carries out this iteration untilif t decimalplaces are carried during the calculations. The number of iteration stepsnecessary to achieve this end can be shown to increase with cond(A) .When cond(A) is “very large,” the correctionsmay neverdecrease in size, thus signaling extreme ill-conditioning of the originalsystem.For the success of iterative improvement, it is absolutely mandatory thatthe residuals be computed as accurately as possible. If, as is usual, floatingpoint arithmetic is used, the residual should always be calculated in doubleprecision arithmetic.Algorithm 4.5: Iterative improvement Given the linear system Ax = band the approximate solutionCalculateusing double-precision arithmeticUse Algorithm 4.2 (or if possible, only Algorithm 4.4) to computean (approximate) solution of the linear system Ae = rIfis “small enough,” stop and takeas the solutionOtherwise, setand repeat the procedure184MATRICES AND SYSTEMS OF LINEAR EQUATIONSIterative improvement can be used whenever an approximate solutionhas been found by any means.
It should always be used after an approximate solution has been found by elimination, since the corrections canthen be calculated relatively cheaply by forward- and back-substitution.Also, the rate of convergence of the process (if any) gives a good indicationof the condition of the system (with respect to the precision used).Examplc 4.9 We apply iterative improvement to the approximate solution of (4.52)calculated in Example 4.8. The correctly computed residual isrounded totwo significant digits.
Applying Algorithm 4.4 to this right side (using two-decimal-digitfloating-point arithmetic), we get the correctionwhich is of the same sizeas the computed solution. Hence we conclude that the given linear system is tooill-conditioned for the precision used and that a higher precision should be employed ifwe wish to calculate the solution of (4.52).In Example 4.8 we also calculated an approximate solutionfor thelinear system with the same coefficient matrix but a different right side, using three-decimal-digit floating-point arithmetic.
The correctly computed residual is.Applying Algorithm 4.4 to this r as right side (using the same precision as before), we getthe correctiongives the corrected solution, which is only 10 percent of the computed solution andThe residual for this approximate solutionturns out to be 0, so that just one step of iterative improvement produces the (exact)solution in this example.EXERCISES4.6-1 Use Theorem 4.8 to estimate the condition number of the following matrix:4.6-2 Use iterative improvement on the computed solution in Exercise 4.34.4.6-3 We say that a matrix A of order n is (strictly row) diagonally dominant if |a ii | >Use the corollary to Theorem 4.8 to prove that a diagonallydominant matrix is invertible.
(Hint: Write A = DB, where D is the diagonal matrix withdiagonal entries equal to those of A; then show that4.6-4 Estimate the condition number of the matrix of Exercise 4.6-1 by solving the linearsystem Ax = b with (a) bT = [24,27,27], (b) bT = [24.1,26.9,26.9]. Use iterative improvement.4.6-5 Show that, for the particular matrix norm (4.39), a noninvertible matrix B for whichequality holds in (4.44) can be constructed as follows: By (4.35) one can find x of norm 1 for*4.7DETERMINANT’S185which ||A-1 x|| = ||A-1|| ||x||.
Now choose B as the matrix A - xz T, withA - 1 x, and m so chosen that4.6-6 Show that one can carry out the construction of Exercise 4.6-5 for a general normprovided one knows how to choose, for a given nonzero n-vector y, an n-vector z so that, forall n-vectors u, zTu < ||u|| with equality if u = y.
How would you choose z in case the norm isthe 1-norm?*4.7 DETERMINANTSAlthough the student is assumed to be familiar with the concept of adeterminant, we take this section to give the formal definition of determinants and give some of their elementary properties.Associated with every square matrix A of numbers is a number calledthe determinant of the matrix and denoted by det(A). If A = (aij) is ann × n matrix, then the determinant of A is defined by(4.55)where the sum is taken over all n! permutations p of degree n, andis 1or -1, depending on whether p is even or odd (see Sec.
4. I). Hence, ifn = 1, thenwhile if n = 2(4.56)Already, for n = 3, six products have to be summed, and for n = 10, over3 million products, each with 10 factors, have to be computed and summedfor the evaluation of the right side of (4.55). Hence the definition (4.55) isnot very useful for the calculation of determinants. But we give below a listof rules regarding determinants which can be derived quite easily from thedefinition (4.55). With these rules, we then show how the determinant canbe calculated, using the elimination Algorithm 4.2, in about[ratherthanoperations.The determinant of a matrix is of importance because of the followingtheorem.Theorem 4.10 Let A be an n × n matrix; then A is invertible if andonly ifWe make use of this theorem in the next section, which concerns thecalculation of eigenvalues and eigenvectors of a matrix.For certain matrices, the determinant is calculated quite easily.186MATRICES AND SYSTEMS OF LINEAR EQUATIONSRule 1 If A = (aij) is an upper- (lower-) triangular matrix, theni.e., the determinant is just the product of the diagonal entries of A.For if A is, for example, upper-triangular and p is any permutationother than the identity permutation, then, for some i, we must have pi < i,and the corresponding productcontains, therefore, thesubdiagonal, hence zero, entryof A, and must be zero.
Hence, if A isupper-triangular, then the only summand in (4.55) not guaranteed to bezero is the term a11a22 · · · ann corresponding to the (even) identity permutation pT = [1 2 · · · n] .In particular,(4.57)One proves similarly a second rule.Rule 2 If P is the n × n permutation matrix given bywith some permutation p, thenRule 3 If the matrix B results from the matrix A by the interchange oftwo columns (rows) of A, then det(B) = -det(A).ExampleConsequently, if two columns (rows) of the matrix A agree (so that theirinterchange leaves A unchanged), then det(A ) = 0.Rule 4 If the matrix B is obtained from the matrix A by multiplyingall entries of one column (row) of A by the same numberthenExampleRule 5 Suppose that the three n × n matrices A1, A2, A3 differ only inone column (row), say the jth, and the jth column (row) of A, is the vectorsum of the jth column (row) of A1 and the jth column (row) of A,.
ThenExample*4.7DETERMINANTS187Rules 1 to 5 imply Theorems 4.11 and 4.12 below.Theorem 4.11 If A and B are n × n matrices, thenTheorem 4.12 If A is an n × n matrix and x = (xi ) and b are n -vectorssuch thatthen, for j = 1, . . . , n,(4.58)where A(j) is the matrix one gets on replacing the jth column of A byb.If A is invertible, i.e., (by Theorem 4.10), ifsolve (4.58) for xj, gettingthen one canThis is Cramer’s rule for the entries of the solution x of the linear systemAx = b.
Because of the difficulty of evaluating determinants, Cramer’s ruleis, in general, only of theoretical interest.In fact, the fastest known way to calculate det(A ) for an arbitraryn × n matrix A is to apply the elimination Algorithm 4.2 to the matrix A(ignoring the right side). We saw in Sec. 4.4 that this algorithm produces afactorizationof A into a permutation matrix P determined by the pivoting order p, alower-triangular matrix L with all diagonal entries equal to 1, and the finalupper-triangular coefficient matrix U = (uij), which has all the pivots onits diagonal. By Rule 1, det(L) = 1, while by Rule 2, det(P) = 1 or -1,depending on whether p is even or odd, i.e., depending on whether thenumber of interchanges made during the elimination is even or odd.Finally, again by Rule 1, det(U) = u11u22 · · · unn.
Hence(4.59)with i the number of interchanges during the elimination algorithm. Notethat the FORTRAN program FACTOR returns this number (-1)i inIFLAG (in case A is found to be invertible), thus making it easy tocalculate det(A ) by (4.59) from the diagonal entries of the workarray W.Of course, the elimination Algorithm 4.2 succeeds (at least theoretically) only when A is invertible.
But if A is not invertible, then thealgorithm will so indicate, in which case we know that det(A ) = 0, byTheorem 4.10.188MATRICES AND SYSTEMS OF LINEAR EQUATIONSFinally, if the matrix A has special properties, it is at times profitableto make use of the following rule.Rule 6: Expansion of a determinant by minors The minor Mij of then × n matrix A = (aij) is, by definition, the determinant of the matrix oforder n - 1 obtained from A by deleting the ith row and the jth column.One hasandRule 6 allows us to express a determinant of order n as a sum ofdeterminants of order n - 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
