Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 27
Текст из файла (страница 27)
He shows that an appropriately definedcondition number for the Newton form of interpolating polynomial grows at aslower than exponential rate in the degree n for Leja points, which are points114POLYNOMIALStaken from a given compact set that satisfy the condition (5.13). For moreon the numerical benefits of the Leja ordering see §21.3.3.If a polynomial is to be evaluated many times at different, arguments itmay be worthwhile to expend some effort transforming it to a form that canbe evaluated more cheaply than by a straightforward application of Horner’srule. For example, the quarticp(x) = a 4 x4 + a 3 x3 + a 2 x2 + a 1 x + a 0 ,can be rewritten as [668,1981,a40,p.
471]p(x) = (( y + x + a2 ) y + a 3 )a4 ,y = (x + a 0 )x + a 1 ,where the coefficients ai are given by.Once the ai have been computed, p(x ) can he evaluated in three multiplications and five additions, as compared with the four multiplications and fouradditions required by Horner’s rule. If a multiplication takes longer than anaddition, the transformed polynomial should be cheaper to evaluate.
For polynomials of degree n > 4 there exist evaluation schemes that require strictlyless than the 2n total additions and multiplications required by Horner’s rule;see Knuth [665, 196 2], [668, 198 1, pp. 471-475] and Fike [373, 196 7] Oneapplication in which such schemes have been used is in evaluating polynomialapproximations in an elementary function library [412, 1991]. Little seems tobe known about the numerical stability of fast polynomial evaluation schemes;see Problem 5.6.Problems5.1. Give an alternative derivation of Algorithm 5.2 by differentiating theHorner recurrence and rescaling the iterates.5.2.
Give an error analysis for the following “beginner’s” algorithm for evaluating p(x) = a 0 + a1 x + . . . + anxn :q (x) = a 0; y = 1for i = 1:ny = xyq(x) = q(x) + ai yendp(x) = q(x )PROBLEMS1155.3. Let p(x) = a 0 + a 1 x + . . . + anxn and n = 2 m. Thenp(x) = (a 0 + a 2 x2 + . . . + a 2 m x2 m ) + (a 1 x + a 3 x3 + . . . + a 2 m - 1 x2 m - 1 )= a0 + a 2 y + . . . + a2 mym + x(a 1 + a3 y + .
. . + a 2 m - 1 y m- 1 ),where y = x2. Obtain an error bound for fl(p(x)) when p is evaluated usingthis splitting (using Horner’s rule on each part).5.4. Write down an algorithm for computing the Leja ordering (5.13) in n 2flops.5.5. If the polynomial p(x) =has roots x1,. . . , xn , it can be evaluated from the root product form p(x) =Give an erroranalysis for this evaluation.5.6. (RESEARCH PROBLEM) Investigate the numerical stability of fast polynomial evaluation schemes (see the Notes and References) by both roundingerror analysis and numerical experiments.
For a brief empirical study seeMiller [757, 1975, §10].Previous Home NextChapter 6NormsWhile it is true that all norms are equivalent theoretically,on/y a homely one like the -norm is truly useful numerically.-J. H. WILKINSON 12, Lecture at Stanford University (1984)Matrix norms are defined in many different ways in the older literature,but the favorite was the Euclidean norm of the matrixconsidered as a vector in n 2-space.Wedderburn (1934) calls this the absolute value of the matrixand traces the idea back to Peano in 1887.-ALSTON S. HOUSEHOLDER,The Theory of Matrices in Numerical Analysis (1964)12Quoted in Fox [403,19 8 7 ].117118NORMSNorms are an indispensable tool in numerical linear algebra.
Their ability tocompress the mn numbers in an m × n matrix into a single scalar measure ofsize enables perturbation results and rounding error analyses to be expressedin a concise and easily interpreted form. In problems that are badly scaled,or contain a structure such as sparsity, it is often better to measure matricesand vectors componentwise.
But norms remain a valuable instrument for theerror analyst, and in this chapter we describe some of their most useful andinteresting properties.6.1. Vector NormsA vector norm is a function ||·|| :IR satisfying the following conditions:1. ||x|| > 0 with equality iff x = 0.2. ||ax|| = |a| ||x|| for all3. ||x+y|| < ||x|| + ||y|| for all x, y(the triangle inequality).The three most useful norms in error analysis and in numerical computation are“Manhattan“ or “taxi cab” norm,(x*x)½.Euclidean length,These are all special cases of the Holder y-norm:The 2-norm has two properties that make it particularly useful for theoretical purposes.
First, it is invariant under unitary transformations, for ifQ*Q = I, then= x*Q*Qx = x*x =Second, the 2-norm isdifferentiable for all x, with gradient vector ||x||2 = x/||x||2.A fundamental inequality for vectors is the Hölder inequality (see, forexample, [502, 1967, App. 1])|x*y| < ||x||p ||y||q ,(6.1)1196.1 V ECTOR N ORMSThis is an equality when p,dependent and xi yi lies onis also possible when p =with p = q = 2 is calledq > 1 if the vectors (|x i |p ) and (|y i |q ) are linearlythe same ray in the complex plane for all i; equality1 and p = , as is easily verified.
The special casethe Cauchy-Schwarz inequality:|x*y| < ||x||2 ||y||2.For an arbitrary vector norm ||·|| the dual norm is defined by(6.2)It follows from the Hölder inequality that the dual of the p -norm is the q-norm,where p- 1 +q -1 = 1. The definition of dual norm yields, trivially, the generalHölder inequality |x*y| < ||x|| ||y||D . For a proof of the reassuring result thatthe dual of the dual norm is the original norm (the “duality theorem”) seeHorn and Johnson [580, 1985, Thm. 5.5.14].In some analyses we need the vector z dual to y, which is defined by theproperty(6.3)z*y = ||z||D ||y || = 1.That such a vector z exists is a consequence of the duality theorem (see [580,1985, Cor.
5.5.15]).How much two p-norms of a vector can differ is shown by the attainableinequalities [422, 1983, pp. 27-28], [459, 1983, Lem. 1.1](6.4)The p-norms have the properties that ||x|| depends only on the absolutevalue of x, and the norm is an increasing function of the absolute values of theentries of x. These properties are important enough to warrant a definition.Definition 6.1.
A norm on1. monotone if |x| < |y|is||x|| < ||y|| for all x, yand2. absolute if || |x| || = ||x|| for all xThe following nonobvious theorem shows that these two properties areequivalent.Theorem 6.2 (Bauer, Stoer, and Witzgall). A norm onand only if it is absolute.Proof. See Horn and Johnson [580,Sun [954, 1990, Thm. 2.1.3].19 8 5 ,is monotone ifThm. 5.5.10], or Stewart and120NORMS6.2. Matrix NormsA matrix norm is a function ||·|| :IR satisfying obvious analoguesof the three vector norm properties.
The simplest example is the Frobeniusnorm.(which is sometimes called the Euclidean norm and denoted ||·||E ).A very important class of matrix norms are those subordinate to vectornorms. Given a vector norm onthe corresponding subordinate matrixnorm onis defined by(6.5)or, equivalently,(Strictly speaking, this definition uses two different norms: one onin thenumerator of (6.5) and one onin the denominator. Thus the norm usedin the definition is assumed to form a family defined onfor any s.)For the l-, 2-, and-vector norms it can be shown thatwhere the spectral radiusand where σm a x (A) denotes the largest singular value of A. To rememberthe formulae for the 1- and -norms, note that 1 is a vertical symbol (forcolumns) andis a horizontal symbol (for rows).A norm is consistent if it satisfies ||AB|| < ||A|| ||B|| whenever the product AB is defined.
The Frobenius norm and all subordinate norms are consistent. An example of a norm that is not consistent is the “max norm”||A|| = maxi , j |a ij |. The best bound that holds for all AandBis ||AB|| < n||A|| ||B||, with equality when aij1 and bij 1.1216.2 MATRIX NORMSTable 6.1. Constants apq such that ||x||p < apq||x||q, xA norm for which ||UAV|| = ||A || for all unitary U and V is called aunitarily invariant norm. These norms have an interesting theory, which wewill not explore here (see [581, 1991, §3.5] or [954, 1990, §2.3]).
Only twounitarily invariant norms will be needed for our analysis: the 2-norm andthe Frobenius norm. That these two norms are unitarily invariant followseasily from the formulae above. For any unitarily invariant norm, the usefulproperty holds that ||A*|| = ||A||. The 2-norm satisfies the additional relation||A*A||2 = ||A|| .The unitary invariance of the 2- and Frobenius norms has implications forerror analysis, for it means that multiplication by unitary matrices does notmagnify errors.
For example, if Ais contaminated by errors E andQ is unitary, thenQ(A+E)Q* = QAQ*+F,and ||F||2 = ||QEQ*||2 = ||E||2. In contrast, if we do a general, nonsingularsimilarity transformationX(A+E)X -1 = XAX- 1 +G,then ||G||2 = ||XEX-1||2 < κ 2 (X)||E||2, where κ(X) = ||X|| ||X -1|| is thecondition number of X. The condition number satisfies κ(X) > 1 (κF (X) >and can be arbitrarily large.In perturbation theory and error analysis it is often necessary to switchbetween norms.
Therefore inequalities that bound one norm in terms of another are required. It is well known that on a finite-dimensional space anytwo norms differ by at most a constant that depends only on the dimension(so-called norm equivalence). Tables 6.1 and 6.2 give attainable inequalitiesfor the vector and matrix norms of most interest.The definition of subordinate matrix norm can be generalized by permitting different norms on the input and output space:(6.6)122Table 6.2. Constants apq such that ||A||p < apg||A||q, Amax i,j |aij| and ||A||s :=NORMSHere, ||A||M :=Note that, in general, the submultiplicative property ||AB||a, β < ||A||a,β||B||a, βdoes not hold.
but we do have(6.7)for any third vector norm ||·||γ. The choice a = 1 and β =produces themax norm, mentioned above, ||A||1,= maxi , j |a ij |.At least two important results about matrix norms hold for this mixedsubordinate norm. The first is a simple formula for the matrix conditionnumber of a nonsingular Adefined byNote that this definition uses the ||·||a,β norm on the data space and the||·||β,a norm on the solution space, as is natural.We need the following lemma.Lemma 6.3. Given vector norms ||·||a and ||·||β and vectors x, ysuchthat ||x||a = ||y||β = 1, there exists a matrix B with ||B||a,β = 1 such thatBx = y.Proof.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
