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:

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

oldnew3 (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

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.

1999-08-31