An introduction to numerical analysis

所需积分/C币:23 2016-07-27 15:26:06 9.12MB PDF
收藏 收藏

PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE The Pitt Building, Trumpington Street, Cambridge, United Kingdom CAMBRIDGE UNIVERSITY PRESS The Edinburgh Building, Cambridge CB2 2RU, UK 40 West 20th Street. New York, NY 10011-4211USA 477 Williamstown Road. port Melbourne. viC 3207, Australia Ruiz de Alarcon 13, 28014 Madrid, Spain Dock house, The Water front, Cape Town 8001, South Africa O Cambridge University Press, 2003 This book is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements no reproduction of any part may take place without the written permission of Cambridge University Press First published 2003 Printed in the United Kingdom at the University Press, Cambridge ypeface CMR 10/13 pt System. IATEX 22 TB a catalogue record fuy thuis book is available fromn the British Library Library of Congress Cataloguing 2n Pablication data ISBN 0 521 81026 4 hardback ISBN 0 521 00794 1 paperback Contents Solution of equations by iteration 1.1 Iutroduction 1.2 Simple iterate 1. Iterative solution of equation 17 1.4 Relaxation and Newton' s method 19 1.5 The secant method 25 1.6 The bisection method 2 1. 7 Global beh 1. 8 Notes F xercises 2 Solution of systems of linear equations 2.1nt 2. 2 Gaussian elimination 2.3 LU facto 48 2.4 Pivoting 52 2.5 Solution of systems of equations 26C tational work 56 2.7 Norms and condition numbers 58 2. 8 Hilbert matrix 2.9 Least squares method 2.10 Notes Exercises 3 Special matrices 3.1 Introduction 3.2 SyInIletric positive definite matrices 3.3 Tridiagonal and band matrices 93 IV Contents 3.4 Monotone matrices 98 3.5 Notes 101 Exercises 102 4 Simultaneous nonlinear equations 104 4.1 Introduction 104 4.2 Simultaneous iteration 106 4.3 Relaxation and Newton's method 4.4 Global convergence 45N 124 Exercises Eigenvalues alld eigenvectors of a syInlletric matrix 133 5.1 Introduction 133 5.2 The characteristic polynoInlial 5.3 Jacobi’ s method 137 5.4 The Gerschigorin the 145 5.5 Householder' s method 150 5. 6 Eigenvalues of a tridiagonal matrix 156 5.7 Thc QR algorithm 5.7.1 The QR factorisation revisited 162 5.7.2 The dcfinition of thc QR algorithm 164 5. 8 Inverse iteration for the eigenvectors 166 5. 9 The Rayleigh 5.10 Perturbation analysis 172 5.11 Notes 174 6 Polynomial interpolation 179 6.1 Introduction 179 6.2 Lagrange interpolation 180 6.3 Conve 6.4 Hermite interpolati 8 6.5 Differentiation 191 6.6 Note Exercises 195 7 NuMerical integration 7.1 Introduction 200 7.2 Newton-Cotes formulae 7.3 Error estimates 7.4 The Runge phenomenon revisited 208 7.5 Composite formulae 209 Conte 7.6 The Euler-Maclaurin expansion 7.7 Extrapolation methods 215 7. 8 Notes 219 Exercises 220 8 Polynomial approximation in the oo-norm 8.1 Introduction 224 8.2 Normed linear spaces 224 8.3 Best approximation in the x-norm 8.4 Chebyshev polynomials 8.5 Interpolation 8. 6 Notes 247 Exercises 248 9 Approxilllation in the 2-1lorIll 252 9.1 Introduction 252 9.2 Inner product spaces 253 9.3 Best approximation in the 2-norm 256 9.4 Orthogonal polynomials 9.5 Comparisons 9.6 Notes Exercises 10 Numerical integration -Il 10. 1 Introduction 10.2 Construction of Gauss quadrature rules 277 10.3 Direct construction 280 10.4 Error estimation for Gauss quadrature 2 10.5 Composite Gauss formulae 285 10.6 Radau and Lobatto quadrature 287 10.7 Note Exercises 11 Piecewise polynomial approximation 292 11. 1 Introduction 11.2 Linear interpolating splines 293 11.3 Basis functions for t he linear spline 297 11.4 Cubic splines 11.5 Hermite cubic splines 11.6 Basis functions for cubic splines 11.7 Notes 306 307 Contents 12 Initial value problems for ODEs 310 12.1 Introduction 10 12.2 One-ste 317 12.3 Consistency and convergence 321 12. 4 All iMplicit one-step Inethod 324 12.5 Runge Kutta methods 12.6 Linear Multistep inethods 329 12.7 Zero-stability 12.9 Dahlquist's theorems 340 12.10 Systems of 341 12.11 Stiff systcms 343 12.12 Implicit Runge-Kutta methods 349 12.13 Notes 353 Exercises 13 Boundary value problems for ODEs 361 13.1 Introducti 13.2 A model problem 13.3 Error analysis 13.4 Boundary conditions involving a derivative gene 370 13.6 The Sturm-Liouville eigenvalue problem 373 13.7 The shoot 13.8 Not 14 The finite element method 14.1 Introduction: the model problem 14.2 Rayleigh-Ritz and Galerkin principles 388 14.3 Formulation of the finite element method 391 14.4 Error analysis of the finite element method 397 14.5 A posteriori error analysis by duality 403 14.6Nt 412 Exercises 414 Appendise a An overview of results from real allalysis 41 A diabwww. Bibliography Solution of equations by iteration 1.1 Introduction Equations of various kinds arise in a range of physical applications and a substantial body of mathematical research is devoted to their study Some equations are rather simple: in the early days of our mathematical education we all encountered the single linear equation a C+b=0, where a an b are real numbers and a#0, whose solution is given by the formula r=-6/a. Many equations. however, are nonlinear. a simple example is a+b.+c=0, involving a quadratic polynomial with real coefficients a, b, G, and a+0. The two solutions to this equation, labelle .I and 2, are found in terms of the coefficients of the polynomial from the familiar formulae b+√b2-4ac b-√b2-4ac (1.1) It is less likely that you have seen the Inore intricate forMulae for the solution of cubic and quartic polynomial equations due to the sixteenth century Italian mlatheinaticians Niccolo Fontana Tartaglia(1499-1557) and Lodovico Ferrari(1522 1565). respectively, which were published by Girolamo Cardano(1501-1576) in 1545 ill his Ar tis magnae sive de regulis algebraicis liber unus. In any case, if you have been led to believe that similar expressions involving radicals (roots of sums of products of coefficients) will supply the solution to any polynomial equation, then ou should brace yourself for a surprise: no such closed formula exists for a general polynomial equation of degree n when n >> 5. It transpires that for each n> 5 there exists a polynomial equation of degree n with Solution of equations by iteration integer coefficients which cannot be solved in terms of radicals: such is 20 Since there is no general formula for the solution of polynomial equa tions,no general formula will exist for the solution of an arbitrary non. linear equation of the form /(x)=0 where is a continuous real-valued function. How can we then decide whether or not such an equation possesses a solution in the set of real nunbers, and how can we find a The present chapter is devoted to the study of these questiOns. Our goal is to develop simple numerical methods for the approximate solution of the equation f()=0 where f is a real-valued function, defined and continuous on a bounded and closcd interval of the rcal linc. Mcthods of the kind discussed here are iterative in nature and produce sequences of rcal numbcrs which, in favourable circumstances, convcrge to the required solution 1.2 Simple iteration Suppose that f is a real-valued function, defined and continuous on a bounded closed interval a, b of the real line. It will be tacitly assumed throughout the chapter that a <6, so that the interval is nonempty. We wish to find a real number E e a, b] such that f(s)=0. If such s exists it is called a solution to the equation f()=0 Even some relatively simple equations may fail to have a solution in the set of real numbers. Consider for example f:x2+1 Clearly f(a)=0 has no solution in any interval a, b of the real line Indeed, according to(1. 1), the quadratic polynomial +I has two roots 1=V-1= and 2=-V-1=-. However, these belong to the set of imaginary numbers and are therefore excluded by our definition of solution which only admits real numbers. In order to avoid difficulties of this kind gim of solutions to th equation f(a)=0 in the set of real nunbers. Our first result in this direction is rathcr simplc 1 This result was proved in 1824 by the Norwegian mathematician Niels IIenrik abel (1802-1829), and was further refined in the work of Evariste Galois(1811-1832 who clarified t, he circumst. ances in which a closed formula may exist for the solution uf a polynomial equation of degree TL in terns of radicals 1. 2 Simple iteration 3 Theorem 1.1 Let f be a real-valued function, defined and continuous on a bounded closed interval [a, b of the real line. Assume, further, that f(a)f(b)<0: then, there exists s in [a b] such that f($)=0 Proof If f(a)=0 or /(b)=0 then &=a or $=b, respectively, alld the proof is complete. Now, suppose that f(a)f(b)+0. Then, f(a).f(b)< in other words, 0 belongs to the open interval whose endpoints are f(a) and f(b). By the Intermediate Value Theorem(Theorem A1),there exists s in the openl interval (a, b )such that f(S)=0 To pa.raphrase Theorem 1.1, if a continuous function f has opposite signs at the endpoints of the interval a, b, then the equation f(c)=0 as a SoliTion in c The converse statement is. of course false Consider, for example, a continuous function defined on [a, b which changes sign in the open interval(a, b) an even number of times, with f(a)f(b),0; then. f(a)f(b)>0 even though f(a)=0 has solutions inside a, b. Of course, in the latter case, there exist an even number of subintervals of (u, b) at the endpoints of each uf which f does have opposite signs. However, finding such subintervals may not always be To illustrate this last point, consider the rather pathological function a H> 21+M|m-1.05 (1.2) depicted in Figure 1. 1 for m in the closed interval [ 0.8, 1. 8 and M=200 The solutions 1=1.05-(1/ M)and 22=1.05+(1/M) to the equation f (r)=0 are only a distance 2/M apart and, for large and positive M locating them computationally will be a challenging task Remark 1.1 If you have access to the mathematical software packag Maple, plot the function f by typing plot(1/2-1/(1+200*abs(x-1.05)),x=0.8..1.8,y=-0.5..0.6); at the Maple line, and then repeat this erperiment by choosing M=2000,20000,2000,2000.0a20000000 place of the num ber 200. What do you observe For the last two values of M, replot the function f foru in the subinter val[1.04999, 1.05001 An alternative sufficient condition for the existence of a solution to the equation f(x)=0 is arrived at by rewriting it in the equivalent form a-g()=0 where g is a certain real-valued function, defined

试读 127P An introduction to numerical analysis
立即下载 低至0.43元/次 身份认证VIP会员低至7折

    关注 私信 TA的资源

    An introduction to numerical analysis 23积分/C币 立即下载
    An introduction to numerical analysis第1页
    An introduction to numerical analysis第2页
    An introduction to numerical analysis第3页
    An introduction to numerical analysis第4页
    An introduction to numerical analysis第5页
    An introduction to numerical analysis第6页
    An introduction to numerical analysis第7页
    An introduction to numerical analysis第8页
    An introduction to numerical analysis第9页
    An introduction to numerical analysis第10页
    An introduction to numerical analysis第11页
    An introduction to numerical analysis第12页
    An introduction to numerical analysis第13页
    An introduction to numerical analysis第14页
    An introduction to numerical analysis第15页
    An introduction to numerical analysis第16页
    An introduction to numerical analysis第17页
    An introduction to numerical analysis第18页
    An introduction to numerical analysis第19页
    An introduction to numerical analysis第20页


    23积分/C币 立即下载 >