Introduction to numerical analysis

所需积分/C币:19 2018-03-19 14:09:21 8.2MB PDF
收藏 收藏
举报

Introduction to numerical analysis Introduction to numerical analysis
Preface to the second edition On the occasion of t he new edition, the text was en larged by severa l new sections. Two sections on B-splines and their computation were added to the chapter on spline functions: due to their special properties, their flex- ibility, and the availability of well tested programs for their computation B-splines play an important role in many applications Also, thc authors followed suggcstions by many rcadcrs to supplement the chapter on elimination methods by a section dealing with the solution of large sparse systems of linear equations. Even though such systems are usually solved by iterative methods, the realm of elimination methods has been widely extended due to powerful techniques for handling sparse matrices. We will explain some of these techniques in connection with the Cholesky algorithm for solving positive definite linear systems The chapter on eigenvalue problems was enlarged by a section on the Lanczos algorithm; the sections on the LR -and qr algorithm were rewrit ten and now contain also a description of implicit shift techniques In ordcr to takc account of thc progross in the arca of ordinary dif- ferential equations to some extent, a new section on implicit differential quations and differentia.l-aIgebraic systems was added and the section on stiff differential equations was updated by describing further methods to solve such equations Also the last chapter on the iterative solution of linear equations was improved. The modern view of the conjugate gradient algorithm as an iterative method was stressed by adding an analysis of its convergence rate anld a description of sOllle preconditiOning techniques. Fimally, a llew section on multigrid methods was incorporated: It contains a description of their basic ideas in the context of a simple boundary value problem for ordinary differential equations Preface to the Second edition Many of the changes were suggested by several colleagues and readers. In particular, we would like to thank R. seydel, P. Rentrop and A. Neumaier for detailed proposals, and our translators R. Bartels, W. Gautschi and C Witzgall for their valuable work and critical commentaries. The original GerInal version was handled by F. Jarre. alld I. Brugger was responsible for the expert typing of the many versions of the manuscript Finally we thank the Springer-Verlag for the encouragement, patience and close cooperation leading to this new edition Wiirzburg, Miinchen . Stoer May 1991 R. Bulirsch Contents Preface to the Third edition Preface to the Second editi IX 1 Error Analysis 1.2 Roundoff Errors and Floating-Point Arithmetic 4 1.3 Error Pl 1.4 Examples 21 5 Interval Arithmetic: Statistical Roundoff Estination 27 Exercises for Chapter 1 33 References for Chapter 1 36 Interpolation 37 2.1 Interpolation by Polynomials 38 2.1.1 Theoretical Foundation: The Interpolation Formula of Lagrange 38 2. 1.2 Neville's Algorithm 40 2.1.3 Newtons Interpolation Formula: Divided Differences 43 2.1.4 The Error in Polynomial Interpolation 48 2.1.5 Hernite InterpolatiOn 51 2.2 Interpolation by Rationa.l Functions 59 2.2.1 General Properties of Rational Interpolation 59 2.2.2 Inverse and Reciprocal Differences. Thiele's Continued Fraction 64 2.2.3 Algorithms of the Neville Type 68 2.2.4 Comparing Rational and Polynomial Interpolation 73 2.3 Trigonometric Interpolation 74 2.3.1 Basic Facts 74 2.3.2 Fast Fourier Transforms 80 2.3.3 The Algorithms of Gocrtzcl and Reinsch &8 2.3.4 The Calculation of Fourier Coefficients. Attenuation Factors 92 2.4 Interpolation by Spline Functions 97 2.4.1 Theoretical Foundations 97 2.4.2 Determining Interpolating Cubic Spline Functions 101 .4.3 Convergence Properties of Cubic Spline Functions 107 2.4.4 B-Splines 111 4.5 The Computation of B-Splines 117 2.4.6 Multi-Rosolution Mcthods and B-Splines 121 Exercises for Chpater 2 134 References for Chapter2 143 3 Topics in Integration 145 3.1 The Integration Formulas of Newton and Cotes 116 3.2 Peano's Error Representation 151 3.3 The euler-Maclaurin summation formula 156 3.4 Integration by Extrapolation 160 3.5 About Extrapolation Methods 165 3.6 Gaussian Integration Methods 171 3.7 Integrals with Singularities 181 Exercises for Chapter 3 184 References for Chapter 3 188 4 Systems of Linear Equations 190 4.1 Gaussian Elimination. The Triangular Decomposition of a Matrix 190 4.2 The Gauss-Jordan Algorithm 200 4.3 The Choleski Decompostion 204 4.4 Error bounds 207 4.5 Roundoff-Error Analysis for Gaussian Elimination 215 4.6 Roundoff rrors in Solving Triangular Systems 221 4.7 Orthogonalization Techniques of Householder and gram-schmidt 223 4.8 Data Fitting 231 4.8.1 Linear Least Squares. The Normal Equations 232 4.8.2 The Use of Orthogonalization in Solving Linear Least-Squares Problems 235 1.8.3 The Condition of the Linear Least-Squares Problem 236 4.8.4 Nonlinear Least-Squares Problems 241 4.8.5 The Pseudoinverse of a matrix 243 4.9 Modification Techniques for Matrix Decompositions 247 4.10 The Simplex Method 256 4.11 Phase One of the Simplex Method 268 4. 12 Appendix: Elimination Methods for Sparse Matrices 272 Exercises for Chapter 4 280 References for Chapter 4 286 outen 5 Finding Zeros and minimum points by iterative Methods 289 5.1 The Development of Iterative Methods 290 5.2 General Convergence Theorems 293 5. 3 The Convergence of Newtons Method inl Several Variables 298 5.4 A Modified Newton method 302 5.4.1 On the Convergence of Minimization Methods 303 5.4.2 Application of the Convergence Criteria to the Modified Newton Method 308 5.4.3 Suggestions for a Practical Implementation of the Modified Newton Method. A Rank-One method due to broyden 313 5.5 Roots of Polynomials. Application of Newton's Method 316 5.6 Sturm Sequences and Bisection Met, hods 328 5. 7 Bairstow's Mcthod 333 5.8 The Sensitivity of Polynomial Roots 335 5. 9 Interpolation Methods for Determining Roots 338 5. 10 The AMethod of Aitken 344 5.11 Minimization Problems without Constraints 349 Exercises for Chapter 5 358 References for Chapter 5 361 6 Eigenvalue Problems 364 6.0 Introduction 364 6. 1 Basic Facts on Eigenvalues 366 6.2 The Jordan normal Form of a matrix 369 6. Thc Frobenius normal Form of a Matrix 375 6. 4 The Schur Normal Form of a Matrix: Hermitian and Normal Matrices: Singular values of matrixes 379 6.5 Reduction of Matrices to Simpler Form 386 6.5.1 Reduction of a llermitian Matrix to Tridiagonal Form The Method of Householder 388 6.5.2 Reduction of a Hermitian Matrix to Tridiagonal or Diagonal Form: The Methods of Givens and Jacobi 394 6.5.3 Reduction of a Hermitian Matrix to Tridiagonal Forirl The met hod of lanczos 398 6.5.1 Reduction to Hessenberg Form 102 6.6 Methods for Determining the Eigenvalues and Eigenvectors 405 6.6. 1 Computation of the Eigenvalues of a Hermitian Tridi 6.6.2 Computation of the Eigenvalues of a Hessenberg Matr The Method of Hyman 407 6.6.3 Simple Vector Iteration and Inverse Iteration of Wielandt 408 The LR and QR 6.6.5 The Practical Implementation of the QR Method 425 Contents 6.7 Computation of the Singular Values of a Matrix 436 6.8 Generalized Eigenvalue Problems 440 6.9 Estimation of Eigenvalues 441 Exercises for Chapter 6 455 References for Chapter 6 462 7 Ordinary Differential Equations 465 7.0 Introduction 465 7.1 Some Theorems from the Theory of Ordinary Differential Equations 467 7. Initial- Valuc Problems 471 7. 2.1 One-Step Methods: Basic ConCepts 471 7.2.2 Convergence of One-Step Methods 477 7.2.3 Asymptotic Expansions for the Global Discretization Error of One-Step methods 480 7.2.1 The Infuence of Rounding Errors in One-Step Methods 483 7.2.5 Practical Implementation of One-Step Methods 485 7.2.6 Multistep Methods: Examples 492 7.2.7 General Multistep Methods 495 7.2.8 An example of Divergence 498 7.2.9 Lincar Diffcrencc Equations 501 7. 2.10 Convergence of Multistep Methods 504 7. 2.11 Linear Multistep Methods 508 7.2.12 Asymptotic Expansions of the Global Discretization Error for Linear Multistep Methods 513 7. 2.13 Practical Implementation of Multistep Methods 517 7.2.14 Extrapolation Methods for the solution of the Initial-Value Problem 521 7. 2. 15 Cunparisonl of Methods for Solving Initial-Value ProbleMs 524 7. 2.16 Stiff Differential Equations 525 7. 2.17 Implicit Differential Equations. Differential-Algebraic Equations 53 7. 2.18 Ilandling Discontinuities in Differential Quations 536 7. 2. 19 Sensitivity Analysis of Initial-Value Problems 538 7.3 Boundary-Value Problems 539 7.3.0 Introduction 539 7.3. 1 The Simple shooting Method 542 7.3.2 The Simple Shooting Method for Linear Boundary-value Problcms 548 7.3.3 An Existence and Uniqueness Theorem for the Solution of Boundary-Value Problems 550 7.3.4 Difficulties in the Execution of the Simple Shooting Method 552 7.3.5 The Multiple Shooting Method 557 outen 7.3.6 Hints for the Practical Implementation of the Multiple Shooting Method 561 7.3.7 An Example: Optimal Control Program for a Lifting Reentry Space vehicle 565 7.3.8 Advanced Techniques in Multiple Shooting 572 7.3.9 The Limiting Case m-o of the Multiple Shooting Method (Gcncral Nowton's Method, Quasilincarization) 577 7. 4 Difference Methods 582 7.5 Variational Met hods 586 7.6 Comparison of the Methods for Solving Boundary-Value Problems for Ordinary Differential Equations 596 7. 7 Variational Methods for Partial Differential equations The finite-Element method 600 Exercises for Chapter 7 607 References for Chapter 7 613 8 Iterative methods for the solution of Large Systems of Linear Equations Additional method 619 Introduction 61g 8.1 Gcncral Proccdurcs for the Construction of Itcrativc Mcthods 621 8.2 Convergence Theorems 623 3 Relaxation methods 629 8.4 Applications to Difference MethodsAn Example 639 8.5 Block Iterative methods 645 8. 6 The ADI-Method of Peaceman and Rachford 647 8, 7 Kry lov Space Methods for Solving Linear Equations 657 1 The Conjugate-Gradient Method of Hestenes and Stiefel 658 8.7.2 The GMrEs AlgorithIm 667 8.7.3 The Biorthogonalization Method of Lanczos and the QMR algorithm 680 8.7.4 The Bi-CG and BI-CGSTAB Algorithms 686 8.8 Buneman's Algorithm and Fourier Methods for Solving the Discretized Poisson Equation 691 8.9 Multigrid Methods 702 8.10 Comparison of Iterative Methods 712 Exercises for Chapter 8 719 References for Chaptcr 8 727 General literature on Numerical methods 730 Index 732

...展开详情
试读 127P Introduction to numerical analysis
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    acehand

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    Introduction to numerical analysis 19积分/C币 立即下载
    1/127
    Introduction to numerical analysis第1页
    Introduction to numerical analysis第2页
    Introduction to numerical analysis第3页
    Introduction to numerical analysis第4页
    Introduction to numerical analysis第5页
    Introduction to numerical analysis第6页
    Introduction to numerical analysis第7页
    Introduction to numerical analysis第8页
    Introduction to numerical analysis第9页
    Introduction to numerical analysis第10页
    Introduction to numerical analysis第11页
    Introduction to numerical analysis第12页
    Introduction to numerical analysis第13页
    Introduction to numerical analysis第14页
    Introduction to numerical analysis第15页
    Introduction to numerical analysis第16页
    Introduction to numerical analysis第17页
    Introduction to numerical analysis第18页
    Introduction to numerical analysis第19页
    Introduction to numerical analysis第20页

    试读已结束,剩余107页未读...

    19积分/C币 立即下载 >