next up previous
Next: Summary Up: The while statement Previous: Example Program: Student mark

Example Program: Iterative evaluation of a square root

Frequently in solving scientific problems iterative methods are used. In an iterative method a first approximation to a solution of the problem is produced, then some method which improves the accuracy of the solution is used repeatedly until two successive approximations agree to the accuracy required. This process could be described algorithmically as follows:

produce first approximation in a variable old_app.
produce a better approximation as a function
                     of old_app in a variable new_app.
while old_app and new_app are not close enough
   {
    set old_app equal to new_app.
    produce a better approximation as a function
                      of old_app in the variable new_app.
   }

A simple problem that can be solved in this way is that of finding the square root of a positive number. If old is an approximation to the square root of a number x then a better approximation, new, is given by:

\begin{displaymath}
new=(old+\frac{x}{old})/2
\end{displaymath}

For example taking 3 as an approximation to the square root of 10 gives the following sequence of approximations:

oldnew
3 (3 + 10/3)/2 = 3.17
3.17 (3.17 + 10/3.17)/2 = 3.1623
3.1623 (3.1623 + 10/3.1623)/2 = 3.162278

It can be seen that the sequence of approximations is rapidly converging to the correct value, which is 3.16227766. This may not always be true in every application of iterative methods, but in the case of square roots it will always happen as long as the first approximation chosen is positive.

In the algorithmic description above the phrase `while old_app and new_app are not close enough' was used. How do we test this? In the square root example it might be decided that the new approximation would be accepted as the correct value of the root when it differed by less than 0.0005 from the previous approximation. This would mean that the estimate of the root was correct to three decimal places. It might be tempting to write the test as

while ((new_app-old_app) > 0.0005)
but in the second iteration this test would give 3.1623-3.17 > 0.0005 which is equivalent to -0.0077 > 0.0005 which is false, causing the iteration process would stop prematurely. The problem is that if new_app-old_app is ever negative then since a negative number can never be greater than a positive number the condition will become false however large the difference between new_app and old_app! The solution to this problem is to test the absolute magnitude, without regard to sign, of new_app and old_app. C++ has a function fabs(x) which returns the absolute value of x i.e. x if x is positive and -x if x is negative. Using this function the test could be written:
while (fabs(new_app-old_app) > 0.0005)
which solves the problem above. In general if trying to find if two quantities are within some tolerance of each other then test the absolute value of the difference between them against the tolerance. However there is another difficulty with the above. Consider the following approximations:
exact value approximation
100 100.1
0.1 0.2

Which of these approximations is the most accurate? They both have an absolute error of 0.1 but in one case the error is 0.1% of the quantity being approximated and in the other it is 100% of the quantity being approximated. Thus if these approximations were used as a multiplying factor in the next stage of a computation then in one case the answer would be a small fraction larger than it should be whereas in the other case the answer would be twice what it should be! Thus the relative size of the error with respect to the quantity being approximated is important. In the square root problem if x was 0.000001, with square root 0.001, then two successive approximations 0.0015 and 0.00108 would have a difference less than 0.0005 and hence 0.00108 would be accepted as a result. However this result would be 8% in error. Hence it is always safer to test the relative error against the tolerance, this ensures that results of different sizes have the same number of significant figures correct. Hence if three significant figures were required in the result the test should be:

while (fabs((new_app-old_app)/new_app) > 0.0005)

Since the square root of a negative number is not defined (in real arithmetic) no attempt should be made to use this algorithm if the value input is negative. Also if the input is zero, which has square root zero, the use of this algorithm will lead to a division by something approaching zero. This should be avoided by making zero a special case. Hence the program:

void main()
{
  const float tol = 0.000005; // relative error tolerance
  float value;
  float old_app, new_app;
  cout << "Square root of a number"
       << endl << endl;
  cout << "Enter a positive number: ";
  cin >> value;
  if (value < 0.0)
    cout << "Cannot find square root of negative number"
         << endl;
  else
     if (value == 0.0)
        cout << "square root of "
             << value
             << " is 0.0"
             << endl;
     else
       {
         old_app = value; // take value as first approximation
         new_app = (old_app + value/old_app)/2;
         while (fabs((new_app-old_app)/new_app) > tol)
           {
             old_app = new_app;
             new_app = (old_app + value/old_app)/2;
           }
         cout << "square root of "
              << value
              << " is " << new_app
              << endl;
       }
}
Download program.


next up previous
Next: Summary Up: The while statement Previous: Example Program: Student mark
Peter JB King
1999-08-31