Homework 2 Solution

Description

Please submit to CANVAS a .zip le that includes the following functions:

chord method.m

Newton method.m

test zero.m

For the extra credit part, please scan your notes into a PDF le proof.pdf and attach it to your submission.

Exercise 1 Write two functions chord method.m and Newton method.m implementing, respectively, the chord and the Newton methods to nd the zeros of nonlinear (scalar) equations. The functions should be of the following form

function [z0,iter,res,his] = chord method(fun,a,b,tol,Nmax)

function [z0,iter,res,his] = Newton method(fun,dfun,x0,tol,Nmax)

Inputs:

fun: function handle representing f(x)

a, b: interval [a; b] in which we believe there is a zero

tol: maximum tolerance allowed for the increment jx^(k+1) x^(k)j

Nmax: maximum number of iterations allowed

dfun: function handle representing df(x)=dx (Newton method)

x0: initial guess for the zero (Newton method)

Outputs:

z0: approximation of the zero z₀

iter: number of iterations to obtain z₀

res: residual at z₀ (i.e., jf(z₀)j)

his: vector collecting all the elements of the sequence fx^(k)g_k=0;1;:: (convergence history)

Both functions should return the numerical approximation of the zero when the increment at iteration k +1 is such that jx^(k+1) x^(k)j < tol or when the iteration number reaches the maximum value Nmax.

Exercise 2 Use the functions of Exercise 1 to compute an approximation of the smallest zero of the fth-order Chebyshev polynomial

f(x) = 16x5 20x3 + 5x;

x 2 [ 1; 1]:

(1)

To this end, set tol=10 ¹⁵, Nmax=20000, a= 0:99, b= 0:9, x0= 0:99 and write a function test zero.m that returns the aforementioned approximate zero by using the chord and the Newton methods. The function should be of the form

function [zc,zn,ec,en,x,f] = test zero()

Outputs:

zc, zn: zero obtained with the chord method (zc) and the Newton method (zn).

ec, en: error vectors with components jx^(k) z₀j (k = 0; 1; :::) generated by the cord method (ec)

and the Newton method (en): z₀ = cos(9 =10) is the exact zero of (1) in the interval [ 1; 0:9], while x^(k) is the sequence converging to z₀ generated by the chord or the Newton method.

x: row vector of 1000 evenly spaced nodes in [ 1; 1] including the endopoints.

f: row vector representing the function (1) evaluated at x.

The function test zero() should also produce the following three gures

1.	The graph of the function (1) in figure(1).
2.	The plots of the convergence histories, i.e., the errors ek = jx(k) z0j versus k for the chord
	and the Newton methods. These two plots should be in the same figure(2), and in a semi-log
	scale (use the command semilogy).
3.	The plots of ek+1 = jx(k+1) z0j (y-axis) versus ek = jx(k) z0j (x-axis) in a log-log scale (use
	the command loglog) for the chord and the Newton methods. These plots should be in the
	same figure(3). Remember, for su ciently large k, the slope of the curves in such log-log
	plots represents the convergence order of the sequences.

Extra Credit Let f 2 C⁽¹⁾([a; b]) be a real valued function, 2 [a; b] such that f( ) = 0 and f⁰( ) 6= 0 (simple zero). By using the theory of xed point iterations prove that the convergence order of the sequence

2