Click here to Skip to main content
15,888,521 members
Search within:


anybody see any problems with my newtons method & modified?
Please Sign up or sign in to vote.
2.78/5 (2 votes)
See more:
C
I am unsure what I have done wrong. The modified should definitely converge faster. I had the same issues trying larger iterations.

Here is my original:

C#
#include <stdio.h>
#include <math.h>

double f(double x)
{
    //return (x*x-6);
    //return (x*x*x-2*x*x-5);
    //return (x*x-2*x*exp(-1*x)+exp(-2*x));
    return (cos(x+sqrt(2))+x*((x/2)+sqrt(2)));
}

double fp(double x)
{
    //return (2*x);
    //return (3*x*x-4*x);
    //return (2*x+2*x*exp(-1*x)-2*exp(-1*x)-2*exp(-2*x));
    return (x-sin(x+sqrt(2))+sqrt(2));
}

int main()
{
    double p0, TOL, p;
    int i=1, N0;

    printf("Initial approximation: ");
    scanf("%lf", &p0);

    printf("Desired Tolerance:  ");
    scanf("%lf", &TOL);

    printf("Maximum number of iterations: ");
    scanf("%d", &N0);

    while(i<=N0)
    {
        p=p0-(f(p0)/fp(p0));

        if((fabs(p-p0)) < TOL)
        {
            printf("Iteration: %d.  Current value= %lf.", i, p);
        }

        i++;

        p0=p;
    }

    if(i>N0)

        printf("Method failed after %d iterations.", N0);
}




Results:
CSS
Initial approximation: -1.5
Desired Tolerance:  .01
Maximum number of iterations: 100
Iteration: 2.  Current value= -1.414242.Iteration: 3.  Current value= -1.414251.
Iteration: 4.  Current value= -1.414263.Iteration: 5.  Current value= -1.414280.
Iteration: 6.  Current value= -1.414302.Iteration: 7.  Current value= -1.414331.
Iteration: 8.  Current value= -1.414368.Iteration: 9.  Current value= -1.414404.
Iteration: 10.  Current value= -1.414444.Iteration: 11.  Current value= -1.41444
5.Iteration: 12.  Current value= -1.414462.Iteration: 13.  Current value= -1.414
457.Iteration: 14.  Current value= -1.414463.Iteration: 15.  Current value= -1.4
14442.Iteration: 16.  Current value= -1.414447.Iteration: 17.  Current value= -1
.414442.Iteration: 18.  Current value= -1.414457.Iteration: 19.  Current value=
-1.414436.Iteration: 20.  Current value= -1.414444.Iteration: 21.  Current value
= -1.414461.Iteration: 22.  Current value= -1.414450.Iteration: 23.  Current val
ue= -1.414452.Iteration: 24.  Current value= -1.414448.Iteration: 25.  Current v
alue= -1.414459.Iteration: 26.  Current value= -1.414460.Iteration: 27.  Current
 value= -1.414469.Iteration: 28.  Current value= -1.414438.Iteration: 29.  Curre
nt value= -1.414442.Iteration: 30.  Current value= -1.414439.Iteration: 31.  Cur
rent value= -1.414465.Iteration: 32.  Current value= -1.414448.Iteration: 33.  C
urrent value= -1.414448.Iteration: 34.  Current value= -1.414434.Iteration: 35.
 Current value= -1.414455.Iteration: 36.  Current value= -1.414469.Iteration: 37
.  Current value= -1.414435.Iteration: 38.  Current value= -1.414459.Iteration:
39.  Current value= -1.414442.Iteration: 40.  Current value= -1.414466.Iteration
: 41.  Current value= -1.414441.Iteration: 42.  Current value= -1.414456.Iterati
on: 43.  Current value= -1.414442.Iteration: 44.  Current value= -1.414424.Itera
tion: 45.  Current value= -1.414454.Iteration: 46.  Current value= -1.414466.Ite
ration: 47.  Current value= -1.414413.Iteration: 48.  Current value= -1.414441.I
teration: 49.  Current value= -1.414437.Iteration: 50.  Current value= -1.414457
.Iteration: 51.  Current value= -1.414462.Iteration: 52.  Current value= -1.4144
62.Iteration: 53.  Current value= -1.414457.Iteration: 54.  Current value= -1.41
4446.Iteration: 55.  Current value= -1.414454.Iteration: 56.  Current value= -1.
414466.Iteration: 57.  Current value= -1.414460.Iteration: 58.  Current value= -
1.414468.Iteration: 59.  Current value= -1.414460.Iteration: 60.  Current value=
 -1.414434.Iteration: 61.  Current value= -1.414436.Iteration: 62.  Current valu
e= -1.414438.Iteration: 63.  Current value= -1.414432.Iteration: 64.  Current va
lue= -1.414435.Iteration: 65.  Current value= -1.414436.Iteration: 66.  Current
value= -1.414449.Iteration: 67.  Current value= -1.414468.Iteration: 68.  Curren
t value= -1.414468.Iteration: 69.  Current value= -1.414448.Iteration: 70.  Curr
ent value= -1.414467.Iteration: 71.  Current value= -1.414466.Iteration: 72.  Cu
rrent value= -1.414456.Iteration: 73.  Current value= -1.414470.Iteration: 74.
Current value= -1.414437.Iteration: 75.  Current value= -1.414439.Iteration: 76.
  Current value= -1.414456.Iteration: 77.  Current value= -1.414434.Iteration: 7
8.  Current value= -1.414427.Iteration: 79.  Current value= -1.414426.Iteration:
 80.  Current value= -1.414460.Iteration: 81.  Current value= -1.414465.Iteratio
n: 82.  Current value= -1.414420.Iteration: 83.  Current value= -1.414456.Iterat
ion: 84.  Current value= -1.414456.Iteration: 85.  Current value= -1.414469.Iter
ation: 86.  Current value= -1.414468.Iteration: 87.  Current value= -1.414447.It
eration: 88.  Current value= -1.414422.Iteration: 89.  Current value= -1.414448.
Iteration: 90.  Current value= -1.414442.Iteration: 91.  Current value= -1.41445
1.Iteration: 92.  Current value= -1.414464.Iteration: 93.  Current value= -1.414
466.Iteration: 94.  Current value= -1.414417.Iteration: 95.  Current value= -1.4
14444.Iteration: 96.  Current value= -1.414429.Iteration: 97.  Current value= -1
.414453.Iteration: 98.  Current value= -1.414434.Iteration: 99.  Current value=
-1.414438.Iteration: 100.  Current value= -1.414436.Method failed after 100 iter
ations.
Process returned 35 (0x23)   execution time : 8.484 s
Press any key to continue.


Here is the modified Newtons:
C#
#include <stdio.h>
#include <math.h>

double f(double x)
{
    //return (x*x-2*x*exp(-1*x)+exp(-2*x));
    return (cos(x+sqrt(2))+x*((x/2)+sqrt(2)));
}

double fp(double x)
{
    //return (2*x+2*x*exp(-1*x)-2*exp(-1*x)-2*exp(-2*x));
    return (x-sin(x+sqrt(2))+sqrt(2));
}

double fpp(double x)
{
    //return (2-2*x*exp(-1*x)+4*exp(-1*x)+4*exp(-2*x));
    return (1-cos(x+sqrt(2)));
}

int main()
{
    double p0, TOL, p;
    int i=1, N0;

    printf("Initial approximation: ");
    scanf("%lf", &p0);

    printf("Desired Tolerance:  ");
    scanf("%lf", &TOL);

    printf("Maximum number of iterations: ");
    scanf("%d", &N0);

    while(i<=N0)
    {
        p=p0-((f(p0)*fp(p0))/(pow(fp(p0),2)-f(p0)*fpp(p0)));

        if((fabs(p-p0)) < TOL)
        {
            printf("Iteration: %d.  Current value= %lf.", i, p);
        }

        i++;

        p0=p;
    }

    if(i>N0)

        printf("Method failed after %d iterations.", N0);
}


Results:
CSS
Initial approximation: -1.5
Desired Tolerance:  .01
Maximum number of iterations: 100
Iteration: 2.  Current value= -1.414242.Iteration: 3.  Current value= -1.414251.
Iteration: 4.  Current value= -1.414263.Iteration: 5.  Current value= -1.414280.
Iteration: 6.  Current value= -1.414302.Iteration: 7.  Current value= -1.414331.
Iteration: 8.  Current value= -1.414368.Iteration: 9.  Current value= -1.414404.
Iteration: 10.  Current value= -1.414444.Iteration: 11.  Current value= -1.41444
5.Iteration: 12.  Current value= -1.414462.Iteration: 13.  Current value= -1.414
457.Iteration: 14.  Current value= -1.414463.Iteration: 15.  Current value= -1.4
14442.Iteration: 16.  Current value= -1.414447.Iteration: 17.  Current value= -1
.414442.Iteration: 18.  Current value= -1.414457.Iteration: 19.  Current value=
-1.414436.Iteration: 20.  Current value= -1.414444.Iteration: 21.  Current value
= -1.414461.Iteration: 22.  Current value= -1.414450.Iteration: 23.  Current val
ue= -1.414452.Iteration: 24.  Current value= -1.414448.Iteration: 25.  Current v
alue= -1.414459.Iteration: 26.  Current value= -1.414460.Iteration: 27.  Current
 value= -1.414469.Iteration: 28.  Current value= -1.414438.Iteration: 29.  Curre
nt value= -1.414442.Iteration: 30.  Current value= -1.414439.Iteration: 31.  Cur
rent value= -1.414465.Iteration: 32.  Current value= -1.414448.Iteration: 33.  C
urrent value= -1.414448.Iteration: 34.  Current value= -1.414434.Iteration: 35.
 Current value= -1.414455.Iteration: 36.  Current value= -1.414469.Iteration: 37
.  Current value= -1.414435.Iteration: 38.  Current value= -1.414459.Iteration:
39.  Current value= -1.414442.Iteration: 40.  Current value= -1.414466.Iteration
: 41.  Current value= -1.414441.Iteration: 42.  Current value= -1.414456.Iterati
on: 43.  Current value= -1.414442.Iteration: 44.  Current value= -1.414424.Itera
tion: 45.  Current value= -1.414454.Iteration: 46.  Current value= -1.414466.Ite
ration: 47.  Current value= -1.414413.Iteration: 48.  Current value= -1.414441.I
teration: 49.  Current value= -1.414437.Iteration: 50.  Current value= -1.414457
.Iteration: 51.  Current value= -1.414462.Iteration: 52.  Current value= -1.4144
62.Iteration: 53.  Current value= -1.414457.Iteration: 54.  Current value= -1.41
4446.Iteration: 55.  Current value= -1.414454.Iteration: 56.  Current value= -1.
414466.Iteration: 57.  Current value= -1.414460.Iteration: 58.  Current value= -
1.414468.Iteration: 59.  Current value= -1.414460.Iteration: 60.  Current value=
 -1.414434.Iteration: 61.  Current value= -1.414436.Iteration: 62.  Current valu
e= -1.414438.Iteration: 63.  Current value= -1.414432.Iteration: 64.  Current va
lue= -1.414435.Iteration: 65.  Current value= -1.414436.Iteration: 66.  Current
value= -1.414449.Iteration: 67.  Current value= -1.414468.Iteration: 68.  Curren
t value= -1.414468.Iteration: 69.  Current value= -1.414448.Iteration: 70.  Curr
ent value= -1.414467.Iteration: 71.  Current value= -1.414466.Iteration: 72.  Cu
rrent value= -1.414456.Iteration: 73.  Current value= -1.414470.Iteration: 74.
Current value= -1.414437.Iteration: 75.  Current value= -1.414439.Iteration: 76.
  Current value= -1.414456.Iteration: 77.  Current value= -1.414434.Iteration: 7
8.  Current value= -1.414427.Iteration: 79.  Current value= -1.414426.Iteration:
 80.  Current value= -1.414460.Iteration: 81.  Current value= -1.414465.Iteratio
n: 82.  Current value= -1.414420.Iteration: 83.  Current value= -1.414456.Iterat
ion: 84.  Current value= -1.414456.Iteration: 85.  Current value= -1.414469.Iter
ation: 86.  Current value= -1.414468.Iteration: 87.  Current value= -1.414447.It
eration: 88.  Current value= -1.414422.Iteration: 89.  Current value= -1.414448.
Iteration: 90.  Current value= -1.414442.Iteration: 91.  Current value= -1.41445
1.Iteration: 92.  Current value= -1.414464.Iteration: 93.  Current value= -1.414
466.Iteration: 94.  Current value= -1.414417.Iteration: 95.  Current value= -1.4
14444.Iteration: 96.  Current value= -1.414429.Iteration: 97.  Current value= -1
.414453.Iteration: 98.  Current value= -1.414434.Iteration: 99.  Current value=
-1.414438.Iteration: 100.  Current value= -1.414436.Method failed after 100 iter
ations.
Process returned 35 (0x23)   execution time : 8.484 s
Press any key to continue.
Posted
Add a Solution
Comments
Richard MacCutchan 14-Feb-14 13:33pm    
And what is your question?
MalDrHoop 14-Feb-14 13:50pm    
As you can see, my program went through fine, but I think I may have set something up wrong that wasn't incorrect in relation to the debugging but is incorrect in relation to the program and its purpose. After trying larger amounts of iterations, my method continues to fail, and doesnt reach the value it should. I can not find the problem in my program, my eye is untrained at this sort of thing. I have done the best I can with what I have. I had no programming experience just a couple weeks ago so I am proud that I am this far, but that is besides the point. I should be converging to a value of -1.414325. It is possible to take quite a few iterations using Newtons method, but It should be pretty quick using the modified.
Vedat Ozan Oner 14-Feb-14 16:02pm    
do you still need help?
MalDrHoop 14-Feb-14 16:18pm    
Did you see any problems?

2 solutions

Apart from your failure to recognize convergence, there is a more severe problem with your code: you don't test for 0 or near-0 values when calculating the next step and performing divisions, i. e. in the simple newton method you should test fp for 0 (or near-0) before dividing.

The problem in question is very ill conditioned, meaning that it it is prone to convergence problems due to rounding effects. It's likely the problem was deliberately set up this way to make you aware of these potential problems, so I won't spoil your experience by going into more detail. But I would advise you to do the following:

1. Change your print-out to show the curent value of p at every step of the iteration, even before it has converged. Please do add a linebreak at the end, too - it will help!

2. Along with the current value of p, also print out the value of the function f(p). f(p) should converge to 0, so it's easier to judge the quality of the current guess

3. Fix the loop to exit after convergence, as suggested in solution 1

4. Try out very small tolerance values (try repeatedly with ever shrinking values). Take note how you'll eventually reach a point where the iteration simply doesn't improve, or even gets significantly worse.


P.S.:
There are many ways to control an iterative numerical algorithm such as the newton method:
1. number of steps: this will always work, and is a good way to prevent endless loops or detect convergence issues.
2. difference of function value to target value (0 in this case): you don't check this here - why? That is the central goal here!
3. relative improvement, i. e. how much has the result (obtained from 2.) improved compared to the last step, or couple of last steps?
4. relative step size, i. e. how much (or, rather, how little) is the argument being changed compared to the last step - this is what you test; consider that this step size does not in fact indicate your progress (or lack thereof) towards a better solution! To judge that, see 2. and 3. above!
5. history of steps: when you keep stepping back and forth (as you can see in your results from about iteration 15) without any progress (which you can measure by looking at f(p)), then your algorithm is stuck!

The importance of implementing convergance criteria is pretty much in the order as they are listed here: the first is just a safeguard in case the others don't catch a problem. The second is measuring what you're trying to accomplish. The 3rd and 4th are really only needed to keep the calculations in a range where rounding errors (hopefully) won't influence the algorithm. And the 5th (and possibly other tests) is there to catch the really odd corner cases where your chosen algorithm simply doesn't work as expected.



P.P.S.:
Just to get an impression about things you need to consider when programming a foolproof rootfinder that always delivers a right answer, google for Jack Crenshaws "The Worlds Best Rootfinder" or just look it up on www.embedded.com[^]. You'll find a series of about 6 articles spread out over the course of several years where Crenshaw describes how he went to implement a rootfinder that is efficient, but also capable to deal with every conceivable corner case that it might encounter.

It's also very enlightening how, over the time, Crenshaw came to consider specific cases that he didn't think of at first. Even if you have difficulties following the math involved there, I encourage you to take a look!

Funnily, "TWBRF" wouldn't help here, as it's core assumption is a true root, i. e. a function that passes from negative to positive values or vice versa, whereas your example has a local minimum in it's root.
 
Share this answer
 
Posted
Updated 17-Feb-14 4:19am
v3
first, you don't break the iteration when diff falls into the tolerance value. therefore, you end up with 'i>NO'. convert to that
C#
printf("Iteration: %d.  Current value= %lf.", i, p);
if((fabs(p-p0)) < TOL)
{
  break;
}


secondly, I think you forgot to compile one of your codes before pasting output into the question. both outputs are the same, which is not expected.

third, tolerance value is too big. you may get a better output with 0.0001 since the root is about -1.4144.

last, could you provide a website for the proof of the second approximation? (this part is for me. please? :) )
 
Share this answer
 
Posted
Updated 14-Feb-14 11:32am
v2
Comments
Matt T Heffron 14-Feb-14 17:59pm    
Please, for the sake of our eyes and sanity, put a linebreak in the printf! :-)

printf("Iteration: %d. Current value= %lf.\n", i, p);
Vedat Ozan Oner 14-Feb-14 18:41pm    
why? the effect is good :p
MalDrHoop 14-Feb-14 20:54pm    
Both outputs are similar cause the two codes are different. They aren't quite the same. If I copied and pasted the same outputs its because I got all jumbled trying to get everything straightened up lol. My bad on that part. I knew the tolerance was too big, I had just chose one to try and type the inputs quickly to have the results here for someone to look at. I had been running about .00001. All of my stuff came from my numerical analysis textbook and class. My class is using Faire's and Burden 7th edition. I don't have it with me right now to look it up
MalDrHoop 14-Feb-14 20:46pm    
Beginner's mistake!
Stefan_Lang 17-Feb-14 6:37am    
FYI, the root is not about -1.4144 (as you might think when looking at the output), it is closer to -1.41421356, or -sqrt(2)!

Looks like the function at hand has been deliberately set up to break simple algorithms such as Newtons. The preconditions for Newtons algorithm (fp(p) != 0) are broken at the root of the function, so the algorithm breaks down when getting too close.
Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month
Related Questions
C# Newton Raphson help
Draw newton's fractal in F#
How to newton's divided difference interpolation using C#
problem with methods
Any problem with my PHP code?
Access MDI property but not any methods
DrawToBitmap method problem
Why is there no any method to comment in JSON
Silverlight Application unable to call webservice method
Problem with bitmaps

Advertise
Privacy
Cookies
Terms of Use
Last Updated 17 Feb 2014
Layout: fixed | fluid
Copyright © CodeProject, 1999-2024
All Rights Reserved.

Web01 2.8:2024-04-02:1

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900