Tutorial-NA-MA214 PDF

Preview

Summary

Tut sheet...

Description

Introduction to Numerical Analysis Tutorial Sheets MA 214, Spring Semester 2018-19

Instructors:

S. Sivaji Ganesh and S. Baskar

Department of Mathematics Indian Institute of Technology Bombay Powai, Mumbai 400 076.

0

General Information Syllabus Up to Midsem • Mathematical Preliminaries: Sequences of real numbers; Continuity of a Function and Intermediate Value Theorem; Mean Value Theorems for Differentiation and Integration; Taylor’s Theorem; Order of Convergence. (10 Marks) • Error Analysis: Floating-Point Representation; Types of Errors; Loss of Significance; Propagation of Error. (15 Marks) • Numerical Linear Algebra: Gaussian Elimination; Pivoting Strategy; LU factorization; Matrix Norms, Condition Number of a Matrix; Solution by Iteration: Methods of Jacobi, Gauss-Seidel, and Residual Corrector Method; Eigenvalue problems: Power Method, Gershgorin’s Theorem. (30 Marks) After Midsem • Nonlinear Equations: Bisection Method; Secant Method; Newton-Raphson Method; Fixed-point Iteration Method; Rates of Convergence. (15 Marks) • Interpolation: Lagrange and Newton Forms of Interpolating Polynomials; Divided Differences; Error in Polynomial Interpolation; Runge Phenomena; Piecewise Polynomial and Cubic Spline Interpolations. (15 Marks) • Numerical Integration and Differentiation: Rectangule rule, Trapezoidal rule, Simpson’s rule; Composite Rules; Gaussian Rules; Difference Formulae. (15 Marks) • Numerical Ordinary Differential Equations: Euler’s Method; Modified Euler’s Methods; Runge-Kutta Methods. (10 Marks)

Texts: Text to be followed: S. Baskar and S. Sivaji Ganesh, Introduction to Numerical Analysis, Lecture notes. (a soft copy will be provided). Other References: (1) K. Atkinson and W. Han, Elementary Numerical Analysis (3rd edition), Wiley-India, 2004. (2) S. D. Conte and C. de Boor, Elementary Numerical Analysis - An Algorithmic Approach (3rd edition), McGraw-Hill, 1981. (3) R. L. Burden and J. D. Faires, Numerical Analysis: Theory and Applications, Ceneage Learning India Pvt. Ltd., 2010.

1

Lectures and Tutorials We will have two lectures of one and a half hours each, and one tutorial session of at least one hour duration, every week. Since the class size is quite large, it may be difficult for us to give you the kind of personal attention that is ideal. Therefore, the onus is on you to be attentive in the class and make the best use of the lectures. It may not be possible for you to take down the class notes; in fact it is not necessary as the lecture notes will be uploaded on the moodle site for the course. These notes are intended to serve as a supplement to the lectures of MA 214, spring semester 2018-19. From the examination point of view, it is enough for a student to study only these lecture notes. However, these lecture notes are by no means a substitute for a text book. You are strongly encouraged to read the text books for a better understanding of the subject. The tutorials are meant for you to practise problem solving. You are expected to try the problems from the relevant tutorial sheet before coming to the class. You should also make use of the tutorial hour to clear your doubts with the course associate. More problems are given as exercises at the end of each chapter in the lecture notes. These exercise problems may not be discussed in the tutorial classes, but may have weightage in the quizzes and the examinations. We strongly recommend students to attend the classes regularly and study systematically from day one. You are, of course, welcome to approach the course instructor or your course associate for any guidance or assistance regarding the course.

Policy on Attendance Attendance in the lectures and tutorials is compulsory. Students who do not meet 80% attendance requirement will be given an DX grade. In case you miss lectures for valid (medical) reasons, get a medical certificate (issued only by the IIT hospital) and keep it with you. You have to submit it if you fall short of attendance. Note: If you are falling short of attendance (i.e. your attendance is less than 80%), then you have to submit medical certificates for all the classes (tutorials) that you missed.

Evaluation Plan (1) There will be three quizzes common to both the sections. These quizzes will be of one hour duration and they will carry 15 marks each. Dates and timings for the quizzes will be announced in the class. (2) The Mid-semester examination, scheduled to be held between 22nd and 28th February 2019, will be for 25 marks. The End-Semester examination, scheduled to be held between 22nd April and 5th May 2019, will be for 40 marks. Dates and timings for these examinations will be announced in the class. (3) Make-up examination will be conducted after the last day of instructions for those who produce the medical certificate issued by the institute hospital or with valid rea2

sons as per the institute rules. Syllabus for make-up examination will be the full syllabus of the course. This examination will be for 40 marks, which will be suitably scaled.

Grading Scheme (1) AP will be awarded if the total marks is greater than or equal to 100. (2) Let M = 40% of the highest mark that is less than 100. DD will be awarded if the total marks lie in the interval [M, M + 5]. FR will be awarded if the total marks is strictly less than M. (3) Other grades are decided relatively.

Schedule of Lectures and Tutorials See the institute timetable.

3

4

Tutorial Sheet 1

Mathematical Preliminaries (1) Let L be a real number and let {an } be a sequence of real numbers. If there exists a positive integer N such that |an − L| ≤ µ|an−1 − L|, for all n ≥ N and for some fixed µ ∈ (0, 1), then show that an → L as n → ∞. (2) Show that the equation sin x + x2 = 1 has at least one root in the interval [0, 1]. (3) Let f be continuous on [a, b], let x1 , · · · , xn be points in [a, b], and let g1 , · · · , gn be real numbers having same sign. Show that n ! i=1

n ! f (xi )gi = f (ξ) gi , for some ξ ∈ [a, b]. i=1

(4) Let f : [0, 1] → [0, 1] be a continuous function. Prove that the equation f (x) = x has at least one root lying in the interval [0, 1] (Note: A root of this equation is called a fixed point of the function f ). (5) Let g be a continuously differentiable function (C 1 function) such that the equation g(x) = 0 has at least n distinct real roots. Show that the equation g ′ (x) = 0 has at least n − 1 distinct real roots. (6) Prove the second mean value theorem for integrals. Does the theorem hold if the hypothesis g(x) ≥ 0 for all x ∈ R is replaced by g(x) ≤ 0 for all x ∈ R. (7) In the second mean-value theorem for integrals, let f (x) = ex , g(x) = x, x ∈ [0, 1]. Find a point c specified by the theorem and verify that this point lies in the interval (0, 1). (8) Obtain the Taylor polynomials T1 and T5 for the function f (x) = sin(x) about the point a = 0. Give the remainder term in both the cases and obtain their remainder estimates when x ∈ [0, 1]. (9) Prove or disprove: " # 1 n+1 =O (i) as n → ∞ 2 n n

" # 1 1 =o (ii) as n → ∞ ln n n

(10) Assume that f (h) = p(h) + O(hn ) and g(h) = q(h) + O(hm ), for some positive integers n and m, and as h → 0. Find a positive integer r such that f (h) + g(h) = p(h) + q(h) + O(hr ),

5

h → 0.

Tutorial Sheet 2 Error Analysis

(1) Let X be a sufficiently large number which results in an overflow of memory on a computing device. Let x be a sufficiently small number which results in underflow of memory on the same computing device. Then give the output of the following operations: (i) X × x (ii) X/X (iii) x/x (iv) 3 × X (v) 3 × x (vi) x/X (2) Consider a computing device having exponents e in the range m ≤ e ≤ M, m, M ∈ Z. If the device uses n-digit rounding binary floating-point arithmetic, then show that δ = 2−n is the machine epsilon when n ≤ |m| + 1. (3) Let x, y, and z be real numbers whose floating point approximations in a computing device coincide with x, y, and z , respectively. Show that the relative error in computing x(y + z) equals #1 + #2 − #1 #2 , where #1 = Er (fl(y + z)) and #2 = Er (fl(x × fl(y + z ))). (4) Let # = Er (fl(x)). Show that |#| ≤ 10−n+1 if the computing device uses n-digit (decimal) chopping. Can the equality hold in the above inequality? (5) Let xA = 3.14 and yA = 2.651 be obtained from the numbers xT and yT , respectively, using 4-digit rounding. For any such values of xT and yT , f ind the smallest interval that contains (i) xT + yT (ii) xT /yT . (6) Let x < 0 < y be such that the approximate numbers xA and yA has seven and nine significant digits with x and y respectively. Show that zA := xA − yA has at least six significant digits when compared to z := x − y. (7) Let xT be a real number. Let xA = 2.5 be an approximate value of xT with an absolute error at most 0.01. The function f (x) = x3 is evaluated at x = xA instead of x = xT . Estimate the resulting absolute error. (8) Check for stability of computing the function h(x) =

sin2 x 1 − cos2 x

for values of x very close to 0. Run the following statement in Matlab and see the output: x=10^(-7.97); h=sin(x)^2/(1-cos(x)^2) Also, try with some non-negative number less than x, for instance, x = 10−8 . Note that for any x ∈ R, h(x) = 1.

6

Tutorial Sheet 3 Numerical Linear Algebra (Direct Methods)

(1) Solve the following system of linear equations using modified Gaussian elimination method with partial pivoting using infinite precision arithmetic: x1 − x2 + 3x3 = 2, 3x1 − 3x2 + x3 = −1, x1 + x2 = 3. (2) Count the number of operations involved in finding a solution using naive Gaussian elimination method to the following special class of linear systems having the form a11x1 + · · · +a1n xn = b1 , ··· ··· an1 x1 + · · · +ann xn = bn , where aij = 0 whenever i − j ≥ 2. In this exercise, we assume that the naive Gaussian elimination method has been implemented successfully. You must take into account the special nature of the given system. (3) Use Thomas method to solve the tri-diagonal system of equations 2x1 + 3x2 = 1, x 1 + 2x2 + 3x3 = 4, x2 + 2x3 + 3x4 = 5, x 3 + 2x4 = 2. (4) Prove or disprove the following statements: (i) An invertible matrix has at most one Doolittle factorization. (ii) If a singular matrix has a Doolittle factorization, then the matrix has at least two Doolittle factorizations. (5) Prove that if an invertible matrix A has a LU -factorization, then all principal minors of A are non-zero. Show that the matrix ⎛ ⎞ 2 2 1 ⎝1 1 1 ⎠ 3 2 1 is invertible but has no LU factorization. Do a suitable interchange of rows to get an invertible matrix, which has an LU factorization.

(6) Use Cholesky factorization to solve the system of equations x1 − 2x2 + 2x3 = 4, −2x1 + 5x2 − 3x3 = −7, 2x1 − 3x2 + 6x3 = 10. 7

Tutorial Sheet 4 Numerical Linear Algebra (Matrix Theory and Iterative Methods)

(1) Show that the norm defined on the set of all n × n matrices by ∥A∥ := max |aij | 1≤i≤n 1≤j≤n

is not subordinate to any vector norm on Rn . (2) Let A be an invertible matrix. Show that its condition number κ(A) satisf ies κ(A) ≥ 1. (3) Let A be an n × n matrix with real entries. Let κ2 (A) and κ∞ (A) denote the condition numbers of the matrix A that are computed using the matrix norms ∥A∥2 and ∥A∥∞ , respectively. Answer the following questions. (i) Determine all the diagonal matrices such that κ∞ (A) = 1. (ii) Let Q be a matrix such that QT Q = I (such matrices are called orthogonal matrices). Show that κ2 (Q) = 1. (4) In solving the system of equations Ax = b with matrix " # 1 2 A= , 1 2.01 estimate the relative error in the solution vector x in terms of the relative error in b. Test your estimate in the case when b = (4, 4)T and b˜ = (3, 5)T . Use the maximum norm for vectors in R2 . (5) Let A and A˜ be non-singular square matrices, and b = 0. If x and x˜ are the solutions ˜x = b, respectively, then show that of the systems Ax = b and A˜ ˜ ∥A − A∥ x − x∥ ∥˜ ≤ κ(A) . x∥ ∥˜ ∥A∥

(6) Find the n × n matrix B and the n-dimensional vector c such that the Gauss-Seidal method can be written in the form x(k+1) = B x(k) + c,

k = 0, 1, 2, · · · .

(7) Spectral radius of a square matrix A is defined as ρ(A) := max |λj |, where λj ’s are j=1,··· ,n

the eigenvalues of A. (i) For any subordinate matrix norm ∥ · ∥, show that ρ(A) ≤ ∥A∥. (ii) If A is invertible and if an iterative method of the form x(k+1) = Bx(k) +c converges to the solution of Ax = b for any initial guess x(0) and any vector b, then show that ρ(B) < 1. 8

(8) Write the formula for the Jacobi iterative sequence of the system 7x1 − 15x2 − 21x3 = 2, 7x1 − x2 − 5x3 = −3, 7x1 + 5x2 + x3 = 1. Without performing the iterations, show that the sequence does not converge to the exact solution of this system. Can you make a suitable interchange of rows so that the resulting system is diagonally dominants? (9) Let x(7) be the 7th term of the Gauss-Seidel iterative sequence for the system 3x1 + 2x2 = 1 4x1 + 12x2 + 3x3 = −2 x1 + 3x2 − 5x3 = 3 with x(0) = (0, 0, 0)T . If x denotes the exact solution of the given system, then show that ∥e(7)∥∞ ≤ 0.058527664∥x∥∞ .

9

Tutorial Sheet 5

Numerical Linear Algebra (Power Method)

(1) The matrix ⎞ ⎛ 2 0 0 A = ⎝ 2 1 0⎠ 3 0 1 has eigenvalues λ1 = 2, λ2 = 1, and λ3 = 1 and the corresponding eigenvectors may be taken as v1 = (1, 2, 3)T , v2 = (0, 2, 3)T , and v3 = (0, 3, 2)T . Perform 2 iterations to find the eigenvalue and the corresponding eigen vector to which the power method converges when we start the iteration with the initial guess x(0) = (0, 0.5, 0.75)T . Without performing the iteration, find the eigenvalue and the corresponding eigenvector to which the power method converges when we start the iteration with the initial guess x(0) = (0.001, 0.5, 0.75)T . Justify your answer. (2) The matrix

⎞ 4/3 1/3 1/3 A = ⎝ −4/3 −1/3 11/3⎠ 2 2 −2 ⎛

has eigenvalues λ1 = −4, λ2 = 2, and λ3 = 1 with corresponding eigenvectors v1 = (0, −1, 1)T , v2 = (1, 1, 1)T , and v3 = (−1, 1, 0)T . To which eigenvalue and the corresponding eigenvector does the power method converge if we start with the initial guess x(0) = (3, −1, 1)? Justify your answer without performing the iterations. (3) Use Gerschgorin circle theorem to determine the intervals in which the eigenvalues of the matrix ⎞ ⎛ 0.5 0 0.2 3.15 −1 ⎠ . A=⎝ 0 0.57 0 −7.43

lie, given that all eigenvalues of A are real. Show that the power method can be applied for this matrix to find the dominant eigenvalue without computing eigenvalues explicitly.

(4) Use the Gerschgorin circle theorem to find the lower and the upper bounds for the absolute values of the eigenvalues of the following matrices: ⎛ ⎞ ⎞ ⎛ 7 −1 4 6 2 1 (ii) ⎝ 3 −6 −1 ⎠ (i) ⎝1 −5 0 ⎠ −1 1 5 2 1 4 Also, find the optimum bounds in each case.

10

Tutorial Sheet 6 Nonlinear Equations (Bisection, Regula-Falsi, and Secant Methods)

(1) Let the bisection method be used to solve the nonlinear equation 2x6 − 5x4 + 2 = 0 starting with the initial interval [0, 1]. In order to approximate a solution of the nonlinear equation with an absolute error less than or equal to 10−3 , what is the number of iterations required as per the error estimate of the bisection method? Perform three iterations. (2) Let bisection method be used to solve a nonlinear equation f (x) = 0 starting with the initial interval [a0 , b0 ] where a0 > 0. Let xn be as in the bisection method, and r be the solution of the nonlinear equation f (x) = 0 to which bisection method converges. Let # > 0. Show that the relative error of xn w.r.t. r is at most # whenever n satisfies n≥

log(b0 − a0 ) − log # − log a0 . log 2

What happens if a0 < 0 < b0 ? (3) Let {xn } be the iterative sequence defined by the regula-falsi method for the equation f (x) = 0. If f (xn ) < 0 for all n = 1, 2, · · · and xn → α, then show that f (α) = 0. (4) Discuss some instances where the secant method fails. Note that failure of secant method results from one of the following two situations: (i) the iterative sequence is not well-defined, and (ii) the iterative sequence does not converge at all. (5) Let {xn } be the iterative sequence generated by the secant method that converges to a root r of the equation f (x) = 0. If f ′ (r) = 0, then show that r − xn = αn (xn+1 − xn ), where αn → 1 as n → ∞. (6) Consider the equation x2 − 6x + 5 = 0. (i) Taking x0 = 0 and x1 = 4.5, generate first 7 terms of the iterative sequence of the secant method. (ii) Take the initial interval as [a0 , b0 ] = [0, 4.5], generate the first 7 terms of the iterative equations of the regula-falsi method. Observe to which roots of the given equation does the above two sequences converge?

11

Tutorial Sheet 7 Nonlinear Equations (Newton-Raphson and Fixed-point Methods)

(1) Newton-Raphson method is to be applied for approximating a root of the equation sin x = 0. Let α ∈ (−π/2, π/2) and α =  0 be such that if x0 = α, then the iteration becomes a cycle i.e., α = x0 = x2 = · · · = x2k = x2k+2 = · · · ,

x1 = x2 = · · · = x2k+1 = x2k+3 = · · ·

Find a non-linear equation g(y) = 0 whose solution is α. (2) Let {xn } be the iterative sequence defined by the Newton-Raphson method for the equation f (x) = 0 and r be a root of this equation such that f ′ (r) = 0. If x0 is chosen such that xn → r as n → ∞, then show that for each n = 1, 2, · · · there exists a ξn between xn and r such that r − xn+1 = −

f ′′(ξn ) (r − xn )2 . 2f ′ (xn )

[Note: This shows that the Newton-Raphson method converges quadratically] (3) Give an example of a function f : R → R such that the equation f (x) = 0 has an isolated real root with the condition that the Newton-Raphson method converges but does not have quadratic convergence. (4) To solve the nonlinear equation e−x − cos x = 0 by f ixed-point iteration method, the following fixed-point formulations may be considered. (i) x = − ln(cos x) (ii) x = cos−1 (e−x ) Discuss about convergence of the fixed-point iterative sequences generated by the two formulations. (5) Let α ∈ R and β ∈ R be the roots of x2 + ax + b = 0, and such that |α| > |β|. Let g and h be two iterating functions satisfying the hypothesis of the theorem on fixed-point method. Consider the iterative sequences {xn } and {yn } corresponding to two the iterating functions g and h given by xn+1 = −

b axn + b , and yn+1 = − yn + a xn

respectively. Show that the iterative sequences {xn } and {yn } converge to α and β respectively. (6) Let {xn } ⊂ [a, b] be a sequence generated by a f ixed point iteration method with a continuously differentiable iteration function g(x). If this sequence converges to x∗ , then show that λ |xn+1 − xn |, |xn+1 − x∗ | ≤ 1−λ where λ := max |g ′ (x)|. (This estimate helps us to decide when to stop iterating if we x∈[a,b]

are using a stopping criterion based on the distance between successive iterates.)

12

Tutorial Sheet 8 Interpolation

(Lagrange and Newton Formulae and Errors)

(1) Using Lagrange form of interpolating polynomial for the function g(x) = 3x2 + x + 1, express the following rational function as a sum of partial fractions: f (x) =

3x2 + x + 1 . (x − 1)(x − 2)(x − 3)

(2) Find the Newton form of interpolating polynomial for the data x y

-3 -1 0 3 5 . -30 -22 -12 330 3458

1 (3) Calculate the nth divided difference f [x0 , x1 , · · · , xn ] of f (x) = . x (4) Prove that if we take any set of 23 nodes in the interval [−1, 1] and interpolate the function f (x) = cosh x with a polynomial p22 of degree less than or equal to 22, then at each x ∈ [−1, 1] the relative error satisfies the bound |f (x) − p22(x)| ≤ 5 × 10−16. |f (x)| (5) If f ∈ C n+1[a, b] and if x0 , x1 , · · · , xn are distinct nodes in [a, b], then show that there exists a poi...