Introduction to Numerical Analysis - IIT Bombay

1 Introduction toNumerical AnalysisLecture Notes for SI 507 Authors:S. Baskar and S. Sivaji GaneshDepartment of MathematicsIndian Institute of Technology BombayPowai, Mumbai 400 Mathematical Preliminaries.. Sequences of Real Numbers.. Limits and Continuity.. Differentiation.. Integration.. Taylor's Theorem.. Orders of Convergence.. Big Oh and Little oh Notations.. Rates of Convergence.. Exercises..242 Error Analysis .. Floating-Point Representation.. Floating-Point Approximation.. Under ow and Over ow of Memory.. Chopping and Rounding a Number.. Arithmetic Usingn-Digit Rounding and Chopping.. Types of Errors.. Loss of Signi cance.. Propagation of Relative Error in Arithmetic Operations.. Addition and Subtraction.

2 Multiplication.. Division.. Total Error.. Propagation of Relative Error in Function Evaluation.. Stable and Unstable Computations.. Exercises..483 Numerical Linear Algebra.. System of Linear Equations.. Direct Methods for Linear Systems.. Naive Gaussian Elimination Method.. Modi ed Gaussian Elimination Method with Partial Pivoting.. Operations Count in Naive Gaussian Elimination Method.. Thomas Method for Tri-diagonal System.. LU Factorization.. Matrix Norms and Condition Number of a Matrix.. Iterative Methods for Linear Systems.. Jacobi Method.. Gauss-Seidel Method.. Mathematical Error.. Residual Corrector Method.. Stopping Criteria.. Eigenvalue Problems.. Power Method.. Gerschgorin's Theorem.

3 Exercises..1104 Nonlinear Equations.. Closed Domain Methods.. Bisection Method.. Regula-falsi Method.. Stopping Criteria.. Open Domain Methods.. Secant Method.. Newton-Raphson Method.. Fixed-Point Iteration Method.. Comparison and Pitfalls of Iterative Methods.. Exercises..1515 Interpolation.. Polynomial Interpolation.. Existence and Uniqueness of Interpolating Polynomial.. Lagrange's Form of Interpolating Polynomial.. Newton's Form of Interpolating Polynomial.. Newton's Divided Difference Formulas.. Divided Differences Table.. Divided Difference Formula for Repeated Nodes.. Error in Polynomial Interpolation.. Mathematical Error.. Arithmetic Error.. Total Error.. Runge Phenomenon.. Convergence of Sequence of Interpolating Polynomials.

4 Piecewise Polynomial Interpolation.. Spline Interpolation.. Exercises..1886 Numerical Integration and Differentiation.. Numerical Integration.. Rectangle Rule.. Trapezoidal Rule.. Simpson's Rule.. Method of Undetermined Coefficients.. Gaussian Rules.. Numerical Differentiation.. Approximations of First Derivative.. Methods based on Interpolation.. Methods based on Undetermined Coefficients.. Arithmetic Error in Numerical Differentiation.. Exercises..2187 Numerical Ordinary Differential Equations.. Review of Theory.. Discretization Notations.. Euler's Method.. Error in Euler's Method.. Modi ed Euler's Methods.. Runge-Kutta Methods.. Order Two.. Order Four.. Exercises..238 Index.. 241 Baskar and Sivaji6SI 507, IITBCHAPTER 1 Mathematical PreliminariesThis chapter reviews some of the concepts and results from calculus that are fre-quently used in this course.

5 We recall important de nitions and theorems whoseproof is outlined brie y. The readers are assumed to be familiar with a rst coursein , we introduce sequences of real numbers and discuss the concept oflimit and continuity in the intermediate value theorem. This theoremplays a basic role in nding initial guesses in iterative methods for solving nonlinearequations. In de ne derivative of a function, and prove Rolle's theoremand mean-value theorem for derivatives. The mean-value theorem for integration isdiscussed in These two theorems are crucially used in devising methodsfor Numerical integration and differentiation. Finally, Taylor's theorem is discussed , which is essential for derivation and error Analysis of almost all numericalmethods discussed in this course.

6 In introduce tools useful in discussingspeed of convergence of sequences and rate at which a functionfpxqapproaches apointfpx0qasx ;bPRbe such thata b. We use the notationsra;bsandpa;bqfor the closedand the open intervals, respectively, and are de ned byra;bs txPR:a x buandpa;bq txPR:a x Sequences of Real NumbersDe nition (Sequence).Asequenceof real numbers is an ordered list of real numbersa1;a2; ;an;an 1; In other words, asequenceis a function that associates the real numberanforeach natural numbern. The notationtanuis often used to denote the sequencea1;a2; ;an;an 1; chapter 1. Mathematical PreliminariesThe concept of convergence of a sequence plays an important role in Numerical anal-ysis, for instance when approximating a solutionxof a certain problem via an iter-ative procedure that produces a sequence of approximation.

7 Here, we are interestedin knowing the convergence of the sequence of approximate solutions to the nition (Convergence of a Sequence).Lettanube a sequence of real numbers and letLbe a real number. The sequencetanuis said toconvergetoL, and we writelimn 8an L(oran Lasn 8),if for every 0there exists a natural numberNsuch that|an L| whenevern N:The real numberLis called thelimitof the (Sandwich Theorem).Lettanu;tbnu;tcnube sequences of real numbers such that(1)there exists ann0 PNsuch that for everyn n0, the sequences satisfy theinequalitiesan bn cnand(2)limn 8an limn 8cn the sequencetbnualso converges andlimn 8bn L.[\De nition (Bounded Sequence).A sequencetanuis said to be abounded sequenceif there exists a real numberMsuch that|an| Mfor everynPN:Theorem (Bolzano-Weierstrass theorem).]

8 Every bounded sequencetanuhasa convergent following result is very useful in computing the limit of a sequence sandwichedbetween two sequences having a common nition (Monotonic Sequences).A sequencetanuof real numbers is said to be(1)anincreasing sequenceifan an 1, for everynPN:Baskar and Sivaji8SI 507, IITBS ection Limits and Continuity(2)astrictly increasing sequenceifan an 1, for everynPN:(3)adecreasing sequenceifan an 1, for everynPN:(4)astrictly decreasing sequenceifan an 1, for everynPN:A sequencetanuis said to be a(strictly) monotonic sequenceif it is either(strictly) increasing or (strictly) monotonic sequences always converge.[\Note that any bounded sequence need not converge. The monotonicity in the abovetheorem is very important.]

9 The following result is known as \algebra of limits ofsequences".Theorem two sequences. Assume thatlimn 8anandlimn 8bnexist. Then(1)limn 8pan bnq limn 8an limn 8bn.(2)limn 8can climn 8an, for any numberc.(3)limn 8anbn limn 8anlimn 8bn.(4)limn 81an 1limn 8an, providedlimn 8an Limits and ContinuityIn the previous section, we introduced the concept of limit for a sequences of realnumbers. We now de ne the \limit" in the context of nition (Limit of a Function).(1)Letfbe a function de ned on the left side (or both sides) ofa, except possibly ataitself. Then, we say \theleft-hand limitoffpxqasxapproachesa, equalsl"and denotelimx a fpxq l;if we can make the values offpxqarbitrarily close tol(as close tolas we like)by takingxto be sufficiently close toaandxless and Sivaji9SI 507, IITBC hapter 1.

10 Mathematical Preliminaries(2)Letfbe a function de ned on the right side (or both sides) ofa, except possiblyataitself. Then, we say \theright-hand limitoffpxqasxapproachesa, equalsr" and denotelimx a fpxq r;if we can make the values offpxqarbitrarily close tor(as close toras we like)by takingxto be sufficiently close toaandxgreater thana.(3)Letfbe a function de ned on both sides ofa, except possibly ataitself. Then, wesay\thelimitoffpxqasxapproachesa, equalsL" and denotelimx afpxq L;if we can make the values offpxqarbitrarily close toL(as close toLas we like)by takingxto be sufficiently close toa(on either side ofa) but not equal that in each of the above de nitions the value of the functionfat the pointadoes not play any role.