Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 70
Текст из файла (страница 70)
Orthonormality of Q is a consequence of orthogonalityrelations that are implicit in the methods, and these relations may be vitiatedby rounding errors.Some insight is provided by the case n = 2, for which the CGS and MGSmethods are identical. Given a1, a2we compute q 1 = a 1 /||a 1 ||2, whichwe will suppose is done exactly, and then we form the unnormalized vectorq2 = a2 –The computed vector satisfieswhereHence18.7 G RAM -S CHMIDT O RTHOGONALIZATION379and so the normalized inner product satisfies(18.18)whereis the angle between a 1 and a2. Butwhere A = [a 1, a2] (Problem 18.8).
Hence, for n = 2, the loss of orthogonalitycan be bounded in terms of κ 2 (A). The same is true in general for the MGSmethod, as proved by Björck [107, 196 7]. A direct proof is quite long andcomplicated, but a recent approach of Björck and Paige [119, 1992] enables amuch shorter derivation; we take this approach here.The observation that simplifies the error analysis of the MGS methodis that the method is equivalent, both mathematically and numerically, toHouseholder QR factorization of the padded matrixTounderstand this equivalence, consider the Householder QR factorization(18.19)Let q1 ,be the vectors obtained by applying the MGS method toA. Then it is easy to see thatand that the multiplication A 2 =carries out the first step of the MGSmethod on A, producing the first row of R andThe argument continues in the same way, and we find that(18.20)With the Householder–MGS connection established, we are ready to deriveerror bounds for the MGS method by making use of our existing error analysisfor the Householder method.Theorem 18.12.
Suppose the MGS method is applied ton, yielding computed matricesandconstants ci = ci (m, n) such thatof rankThen there are(18.21)(18.22)380QR F ACTORIZATIONand there exists an orthonormal matrix Q such that(18.23)Proof. To prove (18.21) we use the matrix form of the MGS method. Forthe computed matrices we haveExpanding this recurrence, we obtainHence(18.24)and a typical term has the form(18.25)where Sk-1 agrees within its first k – 1 rows and the identity in its lastn – k + 1 rows. Assume for simplicity that(this does not affect thefinal result).
We haveand Lemma 3.8 shows that thecomputed vector satisfieswhich impliesand, fromweUsing (18.24) and exploitinghavethe form of (18.25) we find, after a little working, thatprovided thatTo prove the last two parts of the theorem we exploit the Householder–MGS connection. By applying Theorem 18.4 to (18.19) we find that there isan orthogonalsuch that(18.26)with18.8 S ENSITIVITYOF THEQR FACTORIZATION381This does not directly yield (18.23), sinceis not orthonormal. However,it can be shown that if we define Q to be the nearest orthonormal matrixtoin the Frobenius norm, then (18.23) holds with c3 =(seeProblem 18.11).Now (18.21) and (18.23) yieldwhere c5 = c1and we have used (18.23) to boundThis boundimplies (18.22) with c2 = 2c5 (use the first inequality in Problem 18.13).We note that (18.22) can be strengthened by replacing κ 2 (A) in the boundby the minimum over positive diagonal matrices D of κ 2 (AD).
This followsfrom the observation that in the MGS method the computed Q is invariantunder scalings AAD, at least if D comprises powers of the machine base.As a check, note that the bound in (18.18) for the case n = 2 is independentof the column scaling, since sinTheorem 18.12 tells us three things. First, the computed QR factors fromthe MGS method have a small residual.
Second, the departure from orthonormality of Q is bounded by a multiple of κ 2 (A)u, so that Q is guaranteed to benearly orthonormal if A is well conditioned. Finally, R is the exact triangularQR factor of a matrix near to A in a componentwise sense, so it is as goodan R-factor as that produced by Householder QR factorization applied to A.In terms of the error analysis, the MGS method is weaker than HouseholderQR factorization only in that Q is not guaranteed to be nearly orthonormal.For the CGS method the residual bound (18.21) still holds, but no boundof the form (18.22) holds for n > 2 (see Problem 18.9).Here is a numerical example to illustrate the behaviour of the Gram–Schmidt methods. We take the 25 × 15 Vandermonde matrix A =where the pi are equally spaced on [0, 1].
The condition number κ 2 (A) =1.47 × 109. We haveBoth methods produce a small residual for the QR factorization. WhileCGS produces a Q showing no semblance of orthogonality, for MGS we have18.8. Sensitivity of the QR FactorizationHow do the QR factors of a matrix behave under small perturbations of thematrix? This question was first considered by Stewart [944, 1977]. He showed382QR F ACTORIZATIONthat ifhas rank n andare QR factorization, then, for sufficiently small ∆A,(18.27)(18.28)where cn is a constant. Here, and throughout this section, we use the “economy size” QR factorization with R a square matrix normalized to have nonnegative diagonal elements.
Similar normwise bounds are given by Stewart [951,1993] and Sun [971, 1991], and, for AQ only, by Bhatia and Mukherjea [95,1994] and Sun [975, 1995].Componentwise sensitivity analyses have been given by Zha [1126, 1993]and Sun [972, 1992], [973, 1992]. Zha’s bounds can be summarized as follows,with the same assumptions and notation as for Stewart’s result above. Let|∆A| <where G is nonnegative withThen, for sufficientlysmall(18.29)where c m,n is a constant depending on m and n.
The quantity φ(A) =cond(R –1) can therefore be thought of as a condition number for the QRfactorization under the columnwise class of perturbations considered. Notethat φ is independent of the column scaling of A.As application of these bounds, consider a computed QR factorizationAQR obtained via the Householder algorithm, where Q is the computedproduct of the computed Householder matrices. Theorem 18.4 shows that A+∆A =whereis orthogonal andwith ||G1 ||F = 1.Applying Lemma 18.3 to_ the computation ofwe have thatwherewith ||G2 ||F = 1. From the expressionwe have, on applying (18.29) to the firstterm,(18.30)To illustrate this analysis we describe an example of Zha.
Let18.9 N OTESANDR EFERENCES383whereis a parameter. It is easy to verify that A = QRA and B = QRBare QR factorization (the same Q in each case) whereWith= 10–8, the computed Q factors from MATLAB areandSince φ(A)2.8 × 108 and φ(B)3.8, the actual errors match the bound(18.30) very well. Note that κ 2 (A)2.8 × 108 and κ2 (B)2.1 × 108, sothe normwise perturbation bound (18.28) is not strong enough to predict thedifference in accuracy of the computed Q factors, unless we scale the factorout of the last column of B to leave a well-conditioned matrix.
The virtueof the componentwise analysis is that it does not require a judicious scalingin order to yield useful results.18.9. Notes and ReferencesThe earliest appearance of Householder matrices is in the book by Turnbulland Aitken [1029, 1932, pp. 102–105]. These authors show that if ||x||2 = ||y||2then a unitary matrix of the form R = azz* – I (in their notation)can be constructed so that Rx = y.
They use this result to prove the existenceof the Schur decomposition. The first systematic use of Householder matricesfor computational purposes was by Householder [586, 1958], who used themto construct the QR factorization. Householder’s motivation was to computethe QR factorization with less arithmetic operations (in particular, less squareroots) than are required by the use of Givens rotations.In the construction of §18.1 for a Householder matrix P such that Px =σe 1, the other choice of sign, sign(σ) = sign(x1), can be used, provided thatυ 1 is formed in a numerically stable way.
The appropriate formula is derivedas follows [264, 1976], [819, 1971], [820, 1980, p. 91]:A detailed analysis of different algorithms for constructing P such that Px =σe 1 is given by Parlett [819, 1971].384QR F ACTORIZATIONTsao [1023, 1975] describes an alternative way to form the product of aHouseholder matrix with a vector and gives an error analysis.
There is nomajor advantage over the usual approach.As for Householder matrices, normwise error analysis for Givens rotations was given by Wilkinson [1087, 1963], [1089, 1965, pp. 131–139]. Wilkinson analysed QR factorization by Givens rotations for square matrices [1089,1965, pp. 240-241], and his analysis was extended to rectangular matrices byGentleman [435, 1973].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
