Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 28
Текст из файла (страница 28)
Recall that the dual of the a-norm is definedmax||w ||a= 1 |z*w|. Let z be a vector dual to x, so that z*x =and henceLet B = yz*. Then Bx = y andas required.by1236.2 M A T R I X N O R M STheorem 6.4. For nonsingular Aκa , β (A) satisfiesthe matrix condition numberκa ,β (A) = ||A||a , β ||A -1 || β , a .(6.8)Proof. In view of the expansion(A+ ∆A) - 1 - A- 1 = - A- 1 ∆AA - 1 + O(||∆A|| 2 ),the result is proved if we can show that(6.9)That (6.9) holds with the equality replaced by “<” follows from two applications of (6.7).
To show the opposite inequality, we have(6.10)where, for the lower bound, we have chosen y so that ||A - 1 y||a = ||A- 1 ||β , a ,and where A- 1 y=||A - 1 ||β ,ax with ||x||a = 1. Now, from Lemma 6.3, thereexists a matrix AA with ||∆ A|| a ,β = 1 such that ∆Ax = y. In (6.10) thisgivesas required.The next result concerns the relative distance to singularity for a matrixIt states that the relative distance to singularity is the reciprocal of the condition number.Theorem 6.5 (Gastinel, Kahan). For nonsingulardista ,β (A)=(||A||a ,β ||A -1 || β , a )-1=we haveκa ,β (A) - 1 .Proof.
If A + ∆A is singular, then there exists x∆A)x = 0. Hencegiving0 such that ( A +124NORMSTo show that a suitable perturbation achieves this lower bound, let y besuch that ||y||β = 1 and ||A - 1 y||a = ||A -1 ||β , a , and write x = A- 1 y. ByLemma 6.3 there exists B with ||B ||a ,β = 1 such that Bx/||x||a = -y. Letting∆A = B/||x||a we have ||∆A||a ,β /||A||a ,β = κa ,β (A)-1. and A+∆A is singularbecause (A + ∆A)A - 1 y = 0.6 . 3 .
T h e M a t r i x p-NormThe matrix p-norm is the norm subordinate to the Hölder p-norm:(6.11). For other values of p, howFormulae for ||A||p are known only for p = 1, 2,to estimate or compute ||A||p is an interesting problem, the study of which,as well as being interesting in its own right, yields insight into the propertiesof the 1, 2, andnorms.By taking x = ej in (6.11). using (6.4).
and using (6.21) below, we canderive the bounds, for(6.12)(6.13)Matrix norms can be compared using the following elegant result of Schneider and Strang [900, 1962] (see also [580, 1985, Thm. 5.6.18]): if ||·|| a and ||·||βdenote two vector norms and the corresponding subordinate matrix norms,then for(6.14)From (6.4) and (6.14), we have, when m = n ,(6.15)Note that, unlike for vectors, p 1 < p 2 does not imply ||A||p 1 > ||A||p 2. Theresult (6.15) implies, for example, that for all p > 1(6.16)(6.17)1256.3 THE MATRIX p- N O R MFigure 6.1.
Plots of p versus ||A||p, for 1 < p < 15. Fourth plot shows 1/ p versuslog ||A||p for the matrices in the first three plots.Upper bounds for ||A||p that do not involve m or n can be obtained fromthe interesting property that log ||A||p is a convex function of 1/p for p > 1(see Figure 6.1), which is a consequence of the Riesz-Thorin theorem [503,1952, pp.
214, 219], [450, 1991]. The convexity implies that if f(a) = ||A||1 / a ,then for 0 < a,β < 1,logf(θ a + (1 - θ)β) < θ logf(a) + ( 1 - θ1) logf(β),0 < θ < l.Writing p 1 = 1/a and p 2 = 1/β, this inequality can be expressed as(6.18)Two interesting special cases are(6.19)and(6.20)Note that (6.19) includes the well-known inequalityNORMS126Two further results that are familiar for p = 1, 2,are(6.21)(see, for example, [580,1985,Thm.
5.6.36]) andThe bounds (6.16) and (6.17) imply that given the ability to compute||A||1, ||A||2 and ||A||we can estimate ||A||p correct to within a factor n 1 / 4 .These a priori estimates are at their best when p is close to 1, 2, orbut ingeneral they will not provide even one correct significant digit. The bound in(6.18) can be much smaller than the other upper bounds given above, but howtight it is depends on how nearly log ||A||p is linear in p . Numerical methodsare needed to obtain better estimates: these are developed in chapter 14.6.4. Notes and ReferencesThe matrix condition number appears to have been first introduced explicitlyby Turing [1027, 1948], who defined, for example, the N-condition numberof AIRn×x as n -1 N(A)N(A -1), where N(·) is Turing’s notation for theFrobenius norm.
Todd [1003, 1968] gives a short survey of the matrix condition number with many references.Theorem 6.2 was originally proved by Bauer, Stoer, and Witzgall, in apaper that contains many interesting results on monotonic norms [84, 1961].Tables of constants in inequalities between different norms have been givenby various authors: see, for example, Stone [957, 1962] and Zielke [1129, 1988].Our development of the mixed subordinate norm ||·|| a ,β is based on thatof D. J. Higham [526, 1995].Theorem 6.5 is proved by Kahan [626, 1966, pp. 775 776], who attributesit to Gastinel but gives no reference.
For the 2-norm, this result goes backto a paper by Eckart and Young [334, 1936]. Theorem 6.5 is an instanceof a relationship that holds for many problems: the condition number is thereciprocal of the distance to the nearest singular problem (one with an infinitecondition number). This relationship applies to matrix inversion, eigenvalueand eigenvector computation, polynomial zero-finding, and pole assignmentin linear control systems.
For an in-depth study see Demmel [281, 1987].Direct proofs of inequality (6.19) can be found in Kato [646, 1976, p. 29]and Todd [1006, 1977, pp. 25-26]. The inequality does not seem to be wellknown.For historical comments on the development of norms in numerical analysis, see Householder [587, 1964, Chap. 2] and Stewart and Sun [954, 1990,Chap. 2].127PROBLEMSProblemsProblems worthyof attackprove their worthby hitting back.-PIET HEIN, Grooks (1966)6.1. Prove the inequalities given in Tables 6.1 and 6.2. Show that eachinequality in Table 6.2 (except the one for aS,2) is attainable for a matrix of theform A = xyT, where x, y{e, ej}, where e = [1, 1,. . .
, 1]T. Show that equality in ||A||s < as,2 ||A||2 is attained for square real matrices A iff A is a scalarmultiple of a Hadamard matrix (see §9.3 for the definition of a Hadamardmatrix), and for square complex matrices if a rs = exp(2 πi(r - 1)(s - 1)/n)(this is a Vandermonde matrix based on the roots of unity).6.2. Let x, y||x|| ||y||D .Show that, for any subordinate matrix norm, ||xy*|| =6.3.
Show that a subordinate matrix norm ||·|| onsatisfiesFrom ancient times until now thestudy of magic squares has flourished as a kind of cult,often with occult trappings, whose initiates range fromsuch eminent mathematicians as Arthur Cayley and Oswald Veblento laymen such as Benjamin Franklin.-MARTIN GARDNER, More Mathematical Puzzles and Diversions (1961)6.4. Let Mndenote a magic square matrix, that is, an n × n matrixcontaining the integers from 1 to n 2 arranged in such a way that the row andcolumn sums are all the same. Let µ n , denote the magic sum of Mn (thus,µn = n(n2 + 1)/2). Show that ||Mn||p = µ n for all 1 < p <(This resultis a special case of an apparently little-known result of Stoer and Witzgall,which states that the norm of a doubly stochastic matrix is 1 for any normsubordinate to a permutation-invariant absolute vector norm [956, 1962].)6.5.
Show that ||ABC||F < ||A||2 ||B||F||C|| 2 for any A, B, and C such thatthe product is defined. (This result remains true when the Frobenius norm isreplaced by any unitarily invariant norm [581, 1991, p. 211].)NORMS1286.6. Show that for any nonsingular6.7. Show that for anyand any consistent matrix norm, p(A) <||A||, where p is the spectral radius.6.8. Show that for anyand δ > 0 there is a consistent norm ||·||(which depends on A and δ) such that ||A|| < p(A) + δ, where p is the spectralradius.
Hence show that if p (A) < 1 then there is a consistent norm ||·|| suchthat ||A|| < 1.6.9. LetUse the SVD to find expressions for ||A||2 and ||A||Fin terms of the singular values of A. Hence obtain a bound of the formc1 ||A|| 2 < ||A|| F < c2 ||A|| 2, where c 1 and c2 are constants that depend on n.When is there equality in the upper bound? When is there equality in thelower bound?6.10. Show thatDeduce that when ||F||2 = 1, the norm is6.11. Let||A||a,= maxi6.12. (Tao [994,(Rohn [879,1995]the golden ratio.Prove that (a) ||A||1 , β = maxj||A (i,:)||What is ||A||1 , ?1984])||A (:,j)||β , and (b)Show that if A is Hermitian positive definite thenshows that the problem of computing ||A|| ,1 is NP-hard.)6.13.
Prove that if HIRn×n is a Hadamard matrix then||H|| p = max{n1 /p ,n1 - 1 /p }.(See §9.3 for the definition of a Hadamard matrix.)6.14. Show that if AIRm×n has at most µ nonzeros per row then(6.22)129PROBLEMSwhile if A has at most µ nonzeros per column then(6.23)where p -1 + q-1 = 1. (These inequalities generalize (6.12) and (6.13).)6.15. Show that if Athen for any p-norm (1 < p <6.16. Define the function v :Is v a vector norm onIR byDerive an explicit expression for),PreviousChapter 7Perturbation Theory for LinearSystemsOur hero is the intrepid, yet sensitive matrix A.Our villain is E, who keeps perturbing A.When A is perturbed he puts on a crumpled hat: Ã = A + E.-G. W. STEWART and JI-GUANG SUN, Matrix Perturbation Theory (1990)The expression ‘ill-conditioned’ is sometimes used merely as aterm of abuse applicable to matrices or equations .
. .It is characteristic of ill-conditioned sets of equations thatsmall percentage errors in the coefficients given may lead tolarge percentage errors in the solution.-A. M. TURING, Rounding-Off Errors in Matrix Processes (1948)131HomeNext132P ERTURBATION T HEORYFORLINEAR S YSTEMSIn this chapter we are concerned with a linear system Ax = b , where AIRn × n . In the context of uncertain data or inexact arithmetic there are threeimport ant quest ions:(1) How much does x change if we perturb A and b ; that is, how sensitiveis the solution to perturbations in the data?(2) How much do we have to perturb the data A and b for an approximatesolution y to be the exact solution of the perturbed system-in other words,what is the backward error of y?(3) What bound should we compute in practice for the forward error of agiven approximate solution?To answer these questions we need both normwise and componentwiseperturbation theory.7.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
