Scribd
Upload
603 views342 pages

Numerical Analysis Rainer

Libro de metodos numericos

Uploaded by

Ivan Dario Romero Yepez
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
603 views342 pages

Numerical Analysis Rainer

Libro de metodos numericos

Uploaded by

Ivan Dario Romero Yepez
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Gratuate Texts InMathematics Rainer Kress Numerical Analysis 6 Springer Springer New York Berlin Heidelberg Barcelona Budepest Hong Kong London Milan Paris Santa Clara Singapore Tokyo Graduate Texts in Mathematics 1 81 S. Asler Editorial Board EW, Gehring K.A. Ribet Graduate Texts in Mathematics 2s ” Taseumv asm. lotion o ‘Axion Set Theory. 2d ed (Oxtony. Mensote and Category. 2nd of, ScHAErER. Tepoopicl Veer Spaces, Hucrowstasitanc. A Course Homolog Alper. 2d Mac Lane, Categories or the Working Materaicin ed ed cues ee. Prjcive Plane. Sean, A Course in Arh, “Taster /Zaune, Asiomatie Set Theory. [Link] Lie Cons. A Cov in Sie Homan Theo, Cosy. Funston of One Complex Beats. Advanced Mathematics! Ansys ‘AsoensonFvtsen, Ring and Caters of Modules nd ‘Gouanssv/Gunibi, Suble Maprings snd Their Singles. Beauens, Lecter Furtonl ‘Analysicard Operator Theory ‘Wistbe The Strctre of Fs RosexnLaT, Random Process, 2d Humor. a Hibe Space Problem Book 2nd ol Use. Fie Banden 3 amines Liner Alpebae Gru annts/Mnos. An Alesha Inodutionte Mathemaisa Logic. Grou Linea Alea, he. Howie, Geomets Fanstional Analy nis Appian. Hirwir/Stronenc, Real and Abst Analysis sts. General Topol. ZavoselSanec. Comantaive Algebra, vous Zavsse/Sane. Coomataive Ales, Vout {ncomson. Lectures in Abtat Al {Basie Coeepte nconsos. Lectures in Abstat Algebra Linear Alger acouson. Leese in Abarct Albee IL Theory of Fld and Goi They a M as 26 a a ” 2 2 ss ” cy msc, ile! Topology Shr2E, Prils of Random Walk ane ‘ALEXANOEN/WERMER. Several Complex Wariabes an Borah Algebras. Sele Keung ea. Linear “Topologies! Space. Mone. Mathematical Log. Gravenv/Femscne. Several Complex Variables Arvest, Ao lovistion C™-Algeba. Kewsr/SweuuKarr, Denumerate Mackov Chains ede Dich See in Neer Toy. ‘Stat, Linear Repesaions of Fite ‘Groups Gupasttensen. Rings of Cotimuous Fences. enc, Elementary Algebraic Gert [Link] Theory 1 Locve: Probably Theory he Mont. Geomete Topology ia Dinan? ad 3. Snes Gott Reavy for Matbenaiciane. Greansene/Wen. Linear Gcomety odes Ewa. Fennat's Las Theorem Kusceraere. A Couns Oilereniat [Link] Geom. Masts. A Cour ia Miter Lope Graven Wareas. Combis with Enhasison the Teor of Grae ‘Blows [Link] to Operator ‘Thooy I Element of Funstinal ‘aly. Masse Algerie Tepaogy: An Iran (GeoweLL/[Link] to Keat Theory. Komi, patie Nunber, pie Aral, Zt: unto a Lana. Cycltomi Fes, ‘Avseup, Matera! Mods iowa] Mechanics, 2 Rainer Kress Numerical Analysis With 11 Illustrations Rainer Kress Institut for Numersche und ‘Angewandte Mathematik ‘Universitat Gontingen 137083 Gottingen Germany Ecltorial Board S. Axler EW, Gehring KAA. Ribet Department of Department of Department of Mathematics ‘Mathematics Mathematics San Francisco State University University of Michigan University of California San Francisco, CA 98132 Ann Arbor, ML48109. at Berkeley Usa USA, Berkeley, CA 98720, USA “Mathematics Subject Classification (1991): 65.01, Library of Congres Catalogin-n-Publication Data res, Ree, 1941~ merc analss/ Raia Kress. eth ~ (Graduate ents in mathemares: 181 Intludes bibliographical references a ies ISBN 0387-98089 (hardcover ak paper 1. Numerical analysis. I Tie. Il Sein gaisriknas 1998 Si9a—ae2t snares Printed on aie pape ‘1998 Springer-Verlag New Yor, In. Alleiphs reseed Tht work may nab Warslatedor coped in whale a in pant without the ‘wtten permission ofthe publisher (Springer-Verlag New Voth In, 128 Filth Avenue, New York, NY TOOI0. USA). excep for brit excep in connection with teiews o seolaly naiyis, Use in connection with any Tors Of Halormation storage and rcs clcconk {dsptation, computer software, orbysmiar or similar methodology no Know os Bera. Ter eveopoaisfrbioen, “Thea of general desciive names, ead names, radcmarhs in this pubistion, even {tne former ate ot especialy ened, not tobe taken sgn thar ssh name 8 Understood bythe Trade Marks and Merchandise Marks Act may aeeowiogly be ane fcly byamone Production managed by Karna Mik; manufacturing supervised by Jl Avbs Phetocomposed copy prepared from the authors TeX ie Printed an bound by RR. Donnelly apd Som, Haeonbure, VA, Printed inthe United Sites Americ. garesaszi {SBN 0-37-984089 Springer-Vsrng Now York Uerhn Hsnebere SPIN 1063931 Preface ‘No applied mathematician can be properly trained without some basic un- derstanding of numerical methods, ie., numerical analysis. And no scientist and engineer should be using a package program for numerical comy tions without understanding the program's purpose and its limitations This book is an attempt to provide some of the required knowledge and understanding. It is written in a spirit that considers numerical analysis ‘not merely as a tool for solving applied problems but also as a challenging and rewarding part of mathematics. The main goal is to provide insight into numerical analysis rather than merely to provide numerical recipes. ‘The book evolved from the courses on numerical analysis I have taught since 1971 at the University of Gattingen and may be viewed as a suocessor of an earlier version jointly written with Bruno Brosowski {10} in 1974. It ‘aims at presenting the basic ideas of numerical analysis in a style as concise as possible. Its volume is sealed to a one-year course, ie., a two-semester course, addressing second-year students at a German university or advanced ‘undergraduate or first-year graduate students at an American university In order to make the book accessible not only to mathematicians but also to scientists and engineers, I have planned it to be as self-contained as possible. As prerequisites it requires only a sold foundation in differential ‘and integral calculus and in linear algebra as well as an enthusiasm to see these fundamental and powerful tools in action for solving applied prob- Jems. A short presentation of some basic functional analysis is provided in the book to the extent required for a modern presentation of numerical analysis and a deeper understanding of the subject. vi Preface ‘An introductory book of a few hundred pages cannot completely cover all classical aspects of numerical analysis and all of the more recent devel- ‘opments. [am willing to admit that the choice of some of the topics in the present volume is biased by my own preferences and that some important subjects are omitted, Twas taught numerical analysis in the mid sixties by my thesis adviser, Professor Erich Martensen, at the Technische Hochschule in Darmstadt. Martensen’s perspective on teaching mathematics in general and numeri- cal analysis in particular had a great and long-lasting impact on my own teaching. Therefore, this book is dedicated to Erich Martensen on the oc- ‘casion of his seventieth birthday. T would like to thank Thomas Gerlach and Peter Otte for carefully read- ing the book, for checking the solutions to the problems, and for a number of suggestions for improvements. Special thanks arc given to my friend David Colton for reading over the book for correct use of the English lan- guage. Part of the book was written while I was on sabbatical leave at the Department of Mathematical Sciences at the University of Delaware and the Department of Mathematics at the University of New South Wales. I {gratefully acknowledge the hospitality of these institutions. [also am grate- ful to Springer-Verlag for being willing to take the economic risk of adding yet another volume to the already huge number of existing introductions Gottingen, September 1997 Rainer Kress Contents 1 Introduction 2 Linear Systems 2.1 Examples for Systems of Equations 22 Gaussian Elimination . . 2.3 LR Decomposition - 24 QR Decomposition Problems 3 Basic Functional Analysis 3.1 Normed Spaces, 43.2 Scalar Products . 33, Bounded Linear Operios 34 Matrix Norms . 3.5 Completeness . . . . 36 The Banach Fixed Point Theorem 3.7 Best Approximation . Problems 4 Iterative Methods for Linear Systems 4.1 Jacobi and Gauss-Seidel Iterations 42. Relaxation Methods 43. Two-Grid Methods Problems 10 Contents Ill-Conditioned Linear Systems 5.1 Condition Number 5.2 Singular Value Decomposition 5.3. Tikhonov Regularization Problems Iterative Methods for Nonlinear Systems 6.1 Successive Approximations 62. Newton's Method 6.3. Zeros of Polynomials 64 Least Squares Proble Problems. Matrix Eigenvalue Problems 71 Bxamples 7.2 Bstimates forthe Eigenvalues 7.3 The Jacobi Method 74. The QR Algorithm 7.5. Hessenberg Matrices Problems Interpolation 8.1 Polynomial Interpolation 82. Trigonometric Interpolation 83. Spline Interpolation 84 Bézier Polynomials Problems Numerical Integration 9.1 Interpolatory Quadratures 92 Convergence of Quadrature Formulae . 9.3 Gaussian Quadrature Formulae 9.4 Quadrature of Periodic Functions 9.5 Romberg Integration . 9.6 Improper Integrals Problems Initial Value Problems 10.1 The Picard-Lindelof Theorem 10.2 Euler's Method 10.3 Single-Step Methods 104 Multistep Methods . Problems : 101 1 B aL 93 110 4 nT 119 120 122 126 133, Ma - 49 151 152 161 169 179 186 189 190 198 207 212 a7 2a 225 226 21 24 243 254 11 Boundary Value Problems 11.1 Shooting Methods 11.2 Finite Difference Methods 11.3 The Riesz and Lax-Milgram Theorems 11.4 Weak Solutions 5 11.5 The Finite Blement Method Problems Peer 12 Integral Equations 12.1 The Riesz Theory 12.2 Operator Approximations . . 12.3 Nystrém’s Method 124 The Collocation Method 125 Stability Problems References Index Contents 257 - 258 262 268 214 279 283 287 291 310 313 siz 322 Glossary of Symbols Sets and Spaces N set of natural numbers Zz set of integers R set of real numbers c set of complex numbers lal absolute value of a real or complex number 2 (a0) open interval (9,0) = (r€R:a 0? At this point we would like only to point out that the discretization of boundary value problems for ordinary differential equations leads to sys- tems of equations with a large number of unknowns, since we expect that in order to achieve a reasonably accurate approximation we need to choose the step size h sufficiently small o Example 2.2 We now consider the discretization of the boundary value problem for the elliptic partial differential equation — Aula) = f(zulz), 2€D, (24) with Dirichlet boundary condi Hi) =0, 2600, 23) 82, Linear Systems Here, D CR? is a bounded domain, A denotes the Laplacian Bu, Fu ous Sat a J: D xR Ris a given continuous function, and we are looking for 2 solution u : D+ R that is continuous in D and twice continuously differentiable in D. Boundary value problems ofthis type arise, for example, in potential theory and in heat conduction problems. The theory of elliptic partial diflerential equations (see {24)) provides conditions on the given function f that ensure existence and uniqueness of a solution u. For describing a numerical approximation method we restrict ourselves to the case of the square D = (0,1) x (0,1). We choose an ‘quadratic grid with grid points zy = (ih jh), 4,7=0).4n41, where the step size again is given by h = 1/(n41) with n € IV. Analogously to the previous example, atthe internal grid points 24, f,j = 1,-.-.2, we replace the Laplacian by the Laplace diference operator Aulzis) © B (aegis) + (ia) + wlzijea) + mlzj-1) — dulzy)) Obviously, for each point 2);, this difference operator has nonvanishing weights only at the four neighboring points on the vertical and horizontal Tine through xij. This observation also illustrates why the set of grid points h nonvanishing, weights is called the star associated with the Laplace difference operator. Using this difference approximation leads to the system of equations Fe lus — tans fleyugh 65= Moon, ages — Mig for approximate values uj to the exact solut be complemented by the boundary conditions uz): This system has to Woy = Ue =O F= 0-1, at the grid points on the vertical parts and tie = tins Assam, ‘at the grid points on the horizontal parts of the boundary QD. In order to write this system in matrix form we rearrange the unknowns by ordering, them row by row and setting 2.1 Examples for Systems of Equations 9 where m = n?, Purthermore, we introduce an m xm matrix A in the form of an m x n block tridiagonal matrix B-I IR. Such integral ‘equations either arise directly in the solution of applied problems, or more ‘often they occur indirectly in the solution of boundary value problems for differential equations. If the homogeneous form of this equation, ie., the integral equation with the right-hand side f = 0, admits only the trivial solution ¥y = 0, then for each f the inhomogeneous integral equation has tunique solution ¢ (see Chapter 12) 102 Liar Systems For the numerical approximation we replace the integral by the ectan- gular sum ff Kevsveanan = 2S Kteszeelen) with ouidstan grid points 24. = ky k= Ayes If we require the approximated equation to be satisfied only at the grid points, we arrive at the system of linear equations LK te tee = Slay), 5 ~ for approximate values yy to the exact solution ylzy). As in the preced- ing examples, we postpone the question of unique solvability of the linear system and the convergence and error analysis (see Chapter 12). Example 2.4 In this last example we will briefly touch on the method of least squares. Consider some (physical) quantity w depending on time t and a parameter vector a = (a1,...,2q)” € IR" in terms of a known function ult) = S60). In order to determine the values of the parameter a (representing some physical constants), one can take m measurements of w at different times tiy-ssstm and then try to find a by solving the system of equations ult) = fltsia), fm = n, this system consists of n equations for the n unknowns a). .-+4n However, in general, the measurements will be contaminated by errors. Therefore, usually one will take m > n meas determine a by requiring the deviations ult) = Mejias 5 to be as small as possible, Usually the latter requirement is posed in the least squares sense, ie, the parameter a is chosen such that g(a) = S Slulte) ~ fltesa)® attains a minimal value. The necessary conditions for a minimum, lead to the normal equations Lihue) — frei} 2.2 Gaussian Elimination 11 for the method of least squares. These constitute a system of n, in general, nonlinear equations for the n unknowns a)... dy. oO At this point, the reader should be convinced of the need for effective ‘methods for solving large systems of linear and nonlinear equations and be willing to be introduced to such methods in the subsequent chapters. We also wish to note that the discretization of differential equations leads to sparse matrices, whereas for the least squares problem and the discretiza- tion of integral equations one is faced with full matrices. 2.2 Gaussian Elimination We proceed with describing the Gaussian elimination method for a system of linear equations Ar=y, Here A is a given n x n matrix A = (ays) with real (or complex) entries, y a given right-hand side y = (y1,---,¥q)? € IR" (or €*), and we are looking for a solution vector x = (21,.--,2n)" € IR" (or ©"). More explicitly, our ‘system of equations can be written in the form Deawre sup Fs beans that is, 2 Fait, ts taint = anit, + anata boo + Gann = Opie + date + 8+ + Oantn = Ua: ‘Assuming that the reader is familiar with basic linear algebra, we recall the following various ways of saying that the matrix A is nonsingular: 1. The inverse matrix A~! exists. 2. For each y the linear system Az = y has a unique solution. 3. The homogeneous system Az = 0 has only the trivial solution, 4. The determinant of A satisfies det A #0. 5. The rows (columns) of A are linearly independent. ‘The very basic idea of the Gaussian elimination method is to use the first equation to eliminate the first unknown from the last — 1 equations, then use the new second equation to eliminate the second unknown from the last rn ~2 equations, etc. This way, by n ~ 1 such eliminations the given linear 122 Liar Systems syst is rasformed into an equivalent nar system tat of triangular fm tumtbamt bate bans + + tte = naa + Oa Onntin = Bn Recall that two linear systems are called equivalent if every solution of one is a solution of the other. The triangular system can be solved recursively by first obtaining 2» from the last equation, then obtaining z»1 from the second to last equation, ete. This procedure is known as backward substi- tution. Explicitly, itis described by tq = 2n/bon and We begin by considering a nonsingular matrix A. To eliminate the un- known zs, for j = 2,...9n we multiply the first equation by ajay and subtract the result from the jth equation. For this we have to require that ‘#0. Since we assume the matrix to be nonsingular, this can be achieved by reordering the rows or the columas of the given system. This procedure leads to a system ofthe form ener eee ett Gln + tafe, = yf? alley + + + aay = yf? with the new coefficients given by bu = al, ata ‘and the new right-hand sides given by (944 ay _ aru yo eg a yes xa 22 Gausian Elimination 13, Here, for the coeficints and right hand sides ofthe original system we hrave set al!) = aj, and yf!) = Proceeding in this way, ee the unknowns 21,---,2n is equivalently transformed into an (n—1) x(n—1) system forthe unknowns 21)... Adding a multiple of one row of a matrix to another row does not change the value of its determinant. Therefore, in the above elimina- tion the determinant ofthe system remains the same (with the exception of possible change of is sign ifthe order of rows or columns is changed) Hence, the resulting (rn 1) x (n ~ 1) system for z2,-.-.2y again has a nonvanishing determinant, and we can apply precisely the saine procedure to eliminate the second unknown 22 from the remaining (n —1) x (n—1) system. By repeating this process we complete the forward elimination, by which the system of linear equations 1, + ale, aay + olan + +z, allay + alee + os + allen = yf? witha nonsingular matix A = (of!) is equivalently transformed into a triangular eystem dun thant + inte = 21 bat + + Oanty = 22 Optin tna + Un-tsntin = Eno Yann by n— 1 recursive elimination steps of the form aimata) aE ca off) — SEEM km dt Nooam 142 Linear Systems ‘The coefficients and the right-hand sides of the final triangular system are given by be and ‘The condition aff 0, which is necessary for performing the algorithm, always can be achieved bya reordering ofthe rows of clumna, ine otk trwise the matrix A would not be nosing. ‘We would lite to compress the operation of on eli the flowing scheme ation step into where the rectangle illustrates the remaining part of the matrix and the right-hand side for which the elimination has to be performed. Here, a stands for the elimination element, or pivot element; the elements 4 in the elimination row remain unchanged; the elements ¢ of the elimination column ate replaced by zero (with the exception of the pivot element, a); and the remaining elements d are changed according to the rule daa We note that in computer calculations, of course, the new values for the coefficients of the matrix and the right-hand sides can be stored in the locations held by the old values. More explicitly, the entire Gaussian elimination can be written in the following algorithmic form. Algorithm 2.5 (Gaussian elimination) 1. Forward elimination: Form ana do forj=m+ly..n do fork=m-+ty...n doa wis yy 22 Gaussian Elimination 15 If the matrix A is singular and has rank r, the climination procedure will terminate after r steps. The matrix of the remaining (n —r) x (n —r) system for the unknowns x,41,--.4q is the zero matrix, because otherwise the rank of A would be different from r. Hence, inthis case the given linear system is solvable if and only if the right-hand sides after r elimination steps satisfy ‘The solutions canbe found from the triangular system by arbitrarily choos- ing e4iy---s2q and then recursively determining ty,.-,z0. This way we abtain the (1 ~r-dimensional solution manifold. Ih order to control the infuence of roundoff errors we want to keep the quotient al? fa) smal; ie, we want to havea lage pivot element of. Therefore, instead of only requiring of) # 0, in practice, either complete leoting or partial row or coleman piootng i employed. Foe complete piv ling, both the rows and the columns are reordered such that of has maximal absolute value in the (r— mn +1) x (n =m + 1) matrix remaining for the mth forward elimination step. In order to minimize the additional computational cost caused by pivoting, for row (or column) pivoting the rows (or columre) are reordered such that of has maximal absolute value in the elimination column (or row), i.c., in the mth column (or row). OF course, in the actual implementation of the Gaussian elimination algorithm the reordering of rows and columns need not be dove explcly. Insicad, the interchange may be done only implicitly by leaving the pivot clement at its original location and keeping track ofthe interchange of rows and Columns through the associated permutation matrix. ‘The fllowing example strates that partial pivoting docs nat always prevent lots of accuracy Inthe numerical computations. Example 2.6 We consider the system 21 + 2002 = 100 n+ msl with the exact solution x; = 100/199 = 0.502..., 2» = 99/199 = 0.497. For the following computasons we use two-decimal-digit. floating-point 16 2 Linear Systems arithmetic. Column pivoting leads to ayy as pivot element, and the eli nation yields since 199 = 200 in two-digit floating-point representation. From the second equation we then have x = 0.50 (0.495 = 0.50 in two decimal digits), and from the first equation it finally follows that 1 = 0. However, if by complete pivoting we choose ay2 as pivot element, the climination leads to 21 + 20022 = 100 a =05 (0.995 = 1.00 in two decimal digits), and from this we get the solution 21 = 05, 2 = 0.5 (0.4975 = 0.50 in two decimal digits), which is correct to two decimal digits o ‘Since complete pivoting is more costly than partial pivoting, in practical ‘computations one can try to overcome the disadvantages of partial pivoting by soaling the matrix. This means that if B = D,ADz, in order to obtain the solution z of Az = y we fist solve Bz = Duy for 2 and then determine zz from z = Dy2. Here D, and Dz are some diagonal matrices chosen such that for the matrix B the row and column sums of the absolute values are approximately equal. A diagonal matrix D = (djx) is a matrix with the off-diagonal elements equal to zero; ie. djy =O for j # k. For a detailed discusion of scaling we refer to (27). Unfortunately, there is no known ‘general procedure for such scaling, i.e, for choosing the diagonal matrices ‘Dy and Ds, For an estimate of the computational cost of Gaussian elimination we perform a count of the number of multiplications. By a, we denote the ‘number of multiplications that are required for solving a triangular n x n system by back substitution. Obviously, for aq we have the recurrence relation Oy = On +1, since we need n multiplications to obtain 21 from the first equation after having already determined z2,...,q- Hence, we have be meen since a) = 1. By Bp, we denote the number of multiplications needed for the forward elimination simultaneously for r different right-hand sides. Here we have the recurrence relation Baw = Bn te + (ork = Ny 7 since the elimination of the unknown 2, requires n +r multiplications for each row of the n 1 rows. From this it follows that e ® on, nln-r oa = Dee rk =) = 5-3 |. Adding ray and Br we obtain the fllowing result. ‘Theorem 2.7 Gaussian elimination for the simultancous solution of an nxn system for r different right-hand sides requires a total of Ftw-3 ‘multiplications. ‘The computational cost, counting only the multiplications, in Gaussian 0 for all: € IR” with z # 0. Positive definite matrices have postive diagonal elements (see Problem 2.10), and therefore a reordering of rows and columns is not necessary for Gaussian elimination (for pivoting, the largest diagonal element is chosen). It can be shown (see Problem 2.13) that symmetry and positive definiteness are preserved throughout the elimination if diagonal clements are taken as pivot elements. Therefore, for symmetric positive definite matrices the LR decomposition is always possible. If A = LR, then we have also A = AT = RTLT, and from Problem 2.15 we can deduce that L can be normalized such that A= LL? Such a decomposition is used in the Cholesky methed for the solution of linear systems with symmetric Positive definite matrices. Because of symmetry, the computational cost for the Cholesky method is n? /6+ O(n?) multiplications and n°/6-+ O(n?) additions. For details we refer to [26, 27) 2.4 QR Decomposition We conclude this chapter by describing a second elimination method for linear systems, which leads co a QR decomposition.

You might also like