Higham - Accuracy and Stability of Numerical Algorithms (523152)
Текст из файла
Home NextAccuracy and Stabilityof Numerical AlgorithmsNicholas J. HighamUniversity of ManchesterManchester, EnglandAccuracy and Stabilityof Numerical AlgorithmsSociety for Industrial and Applied MathematicsPhiladelphiaCopyright © 1996 by the Society for Industrial and Applied Mathematics.1098765432All rights reserved. Printed in the United States of America.
No part of this book may bereproduced, stored, or transmitted in any manner without the written permission of thepublisher. For information. write to the Society for Industrial and Applied Mathematics,3600 University City Science Center, Philadelphia, PA 19104-2688.Library of Congress Cataloging-in-Publication DataHigham, Nicholas J., 1961Accuracy and stability of numerical algorithms / Nicholas J.Higham.p. cm.Includes bibliographical references (p. - ) and index.ISBN O-8987 l-355-2 (pbk.)1. Numerical analysis--Data processing.
2. Computer algorithms.I. Title.QA297.H53 19965 19.4’0285’5 1 --dc2095-39903o is a registered trademark.Dedicated toAlan M. TuringandJames H. WilkinsonContentsList of FiguresxviiList of TablesxixPrefacexxixxviiAbout the Dedication1 Principles of Finite Precision Computation1.1 Notation and Background . . . . . . . . . . . . .
. . . . . . .1.2 Relative Error and Significant Digits . . . . . . . . . . . . . .1.3 Sources of Errors . . . . . . . . . . . . . . . . . . . . . . . . .1.4 Precision Versus Accuracy . . . . . . . . . . . . . . . . . . . .1.5 Backward and Forward Errors .
. . . . . . . . . . . . . . . . .1.6 Conditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.7 Cancellation . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.8 Solving a Quadratic Equation . . . . . . . . . . . . . . . . . .1.9 Computing the Sample Variance . . . . . . . .
. . . . . . . . .1.10 Solving Linear Equations . . . . . . . . . . . . . . . . . . . . .1.10.1 GEPP Versus Cramer’s Rule . . . . . . . . . . . . . . .1.11 Accumulation of Rounding Errors . . . . . . . . . . . . . . . .1.12 Instability Without Cancellation . .
. . . . . . . . . . . . . . .1.12.1 The Need for Pivoting . . . . . . . . . . . . . . . . . .1.12.2 An Innocuous Calculation? . . . . . . . . . . . . . . . .1.12.3 An Infinite Sum . . . . . . . . . . . . . . . . . . . . . .1.13 Increasing the Precision .
. . . . . . . . . . . . . . . . . . . . .1.14 Cancellation of Rounding Errors . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .1.14.1 Computing1.14.2 QR Factorization . . . . . . . . . . . . . . . . . . . . .1.15 Rounding Errors Can Be Beneficial . . .
. . . . . . . . . . . .1.16 Stability of an Algorithm Depends on the Problem . . . . . .1.17 Rounding Errors Are Not Random . . . . . . . . . . . . . . .1.18 Designing St able Algorithms . . . . . . . . . . . . . . . . . . .1.19 Misconceptions . . . . . . . . . . . . . . . . . . . . . . . . . .vii124577910111213141617171718192122242627293031V1111.20 Rounding Errors in Numerical Analysis . .
. . . . . . . . . . .1.21 Notes and References . . . . . . . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .323236392 Floating Point ArithmeticFloating Point Number System . . . . . . . . . . . . . . . . . 402.1Model of Arithmetic .
. . . . . . . . . . . . . . . . . . . . . . . 442.2IEEE Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 452.32.4Aberrant Arithmetics . . . . . . . . . . . . . . . . . . . . . . . 48Choice of Base and Distribution of Numbers . . . . . . . . . . 512.5Statistical Distribution of Rounding Errors . . . . . . . . . . . 522.653Alternative Number Systems . .
. . . . . . . . . . . . . . . . .2.7Accuracy Tests . . . . . . . . . . . . . . . . . . . . . . . . . . 542.8Notes and References . . . . . . . . . . . . . . . . . . . . . . . 562.9Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623BasicsInner and Outer Products . . .3.1The Purpose of Rounding Error3.2Running Error Analysis .
. . . .3.3Notation for Error Analysis . .3.4Matrix Multiplication . . . . . .3.5Complex Arithmetic . . . . . . .3.6Miscellany . . . . . . . . . . . .3.7Error Analysis Demystified . . .3.8Other Approaches . . . . . . . .3.93.10 Notes and References . . . . . .Problems . . . . . . . .
. . . . .. . . . .Analysis. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .4 Summation4.1Summation Methods . . . . . . .Error Analysis . . . . . . . . . . .4.2Compensated Summation . . . . .4.3Other Summation Methods . . . .4.4Statistical Estimates of Accuracy4.5Choice of Method . . . .
. . . . .4.6Notes and References . . . . . . .4.7Problems . . . . . . . . . . . . . .......................................................67. 68. 71. 72. 73. 76. 78. 80. 82. 83. 84. 84...................................................................................................................................................................87. . . . 88. . . . 89. .
. . 92. . . . 97. . . . 98. . . . 98. . . . 100. . . . 1001035 PolynomialsHorner‘s Method . . . . . . . . . . . . . . . . . . . . . . . . . 1045.1Evaluating Derivatives . . . . . . . . . . . . . . . . . . . . . . 1065.2The Newton Form and Polynomial Interpolation . . . , .
. . . 1095.3ix5.4Notes and References . . . . . . . . . . . . . . . . . . . . . . . 113Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114. . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. . . .
. . . . . . . . . . .1171181201241261277 Perturbation Theory for Linear SystemsNormwise Analysis . . . . . . . . . . . . . . . . . . . . . . . .7.17.2Componentwise Analysis . . . . . . . . . . . . . . . . . . . . .7.3Scaling to Minimize the Condition Number . . . . . . . . . . .7.4The Matrix Inverse . . . . . . .
. . . . . . . . . . . . . . . . .7.5Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.6Numerical Stability . . . . . . . . . . . . . . . . . . . . . . . .7.7Practical Error Bounds . . . . . . . . . . . . . . . . . . . . . .7.8Perturbation Theory by Calculus . . . .
. . . . . . . . . . . .Notes and References . . . . . . . . . . . . . . . . . . . . . . .7.9Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1311321341371401401411421441451478 Triangular Systems8.1Backward Error Analysis . .8.2Forward Error Analysis .
. .Bounds for the Inverse . . .8.38.4A Parallel Fan-In Algorithm8.5Notes and References . . . .8.5.1 LAPACK . . . . . . .Problems . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .151152155159162164166166...........1691701741771811831861911921941951986 NormsVector Norms . . . .6.16.2Matrix Norms . . . .6.3The Matrix p-Norm .6.4Notes and ReferencesProblems . . . . . .
...................................................................................9 LU Factorization and Linear EquationsGaussian Elimination . . . . . . . . . .9.1Error Analysis . . . . . . . . . . . . . .9.29.3The Growth Factor . . . . . . . . . . .Special Matrices . . . . . . . . . . . . .9.49.5Tridiagonal Matrices . . . . . . . . . .Historical Perspective . . . . .
. . . . .9.6Scaling . . . . . . . . . . . . . . . . . .9.79.8A Posteriori Stability Tests . . . . . . .Sensitivity of the LU Factorization . .9.99.10 Notes and References . . . . . . . . . .9.10.1 LAPACK . . . . . . . . . . . . ............................................................................... . . . ..
. . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .XProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19910 Cholesky Factorization10.1 Symmetric Positive Definite Matrices . . . .10.1.1 Error Analysis . . . .
. . . . . . . . .10.2 Sensitivity of the Cholesky Factorization . .10.3 Positive Semidefinite Matrices . . . . . . . .10.3.1 Perturbation Theory . . . . . . . . .10.3.2 Error Analysis . . . . . . . . . . . . .10.4 Symmetric Indefinite Matrices and DiagonalMethod. . . . .
. . . . . . . . . . . . . . . .10.4.1 Complete Pivoting . . . . . . . . . .10.4.2 Partial Pivoting . . . . . . . . . . . .10.5 Nonsymmetric Positive Definite Matrices . .10.6 Notes and References . . . . . . . . . . . . .10.6.1 LAPACK . . . . . . .
. . . . . . . . .Problems . . . . . . . . . . . . . . . . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .Pivoting. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .............. . .. . .. . .. . .. . .. . .203204205209210211214............................21821922122322422622711 Iterative Refinement11.1 Convergence of Iterative Refinement .11.2 Iterative Refinement Implies Stability11.3 Notes and References .
. . . . . . . .11.3.1 LAPACK. . . . . . . . . . . .Problems . . . . . . . . . . . . . . . ................. . .. . .. . .. . .. . .23123223524124324312 Block LU Factorization12.1 Block Versus Partitioned LU Factorization . . . . . . . . . . .12.2 Error Analysis of Partitioned LU Factorization .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
