Newton's method-numerical analysis

[evinda]

Hello again..! ;) I also wrote a program of the Newton mathod,with the same termination criteria (The program should end if the number of iterations surpass the maximum number of iterations,or if one or both of these conditions :
$$\left | x_{k}-x_{k-1} \right |$$ < ε and $$\left | f(x_{k}) \right |$$ < ε
are valid. )
At the bisection method I found the maximum number of iterations needed so that the method converges,using the formula $$n=log_{2}(\frac{b-a}{ε})$$ (or am I wrong? ).Is there a similar formula to find the maximum number of iterations needed so that the Newton method converges?

 

[chisigma]

Re: Newton method-numerical analysis

Hello again..! ;) I also wrote a program of the Newton mathod,with the same termination criteria (The program should end if the number of iterations surpass the maximum number of iterations,or if one or both of these conditions :
$$\left | x_{k}-x_{k-1} \right |$$ < ε and $$\left | f(x_{k}) \right |$$ < ε
are valid. )
At the bisection method I found the maximum number of iterations needed so that the method converges,using the formula $$n=log_{2}(\frac{b-a}{ε})$$ (or am I wrong? ).Is there a similar formula to find the maximum number of iterations needed so that the Newton method converges?

The convergence of the Newton-Raphson method is strongly dependent from the initial point $x_{0}$. A non properly 'inspired' choice of $x_{0}$ can produce slow convergence or even divergence as described in...

http://mathhelpboards.com/discrete-mathematics-set-theory-logic-15/difference-equation-tutorial-draft-part-i-426.html#post2492

A good strategy is to use a different method [... like the bisection method for example...] to arrive to an 'accurate enough' approximation of the solution and use that as $x_{0}$ for the Newton's iterations...

Kind regards

$\chi$ $\sigma$

 

[I like Serena]

Re: Newton method-numerical analysis

Hello again..! ;) I also wrote a program of the Newton mathod,with the same termination criteria (The program should end if the number of iterations surpass the maximum number of iterations,or if one or both of these conditions :
$$\left | x_{k}-x_{k-1} \right |$$ < ε and $$\left | f(x_{k}) \right |$$ < ε
are valid. )
At the bisection method I found the maximum number of iterations needed so that the method converges,using the formula $$n=log_{2}(\frac{b-a}{ε})$$ (or am I wrong? ).Is there a similar formula to find the maximum number of iterations needed so that the Newton method converges?

Your maximum iteration formula for bisection looks correct. :)

But there is not really such a formula for Newton's method.
Newton's method is a bit unpredictable in that respect.
It may not converge at all, or converge only linearly if it has a duplicated multiple root, or converge slowly if there are a couple of roots close together.

As I know it, the best we can say, is that under "normal" circumstances, it converges quadratically, which is way faster than the bisection method.

 

[evinda]

Re: Newton method-numerical analysis

I understand...thank you both for your help! :)

Could you give me also for the Newton method an example of the results with a specific initial value xo,a specific maximum number of iterations and a specific T0L of the function e^x+x+1,so I can check my output??

Also,could you tell me how I can find the error $$\left | x_{k}-B \right |$$ of the last iteration of the method?? (B is the real solution of the function and $$x_{k}$$ the approximation of the last iteration of the Newton method)

 

[I like Serena]

Re: Newton method-numerical analysis

I understand...thank you both for your help! :)

Could you give me also for the Newton method an example of the results with a specific initial value xo,a specific maximum number of iterations and a specific T0L of the function e^x+x+1,so I can check my output??

Also,could you tell me how I can find the error $$\left | x_{k}-B \right |$$ of the last iteration of the method?? (B is the real solution of the function and $$x_{k}$$ the approximation of the last iteration of the Newton method)

When the method is converging to the root, the remaining error is less than the difference with the last approximation.

With x[0] = -1 and TOL = 0.001, I get:

x[2] = -1.278454624, f(x[2]) = 0.000012681, upper bound for error = 0.009513202.

 

[evinda]

Re: Newton method-numerical analysis

When the method is converging to the root, the remaining error is less than the difference with the last approximation.

With x[0] = -1 and TOL = 0.001, I get:

x[2] = -1.278454624, f(x[2]) = 0.000012681, upper bound for error = 0.009513202.

Nice...I get the same x[2] and f(x[2])!But...How did you find the upper bound for error?

 

[I like Serena]

Re: Newton method-numerical analysis

Nice...I get the same x[2] and f(x[2])!But...How did you find the upper bound for error?

The difference between this approximation and the one before it.
Which error do you have?

 

[evinda]

Re: Newton method-numerical analysis

I had not calculated it before..Now,I found the difference $$\left |x_{k}-x_{k-1} \right |$$ and the result is the same as yours! :D

Last but not least ;) I have to plot the 5 first approximations of the Newton method in Matlab.I am confused now..What do I have to plot??Only the x of each iteration??

 

[I like Serena]

Re: Newton method-numerical analysis

I had not calculated it before..Now,I found the difference $$\left |x_{k}-x_{k-1} \right |$$ and the result is the same as yours! :D

Good!

Last but not least ;) I have to plot the 5 first approximations of the Newton method in Matlab.I am confused now..What do I have to plot??Only the x of each iteration??

Perhaps f(x) versus x?

 

[evinda]

Re: Newton method-numerical analysis

I wrote the following loop in the function:

 for k=1:5
    if (g(x_o)==0)
        return;
    end
    x_1=x_o-f(x_o)/g(x_o);
    t=@(x) g(x_1)*(x-x_1)+f(x_1);
    plot(x_1,f(x_1))
    hold on
    x_o=x_1;  
end

where g the derivative of f.
I don't get a plot.. Where is my error?

 

[I like Serena]

Re: Newton method-numerical analysis

I wrote the following loop in the function:

 for k=1:5
    if (g(x_o)==0)
        return;
    end
    x_1=x_o-f(x_o)/g(x_o);
    t=@(x) g(x_1)*(x-x_1)+f(x_1);
    plot(x_1,f(x_1))
    hold on
    x_o=x_1;  
end

where g the derivative of f.
I don't get a plot.. Where is my error?

Perhaps you should collect the data first in 2 vectors before plotting?

Something like:

N = 5;
x = zeros(N, 1);
fx = zeros(N, 1);
x(1) = x_o;
fx(1) = f(x(1));

for k=2:N
    x(k) = x(k-1)-fx(k-1)/fp(x(k-1));
    fx(k) = f(x(k));
end

plot(x, fx);

Btw, I do not have Matlab.

 

[evinda]

Re: Newton method-numerical analysis

Perhaps you should collect the data first in 2 vectors before plotting?

Something like:

N = 5;
x = zeros(N, 1);
fx = zeros(N, 1);
x(1) = x_o;
fx(1) = f(x(1));

for k=2:N
    x(k) = x(k-1)-fx(k-1)/fp(x(k-1));
    fx(k) = f(x(k));
end

plot(x, fx);

Btw, I do not have Matlab.

I ran your code and the result is just one line...

 

[I like Serena]

Re: Newton method-numerical analysis

I ran your code and the result is just one line...

That sounds about right for exp(x)+x+1 and an initial value of x = -1. ;)
Try it with x = 5.
Then you should get a curve.

Btw, I guess your original code should work as well??

 

[I like Serena]

Re: Newton method-numerical analysis

If you want, you might also draw a line from (x[k], f(x[k])) to (x[k+1], 0).
And perhaps another one from (x[k+1], 0) to (x[k+1], f(x[k+1])).

Those lines show how the algorithm works: the tangent line at x[k] is used to find the next approximation (where it intersects the x-axis).

 

[evinda]

Re: Newton method-numerical analysis

At my graph, except form the five first approximation there should also be the function f and its tangent.. My code is the following:

tan=@(x) g(x_o)*(x-x_o)+f(x_o);
plot(x,f(x),'m',x,tan(x),'g')
 hold on
for k=1:5
    if (g(x_o)==0)
        return;
    end
    x_1=x_o-f(x_o)/g(x_o);
    t=@(x) g(x_1)*(x-x_1)+f(x_1);
    plot(x_o,f(x_o),x,t(x))
   hold on
    x_o=x_1;   
end

The plot that comes out is this: (see attachment).
Is this right?

How can I show how the algorithm works as you said in your last post??because when I do it like that

 plot(x(k),f(x(k)),x(k+1),0);
    hold on

it says that there is somewhere an error...
:(

 

[I like Serena]

Re: Newton method-numerical analysis

At my graph, except form the five first approximation there should also be the function f and its tangent.. My code is the following:

tan=@(x) g(x_o)*(x-x_o)+f(x_o);
plot(x,f(x),'m',x,tan(x),'g')
 hold on
for k=1:5
    if (g(x_o)==0)
        return;
    end
    x_1=x_o-f(x_o)/g(x_o);
    t=@(x) g(x_1)*(x-x_1)+f(x_1);
    plot(x_o,f(x_o),x,t(x))
   hold on
    x_o=x_1;   
end

The plot that comes out is this: (see attachment).
Is this right? :(

Perhaps you can replace

    t=@(x) g(x_1)*(x-x_1)+f(x_1);
    plot(x_o,f(x_o),x,t(x))

by

    t=@(x) g(x_o)*(x-x_o)+f(x_o);
    plot(x_o,f(x_o),x_1,t(x_1))

??

How can I show how the algorithm works as you said in your last post??because when I do it like that

    plot(x(k),f(x(k)),x(k+1),0);
    hold on

it says that there is somewhere an error...

Not entirely sure since I don't have Matlab.
But perhaps it's trying to access x(6) even though it does not exist?
What error does it give?