CMPS 251 Homework Assignment 4, Fall 2015

CMPS 251-Numerical Computing Assignment 4 Due Monday, November 9, 2015 Reading Material: - Cheney & Kincaid: Sections 3.1-3.3 Notes: You are encouraged in work individually on the assignment. Piazza can be used to ask questions (without requesting a solution !!). Problem 1 Practicing with root finding techniques Consider the following function f(x) = x − 2e−x. Determine the root of this equation using the following 1) Bisection method starting with a = 0 and b = 1. Show the first three iterations. 2) Regula Falsi method starting with a = 0 and b = 1. Show the first three iterations. 3) Secant method starting with x0 = 0 and x1 = 1. Show the first three iterations. 4) Newton method starting with x0 = 1. Show the first three iterations. Now find the exact value in MATLAB either using the fzero() command or using the following lines of code syms x f=x-2*exp(-x); t=solve(f==0); t=eval(t) Calculate the relative error between the exact solution and the value obtained after three itera- tion. Comment on the results. Problem 2 System of nonlinear equations Using the Taylor series in two variables (x, y) of the form f(x + h, y + k) = f(x, y) + hfx(x, y) + kfy(x, y) + · · · where fx = ∂f/∂x and fy = ∂f/∂y, establish that Newton’s method for solving the two simul- taneous nonlinear equations { f(x, y) = 0 g(x, y) = 0 can be described with the following formulas xn+1 = xn − fgy − gfy fxgy − gxfy yn+1 = yn − fxg − gxf fxgy − gxfy Here, the functions f, fx, fy, g, gx, and gy are evaluated at (xn, yn). Now consider the following system of nonlinear equations { −2x3 + 3y2 + 42 = 0 5x2 + 3y3 − 69 = 0 1 With a sharp eye �, we find that the exact solution is x = 3, y = 2. Now, you need to solve it numerically. 1) Use Newton’s method starting with x0 = 1 and y0 = 1. Show the first five iterations. Note that you can use the expressions derived above or the approach discussed in the slides (both are equivalent). 2) Use fixed point iterations. Use the following iteration function yn+1 = (−5x2 n + 69 3 )1/3 xn+1 = (3y2 n + 42 2 )1/3 starting with x0 = 1 and y0 = 1. Show the first five iterations. Problem 3 Convergence of the fixed point iteration In class, we argued that the fixed point iteration technique converges if, in the region of in- terest, |g′(x)| < 1. In other words, convergence occurs if the magnitude of the slope of g(x) is less than the slope of the line y = x. The purpose of this problem is to prove this criterion. To this end, try to establish the relation en+1 = g′(ξ)en and then deduce the convergence criterion. The following properties are useful • xn+1 = g(xn) and r = g(r) (root of the equation which is a fixed point) • ei = r − xi • Mean value theorem: If f(x) is a continuous function on the closed interval [a, b] and differentiable on the open interval (a, b), there exists a number ξ such that a < ξ < b and f′(ξ) = f(b) − f(a) b − a Problem 4 MATLAB: Moler-Morrison algorithm This is a typical MATLAB exam problem ! Computing an approximation to √ x2 + y2 does not require square roots. It can be done as follows: real function f(x, y) integer n; real a, b, c, x, y f ← max {|x|, |y|} a ← min {|x|, |y|} for n = 1 : 3 b ← (a/f)2 c ← b/(4 + b) f ← f + 2cf a ← ca end for end function f The output of the algorithm is the value of f. Test the algorithm on some simple cases such as (x, y) = (3, 4), (−5, 12), and (7, −24). Then write a routine that uses the func- tion f(x, y) for approximating the Euclidean norm of the vector x = (x1, · · · , xn) given as ||x||2 = √ x2 1 + x2 2 + · · · + x2n. 2 Problem 5 MATLAB: Steffensen’s method Steffensen’s method is a scheme for finding a numerical solution of an equation of the form f(x) = 0 that is similar to Newton’s method but does not require the derivative of f(x). The solution process starts by choosing a point x0, near the solution, as the first estimate of the solution. The next estimates of the solution xn+1 are calculated by: xn+1 = xn − (f(xn))2 f(xn + f(xn)) − f(xn) Write a MATLAB user-defined function that solves a nonlinear equation with Steffensen’s method. Name the function Xs = SteffensenRoot(Fun, Xest), where the output argument Xs is the numerical solution. The input argument Fun is a name for the function that calculates f(x) for a given x (Remember to use the handle @ when calling the function which you define in a separate script), and Xest is the initial estimate of the solution. The iterations should stop when the estimated relative error given as ��� xn+1−xn xn ��� is smaller than 10−6. The number of iterations should be limited to 100 (to avoid an infinite loop). If a solution with the required ac- curacy is not obtained in 100 iterations, the program should stop and display an error message. Test your code using the function from Problem 1 with a starting point x0 = 1. Display the output at each iteration in a tabulated format with the iteration number, xn, f(xn), and the relative error. Problem 6 OPTIONAL but important The speed of convergence of a root finding technique is a very important parameter. The different proposed algorithms generate a sequence of values {xn, n = 0, · · · , ∞} that converges to a root r. If positive constants α and λ exist with lim n→∞ |xn+1 − r| |xn − r|α = λ then the sequence xn converges to r of order α with asymptotic error constant λ. • If λ = 0, the convergence is superlinear • If λ = 1, the convergence is sublinear • If α = 1 and λ < 1, the convergence is linear • If α = 2 and λ > 0, the convergence is quadratic (α = 3 is cubic, etc.) Determine the order of convergence of the following sequences for r = 0 (a) (1/3)n (b) 10−3·2n (c) n−10 (d) 10−n2 3