Homework 2 Solution

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 z0

iter: number of iterations to obtain z0




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




his: vector collecting all the elements of the sequence fx(k)gk=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.







1






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 15, 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) z0j (k = 0; 1; :::) generated by the cord method (ec)




and the Newton method (en): z0 = cos(9 =10) is the exact zero of (1) in the interval [ 1; 0:9], while x(k) is the sequence converging to z0 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(1)([a; b]) be a real valued function, 2 [a; b] such that f( ) = 0 and f0( ) 6= 0 (simple zero). By using the theory of xed point iterations prove that the convergence order of the sequence







x(k+1)
= x(k)


f(x(k))
f0(x(k))







f


f(x(k)




x(k)
)


f0(x(k))
(2)


f0(x(k))











is 3 in a suitable neighborhood of .






2