DUE DATE: APRIL 3, 2013
Your Assignment
In this assignment, we will be investigating convergence of Newton's Method for the function f(x)=x3 - 3x + 3.
Plot the function and show clearly (by hand) using methods of Calculus why there must be exactly one root (or zero) of the function.
Revise the code below to use the function above with its derivative and consider the convergence of Newton's Method to the root for the following initial guesses x0:
x0= -3
x0= -2
x0= -1
x0= 0
x0= 2
x0= 1.2458005565
Provide the plot (on REASONABLE axes) and relevant printout for each case and discuss the convergence for each case (No more than two sentences in each case).
The following MATLAB code should be quite useful for the assignment.
% MATLAB assignment 3 - Newton's method
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% First, define the function we wish to find a zero for
f = @(x) x.^2; % = x^2
% Next define the derivative df/dx. Usually this would be
% estimated by picking a small number dx and using
% df/dx ~ [f(x+dx) - f(x)]/dx
% OR
% df/dx ~ [f(x+dx) - f(x-dx)]/(2dx)
% You can just enter the formula for df/dx.
dfdx = @(x) 2*x;
% set the maximum number of iterations of the method to use
max_iteration_count = 20;
% set aside space for Xn, f(Xn), and f'(Xn)
Xn = zeros(1,max_iteration_count + 1); % The '+1' is for X0
FXn = zeros(1,max_iteration_count);
dFXn = zeros(1,max_iteration_count);
% set the initial estimate X0
Xn(1) = -0.5;
% stopping criteria - if Xn changes by less than DX, then stop iterations
% we are assuming that this indicates convergence of the Xn
DX = 0.0001;
% for graphing
plot_title = 'student name x0=???'; % put your name at the top of the graph
my_xlim = [-2,2]; % how much should we show on the x axis?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% you should not need to modify anything after this point
% you should, however, look through the code to see what it does
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% iterate through Newton's method
% note that because 'i' represents the square root of -1, it
% should never be used as a variable in your MATLAB programs
plot_to = max_iteration_count; % there is a chance that Newtons method will fail
% at some point, if so, we do not need the extra
% data in our plot or table
for ind = 1:max_iteration_count
FXn(ind) = f(Xn(ind)); % f(Xn)
dFXn(ind) = dfdx(Xn(ind)); % df/dx(Xn)
if abs(dFXn) < eps
% Newton's method fails if df/dx(Xn)=0. 'eps' is just a very small
% number to see if the derivative is about zero
plot_to = ind-1;
fprintf('The derivative vanishes at iteration %1i.\n Terminating the procedure.\n',ind);
break;
else
% if df/dx(Xn) is not zero, continue with the method
Xn(ind + 1) = Xn(ind) - FXn(ind)/dFXn(ind); %X(n+1) = Xn - f(Xn)/df/dx(Xn)
% check stopping criteria
if abs( Xn(ind+1) - Xn(ind) ) < DX
plot_to = ind;
break;
end
end
end
% Print a table with Xn, f(Xn), and f'(Xn)
fprintf(' n Xn f(Xn) df/dx(Xn)\n')
fprintf('--- --------- -------- ----------\n')
for ind = 1:plot_to
fprintf(' %1i %1.4f %1.4f %1.4f\n',ind-1,Xn(ind),FXn(ind),dFXn(ind));
end
fprintf(' %1i %1.4f -- --\n',plot_to,Xn(plot_to+1));
% create data for plotting the function
x = linspace(my_xlim(1),my_xlim(2),200);
y = f(x);
% open a new plot
figure;
% plot the function
plot(x,y,'k');
% plot the steps of Newtons method starting with blue and transitioning
% to red
if plot_to > 0
hold on;
for ind = 1:plot_to
plot([Xn(ind),Xn(ind),Xn(ind+1)],[0,f(Xn(ind)),0],'-o','Color',[ind/plot_to,0,1-ind/plot_to],'MarkerSize',4);
end
hold off;
else
plot(Xn(1),f(Xn(1)),'or');
end
grid on;
xlim(my_xlim);
% add descriptors in a legible font
set(gca,'FontSize',13)
title(plot_title);
xlabel('x');
ylabel('y');
Last update: 2/7/13