Newton's method is a fixed point iteration (FPI) method, so here you use your work from Lab2A on FPI to help implement Newton's method: f(xk) ACK f'(xk) (2) Xk+1 = Ik + A.2k (3) Note that in this Lab you will be storing values in vectors with components xk (or in Matlab notation x(k)). The header below outlines what your code should take as input and output: function [x, flag]=mynewton (f, fx, x0, tol, maxiter) $ Function file: mynewton.m Author: % Date: % Purpose: Compute approximate solution to f(x)=0 via Newton's method 8 & Input arguments: 8 f -- A function handle for the function f(x) being solved. 8 fx -- A function handle for the derivative f'(x) $ x0 Initial guess for the solution $ tol -- Tolerance wanted in the solution. maxiter Maximum number of iterations. & Output arguments: X -- Vector containing the iterates of the Newton's method. % flag -- Flag specifying if solution obtained within the tolerance, it should take the values: = The number of iterations taken to converge. = -1 If the algorithm has not converged in maxiter iterations. $ Note that you should implement this incrementally, not trying to add all the conditions at once, since this is much harder to debug. For example just start with the main loop and the maxiters stopping condition. Testing your code To ensure that your function mynewton is working correctly, you should test the function on some problems which you know the solution for. For example, the function f(x) = (x + 1)(x 1/2) has roots at x = -1 and x = 1/2, and the derivative is f'(x) = 2x +1/2. Thus, the MATLAB code 1 f=@ (x) (x+1).*(x-1/2); df = m ( x ) 2*x+1/2; [x1, f1]=mynewton (f, df, -1.2,0.001, 10); [x2 , f1]=mynewton(f, df, 0.6,0.001 , 10); should give output vectors xl and x2 of the iterates that yield 21 7-1 and 22 ~0.5. Ik+1 You will also need to look at the order of convergence a, as discussed in lectures, we have x* lekti! |xk x*la lekla multiplying by the denominator and taking logarithms gives, (4) loge lek+1 a loge lekl + loge (C) (5) which is a linear model in loge lekwith slope a and intercept log C. For your Newton method do the following, on your example: Plot the logarithms of the errors against each other. By hand draw what you think is the line which best fits the data. Estimate the slope of the line (the order of convergence) and compare it to the expected value. Do the different schemes meet expectations for their relative order of convergence? Why or why not? Newton's method is a fixed point iteration (FPI) method, so here you use your work from Lab2A on FPI to help implement Newton's method: f(xk) ACK f'(xk) (2) Xk+1 = Ik + A.2k (3) Note that in this Lab you will be storing values in vectors with components xk (or in Matlab notation x(k)). The header below outlines what your code should take as input and output: function [x, flag]=mynewton (f, fx, x0, tol, maxiter) $ Function file: mynewton.m Author: % Date: % Purpose: Compute approximate solution to f(x)=0 via Newton's method 8 & Input arguments: 8 f -- A function handle for the function f(x) being solved. 8 fx -- A function handle for the derivative f'(x) $ x0 Initial guess for the solution $ tol -- Tolerance wanted in the solution. maxiter Maximum number of iterations. & Output arguments: X -- Vector containing the iterates of the Newton's method. % flag -- Flag specifying if solution obtained within the tolerance, it should take the values: = The number of iterations taken to converge. = -1 If the algorithm has not converged in maxiter iterations. $ Note that you should implement this incrementally, not trying to add all the conditions at once, since this is much harder to debug. For example just start with the main loop and the maxiters stopping condition. Testing your code To ensure that your function mynewton is working correctly, you should test the function on some problems which you know the solution for. For example, the function f(x) = (x + 1)(x 1/2) has roots at x = -1 and x = 1/2, and the derivative is f'(x) = 2x +1/2. Thus, the MATLAB code 1 f=@ (x) (x+1).*(x-1/2); df = m ( x ) 2*x+1/2; [x1, f1]=mynewton (f, df, -1.2,0.001, 10); [x2 , f1]=mynewton(f, df, 0.6,0.001 , 10); should give output vectors xl and x2 of the iterates that yield 21 7-1 and 22 ~0.5. Ik+1 You will also need to look at the order of convergence a, as discussed in lectures, we have x* lekti! |xk x*la lekla multiplying by the denominator and taking logarithms gives, (4) loge lek+1 a loge lekl + loge (C) (5) which is a linear model in loge lekwith slope a and intercept log C. For your Newton method do the following, on your example: Plot the logarithms of the errors against each other. By hand draw what you think is the line which best fits the data. Estimate the slope of the line (the order of convergence) and compare it to the expected value. Do the different schemes meet expectations for their relative order of convergence? Why or why not