Iteration

Iteration consists of repeating an operation of a value obtained by the same operation. It is often used in making successive approximations, each one more accurate than the one that preceded it. One begins with an approximate solution and substitutes it into an appropriate formula to obtain a better approximation. This approximation is subsequently substituted into the same formula to arrive at a still better approximation, and so on, until an exact solution or one that is arbitrarily close to an exact solution is obtained.

An example of using iteration for approximation is finding the square root. If s is the exact square root of A, then A |6-8| s = s. For example, since 8 is the square root of 64, it is true that 64 |6-8| 8 = 8. If you did not know the value of |5-14| 64, you might guess 7 as the value. By dividing 64 by 7, you get 9.1. The average of 7 and 9.1 would be closer. It is 8.05.

Now you make a second iteration by repeating all the steps but beginning with 8.05. Carry out the division to the hundredths place; 64 |6-8| 8.05 = 7.95. The average of 8.05 and 7.95 is 8. A third iteration shows that 8 is the exact square root of 64.

Various methods and formulas exist for finding the roots of equations by iteration. One of the most general methods is called the method of successive bisection. This method can be used to find solutions to many equations. It involves finding solutions by beginning with two approximate solutions, one that is known to be too large and one that is known to be too small, then using their average as a third approximate solution. To arrive at a fourth approximation, it is first determined whether the third approximation is too large or too small. If the third approximation is too large it is averaged with the most recent previous approximation that was too small, or the other way around; if approximation number three is too small it is averaged with the most recent previous approximation that was too large. In this way, each successive approximation gets closer to the correct solution.

Testing each successive approximation is done by substituting it into the original equation and comparing the result to zero. If the result is greater than zero then the approximation is too large, and if the result is less than zero, then the approximation is too small.

Iteration has many other applications. In proof, for example, mathematical induction is a form of iteration. Many computer programs use iteration for looping.