Algebra/Chapter 21/Iteration

Algebra

Iteration

Iteration is a method of calculating of finding a value of a function through repeated guesses, with each one becoming closer and closer to the correct answer. This is commonly used in computer programs, where this kind of evaluation is easier than direct algebraic manipulation. It is also used in pure mathematics where the answer to a problem is either very difficult or impossible to find using algebraic manipulation. The main problem with Iteration is that it takes many steps to arrive at a suitably precise value for the calculation. However due to the speed of modern computers, it remains a very effective method of calculating values of equation.

When to use Iteration

Iteration can be used for all equations needed to be evaluated in a computer program. Due to the simplicity of the code required to implement this kind of evaluation, and the accuracy and speed that the computer can calculate the result, it is one of the most effective ways for a computer to evaluate mathematical expressions.

Iteration can also be used for formula that cannot be solved using conventional mathematical techniques. For example, for the equation $27=e^{x}+x$ , there is no known way to directly solve it for x. Using iteration however, the correct answer of 3.17 (to 2 decimal places) is easily calculated.

Thirdly, iteration is useful as a guide to the correct solution to a problem. For example, to evaluate all the values of x in the equation $x^{3}-3*x^{2}-10*x+24$ , one must first be found using either the Remainder Theorem and trial and error, or complicated simultaneous equation involving the sum, product and sum of product of roots of this equation. By using iteration, one root may be found easily, thereby making the final solution much easier to calculate.

Finally, iteration can be used to provide an estimate for the solution to a mathematical problem. Using iteration, simple arithmetic errors can often be detected as the calculated result does not match up with the expected result (see Mathematical estimation Techniques.

When not to use Iteration

Iteration can not be used to prove a mathematical equation. This is because iteration never provides an exact answer to a problem, only increasingly accurate estimates.

Also, sometimes the iteration method fails to calculate the correct answer for an equation. This will be discussed later.

Iteration will not work if the equation being tested uses function that only work with integer values. For example an equation with a factorial in it will not work.

Finally, for an equation with multiple roots, the iteration method will only find one (root).

How to use Iteration

Iteration is very simple to use once the basics are understood. Note that basic function notation is required to understand this explanation.

Move all elements of the equation to one side of the equation so that one side of the equation equals 0 and call the other side f(x)
Draw a rough graph of f(x) to find an estimate of which value of x f(x) = 0. Call this value x1.
Choose values to the left and to the right of x1 and find f(x2) and f(x3).
If either f(x2) or f(x3) is not an opposite sign to the evaluated value of the initial guess.
1. If f(x2) or f(x3) is closer to 0 than f(x1) then choose x2 or x3 the new x1 and start again from step 3.
2. Otherwise try different values to the left and right of the initial guess.
If f(x2) or f(x3) is an opposite sign to f(x1):
1. Take xA = x1 and xB = x2 or x3.
2. Take a new guess xC from between xA and xB (i.e. $xC=(xA+xB)/2$ ). For example xC = 3.5
3. If f(xC) is an opposite sign to f(xA)
  1. Make xB = xC
  2. Repeate from step 5b until desired accuracy is achieved
4. If f(xC) is an opposite sign to f(xB)
  1. Make xA = xC
  2. Repeat from step 5b until desired accuracy is achieved

Here is an example of this process in operation:

$x^{2}+lnx+3^{x}=87$ becomes
$f(x)=x^{2}+lnx+3^{x}-87=0$ (note how one side equals 0).
Clearly $3^{x}$ has to be less than 87 for f(x) to be 0. $3^{4}=81$ would be a good approximation as 81 nearly cancels out the -87. Hence x1 = 4.
f(x1) = 11.38
try x2 = 3... $f(3)=-49.90$
x3 = 5... $f(5)=182.61$
Not necessary.
f(x1) has an opposite sign to f(x2)
a) xA = 4, xB = 3
f(xA) = 11.38

f(xB) = -49.90

b) xC = (4 + 3) / 2 = 3.5
f(xC) = f(3.5) = -26.73

c) f(xC) is opposite sign to f(xA)
i) xB = 3.5
f(xB) = -26.73

ii) go back to step 5b

5  b) xC = (3.5 + 3) / 2 = 3.25
      f(xC) = -39.72
   c) f(xC) is opposite sign to f(xA)
      i) xB = 3.25
         Take xB as answer

That’s all that's to it. It may seem to take a lot of working on paper but normally most of the working can be skipped once you understand the method of iteration.