Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 27
Текст из файла (страница 27)
Show that Algorithm 4.2 applied to a system of order nrequires n(n - 1)/2 divisions, (n3 - n)/3 multiplications, and (n3 - n)/3 additions.4.2-2 Show that the back-substitution Algorithm 4.1 requires n divisions, n(n - 1)/2 multiplications, and n(n - 1)/2 additions.4.2-3 On some machines, division is more time-consuming than multiplication. How wouldyou modify Algorithm 4.2 for such a machine?4.2-4 Calculate the number of additions and the number of multiplications necessary tomultiply an n × n matrix with an n -vector.4.2-5 How many additions, multiplications, and divisions are required in Algorithm 4.2 ifonly the final upper-triangular matrix U is desired?4.2-6 Use elimination to show that the following system does not have a solution.4.2-7 The execution time of a program incorporating Algorithm 4.2 is largely determined bythe time spent in the innermost loop.
For this reason, one would like to have that loop asefficient as possible. At the same time, FORTRAN stores arrays by columns and, on manymachines, it is therefore much faster to deal with an array column by column rather than rowby row.For these reasons, reorganize Algorithm 4.2 in such a way that the innermost loop(s)run(s) over row indices, i.e., so that a column rather than a row is modified at a time.4.2-8 Solve the following system by elimination. Round off all calculations to three significant digits.Check your answers by substituting back into the original equations, and estimate theiraccuracy. Exact solution: [l,l,l,l].4.3THE PIVOTING STRATEGY1574.2-9 use subroutine TRID to solve the linear systemwhen n = 30 and h = 0.1.4.2-10 Use Theorem 4.6 and the corollary to Lemma 2.1 to prove that every polynomial ofdegree < n can be written in exactly one way in Newton form for given centers c1, .
. . , cn.(Hint: Consider the linear system for the coefficients in the Newton form for a polynomialwhich agrees with a given function at c1, . . . , cn, cn+1.)4.2-11 Prove Theorem 4.7. (Hint: Prove first that any solution of Ax = b remains a solutionofThen show that any operation of the kind mentioned can be undone by anoperation of the same kind, hence show that Ax = b can in turn be obtained frombya sequence of such operations.)4.3 THE PIVOTING STRATEGYThe elimination algorithm 4.2 presented in the preceding section calculatesefficiently and with certainty the solution of any system Ax = b, if allcalculations are carried out in infinite-precision arithmetic. If, as is moreusual, finite-precision arithmetic is used, it is not difficult to give examplesfor which Algorithm 4.2 produces completely erroneous answers.In this section, we discuss briefly just one possible source for such afailure, an incorrect pivoting strategy.
Here, we mean by pivoting strategythe scheme used to choose the pivotal equation (and, possibly even thepivotal column) at each elimination step.Example 4.4 The solution of the systemis x l = 10, x 2 = 1. We use four-decimal floating arithmetic to solve this system byelimination, picking the first equation as the pivotal equation during the first (and only)step. We get the multiplierHenceThis givesHence, from the first equation,158MATRICES AND SYSTEMS OF LINEAR EQUATIONSA “plausible” explanation of this failure goes as follows: The pivotentry a 11 = 0.0003 is “very small”; since the computations would breakdown if a 11 were zero, it is not surprising that, in the environment offinite-precision arithmetic, the algorithm performs badly for a 11 “nearzero.”Of course, this explanation uses such undefined terms as “very small”and “near zero” and is therefore quite useless.
In fact, by multiplying thefirst equation by an appropriate power of 10, we can make a,, as large aswe wish without changing the computed solution. To see this, consider againthe system of Example 4.4, but with the first equation multiplied by 10m,where m is some integer:Using again the first equation as pivotal equation, and using four-decimalfloating arithmetic, we getHencewhich is the same result as before. Hence again x2 = 1.001, and finally,x1 = (0.001 · 10 m )/(0.0003 · 10 m ) = 3.333.Actually, the failure in this example is due to the fact that |a11| is smallcompared with |a12 |; thus a relatively small error due to roundoff in thecomputed x2 led to a large variation of the computed x1, from the correctx1 . This is confirmed if we use equation 2 as pivotal equation, whereas compared withWe getand the new first equation becomesso that x2 = 1, the correct answer, and finally, from the second equation,x1 = 10.
But even if roundoff had conspired to give x2 = 1.001 (as it did inExample 4.4), the second equation would still givea good result.4.3THE PlVOTING STRATEGY159It is much more difficult (if not impossible) to ascertain for a generallinear system how various pivoting strategies affect the accuracy of thecomputed solution.
A notable and important exception to this statementare the linear systems with positive definite coefficient matrix, that is,systems whose coefficient matrix satisfiesFor such a system, the error in the computed solution due to roundingerrors during elimination and back-substitution can be shown [41; p. 127]to be acceptably small if the trivial pivoting strategy of no interchanges isused. (See Exercise 4.4-9 for an efficient algorithm for this case.) But it isnot possible at present to give a “best” pivoting strategy for a generallinear system, nor is it even clear what such a term might mean.For the sake of economy, the pivotal equation for each step must beselected on the basis of the current state of the system under considerationat the beginning of the step, i.e., without foreknowledge of the effect of theselection on later steps.A currently accepted strategy is scaled partial pivoting. In this strategy,one calculates initially the “size” di of row i of A, for i = 1, .
. . , n. Aconvenient measure of this size is (see Sec. 4.5) the numberThen, at the beginning of the general, or kth, step of the eliminationAlgorithm 4.2, one picks as pivotal equation that one from the availablen - k candidates which has the absolutely largest coefficient of xk relativeto the size of the equation. In the terms of Algorithm 4.2, this means thatthe integer j is selected as the (usually smallest) integer between k and nfor whichClearly, scaled partial pivoting selects the correct pivoting strategy forthe system in Example 4.4, and is not thrown off by a resealing of theequations.It is possible to modify Algorithm 4.2 so as to leave not only thepivotal equation, but also the unknown to be eliminated open to choice.
Inthis modification, one chooses two permutations, p and q, which designatethe p kth equation as the equation to be used during the kth step toeliminatek = 1, . . . , n - 1. In total pivoting, pivotal equation andunknown are selected by looking for the absolutely largest coefficient ofany of the n - k unknowns in any of the n - k candidate equations.
Ofcourse, such a strategy is much more expensive than scaled partial pivoting, hence is not often employed, even though it is admittedly superior topartial pivoting.160MATRICES AND SYSTEMS OF LINEAR EQUATIONSEXERCISES4.3-1 Describe a modification of Algorithm 4.2 which incorporates total pivoting.4.3-2 Give an example of a 2 × 2 linear system for whichresults than scaled partial pivoting in four-decimal floatingand a21 “small” compared with a12 and a22.)4.3-3 Solve the following linear system, using four-decimalfirst equation as pivotal equation and once with the secondfinally with total pivoting.total pivoting gives more accuratearithmetic.
(Hint: Make both al1floating arithmetic, once with theequation as pivotal equation, andCompare with the exact answer x1 = 1.000, x2 = 0.2500.4.34 Solve the system of Exercise 4.2-8, but using scaled partial pivoting, and compare withthe results of Exercise 4.2-8.4.4 THE TRIANGULAR FACTORIZATIONIt is possible to visualize the elimination process of Algorithm 4.2 asderiving a factorization of the coefficient matrix A into three factors,a permutation matrix P which accounts for the row interchanges made, aunit lower-triangular matrix L containing (in its interesting part) themultipliers used, and the final upper-triangular matrix U.
This point ofview leads to an efficient algorithm (Choleski factorization, see Exercise4.4-9) in case A is a symmetric positive definite matrix. It is also of value inunderstanding the so-called compact schemes (associated with the names ofDoolittle and Crout, see Exercise 4.4-8) which are advantageous in solvinglinear systems on desk (or pocket) calculators, since they reduce thenumber of intermediate results that have to be recorded. These schemesalso permit the use of double-precision accumulation of scalar products(on some machines), for a reduction of rounding-error effects. Finally, thefactorization point of view of elimination makes it easy to apply backwarderror analysis to the elimination process (as will be done in Sec.
4.6). Forthese reasons, we now exhibit the triangular factorization for A as generated by Algorithm 4.2.Assume, to begin with, that no row interchanges occurred duringexecution of the algorithm and consider what happens to the ith equation.For k = 1, 2, . . . , i - 1, the equation is transformed during the k th stepfromto4.4THE TRIANGULAR FACTORIZATION161by the prescriptionwith the multiplierstored in the (i, k)-entry of the working array. Here,arethe coefficients and right side of the pivotal equation for this step, henceare in their final form. This means, in terms of the output from Algorithm4.2, i.e., in terms of the upper-triangular matrix U and the vector yproduced in that algorithm, thatConsequently,(4.23)(4.24)We now rewrite these equations so that the original data, A and b, appearon the right-hand side.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
