how to find the order of convergence

for the function h(x)=53/162+sin(x-1/3)-(17/18)*(x)-(1/6)*x^2+(1/6)*x^3，how to display the order of convergence(using newton method)?

[J. Alex Lee]

your question is unclear...are you trying to solve h(x)=0 for x with Newton's method?

[kevin liu]

yes!

[J. Alex Lee]

Have you already gone about solving with Newton's method? When you do, keep track of the residuals and solution updates. Quadratic convergence would be residual value roughly halving every step. As Jan notes, you need to track this only for steps close to the actual solution otherwise order of convergence doesn't mean much.

Answer 1

[Jan]

The convergence of the Newton methods depends on the initial value. There is no general order of convergence. For some start values the method does not converge at all.

[J. Alex Lee]

Newton's method should nominally have quadratic convergence near the root(s) where the linearized approximation is "good". Sure, if you start far from the root (and Newton's method succees), you may locally have worse convergence far away, but there the premise of "linear is good approximation" is less valid so I guess it is a matter of semantics if you want to call that order of convergence?

[kevin liu]

if the initial value is 0, then how to find the order of convergence?(as i compute, the root for this function is about 0.33,using initial value 0)

Answer 2

[J. Alex Lee]

It sounds like you already implemented Newton's method, so just save all your residuals and plot [the log of norm] versus the previous values. The slope of the best fit in the linear region (close to zero) should be order of convergence.

r = nan(MaxIter,1)
for k = 1:MaxIter
    % newton iterations
    r(k) = % residual calculation
end

ar = abs(r)

% need to filter values of r that are too big or too small...empirically,
% this works for me
mask = ar > 1e-1 | ar < 1e-12
ar(mask) = []

w = ar(1:end-1)
z = ar(2:end)

plot(w,z,'o')
pf = polyfit(w,z,1)
OrderConv = pf(1)