S.Baskar - IIT Bombay

Introduction to Numerical Analysis

S. Baskar

2

General Instructions

Course Number : SI 507 Course Title : Numerical Analysis

Course Syllabus

1. Mathematical Preliminaries: Continuity of a Function and Intermediate Value Theorem; Mean Value Theorem 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-Corrector Methods; Stability and Convergence; Two Point Boundary Value Problems.

Texts/References

1. 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 Rules

1. 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 student is expected to sign against his/her name only. Students who are found indulging in proxy attendance or any form of cheating will be severely punished.

Evaluation Plan

1. There will be two quizzes (dates will be announced later), each of weightage 10% and one hour duration. 2. The Mid-Semester Examination scheduled during 11-18 September 2010 will be of 30% weightage. 3. The End-Semester Examination scheduled during 16-28 November will be of 40% weightage. 4. Lab assignments will be given through out the semester and the students are expected to complete the

assignment and produce all the outputs asked at the end of the semester. A oral viva will be conducted to each 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. For instance, 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 in t.htm

3

Preface

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

Contents

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1 Mathematical Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1 Continuity of a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Differentiation of a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Integration of a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Taylor's Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Exercise 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1 Floating-Point Form of Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Chopping and Rounding a Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Different Type of Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Loss of Significant Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Propagation of Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Exercise 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3 Linear Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 LU Factorization Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 Error in Solving Linear Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.4 Matrix Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.5 Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.6 Eigenvalue Problem: The Power Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.7 Gerschgorin's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Exercise 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4 Nonlinear Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.1 Fixed-Point Iteration Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Bisection Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.3 Secant Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.4 Newton-Raphson Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.5 System of Nonlinear Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.6 Unconstrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download