Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 3
Текст из файла (страница 3)
. . . . . . . . . . .26.3 “Randsvd” Matrices . . . . . . . . . . . . . . . . . . . . . . . .26.4 The Pascal Matrix . . . . . . . . . . . . . . . . . . . . . . . . .26.5 Tridiagonal Toeplitz Matrices . . . . . . . . . . . . . . . . . .26.6 Companion Matrices . . . . . . . . . . . . . . . . . . .
. . . .26.7 Notes and References . . . . . . . . . . . . . . . . . . . . . . .26.7.1 LAPACK . . . . . . . . . . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .513514517519520524525526527527A Solutions to Problems52925.525.625.7579B S i n g u l a r V a l u e D e c o m p o s i t i o n , M-MatricesB.1 Singular Value Decomposition . . . . . .
. . . . . . . . . . . . 580B.2 M-Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580C Acquiring SoftwareC.1 Internet. . . . . .C.2 Netlib . . . . . . .C.3 MATLAB . . . . .C.4 NAG Library and. . . .. . . .. . . .FTN90. . . . . . .
. . . . . . . .. . . . . . . . . . . . . . .. . . . . . . . . . . . . .Compiler . . . . . . . . .D Program LibrariesD.1 Basic Linear Algebra SubprogramsD.2 EISPACK . . . . . . . . . . . . . .D.3 LINPACK . . . . . . . . . . . . . .D.3 LAPACK . . . . . . . . . . . . . . .D.4.1 Structure of LAPACK . . .E The Test Matrix Toolbox.............................................................581582582583583........... . .
.. . . .. . . .. . . .. . . .585586587587587588........591xvBibliography595Name Index665Subject Index675List of Figures1.11.21.31.41.51.62.14.14.2Backward and forward errors for y =. . . . . . . . . . . .Mixed forward-backward error for y =. . . .
. . . . . . .Forward errorsand relative residuals ||bversus precision. . . . . . . . . . . . . . .Absolute error versus precision, t = -log2 u . . . . . . . . . . .Relative errors ||Ak -Âk ||2/||A||2 for Givens QR factorization.Values of rational functioncomputed by Horner’s rule. .
.20212529Relative distance fromto the next larger machine number(β=2, t =24), displaying wobbling precision. . . . . . . . . . .44Recovering the rounding error. . . . . . . . . . . . . . . . . . .Errorsfor Euler’s method with and without compensated summation. . . . . . . . . . . .
. . . . . . . . . . . . .8992965.1Computed polynomial values and running and a priori boundsfor Horner’s method. . . . . . . . . . . . . . . . . . . . . . . . . 1076.1Plots of p versus ||A||p, for 1 < p < 15. . . . . . . . . . . . . . . 1259.1A banded matrix. . . . . . . . . . . . . . . . . . . . .
. . . . . . 18213.1 Residuals for inverses computed by MATLAB'S INV function. . . 26414.1 Underestimation ratio for Algorithm 14.4 for 5×5 matrix A( θ). 29716.1 Forward and backward errors for SOR iteration.17.117.217.317.417.517.6. . . . . . . . 327A typical hump for a convergent, nonnormal matrix.Diverging powers of a nilpotent matrix, C1 4 . . .
. .Infinity norms of powers of 2 × 2 matrix J in (17.2).Computed powers of chebspec matrices. . . . . . . .Pseudospectra for chebspec matrices. . . . . . . . .Pseudospectrum for SOR iteration matrix. . . . . . .xvii. . . . . .. . . . . .. . . . . .. . . . . .. . . . . .. . . . . .347347349356357359XV111LIST OF FIGURES. . . . . . . . . . . .
. . 36318.1 Householder matrix P times vector. . . . . . . . . . . . . . . . . . 37218.2 Givens rotation, y = G(i,j,θ)22.1 Exponent versus time for matrix multiplication. . . . . . . . . . 44922.2 Errors for Strassen’s method with two random matrices of dimension n = 1024. . . .
. . . . . . . . . . . . . . . . . . . . . . 45723.1 Error in FFT followed by inverse FFT. . . . . . . . . . . . . . . 46824.1 The possible steps in one iteration of the MDS method whenn=2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47825.1 Rational function r .
. . . . . . . . . . . . . . . . . . . . . . . 49325.2 Error in evaluating rational function r . . . . . . . . . . . . . . 49426.1 spy(rem(pascal(32),2)). . . . . . . . . . . . . . . . . . . . . 52426.2 Pseudospectra of compan(A). . . . . .
. . . . . . . . . . . , . . 52626.3 Pseudospectra of 32 × 32 pentadiagonal Toeplitz matrices. . . . 528List of Tables1.1 Computed approximations= ƒl((1+1/n) n ) to e = 2.71828 . . . . 161.2 Computed values offrom Algorithms 1 and 2. . . . 231.3 Results from GE without pivoting on an upper Hessenberg mat r i x . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.12.22.32.42.5Floating point arithmetic parameters. . . . . .IEEE arithmetic exceptions and default results.Test arithmetics. . . . . . . . . . . . . . . . . .Sine test. . . . . . . . . . . . . . . . . . . .
. .Exponentation test. . . . . . . . . . . . . . . .4.1Mean square errors for nonnegative6.16.2Constants αp q such thatConstants αpq such that7.1Backward and forward stability. . . . . . . . . . . . . . . . . . . 1439.19.2Times for solution of a linear system of order n . . . . . . .
. . 189Records for largest dense linear systems solved. . . . . . . . . . 199.............................................4146545555. . . . . . . . . . . . . .99. . . . . . . . 121. . . . . 12211.1 ω|A|,|b| values for A = orthog(25).. . . . . . . . . . . . .
. . . 24011.2 ω|A|,|b| values for A = clement(50) . . . . . . . . . . . . . . . . . 24111.3 ω|A|,|b| values for A = gfpp(50) . . . . . . . . . . . . . . . . . . . 24112.1 Stability of block and point LU factorization. . . . . . . . . . . 25613.113.213.313.413.513.6Backward errorsfor the -norm. . . . . . . . . .
. . .Mflop rates for inverting a triangular matrix on a Cray 2. . . .Mflop rates for inverting a full matrix on a Cray 2. . . . . . . .Times (minutes and seconds) for inverting an n × n matrix. . .Additional timings for inverting an n × n matrix. . . . . . . . .Gauss-Jordan elimination for U =6. . . .
. . . . . . . . . . .16.1 Dates of publication of selected iterative methods.xix262270275276276279. . . . . . . 326LIST OF TABLES16.2 Result for Jacobi method, α = ½-8 -j . . . . . . . . . . . . . 33316.3 Results for Jacobi method, a = -(½-8 -j ). . . . . . . . . . . 33319.1 LS backward errors and residual for Vandermonde system. . .
. 40520.1 Backward errors for underdetermined Vandermonde system. . . 42221.1 Bounds and estimates for. . . . . . . . . . . . . . . . 42821.2 Parameters in the three-term recurrence (21.6). . . . . . . . . . 43321.3 Results for dual Chebyshev-Vandermonde-like system. . . . . . 43825.1 Results from Cholesky factorization. . . . .
. . . . . . . . . . . 49625.2 Effect of extended run time on Patriot missile operation. . . . . 50726.1 Condition numbers of Hilbert and Pascal matrices. . . . . . . . 516PrefaceIt has been 30 years since the publication of Wilkinson’s books Rounding Errors in Algebraic Processes [1088, 1963] and The Algebraic Eigenvalue Problem [1089, 1965]. These books provided the first thorough analysis of theeffects of rounding errors on numerical algorithms, and they rapidly becamehighly influential classics in numerical analysis.
Although a number of morerecent books have included analysis of rounding errors, none has treated thesubject in the same depth as Wilkinson.This book gives a thorough, up-to-date treatment of the behaviour ofnumerical algorithms in finite precision arithmetic. It combines algorithmicderivations, perturbation theory, and rounding error analysis. Software practicalities are emphasized throughout, with particular reference to LAPACK.The best available error bounds, some of them new, are presented in a unifiedformat with a minimum of jargon. Historical perspective is given to provide insight into the development of the subject, and further information isprovided in the many quotations. Perturbation theory is treated in detail,because of its central role in revealing problem sensitivity and providing errorbounds.
The book is unique in that algorithmic derivations and motivationare given succinctly, and implementation details minimized, so that attention can be concentrated on accuracy and stability results. The book wasdesigned to be a comprehensive reference and contains extensive citations tothe research literature.Although the book’s main audience is specialists in numerical analysis, itwill be of use to all computational scientists and engineers who are concernedabout the accuracy of their results.
Much of the book can be understood withonly a basic grounding in numerical analysis and linear algebra.This first two chapters are very general. Chapter 1 describes fundamentalconcepts of finite precision arithmetic, giving many examples for illustrationand dispelling some misconceptions. Chapter 2 gives a thorough treatment offloating point arithmetic and may well be the single most useful chapter in thebook. In addition to describing models of floating point arithmetic and theIEEE standard, it explains how to exploit “low-level” features not representedin the models and contains a large set of informative exercises.In the rest of the book the focus is, inevitably, on numerical linear algebra,because it is in this area that rounding errors are most influential and havexxixxiiPREFACEbeen most extensively studied. However, I found that it was impossible tocover the whole of numerical linear algebra in a single volume.
The mainomission is the area of eigenvalue and singular value computations, whichis still the subject of intensive research and requires a book of its own tosummarize algorithms, perturbation theory, and error analysis. This book istherefore certainly not a replacement for The Algebraic Eigenvalue Problem.Two reasons why rounding error analysis can be hard to understand arethat, first, there is no standard notation and, second, error analyses are oftencluttered with re-derivations of standard results.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
