Iteration

views updated

Iteration

Iteration, in mathematics, is a step-by-step numerical procedure to produce a result by repeating a sequence of steps (what is called iterating a function) to successively solve a problem. That definition can also be applied in computer science where a repetition of a sequence of computer instructions is used to achieve a result. Thus, iteration consistsof 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.

Finding the roots of an equation

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 for 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.

KEY TERMS

Roots of an equation —The roots of an equation are those values of the independent variable that make it a true statement. They are also called solutions of the equation.

Many computer programs use iteration for looping.