[Math] Newton’s Method and Aitken’s Method Convergence

MATLABnewton raphsonnumerical methodsrate-of-convergence

I'm trying to solve this problem in my Numerical Analysis class using MATLAB.

Newton's Method does not converge quadratically for the following problem. Accelerate the convergence using Aitken's $\Delta^2$ method. Iterate until $|q_{n}-q_{n-1}|<10^{-4}$

$x^2-2xe^{-x}+e^{-2x}=0$ , on the interval $[0,1]$

Newton's Method tells us that
The approximation $p_{n+1}$ to a root of $f(x)=0$ is computed from the approximation $p_n$ using the equation

\begin{equation}
p_{n+1}=p_n-\frac{f(p_n)}{f'(p_n)}\label{Newtons},
\end{equation}

provided that $f'(p_n)\neq{0}$.

Aitken's$\Delta^2$ Method says that
If $\{p_n\}^\infty_{n=0}$ is a sequence that converges linearly to $p$, and if
\begin{equation}
q_n=p_n-\frac{(p_{n+1}-p_n)^2}{p_{n+2}-2p_{n+1}+p_n}\label{Aitkens},
\end{equation}

Then $\{q_n\}^\infty_{n=0}$ also converges to $p$, and, in general, more rapidly.

This is what my code looks like so far:

k=500;
TOL=10^-4;
syms x;
f=x^2-2*x*exp(-x)+exp(-2*x);
fp=diff(f);
p(1)=0;
for i=1:3
    p(i+1)=p(i)-subs(f,p(i))/subs(fp,p(i));
end
%we've now stored p(1), p(2), p(3).
%now we can continue on with Aitken's Method.

for i=1:k
    %now we need to calculate for p(3) and beyond, as well as q(i).
    %this next for loop will calculate the next iterations of p(i) after 3
    %and will start calculating q(i).
    
    p(i+3)=p(i+2)-subs(f,p(i+2))/subs(fp,p(i+2));
    q(i)=p(i)-((p(i+1)-p(i))^2/(p(i+2)-2*p(i+1)+p(i)));
    if abs(q(i)-q(i+1))<TOL
        break
    end
end
p(i) %p(i)=0.544876120719794
q(i) %q(i)=0.567189068561896

for p(i) my answer is $0.544876120719794$, and for q(i) I got $0.567189068561896$. It doesn't look like q(i) is converging faster than p(i). I'm unsure if this is the correct way of approaching this problem.

Also, I have a very limited introductory background in MATLAB and programming in general, so apologies if this seems a bit sloppy.

Best Answer

This is a frequent error that comes from the error examination of Aitkens method.

If you have computed the Aitken extrapolation, you are hopefully much closer with $q_n$ to the root than any of the $p_k$ values that entered its computation. So why would you go back to the worse $p$ values to continue the computation instead of restarting it at the much better value?

If you use Aitken to accelerate, then you do not continue the original series. That is, if your original fixed point iteration is $p_{n+1}=g(p_n)$, then the Aitken accelerated sequence is $$ q_{n+1}=q_n-\frac{(g(q_n)-q_n)^2}{g(g(q_n))-2g(q_n)+q_n} $$

So you should do something like

function q = AitkenStep(g,p0)
    p1 = g(p0); p2 = g(p1);
    q = p0-(p1-p0).^2./(p2-2*p1+p0)
end

q(1)=p(1)
for k=1:15
    q(k+1) = AitkenStep(@(x) x-subs(f,x)/subs(fp,x), q(i))
end

Usually you will run into a division-by-zero error before the sixth step,

   k   q(k)
   1   0
   2   6.166121445080276e-01
   3   5.673549747344846e-01
   4   5.671432944634528e-01
   5   NaN

you can catch that by checking

    q = p2
    if abs(p2-p1) > 1e-15*(1+abs(p2))
       q = ... %Aitken
    end

or better check the denominator.

Related Question