2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You did notice that your function is $f(x)=(x-e^{-x})^2$? So that it has a double root at $x=W_0(1)$ and thus the Newton iteration converges linearly with quotient $0.5$. $\endgroup$ – LutzL Feb 12 at 8:20
1
$\begingroup$

This is a frequent error that comes from the error examination of Aitkens method. If you have computed the Aitken extrapolation, you are hopefuller much much closer to the root than any of the p 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 qnext = AitkenStep(g,q)
    q1 = g(q); q2 = g(q1);
    qnext = q-(q1-q).^2./(q2-2*q1+q)
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, you can catch that by checking

qnext = q2
if abs(q2-q1) > 1e-15*(1+abs(q2))
   qnext = ... %Aitken
end

or better check the denominator.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.