Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 100
Текст из файла (страница 100)
In particular, we can take β ι = 1 in (b), whichrequires M(A)d = e, where d = De. Thenso thebound isas required.8.8. (a) Using the formula det(I + xyT) = 1 + yTx we have detHence we takeifotherwise there is no αij that makes A +singular.It follows that the “best” place to perturb A to make it singular (the place thatgives the smallest αij ) is in the (s, r) position, where the element of largest absolutevalue of A–1 is in the (r, s) position.(b) The off-diagonal elements ofare given byHence,using part (a),is singular, where α = –22–n. In fact, Tn is also madesingular by subtracting 21-n from all the elements in the first column.8.9. Here is Zha’s proof.
If s = 1 the result is obvious, so assume s < 1. Define then-vectorsandand letIt is easy to check thatS OLUTIONSTOP ROBLEMS555which shows that σ is a singular value of Un (θ). With σι denoting the ith largestsingular value,Now we prove by induction thatFor n = 2 it is easy to check bydirect computation thatUsing the interlacing property of thesingular values [470, 1989, §8.3.1] and the inductive assumption, we haveTherefore8.10. For a solver of this form, it is not difficult to see thatwheredenotes fi with all its coefficients replaced by their absolute values, andwhere (M(T), |b| ) is a rational expression consisting entirely of nonnegative terms.This is the required bound expressed in a different notation.
An example (admittedly, a contrived one) of a solver that does not satisfy (8.20) is, for a 2 x 2 lowertriangular system LX = b,9.1. The proof is by induction. Assume the result is true for matrices of order n – 1,and supposeis a unique LU factorization. Then MV = C – laT has a unique LU factorization,and so by the inductive hypothesis has nonsingular leading principal submatricesof order 1 to n – 2. Thus vii 0, i = 1:n – 2. If α = 0 then b = 0 and l isarbitrary subject to C – laT having an LU factorization.
But C – ( l + ∆l)aT hasnonsingular leading principal submatrices of order 1 to n – 2 for sufficiently small∆ l (irrespective of a), so has an LU factorization for sufficiently small ∆l. Thus ifα = 0 we have a contradiction to the uniqueness of the factorization. Hence α 0 ,which completes the proof.9.2. A(σ) fails to have an LU factorization without pivoting only if one of itsleading principal submatrices is singular, that is, iffor k{1,2, . .
. ,n – l}. There are thus l + 2 + · · ·+ ( n – 1) = ½(n – 1)n “danger” valuesof u, which may not all be distinct.9.3. If 0 F(A) then all the principal submatrices of A must be nonsingular, sothe result follows by Theorem 9.1. Note that A may have a unique LU factorizationeven when 0 is in the field of values, as shown by the matricesso the implication is only one way. Note also that 0 F(A) iff eiθ A has positivedefinite Hermitian part for some real θ (Horn and Johnson [581, 1991, Thin. 1.3.5]).S OLUTIONS5569.4.
The changes are minor. Denoting bythe result of Theorem 9.3 becomesandTOP ROBLEMSthe computed permutations,and that of Theorem 9.4 becomes9.59.6. Since A is nonsingular and every submatrix has a nonnegative determinant,the determinantal inequality shows that det (A (1: p, 1: p)) > 0 for p = 1: n –1, whichguarantees the existence of an LU factorization (Theorem 9.1). That the elementsof L and U are nonnegative follows from (9.2).GE computessinceThusFor ifor jThus 0for all i, j, kand hence= 1.1.
But9.7. The given fact implies that JAJ is totally nonnegative. Hence it has anLU factorization JAJ = LU with L > 0 and U > 0. This means that A =(JLJ)(JUJ)is an LU factorization, and= LU = JAJ = |A|.9.8. We start with Theorem 9.4, and so need to boundHenceNowimplyingHence (with the same caveat as mentioned after Theorem 9.5)9.9. By inspecting the equations in Algorithm 9.2 we see that the computed LUfactors satisfySince= b, we have, writing α =formula (Problem 24.2),and using the Sherman–MorrisonS OLUTIONSTO557P ROBLEMSSoThe error x –be of orderis a rational function of and is zero if xj = 0, but it will typically9.10. α(B) = α(A), and B-l =soTaking A = Sn g(2n) >(B) =(A).
Hence(B) == n +1.9.11. First, the size or accuracy of the pivots is not the fundamental issue. The erroranalysis shows that instability corresponds to large elements in the intermediatematrices or in L or U. Second, in PAQ = LU,is an element of A-1 (see(9.10)), so it is not necessarily true that the pivoting strategy can force unn to besmall.
Third, from a practical point of view it is good to obtain small final pivotsbecause they reveal near singularity of the matrix.9.12. Because the rows of U are the pivot rows, µ j is the maximum number of timesany element in the jth column of A was modified during the reduction. Since themultipliers are bounded by T–1, the bound for maxifollows easily. Thusp n < (1 +T-l maxjµj).10.1. Observe that if z = αei – ej, where ei is the ith unit vector, then for any αwe have, using the symmetry of A,Since the right-hand side is a quadratic in α, the discriminant must be negative,that is,< 0, which yields the desired result. This result can alsobe proved using the Cholesky decomposition and the Cauchy–Schwarz inequality:A = RTR(there is strict inequality forsinceThe inequality implies that |aij| < max(aii , ajj), which showsthatthat is, the largest element of A lies on the diagonal.10.2.
Compute the Cholesky factorization A = RTR, solve RTy = x, then computeyTy. In addition to being more efficient than forming A-1 explicitly, this approachguarantees a nonnegative result.10.3. Let s = c –Thenas required.By Lemma 8.4,Hence558S OLUTIONSTOP ROBLEMS10.4. A=where B = C–aa T /α. Let y = [1, z] T .Then 0 <for all and so the discriminant 4(z T a)2 –TTT> 0 (since α = a11 > 0).4αz Cz < 0 if z 0, that is, z Bz = z CZ –This shows that B is positive definite.By induction, the elimination succeeds (i.e., all pivots are nonzero) and all thereduced submatrices are positive definite. Hence> 0 for all r. ThereforeThus a kk => 0.
Since the largest element of a positive definitematrix lies on the diagonal (Problem 10.1), for any i, j, k there exists r such thatwhich shows that the growth factor pn = 1 (since pn > 1).10.5. From (10.8),soas required.10.6.so RZ = 0 and hence AZ = 0. Z is of dimensionn (n – r) and of full rank, so it spans null(A).X10.7. The inequalities (10. 13) follow from the easily verified fact that, for j > k,10.8. Examples of indefinite matrices with nonnegative leading principal minors areA necessary and sufficient condition for definiteness is that all the principal minorsof A (of which there are 2n–1 ) be nonnegative (not just the leading principal minors);see, e.g., Horn and Johnson [580, 1985, p.
405] or Mirsky [763, 1961, p. 405] (samepage number in both books!).10.9. For the matrix Z =we have, from (10.15),ZTAZ = Sk (A) and so we can take p = Zel, the first column of Z.S OLUTIONSTOP ROBLEMS55910.10. Theorem 10.3 is applicable only if Cholesky succeeds, which can be guaranteed only if the (suitably scaled) matrix A is not too ill conditioned (Theorem 10.7).Therefore the standard analysis is not applicable to positive semidefinite matricesthat are very close to being singular. Theorem 10.14 provides a bound on the residual after rank(A) stages and, in particular, on the computed Schur complement,which would be zero in exact arithmetic.
The condition of Theorem 10.7 ensuresthat all the computed Schur complements are positive definite, so that even ifmagnification of errors occurs, it is absorbed by the next part of the Cholesky factor.The proposed appeal to continuity is simply not valid.10.11. The analysis in §10.4 shows that for a 2 x 2 pivot E, det(E) < ( α2 – l) forcomplete pivoting and det(E) < (α 2 – 1)λ 2 for partial pivoting. Now α2 – 1 < 0 andµ 0 and λ are nonzero if a 2 x 2 pivot is needed.
Hence det(E ) <0, which means thatE has one positive and one negative eigenvalue. Note that if A is positive definiteit follows that all pivots are 1 x 1.If the block diagonal factor has p+ positive 1 x 1 diagonal blocks, p– negative1 x 1 diagonal blocks, p0 zero 1 x 1 diagonal blocks, and q 2 x 2 diagonal blocks,then the inertia is (+, –, 0) = (p+ + q,p- + q,p0).Denote a 2 x 2 pivot byand consider partial pivoting. We know det(E) = ac – b2 < 0 and |b| > |a|, so theformula det(E) = [(a/b)c – b]b minimizes the risk of overflow. Similarly, the formulahelps to avoid overflow; this is the formula used in LINPACK’S xSIDI and LAPACK’SxSYTRI. The same formulae are suitable for complete pivoting because then |b| >max( |a|, |c| ).10.12.
The partial pivoting strategy simplifies as follows: if |a11| > α|a21| use a1 x 1 pivot all, if |a22| > α|a12| use a 1 x 1 pivot a22, else use a 2 x 2 pivot, that is,do nothing.10.13. There may be interchanges, because the tests |a11| > αλ and αλ2 < |a11|can both fail, for example for A =withBut there can be no 2 x 2pivots, as they would be indefinite (Problem 10.11). Therefore the factorization isPAPT = LDLT for a diagonal D with positive diagonal entries.10.14. That the growth factor bound is unchanged is straightforward to check.
No2x2 pivots are used for a positive definite matrix because, as before (Problem 10.11),any 2x2 pivot is indefinite. To show that no interchanges are required for a positivedefinite matrix we show that the second test, αλ2 < |a11| is always passed.
Theis positive definite, so a11arr –> 0. Hencesubmatrixas required.560S OLUTIONSTOP ROBLEMS10.15. With partial pivoting the diagonal pivoting method produces the factorization, with P = I,As0, ||L||and now ||L||In contrast, complete pivoting yieldsis bounded independently of10.16. For any nonzero x we havePutting x1 =we obtainwhich shows that S is positive definite.10.17.
(a) The nonsingularity of A follows from the factorizationsince G + BH-1 BT is symmetric positive definite.(b) It suffices to show that the first n + m – 1 leading principal submatrices ofare nonsingular for any permutation matrixBut these submatrices are ofthe formwhere AP is a principal submatrix of A andis a permutationmatrix.
Any such AP is of the formwhere Hp and GP are principal submatrices of H and G, respectively, and so arepositive definite. Thus AP is symmetric quasidefinite and hence nonsingular by (a),as required.(c)so (AS + (AS)T)/2 = diag(H, G), which is symmetric positive definite.S OLUTIONSTO561P ROBLEMS11.111.2. The inequality (11.4) yields, with x0 := 0, and dropping the subscripts on thegi and Gi ,Now G|F| <assumed to have a modestwhere B =-norm. Now, using Problem 11.1,can beunder the conditions of Theorem 11.4. The term Gg can be bounded in a similarway. The required bound forfollows.12.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
