S.Baskar - IIT Bombay

3y ago
26 Views
2 Downloads
1,013.71 KB
128 Pages
Last View : 20d ago
Last Download : 2m ago
Upload by : Mika Lloyd
Transcription

Introduction to Numerical AnalysisS. Baskar

2General InstructionsCourse Number : SI 507Course Title: Numerical AnalysisCourse Syllabus1. Mathematical Preliminaries: Continuity of a Function and Intermediate Value Theorem; Mean ValueTheorem for Differentiation and Integration; Taylor’s Theorem (1 and 2 dimensions).2. Error Analysis: Floating-Point Approximation of a Number; Loss of Significance and Error Propagation;Stability in Numerical Computation.3. Linear Systems: Gaussian Elimination; Pivoting Strategy; LU factorization; Residual Corrector Method;Solution by Iteration; Conjugate Gradient Method; Ill-Conditioned Matrices, Matrix Norms; Eigenvalue problem - Power Method; Gershgorin’s Theorem.4. Nonlinear Equations: Bisection Method; Fixed-Point Iteration Method; Secant Method; Newton Method;Rate of Convergences; Solution of a System of Nonlinear Equations; Unconstrained Optimization.5. Interpolation by Polynomials: Lagrange Interpolation; Newton Interpolation and Divided Differences;Hermite Interpolation; Error of the Interpolating Polynomials; Piecewise Linear and Cubic Spline Interpolation; Trigonometric Interpolation; Data Fitting and Least-Squares Approximation Problem.6. Differentiation and Integration: Difference formulae; Some Basic Rules of Integration; Adaptive Quadratures; Gaussian Rules; Composite Rules; Error Formulae.7. Differential Equations: Euler Method; Runge-Kutta Methods; Multi-Step Formulae; Predictor-CorrectorMethods; Stability and Convergence; Two Point Boundary Value Problems.Texts/References1. K. E. Atkinson, An Introduction to Numerical Analysis (2nd edition), Wiley-India, 1989.2. S. D. Conte and Carl de Boor, Elementary Numerical Analysis - An Algorithmic Approach (3rd edition),McGraw-Hill, 1981.General Rules1. Attendance in lectures as well as tutorials is compulsory. Students not fulfilling the 80% attendance requirement may be awarded the XX grade.2. Attendance will be recorded through an attendance sheet that will be circulated in the class. Each studentis expected to sign against his/her name only. Students who are found indulging in proxy attendance or anyform of cheating will be severely punished.Evaluation Plan1.2.3.4.There will be two quizzes (dates will be announced later), each of weightage 10% and one hour duration.The Mid-Semester Examination scheduled during 11-18 September 2010 will be of 30% weightage.The End-Semester Examination scheduled during 16-28 November will be of 40% weightage.Lab assignments will be given through out the semester and the students are expected to complete theassignment and produce all the outputs asked at the end of the semester. A oral viva will be conducted toeach student. The weightage will be of 10%.5. To pass the course (DD), one needs to score minimum of 40% of the maximum mark scored in the class. Forinstance, if the maximum mark scored is 80% at the end of the semester, then the passing mark will be 32%.Higher grades will be based on the over all performance of the class.Web Page: Course related materials will be uploaded inhttp://www.math.iitb.ac.in/ baskar/baskar t.htm

3PrefaceIn addition to the references provided above, class notes will be distributed in the class as a typedmaterial. These notes are meant only for SI 507 in Autumn 2010 as a supplementary material and cannotbe considered as a text book. Students are requested to refer the text books listed under course syllabusfor more details. These notes may have errors of all kind and the author request the readers to take careof such error while going through the material. The author will be grateful to those who brings to hisnotice any kind of error.

ContentsIntroduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71Mathematical Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.1 Continuity of a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.2 Differentiation of a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3 Integration of a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Taylor’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12Exercise 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.1 Floating-Point Form of Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2 Chopping and Rounding a Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.3 Different Type of Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.4 Loss of Significant Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.5 Propagation of Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Exercise 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253Linear Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.1 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2 LU Factorization Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.3 Error in Solving Linear Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.4 Matrix Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.5 Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.6 Eigenvalue Problem: The Power Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.7 Gerschgorin’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43Exercise 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454Nonlinear Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.1 Fixed-Point Iteration Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2 Bisection Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.3 Secant Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.4 Newton-Raphson Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.5 System of Nonlinear Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.6 Unconstrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6ContentsExercise 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645Interpolation by Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.1 Lagrange Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.2 Newton Interpolation and Divide Differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695.3 Error in Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.4 Piecewise Linear and Cubic Spline Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75Exercise 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776Numerical Differentiation and Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 796.1 Numerical Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 796.2 Numerical Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83Exercise 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917Numerical Ordinary Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 937.1 Review on Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 937.2 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 957.3 Euler’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 957.4 Runge-Kutta Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997.5 An Implicit Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1007.6 Multistep Methods: Predictor and Corrector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101Exercise 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

IntroductionNumerical analysis is a branch of Mathematics that deals with devising efficient methods for obtainingnumerical solutions to difficult Mathematical problems.Most of the Mathematical problems that arise in science and engineering are very hard and sometimeimpossible to solve exactly. Thus, an approximation to a difficult Mathematical problem is very important to make it more easy to solve. Due to the immense development in the computational technology,numerical approximation has become more popular and a modern tool for scientists and engineers. As aresult many scientific softwares are developed (for instance, Matlab, Mathematica, Maple etc.) to handlemore difficult problems in an efficient and easy way. These softwares contain functions that uses standardnumerical methods, where a user can pass the required parameters and get the results just by a singlecommand without knowing the details of the numerical method. Thus, one may ask why we need tounderstand numerical methods when such softwares are at our hands?In fact, there is no need of a deeper knowledge of numerical methods and their analysis in most of thecases in order to use some standard softwares as an end user. However, there are at least three reasonsto gain a basic understanding of the theoretical background of numerical methods.1. Learning different numerical methods and their analysis will make a person more familiar with thetechnique of developing new numerical methods. This is important when the available methods arenot enough or not efficient for a specific problem to be solved.2. In many circumstances, one has more methods for a given problem. Hence, choosing an appropriatemethod is important for producing an accurate result in lesser time.3. With a sound background, one can use methods properly (especially when a method has its ownlimitations and/or disadvantages in some specific cases) and, most importantly, one can understandwhat is going wrong when results are not as expected.Numerical analysis include three parts. The first part of the subject is about the development of amethod to a problem. The second part deals with the analysis of the method, which includes the erroranalysis and the efficiency analysis. Error analysis gives us the understanding of how accurate the resultwill be if we use the method and the efficiency analysis tells us how fast we can compute the result.The third part of the subject is the development of an efficient algorithm to implement the method asa computer code. A complete knowledge of the subject includes familiarity in all these three parts. Thiscourse is designed to meet this goal.A first course in Calculus is indispensable for numerical analysis. The first chapter of these lecturenotes quickly reviews all the essential calculus for following this course. Few theorems that are repeatedlyused in the course are collected and presented with an outline of their proofs.Chapter 2 introduces the concept of errors. One may be surprised to see errors at the initial stageof the course when no methods are introduced. Of course, there are two types of errors involved in amethod, namely,1. the error involved in approximating a problem and2. the error due to computation.

8ContentsThe first type of error is purely mathematical and often known as truncation error. The second one isdue to the floating-point approximation of a number. This error is committed by computer due to theirlimited memory capacity. For instance, the number 1/3 0.3333. has infinitely many digits and since acomputer can deal with a number with finite number of digits, this number has to be approximated tothe number 0.333.3 with finite number of digits (depending on the memory capacity of the computer).Such an approximation is called the floating-point approximation. Chapter 2 is devoted mainly tothe floating-point error and related concepts.Devising methods to solve linear systems and computation of eigenvalues and eigen vectors are thesubject of the chapter 2. In this chapter, we discuss direct methods which gives exact solution to thesystems mathematically. However, when we implement these direct methods on a computer we will getan approximate solution as the computed solution involves floating-point error. The chapter then discusssome iterative methods for solving linear systems. After a brief discussion of matrix analysis, the chapterends with power method for computing a eigenvalue and the corresponding eigen vector for a given matrix.Not all eivenvalues can be computed using this method and also not all matrices can be applicable tothis method. Gershgorin’s theorem may be used to decide whether power method can be used for a givenmatrix. We state this theorem without proof and discuss its application to power method.Chapter 4 introduces various iterative methods for a nonlinear equation and their convergence analysis. The methods are further extended to system of nonlinear equations. Unconditioned optimization isdiscussed at the end of the chapter. Interpolation by polynomials, data fitting and least-square approximation are the subject of Chapter 5. Chapter 6 introduced numerical differentiation and integration.These notes end with some basic methods for solving ordinary differential equations.

1Mathematical PreliminariesThis chapter reviews some of the results from calculus that are frequently used in this course. Onlydefinitions and important theorems with outline of a proof are provided. However, the readers are assumedto be familiar with a first course in calculus.Section 1 defines continuity of a function and proves intermediate value theorem. This theorem playsa basic role in finding initial guess in iterative methods for solving nonlinear equations in chapter 3.Derivative of a function, Rolle’s theorem and the mean-value theorem for derivatives in provided insection 2. The mean-value theorem for integration is discussed in section 3. These two theorems arecrucially used in deriving truncation error for numerical methods. Finally, Taylor’s theorem is discussedin section 4, which is essential for derivation and error analysis of almost all numerical methods discussedin this course.Throughout this chapter, we use the notation [a, b] for a closed interval and (a, b) for an open interval,where a and b are some finite real numbers such that a b.1.1 Continuity of a FunctionDefinition 1.1 (Continuity).A function f : R R is said to be continuous at a point x0 R iflim f (x) f (x0 ).(1.1)x x0In other words, for any given ǫ 0, there exists a δ 0 such that f (x) f (x0 ) ǫ whenever x x0 δ.(1.2)y{0{ǫxδFig. 1.1. y x2Example 1.2. Consider the function f (x) x2 . Clearly, f (x) x2 x20 when x x0 . Thus, thisfunction is continuous. Let us now check the condition (1.2). We have, f (x) f (x0 ) x2 x20 x x0 x x0 x x0 2x0 x x0 x x0 ( x x0 2 x0 ).

101 Mathematical PreliminariesFor any given ǫ 0, choose 0 δ x0 example is depicted in figure 1.1.px20 ǫ 0 to get (1.2) as required. An illustration of this Remark 1.3. Note that the δ in the above example depends on x0 . For a continuous function f , if forany given ǫ 0, the δ does not depend on x0 , then the function is said to be uniformly continuous. Theorem 1.4 (Intermediate-Value Theorem).Let f (x) be a continuous function on the interval [a, b]. If f (x1 ) α f (x2 ) for some number α andsome x1 , x2 [a, b] with x1 x2 , thenα f (ξ), for some ξ [a, b].Proof: Let S : {x [x1 , x2 ] : f (x) α} and ξ : sup S.(1) Clearly, there exists a sequence {an } in S such that an ξ. Since f is continuous at ξ, we havef (an ) f (ξ), which implies f (ξ) α.(2) The sequencex2 ξ [x1 , x2 ], n N.nconverges to ξ and hence f (bn ) f (ξ). As bn / S f (bn ) α, and hence f (ξ) α.bn ξ Combining the above two inequalities, we see that f (ξ) α and it is clear that ξ [a, b], whichcompletes the proof. 1.2 Differentiation of a FunctionDefinition 1.5 (Differentiation).A function f : (a, b) R is said to be differentiable at a point c (a, b) if the limitf (c h) f (c)h 0hlimexists. In this case, the value of the limit is denoted by f ′ (c) and is called the derivative of f at c. Thefunction f is said to be differentiable in (a, b) if it is differentiable at every point in (a, b).Remark 1.6. There are two other ways to define the derivative of a continuous function f : (a, b) R.Let us list all the three equivalent definitionsf (c h) f (c),hf (c) f (c h),f ′ (c) limh 0hf (c h) f (c h),f ′ (c) limh 02hf ′ (c) limh 0where c (a, b). For any fixed h 0, the formulaef (c h) f (c)hf (c) f (c h) Dh f (c) : hf (c h) f (c h)0Dh f (c) : 2hDh

to gain a basic understanding of the theoretical background of numerical methods. 1. Learning different numerical methods and their analysis will make a person more familiar with the technique of developing new numerical methods. This is important when the available methods are not enough or not efficient for a specific problem to be solved. 2.

Related Documents:

in St. Louis, FT Global MBA Ranking, 2021 #25 IIT Bombay is India's leading technology and research university. Alumni of IIT Bombay have gone on to become successful entrepreneurs, CEO's and Members of Parliament. About IIT Bombay Washington University in St. Louis (WashU) is renowned for its global contribution as a leader in research and .

IIT agreed to be a part of this competition: As per knowledge at present IIT Guwahati , IIT Kharagpur have agreed and talks are in forward with IIT Varanasi and IIT Roorkee. Finance and Logistics: Cost when not hosting: Travel Cost for maximum 10 member team to and fro to the host college Cost when Hosting the event: Major Distribution

IIT Patna Annual Report (2010-2011) 71 Dr. R.A. Mashelkar Chairman, Board of Governors IIT Gandhinagar-382 424 Member Dr. G. Madhavan Nair Chairman, Board of Governors IIT Patna-800 013 Member Shri Ajay Piramal Chairman, Board of Governors IIT Indore-452 017

Our study is unique because IIT Ropar uses the same student pool as IIT Delhi. Both the institutes have a common admission test known as IIT-JEE. The computer science department of IIT Delhi gets students with higher ranks, typically in the range of 1-300. In comparison, the students in IIT Ropar, typically have ranks between 1500-

ANNUAL REPORT - 2016-17 2 Bombay Chamber of Commerce and Industry BOMBAY CHAMBER AWARDS – 2015-16 Following Awards had been presented to the recipients at the occasion of Bombay Chamber’s 181th Foundation Day Celeb

IIT Bombay , CE Dept, Lecture Notes for CE201 MECHANICS OF MATERIALS 1 - 2 Contents Normal Stress Shearing Stress Bearing Str

Ph.D. Computer Science (Incomplete), New York University, 1995 – 1996 . B. Tech. in Computer Science and Engineering, IIT Bombay, 1991 – 1995 President of India Gold Medalist for the highest GPA among 350 students. Presi dent of India Gold M

API TYPE 6B FLANGE S L WITH RX GASKET STUD BOLT WITH NUTS POINT HEIGHT L API TYPE 6B FLANGE L S Figure 2.0-1 L API TYPE 6BX FLANGE NO STANDOFF AWHEM Recommendation For Stud Bolts and Tap End Studs For API Spec 6A 4 2.0 METHOD OF CALCULATING STUD BOLT LENGTHS FOR TYPE 6B AND 6BX FLANGES 2.0a CALCULATION. The following formula was