Counting iterations in Newton-Raphson's method

Question

I'm working in a simple program that calculates the root of any given function using Newton-Raphson's method. In this program I have to print the found root and the number of iterations made. The program itself is fine, I can find the root of any given function but I can't count properly the number of iterations. It is always 5 over the max. number of iterations or 1 less than it. Here's the code in C++:

#include <iostream>
#include <math.h>
#include <stdlib.h>

using namespace std;

double f(float x)
{
  double function1;
  function1 = exp(x)- 4*pow(x,2); // given function
  return function1;
}

double derivative(float x)
{
  double derivative1;
  derivative1 = exp(x) - 8*x; // derivative of given function
  return derivative1;
}


void newtonMethod(double x0, double error, int N)
{
  double xNext, xPrevious, root;
  int k;

  xPrevious = x0;

  for(int i = 0; i < N || f(xNext) > error; i++)
  {
    xNext = xPrevious - (f(xPrevious)/derivative(xPrevious)); // calculates the next value of x
    xPrevious = xNext;
    root = xNext;
    k = i;
}
cout << endl;
cout << "Iterations made: " << k << endl;
cout << endl;
cout << endl;
cout << endl;
cout << "Root is:  " << root << endl;


}

int main()
{
  double x0, error;
  int N; // max. number of iterations you can do
  cout << "Enter x0: ";
  cin >> x0;
  cout << "Enter the error: ";
  cin >> error;
  cout << "Enter the max. number of iterations: ";
  cin >> N;
  newtonMethod(x0, error, N);
 }

And I'm pretty sure the error is in this piece of code:

;i < N || f(xNext) > error;

If I run this program and put N = 100, it shows the right root but it prints "Iterations made = 99" but this is wrong. What do I do to print the right number of iterations made? For example, for the function in the program above (e^x - 4x²) it should stop in the fourth iteration if I enter x0 = 0.5 and error = 0.0001. How to fix it?

The computer works in binary, not decimal. 0.0001 cannot be represented exactly in binary, thus you may / will not get the exact answer. -- for the function in the program above (e^x - 4x²) it should stop in the fourth iteration if i enter x0 = 0.5 and error = 0.0001. -- In your math book, yes, on a binary computing machine, maybe, maybe not. — PaulMcKenzie
This isn't the problem, but code like this double f(float x) { double function1; function1 = exp(x)- 4*pow(x,2); return function1; } is far too verbose. double f(floats x) { return exp(x) - 4 * pow(x, 2); } does the same thing and is much easier to read. — Pete Becker
You're right about the code part being too verbose but that's not the point. I wrote another program with the bisection method and everything ran perfectly well. Entering the number "0.0001" didn't cause unexpected errors. I just can't understand what's causing this error in Newton's method. — Diego
@Diego All of this boils down to the simple fact that floating point is not exact. I don't know how more simple to put it. It doesn't matter if you're trying to implement Newton-Raphson, or simply summing up a few numbers -- round off error will result. — PaulMcKenzie

panzerpower panzerpower · Accepted Answer · 2016-10-19T00:52:48

To answer your question, which was why the following piece of code does not work:

;i < N || f(xNext) > error;

It is simply because that, in a for loop condition, it is a continuing condition that is evaluated, and not a stopping condition. In the above piece of code, what you are telling the compiler is: continue the loop as long as either i < N is true or f(xNext) > error is true. Therefore, when you input x0 = 0.5, error = 0.0001 and N = 100, what the loop does is that it will not stop until both criteria are false, i.e. when i reaches N AND the tolerance in f(x) is smaller than error.

Now, the solution is simply to swap the || operator to && operator. Like this:

i < N && f(xNext) > error;

but then, your xNext is not initialized. Because that your xNext and xPrevious are equal at the end of each loop, I would simply put xPrevious instead. In addition, as @Rathat has written, evaluating your tolerance in f(x) should take its absolute value, so:

i < N && abs(f(xPrevious)) > error;

Finally, you should output the number of iterations as k + 1 since you started with i = 0.

This should solve your problem.

Counting iterations in Newton-Raphson's method

2 Answers