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?

Answer 1

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.