|
|
Next: Summary
Up: The while statement
Previous: Example Program: Student mark
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:
old new 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.