Introduction To Numerical Analysis - Stoer 3rd ed

Introduction To Numerical Analysis - Stoer 3rd ed，数值分析导论第三版，Stoer编著。包含误差分析、插值、线性方程求解、差分方程等J. StoerR. BulirschInstitut fur Angewandte mathematikInstitut fuir mathematikUniversitat wurzburgTechnische Universitatam Hubl8000 Munchen, GermanyD-97074 Wurzburg, GermanyR. BartelsW. gautschiC. witzgallDepartment of ComputerDepartment of ComputerCenter for appliedScienceciencesMathematicsUniversity of WaterlooPurdue UniversityNational Bureau ofWaterloo, Ontario N2L 3G1 West Lafayette, IN 47907StandardsCanadaUSAWashington DC 20234USAeditorsJerrold e. marsdenL SirovichControl and Dynamical Systems, 107-81Division of Applied mathematicsCalifornia Institute of TechnologyBrown univePasadena.CA91125 USAProvidence, RI 02912, USAWDepartment of mathematicsDepartment of Applied MathematicsUniversity of houstonUniversitat HeidelbergHouston TX 77004im Neuenheimer Feld 294USA69 120 Heidelberg, GermanyMathematics Subject Classification(1991):65-o1Library of Congress Cataloging-in-Publication dataStoer. Josef.[Einfuhrung in die Numerische Mathematik. EnglishIntroduction to numerical analysis /J Stoer, R. Bulirschtranslated by R. Bartels, w. Gautschi, and C. witzgall.--2nd edIncludes bibliographical references and indexISBN038797878Xi. Numerical analysis I. Bulirsch, Roland. Il. TitleOA297S821319925194dc209220536Printed on acid-free paperTitle of the German Original Edition: Einfuhrung in die Numerische Mathematik, I,lPublisher: Springer-Verlag Berlin Heidelberg, 1972, 1976o1980, 1993 Springer-Verlag New York, Inc.All rights reserved. This work may not he translated or c opied in whole or in part without the writtenmission of the publisher (Springer-Verlag New York, Inc, 175 Fifth Avenue, New York, NY 10010,any form of information storagc and retrieval, clcctronic adaptation, computer software, or by similar or dis-similar methodology now known or hereafter developed is forbiddenThe use of general descriptive names, trade names, trademarks, etc, in this publication, even if the formerarc not espccially identified is not to be taken as a sign that such names, as understood by the Trade marksand Merchandise Marks Act, may accordingly be used freely by anyonePrinted and bound by r.R. donnelley sons, HaiVAPrinted in the United Statcs of america987654ISBN (-387-97878-X Springcr-Vcrlag New York Berlin HeidelbergISBN 3-540-97878-X Springer-Verlag Berlin Heidelberg New York SPIN 106.54097Preface to the Second editionOn the occasion of this new edition, the text was enlarged by several newsections. Two sections on B-splines and their computation were added to thechapter on spline functions: Due to their special properties, their flexibilityand the availability of well-tested programs for their computation, B-splinesplay an important role in many applications.Also, the authors followed suggestions by many readers to supplementthe chapter on elimination methods with a section dealing with the solutionof large sparse systems of linear equations. Even though such systems areusually solved by iterative methods, the realm of elimination methods hasbeen widely extended due to powerful techniques for handling sparse matricesWe will explain some of these techniques in connection with the Choleskylgorithm for solving positive definite linear systemsThe chapter on eigenvalue problems was enlarged by a section on theLanczos algorithm; the sections on the LR and Qr algorithm were rewrittenand now contain a description of implicit shift techniques.In order to some extent take into account the progress in the area ofordinary differential equations, a new section on implicit differential equations and differential-algebraic systems was added, and the section on stiffdifferential equations was updated by describing further methods to solvesuch equationsThe last chapter on the iterative solution of linear equations was alsoimproved. The modern view of the conjugate gradient algorithm as an itera-tive method was stressed by adding an analysis of its convergence rate and adescription of some preconditioning techniques. Finally, a new section onmultigrid methods was incorporated: It contains a description of their basicideas in the context of a simple boundary value problem for ordinary differential equationsPreface to the second editMany of the changes were suggested by several colleagues and readers. Inparticular, we would like to thank R Seydel, P Rentrop, and A. Neumaierfor detailed proposals and our translators R. bartels, w. Gautschi, andC. Witzgall for their valuable work and critical commentaries. The originalGerman version was handled by F Jarre, and I. Brugger was responsible forthe expert typing of the many versions of the manuscriptFinally we thank Springer-Verlag for the encouragement, patience, andclose cooperation leading to this new edition.Wurzburg, MunchenJ. StoerMay 1991R BulirschPreface to the First EditionThis book is based on a one-year introductory course on numerical analysisgiven by the authors at several universities in germany and the United StatesThe authors concentrate on methods which can be worked out on a digitalcomputer For important topics, algorithmic descriptions( given more or lessformally in alGoL 60), as well as thorough but concise treatments of theirtheoretical foundations, are provided. Where several methods for solving aproblem are presented, comparisons of their applicability and limitations areoffered. Each comparison is based on operation counts, theoretical propertiessuch as convergence rates, and, more importantly, the intrinsic numericalproperties that account for the reliability or unreliability of an algorithm.Within this context, the introductory chapter on error analysis plays a specialrole because it precisely describes basic concepts, such as the numericalstability of algorithms, that are indispensable in the thorough treatment ofnumerical questions.The remaining seven chapters are devoted to describing numerical methods in various contexts. In addition to covering standard topics, these chapters encompass some special subjects not usually found in introductions tonumerical analysis. Chapter 2, which discusses interpolation, gives an account of modern fast Fourier transform methods. In Chapter 3, extrapolationtechniques for speeding up the convergence of discretization methods inconnection with Romberg integration are explained at lengthThe following chapter on solving linear equations contains a descriptionof a numerically stable realization of the simplex method for solving linearprogramming problems. Further minimization algorithms for solving unconstrained minimization problems are treated in Chapter 5, which is devoted tosolving nonlinear equationsAlter a long chapter on eigenvalue problems for matrices, Chapter 7 isPreface to the first ecdevoted to methods for solving ordinary differential equations. This chaptercontains a broad discussion of modern multiple shooting techniques forsolving two-point boundary-value problems. In contrast, methods for partialdifferential equations are not treated systematically The aim is only to pointout analogies to certain methods for solving ordinary differential equationse.g., diference methods and variational lechniques. The final chapter is devoted to discussing special methods for solving large sparse systems of linearquations resulting primarily from the application of difference or finite element techniques to partial differential equations. In addition to iterationmethods, the conjugate gradient algorithm of Hestenes and Stiefel and theBuneman algorithm(which provides an example of a modern direct methodfor solving the discretized Poisson problem) are describedwithin each chapter numerous examples and exercises illustrate thenumerical and theoretical properties of the various methods. Each chapterconcludes with an extensive list of referencesThe authors are indebted to many who have contributed to this introduc.tion into numerical analysis. Above all, we gratefully acknowledge the deepinfluence of the early lectures of F L. Bauer on our presentation. Manycolleagues have helped us with their careful reading of manuscripts and manyuseful suggestions. Among others we would like to thank are C. ReinschM.B. Spijker, and, in particular, our indefatigable team of translatorsR. Bartels, W. Gautschi, and C. witzgall. Our co-workers K. ButendeichG. Schuller, J, Zowe, and l brugger helped us to prepare the original germanedition. Last but not least we express our sincerest thanks to Springer-Verlagfor their good cooperation during the past yearswurzburg, MunchenStoerAugust 1979R. BulirschContentsPreface to the second editionPreface to the first Edition1 Error Analysis1.1 Representation of Numbers 22 Roundoff Errors and Floating-Point Arithmetic 51.3 Error Propagation 91.4Exampl1.5 Interval Arithmetic: Statistical Roundoff estimation 27Exercises for Chapter 1 33References for Chapter 1 362 Interpolation32.1 Interpolation by polynomials 382.1.1Theoretical Foundation: The Interpolation Formula of lagrange 382.1.2 Neville,s Algorithm 402.1.3Newtons Interpolation Formula: Divided Differences 432.1. 4 The Error in Polynomial Interpolation 492.1.5Hermite Interpolation 522.2Interpolation by Rational Functions 5822.1General Properties of Rational Interpolation 582.2.2 Inverse and Reciprocal Differences. Thiele,s Continued Fraction 632.2.3 Algorithms of the Neville Type 672.2.4 Comparing Rational and Polynomial Interpolations 712. 3 Trigonometric Interpolation 722.3Basic facts 722.3.2 Fast Fourier Transforms 7823. 3 The Algorithms of Goertzel and Reinsch 84234The Calculation of Fourier Coefficients. Attenuation Factors 882.4 Interpolation by Spline Functions 932.4.1 Theoretical Foundations 932.4.2 Determining Interpolating Cubic Spline functions 972.4.3 Convergence Properties of Cubic Spline Functions 1022.4.4 B-Splines 10724.5The Computation of B-splines 110Exercises for Chapter 2 114Refefor Chapter 2 1233 Topics in Integration1251 The Integration Formulas of Newton and Cotes 1263.2 Peano's Error Representation 1313.3 The euler-Maclaurin Summation Formula 1353.4 Integrating by Extrapolation 1393.5 About Extrapolation Methods 1443.6 Gaussian Integration Methods 1503.7 Integrals with singularities 160Exercises for Chapter 3 162References for Chapter 3 1664 Systems of Linear Equations1674.1Gaussian Elimination. The Triangular Decomposition of a matrix 1674.2 The Gauss-Jordan Algorithm 174.3he Cholesky De1804. 4 Error Bounds 1834.5 Roundoff- Error Analysis for Gaussian Elimination 1914.6 Roundoff errors in Solving Triangular Systems 1964.7 Orthogonalization Techniques of Householder and Gram-Schmidt 1984.8 Data Fitting 2(4.8.1 Linear Least Squares. The Normal Equations 2074.8.The Use of Orthogonalization in Solving Linear Least-SquaresProblems 2094.8.3The Condition of the linear Least-Squares Problem 2104.84Nonlinear Least-Squares problems 21748.5The Pseudoinverse of a matrix 2184.9 Modification Techniques for Matrix Decompositions 2214.10 The Simplex Method 2304. 11 Phase One of the Simplex Method 241Appendix to Chapter 4 2454.A Elimination Methods for Sparse Matrices 245Exercises for Chapter 4 253References for Chapter 4 258Contents5 Finding Zeros and Minimum Points by IterativeMethods260The Development of iterative Methods 2615.2 General Convergence Theorems 2645.3 The Convergence of Newtons Method in Several Variables 269A Modified Newton Mcthod 27254.1On the Convergence of minimization Methods 2735.4.2Application of the Convergence Criteria to the ModifiedNewton Method 2785.4.3 Suggestions for a Practical Implementation of the modifiNewton Method. A Rank-One Method Due to Broyden 2825.5 Roots of Polynomials. Application of Newton,s Method 2865.6 Sturm Sequences and Bisection Methods 2975.7 Bairstow's Method 3015. 8 The Sensitivity of Polynomial Roots 3035.9 Interpolation Methods for Determining Roots 3065.10 The A2-Method of Aitken 3125.11 Minimization Problems without Constraints 316Exercises for Chapter 5 325References for Chapter 5 3286 Eigenvalue Problems3306.0 Introduction 3306.1 Basic Facts on Eigenvalues 3326.2 The Jordan Normal Form of a matrix 3356.3 The Frobenius normal Form of a matrix 3406.4 The schur normal Form of a matrix: Hermitian and normalMatrices; Singular Values of Matrices 3456.5 Reduction of Matrices to Simpler Form 3516.5.1 Reduction of a hermitian matrix to Tridiagonal formThe method of householder 3536.5.2 Reduction of a Hermitian Matrix to Tridiagonal or DiagonalForm: The methods of givens and Jacobi 358653Reduction of a Hermitian Matrix to Tridiagonal FormThe method of lanczos 362654Reduction to Hessenberg Form 3666.6 Methods for Determining the eigenvalues and Eigenvectors 3706.6. 1 Computation of the Eigenvalues of a Hermitian Tridiagonal Matrix 3706.6.2 Computation of the Eigenvalues of a Hessenberg matrixThe method of Hyman 3726.6.3 Simple Vector Iteration and Inverse Iteration of Wielandt 3736.6. 4 The LR and or Methods 3806.6.5 The Practical Implementation of the QR Method 3896.7 Computation of the Singular Values of a Matrix 4006.8 Generalized Eigenvalue Problems 4056.9 Estimation of Eigenvalues 406Exercises for Chapter 6 419References for Chapter 6 425