Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 2
Текст из файла (страница 2)
. . . . . . . .12.3 Error Analysis of Block LU Factorization . . . . . . . . . . . .12.3.1 Block Diagonal Dominance . . . . . . . . . . . . . . . .12.3.2 Symmetric Positive Definite Matrices . . . . . . . . . .12.4 Notes and References . . . . . . .
. . . . . . . . . . . . . . . .12.3.1 LAPACK . . . . . . . . . . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24524624825025125525725825813 Matrix Inversion13.1 Use and Abuse of the Matrix Inverse . . .
.13.2 Inverting a Triangular Matrix . . . . . . . .13.2.1 Unblocked Methods . . . . . . . . . .13.2.2 Block Methods . . . . . . . . . . . .13.3 Inverting a Full Matrix by LU Factorization13.3.1 Method A . . . . . . . . . . . . . . .13.3.2 Method B . . . . . . . . . .
. . . . .261262265265267270270271.......................................................................................... . . .. . . .. . . .. . . .. . . .. . . .. . . .xi13.3.3 Method C . . . . .13.3.4 Method D . . . . .13.3.5 Summary. . . . . .13.4 Gauss-Jordan Elimination13.5 The Determinant . .
. . .13.5.1 Hyman’s Method .13.6 Notes and References . . .13.6.1 LAPACK . . . . . .Problems . . . . . . . . . .....................................................................................................................................................................................27227327527528128228328528528914 Condition Number Estimation14.1 H o w t o E s t i m a t e C o m p o n e n t w i s e C o n d i t i o nNumbers .
. . . . . . . . . . . . . . . . . . . . . . . .14.2 The p-Norm Power Method. . . . . . . . . . . . . . .14.3 LAPACK l-Norm Estimator . . . . . . . . . . . . . .14.4 Other Condition Estimators . . . . . . . . . . . . . .14.5 Condition Numbers of Tridiagonal Matrices . . . . .14.6 Notes and References . . . .
. . . . . . . . . . . . . .14.6.1 LAPACK . . . . . . . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . . . . . . . . .........................................29029129429730130430630615 The Sylvester Equation15.1 Solving the Sylvester Equation .15.2 Backward Error . . . . . .
. . .15.2.1 The Lyapunov Equation15.3 Perturbation Result . . . . . . .15.4 Practical Error Bounds . . . . .15.5 Extensions . . . . . . . . . . . .15.6 Notes and References . . . . . .15.6.1 LAPACK . . . . . . . . .Problems . . . . . . . . . . . . ..........................................................................................................................................................30931131331631832032132232432416 Stationary Iterative Methods16.1 Survey of Error Analysis .
. . . .16.2 Forward Error Analysis . . . . . .16.2.1 Jacobi’s Method . . . . . .16.2.2 Successive Overrelaxation16.3 Backward Error Analysis . . . . .16.4 Singular Systems . . . . . . . . .16.4.1 Theoretical Background .16.4.2 Forward Error Analysis . .16.5 Stopping an Iterative Method . .16.6 Notes and References . . . . . . .................................................................................................................................................................325327329332334334336336338341343xiiProblems . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 343......................................... . .. . .. . .. . .. . .34534635335835835918 QR18.118.218.318.418.518.618.718.818.9FactorizationHouseholder Transformations . . . . . . . . .QR Factorization . . . . .
. . . . . . . . . .Error Analysis of Householder ComputationsAggregated Householder Transformations . .Givens Rotations . . . . . . . . . . . . . . .Iterative Refinement . . . . . . . . . . . . . .Gram-Schmidt Orthogonalization . . . . . .Sensitivity of the QR Factorization . . . . .Notes and References . . .
. . . . . . . . . .18.9.1 LAPACK . . . . . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . . . .......................................................................................... .. .. .. .. .. .. .. .. .. .. .36136236336437037137537638138338638719 The19.119.219.319.419.519.619.719.819.9Least Squares ProblemPerturbation Theory . . . . .
. . . . . . . . . . .Solution by QR Factorization . . . . . . . . . . .Solution by the Modified Gram-Schmidt MethodThe Normal Equations . . . . . . . . . . . . . . .Iterative Refinement . . . . . . . . . . . . . . . . .The Seminormal Equations . . . . . . . . . .
. . .Backward Error . . . . . . . . . . . . . . . . . . .Proof of Wedin’s Theorem . . . . . . . . . . . . .Notes and References . . . . . . . . . . . . . . . .19.9.1 LAPACK . . . . . . . . . . . . . . . . . . .Problems . . .
. . . . . . . . . . . . . . . . . . . ..............................................................................391392395396397399403404407409412412..........................................41541641741942242342317 Matrix Powers17.1 Matrix Powers in Exact Arithmetic . .17.2 Bounds for Finite Precision Arithmetic17.3 Application to Stationary Iteration . .17.4 Notes and References .
. . . . . . . . .Problems . . . . . . . . . . . . . . . . .20 Underdetermined Systems20.1 Solution Methods . . . .20.2 Perturbation Theory . .20.3 Error Analysis . . . . . .20.4 Notes and References . .20.4.1 LAPACK . . . . .Problems . . . . . . . . ...............................................................................................X11121 Vandermonde Systems21.1 Matrix Inversion . . . . . . . . .21.2 Primal and Dual Systems .
. . .21.3 Stability . . . . . . . . . . . . .21.3.1 Forward Error . . . . . .21.3.2 Residual . . . . . . . . .21.3.3 Dealing with Instability .21.4 Notes and References . . . . . .Problems . . . . . . . . . . . . .......... . . . . . . . . . . .. . .
. . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . .42542642843443543743844044122 Fast Matrix Multiplication22.1 Methods . . . . . . . . . . . . .22.2 Error Analysis . . . . . . . . . .22.2.1 Winograd’s Method . . .22.2.2 Strassen’s Method . . . .22.2.3 Bilinear Noncommutative22.2.4 The 3M Method .
. . . .22.3 Notes and References . . . . . .Problems . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .Algorithms . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . .
. . . . . . . . . . . . .445446450451452456458459461Fast Fourier Transform and ApplicationsThe Fast Fourier Transform . . . . . . . . . . . . . . . . . . .Circulant Linear Systems . . . . . . . . . . . . . . . . . . . . .Notes and References . . . . . . . . . . . . . . .
. . . . . . . .Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46546646847047123 The23.123.223.3........................24 Automatic Error Analysis24.1 Exploiting Direct Search Optimization24.2 Direct Search Methods . . . . . .
. . .24.3 Examples of Direct Search . . . . . . .24.3.1 Condition Estimation . . . . . .24.3.2 Fast Matrix Inversion . . . . . .24.3.3 Solving a Cubic . . . . . . . . .24.4 Interval Analysis . . . . . . . . . . . . .24.5 Other Work . . . . . . . . . . . . . . .24.6 Notes and References . . . . . . . . . .Problems .
. . . . . . . . . . . . . . . ........................................ . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .25 Software Issues in Floating Point Arithmetic25.1 Exploiting IEEE Arithmetic .
. . . . . . . . .25.2 Subtleties of Floating Point Arithmetic . . . .25.3 Cray Peculiarities . . . . . . . . . . . . . . . .25.4 Compilers . . . . . . . . . . . . . . . . . . . .. . . . . . . . .. . . . . . . . .. . . . . . . . .. . . . . . . . .473474477479480481483485487489490491492495496497xivDetermining Properties of Floating Point Arithmetic . . . . .Testing a Floating Point Arithmetic . . .
. . . . . . . . . . . .Portability . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25.7.1 Arithmetic Parameters . . . . . . . . . . . . . . . . . .25.7.2 2×2 Problems in LAPACK . . . . . . . . . . . . . . .25.7.3 Numerical Constants . . . . . . . . . . . . . . . . . . .25.7.4 Models of Floating Point Arithmetic . . . . . . . . .
.25.8 Avoiding Underflow and Overflow . . . . . . . . . . . . . . . .25.9 Multiple Precision Arithmetic . . . . . . . . . . . . . . . . . .25.10 Patriot Missile Software Problem . . . . . . . . . . . . . . . .25.11 Notes and References . . . . . . . . . . .
. . . . . . . . . . . .Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49749849949950050150150250450650750826 A Gallery of Test Matrices26.1 The Hilbert and Cauchy Matrices . . . . . . . . . . . . . . . .26.2 Random Matrices . . . . . . . . . . . . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
