Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 101
Текст из файла (страница 101)
The equations for the blocks of L and U are U11 = A11 andFirst, consider the case where A is block diagonally dominant by columns. We proveby induction thatwhich implies both the required bounds. This inequality clearly holds for k = 2;suppose it holds for k = i. We havewhereusing the block diagonal dominance for the last inequality.
Henceas required.The proof for A block diagonally dominant by rows is similar. The inductivehypothesis is that562S OLUTIONSTOP ROBLEMSand with P defined as before, we havegivingas required.For block diagonal dominance by columns in the-norm we haveandso block LU factorization is stable. If A is block diagonallydominant by rows, stability is assured if ||Ai,i-1||/||Ai-1,i|| is suitably bounded forall a.12.2. The block 2 x 2 matrixis block diagonally dominant by rows and columns in the 1- and-norms for = 1/2,but is not point diagonally dominant by rows or columns.
The block 2 x 2 matrixis point diagonally dominant by rows and columns but not block diagonally dominantby rows or columns in the -norm or l-norm.12.3. No. A counterexample is the first matrix in the solution to Problem 12.2,with = 1/2, which is clearly not positive definite because the largest element doesnot lie on the diagonal.12.4.
Form (12.2) it can be seen that (A-1)21 =Hencecomplement S =where the SchurS is the trailing submatrix that would be obtained after r – 1 steps of GE. It followsimmediately that ||S|| < pn ||A||.For the last part, note that ||S-1|| < ||A-l||, because S–l is the (2,2) block of-1A , as is easily seen from (12.2).12.5. The proof is similar to that of Problem 8.7(a).
We will show that1. Let y =and letThe kth equation ofgivesSOLUTIONSTOPROBLEMS563Hencewhich yieldsin view of the column diagonal dominance, as required.12.7. We have the block LU factorizationso thatdet(X) = det(A) x det(D – CA-lB).Hence det(X) = det(AD – ACA–l B), which equals det(AD – CB) if C commuteswith A.13.2. The new bounds have norms in place of absolute values and the constants aredifferent.13.3.
Immediate from AX – I = A(XA – I)A-1.13.4. With 0 <« 1, letA=ThenwhileHence ||AX – I||/||XA – I||of AX – I is large.Note that in this example every element13.5. We havewhereHenceSimilarly,where(A.12)HenceClearly,whereS OLUTIONS564From (A.12),TOP ROBLEMSsoThe first conclusion is that the approximate left inverse yields the smaller residualbound, while the approximate right inverse yields the smaller forward error bound.Therefore which inverse is “better” depends on whether a small backward error ora small forward error is desired.
The second conclusion is that neither approximateinverse yields a componentwise backward stable algorithm, despite the favorableassumptions onandMultiplying by an explicit inverse is simply not a goodway to solve a linear system.13.6. Here is a hint: notice that the matrix on the front cover of the LAPACKUsers’ Guide has the form13.7. If the ith row of A contains all 1s then simply sum the elements in the ithrow of the equation AA–1 = I.13.8. (A+ iB)(P + iQ) = I is equivalent to AP – BQ = I and AQ + BP = 0, or–1so X – l is obtainable from the first n columns of Y . The definiteness result followsfrom(x + iy)*(A + iB)(x + iy) = xT(Ax – By) + yT(Ay + Bx)+ i[xT(Ay + Bx) – yT(Ax – By)]where we have used the fact that A = AT and B = –BT. Doubling the dimension(from X to Y) multiplies the number of flops by a factor of 8, since the flop countfor inversion is cubic in the dimension.
Yet complex operations should, in theory,cost between about two and eight times as much as real ones (the extremes beingfor addition and division). The actual relative costs of inverting X and Y dependon the machine and the compiler, so it is not possible to draw any firm conclusions.Note also that Y requires twice the storage of X.13.10. As in the solution to Problem 8.8, we havedetIf (A ) j i = 0, this expression is independent of α, and hence det(A) is independentof aij.
(This result is clearly correct for a triangular matrix. ) That det(A) can beindependent of aij shows that det(A), or even a scaling of it, is an arbitrarily poormeasure of conditioning, for A + αe i approaches a multiple of a rank-1 matrix as-lS OLUTIONSTO565P ROBLEMS13.11. That Hadamard’s inequality can be deduced from QR factorization wasnoted by Householder [586, 1958, p. 341]. From A = QR we havesothatHadamard’s inequality follows since |det(A)| = |det(R)| = |r11 .
. . rnn|. There isequality whenfor k = 1: n, that is, when ak = αkqk, k = 1: n, forsome scalars αk. In other words, there is equality when R in the QR factorizationis diagonal.13.12. (a) Straightforward. (b) ForFor the Pei matrix,13.13. (a) The geometric mean ofisSince the geometric mean does not exceed the arithmetic mean,which gives the required bound.
(b) is trivial.13.14. The key observation is that for a triangular systemcomputed solution from substitution satisfiestheThis result holds for any order of evaluation and is proved (for any particular orderof evaluation) using a variation on the proof of Lemma 8.2 in which we do not dividethrough by the product of 1 + δi terms.
Using (A. 13) we havewheredet(T) = det(T + ∆T), hencewhereIf, andThe conclusion is thatBut, since diag(∆T) = 0,wherethenThusA diagonal similarity therefore has no effect on the error bound and so there is nopoint in scaling H before applying Hyman’s method.S OLUTIONS56613.15. ForTOP ROBLEMSwe have, for any i ε {1,2, . . .
,n},where Aij denotes the submatrix of A obtained by deleting row i and column j. Adefinition of condition number that is easy to evaluate is14.3 Straightforward, since L is unit lower triangular with |lij| < 1.14.6 Let D = diag(dj), where d1 = 1 andThen T = DA is tridiagonal, symmetric and irreducible. By applying Theorem 14.9and using symmetry, we find thatThere is one degree of freedom in the vectors x and y, which can be expended bysetting xl = 1, say.15.1. The equation would imply, on taking traces, 0 = trace(l), which is false.15.2.
It is easily checked that the differential equation given in the hint has thesolution Z(t) = eAt CeBt . Integrating the differential equation between 0 andgives, assuming thatdt satisfies the Sylvester equation. For theHence –Lyapunov equation, the integral –exists under the assumptionon A, and the corresponding quadratic form is easily seen to be positive.S OLUTIONSTO567P ROBLEMS15.3.
SinceXT is a minimizer if X is. If X + XT = 0 then X is a skew-symmetric minimizer.Otherwise, note that the minimization problem is equivalent to finding the rightsingular vector corresponding to the smallest singular value σ min of P = ISince vec(X) and vec(XT) (suitably normalized) are both singular vectorscorresponding to σmin, so is their sum, vec(X + XT)0.
Thus the symmetricmatrix X + XT is a minimizer.Byers and Nash [176, 1987] investigate conditions under which a symmetricminimizer exists.15.4. XLASY2 uses Gaussian elimination with complete pivoting to solve the 2 x 2or 4 x 4 linear system that arises on converting to the Kronecker product form(15.2). For complete pivoting on a 4 x 4 matrix the growth factor is bounded by4 (§9.3), versus 8 for partial pivoting.
The reasons for using complete pivotingrather than partial pivoting are that, first, the small increase in cost is regarded asworthwhile for a reduction in the error bound by a factor of 2 and, second, completepivoting reveals the rank better than partial pivoting, enabling better handling ofill-conditioned systems [38, 1993, p. 78].16.1. Since p(B) < 1, a standard result (Problem 6.8) guarantees the existence of aconsistent norm ||·||p for which ||B||P < 1. The series(1 - ||B||p)-1 is clearly convergent, and so, by the equivalence of norms,is convergent for any norm.the convergence ofensures that ofSinceofcanalsobeproveddirectlyusing the(The convergenceJordan canonical form.)16.2.
(a) We have(A.14)IfthenIfso thatthen, using (A.14),(b) We break the proof into two cases. First, suppose thatfor some m. By part (a), the same inequality holds for all k > m and we arefinished. Otherwise,for all k. By part (a) the positivesequence ||xk – a|| is monotone decreasing and therefore it converges to a limit l.Suppose that l =where δ > 0.
Since β < 1, for some k we must have568S OLUTIONSTOP ROBLEMSBy (A.14),which is a contradiction. Hence l = α/(1 – β), as required.(c) The vectors ek can be regarded as representing the rounding errors on thekth iteration. The bound in (b) tells us that provided the error vectors are boundedby α, we can expect to achieve a relative error no larger than α/(1 – β). In otherwords, the result gives us an upper bound on the achievable accuracy.
When thisresult is applied to stationary iteration, β is a norm of the iteration matrix; to make-1β less than 1 we may have to use a scaled norm of the form ||A|| := ||XAX ||.17.1. Let Xn be the n x n version of the upper triangular matrixwhere D = diagso that ||Xn (:,j)||2 = 1, j = l:n. From (8.3),is the obvious n x n analogue ofLet A = diag(0,...,0, λ), with |λ| < 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
