Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 99
Текст из файла (страница 99)
If A is diagonalizable then with δ = 0 we get||A|| = ρ(A). The last part of the result is trivial.S OLUTIONSTOP ROBLEMS5476.9. Let A have the SVD A = UΣV*. By the unitary invariance of the 2- andFrobenius norms, ||A||2 = ||Σ||2 = σ1, ||A||F = ||Σ||F=Thusby||A||2 < ||A||F <(in fact, we can replacewhere r = rank(A)).There is equality on the left when σ2 = · · · = σn = 0, that is, when A has rank 1(A= xy*) or A = 0. There is equality on the right when σ1 = · · · = σ n = α, thatis, when A = αQ where Q has orthonormal columns,6.10.
Let F = PΣQ* be an SVD. ThenButcan be permuted into the form diag(Di ), where Di =It is easyto find the singular values of Di , and the maximum value is attained for σ1 = ||F||2.6.11 (a)with equality for x = ek, where the maximum is attained for j = k.(b)Equality is attained for an x that gives equality in the Holder inequality involvingthe kth row of A, where the maximum is attained for i = k. Finally, from eitherformula,6.12. Using the Cholesky factorization A = R*R,6.13. HT is also a Hadamard matrix, so by the duality result (6.21) it suffices toshow that ||H||P = nl/p for 1 < p < 2. Since |hij| = 1, (6.12) gives ||H||P > n1/p.Since ||H||1 = n and ||H||2 = n1/2, (6.20) gives ||H||P < nl/p, and so ||H||P = nl/pfor 1 < p < 2, as required.6.14.
We prove the lower bound in (6.22) and the upper bound in (6.23); the otherbounds follow on using ||AT||P = ||A||q. First, note that ||A||P > ||Aej||P = ||A(:, j)||p,which gives the lower bound in (6.22). Now assume that A has at most µ nonzerosper column. DefineDi = diag(si1, . . . . sin ),548S OLUTIONSTOP ROBLEMSand note thatWe havewhich gives the upper bound in (6.23).6.15. The lower bound follows from ||Ax||p/||x||p < || |A||x| ||p/|| |x| ||P. From (6.12)we haveBy (6.21), we also have || |A| ||P = || |AT| ||q < nl-l/q||AT||q = n1/p||A||p and theresult follows.6.16.
The function v is not a vector norm becausedoes not hold forallHowever,and the other two norm conditionshold, so it makes sense to define the “subordinate norm”. We haveThere is equality for xj an appropriate unit vector ej. Hence v(A) = maxj v(A(:,j)).7.1. It is straightforward to obtain from A(y – x) = ∆b – ∆Ax + ∆A(x – y) theinequalityIn general, if B > 0 and ρ(B) < 1then I – B is nonsingular. Sincewe can premultiplybyto obtain the bound for |x – y|. For the last part,S OLUTIONSTO549P ROBLEMS7.2.
Take norms in r = A(x–y) and x–y = A–lr. The result says that the normwiserelative error is at least as large as the normwise relative residual and possibly K(A)times as large. Since the upper bound is attainable, the relative residual is not agood predictor of the relative error unless A is very well conditioned.7.3. Let DR equilibrate the rows of A, so that B = DRA satisfies |B|e = e. ThenHence= cond(D R A) = cond(A), which impliescond(A).The inequality cond(A) <is trivial, and the deduction of (7. 12) is immediate.7.4. The first inequality is trivial.
For the second, since hii = 1 and |hij| < 1 wehave |H| > 1 and< n. Hence7.5. We have ∆x = A-l ∆b, which yieldsNowwhich yields the result.If we take k = n we obtain the bound that would be obtained by applyingstandard perturbation theory (Theorem 7.2).
The gist of this result is that the fullK2(A) magnification of the perturbation will not be felt if b contains a significantcomponent in the subspace span(U k) for a k such thatThis lattercondition says that x must be a large-normed solution:7.6. (a) Useupper bound, use f < |A| |x|.(b) UseFor the7.7. We will prove the result for w; the proof for η is entirely analogous. The lowerbound is trivial. LetThenand(A + ∆A)y = b + ∆b with |∆ A| < |A| andHence |b| = |(A + ∆A)y - ∆b| <yieldingThuswhich implies the result, by Theorem 7.3.S OLUTIONS5507.8. We have ∆x = A-l (∆b – ∆Ax) +∆ Ax) +and soTOP ROBLEMSTherefore cT∆ x = cTA-l (∆b –this inequality being sharp.
HenceThe lower bound forfollows from the inequalities |cTx| = |cTA-1·Ax| <T -lTT -l|c A | |A| |x| and |c x| = |c A b| < |cTA-l ||b|. A slight modification to thederivation of(A, x) yields7.9. (a) For any D1, D2we have(A.4)The rest of the proof shows that equality can be attained in this inequality.Let x1 > 0 be a right Perron vector of BC, so that BCx1 = πx1, where π =ρ(BC) > 0. Define(A.5)x2 = Cx1,so that x2 > 0 andBx2 = πx 1 .(A.6)(We note, incidentally, that x2 is a right Perron vector of CB: CBx2 = πx 2 .)Now define(A.7)D2 = diag(x 2 ).D1 = diag(x 1 ) - 1 ,TorThen, with e = [1, 1, . . . , 1] , (A.6) can be written BD2e =π e. Since D1BD2 > 0, this givessimilary, (A.5) can be writtenD2e =or= e, which givesHence forD1 and D2 defined by (A.7) we haveasrequired.Note that for the optimal D1 and D2, D1BD2 andboth have theproperty that all their rows sums are equal.(b) Take B = |A| and C = |A-l|, and note thatNow apply (a).(c) We can choose F1 > 0 and F2 > 0 so that |A| + tFl > 0 and |A-l| + tF2 > 0for all i! >0.
Hence, using (a),Taking the limit as t0 yields the result, using continuity of eigenvalues.S OLUTIONSTO551P ROBLEMS(d) A nonnegative irreducible matrix has positive Perron vector, from standard Perron-Frobenius theory (see, e.g., Horn and Johnson [580, 1985, Chap. 8]).Therefore the result follows by noting that in the proof of (a) all we need is for D1and D2 in (A.7) to be defined and nonsingular, that is, for x1 and x2 to be positivevectors.
This is the case if BC and CB are irreducible (since x2 is a Perron vectorof CB)(e) Usingandit is easy toshow that the results of (a)–(d) remain true with the co-norm replaced by the 1norm. Fromit then follows that infIn fact, the result in (a) holds for any p-norm, though the optimal D1and D2 depend on the norm; see Bauer [79, 1963, Lem. 1(i)].7.10. Thatcannot exceed the claimed expression follows by taking absolutevalues in the expression ∆X = – (A-l ∆AA–1 + A–1 ∆A∆ X).
To show it can equalit we need to show that if the maximum is attained for ( i, j) = (r,s) thencan be attained, to first order inEquality is attained for ∆A = D1ED2, whereD1 = diag(sign(A -l ) r i), D2 = diag(sign(A - 1 )i s ).7.11. (a) We need to find a symmetric H satisfying Hy = b – Ay =: r. Considerthe QR factorizationThe constraint can be rewritten QTHQ·QTy = QTr, and it is satisfied by QTHQ :=diag( H, 0 n -2) if we can find Hsuch thatwhere t =We can take:= (||u||2/||t||2)Q, where Qis either a suitably chosenHouseholder matrix, or the identity if t is a positive multiple of u.
Thenand(b) We can assume, without loss of generality, that|y1| < |y2| < · · · < |yn|.(A.8)Define the off-diagonal of H by hij = hji = gij for j > i, and let h11 = g11. The i t hequation of the constraint Hy = Gy will be satisfied if(A.9)SOLUTIONS552TOP ROBLEMSIf yi =0 set hii = 0; then (A.9) holds by (A.8). Otherwise, set(A.10)which yieldsby the diagonal dominance.(c) Let D =and A =:Then= 1 and< 1 forij.
The given condition can be writtenwhere= Dy and = D-lb. Definingas in the proof of (b), we find from (A. 10) thatso that< (2n - 1)With H :=wefind that H = HT, (A + H)y = b, and |H| < (2n – 1)7.12. By examining the error analysis for an inner product (33.1), it is easy to seethat for any xHencesatisfies(A.11)which is used in place of (7.26) to obtain the desired bound.7.13. (a) Writing A-1 =we haveBy the independence of theand δι.Hence(b) A traditional condition number would be based on the maximum ofover all “perturbations to the data of relative size σ". The expression condexp(A, b)uses the “expected perturbation”rather than the worst case.(c) For eij = ||A||2 and fi = ||b||2 we haveS OLUTIONSTOP ROBLEMS553soButHence—This inequality shows that when perturbations are measured normwise there is littledifference between the average and worst-case condition numbers.7.14.
We haveNote that this result gives a lower bound for the optimal condition number, whileBauer’s result in Problem 7.9(c) gives an upper bound. There is equality for diagonalA, trivially. For triangular A there is strict inequality in general since the lowerbound is 1!8.1. “Straightforward.8.2. LetThenAsThis 3 x 3 example can be extended toan n x n one by padding with an identity matrix.8.3. The bound follows from Theorem 8.9, sinceUsingwe get a similar result to that given by Theorem 8.7.8.4. Assume T is upper triangular, and write T = D – U, where D = diag( tii ) > 0and U > 0 is strictly upper triangular.
Then, using the fact that (D-1 U)n = 0,S OLUTIONS554TOP ROBLEMSNow 0 < b = TX = (D – U)x, so Dx > Ux, that is, x > D-l Ux. Hencewhich gives the result, since x = T-1b > 0.8.5. Use (8.3).8.7. (a) Writewhere Ab = y. Let |bk| =Fromit follows thatand hence that(b) Apply the result of (a) to AD and use the inequality(c) If A is triangular then we can achieve any diagonal dominance factors β ι welike, by appropriate column scaling.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
