Editing Bisection method (section)

==Higher order roots==
Further problems can arise from the use of computer arithmetic for higher order roots.

To help in considering how to detect and correct inaccurate results consider the following:

<pre>
bisect(lambda x: (x - 1.23456789012345e-100), 0, 1, 5e-15)
Approx. root = 1.23456789012345e-100 Converged after 381 iterations with termination f(c) = 0
Final interval [1.2345678901234491e-100, 1.2345678901234511e-100]
</pre>

The final interval [1.2345678901234491e-100, 1.2345678901234511e-100] indicates fairly good accuracy. The bisection method has a distinct advantage over other root finding techniques in that the final interval can be used to determine the accuracy of the final solution. This information will be useful in assessing the accuracy of some following examples.

Next consider what happens for a root of order 3:

<pre>bisect(lambda x: (x - 1.23456789012345e-100)**3, 0, 1, 5e-15)
Approx. root = 1.234567898094279e-100 Converged after 357 iterations with termination f(c) = 0
Final interval [1.2345678810624394e-100, 1.2345679151261181e-100]
</pre>
The final interval [1.2345678810624394e-100, 1.2345679151261181e-100] indicates that 15 digits have not been returned.

The relative error 
<pre>(1.234567898094279e-100 - 1.23456789012345e-100)/1.23456789012345e-100 
= 6.456371473106003e-09</pre> shows that only 8 digits are correct and again <math>f(c) = 0</math>. This occurs because

<math display="block">
\begin{aligned}
f(approx. root) &= f(1.234567898094279*10^{-100}) \\
&= (1.234567898094279*10^{-100} - 1.23456789012345*10^{-100})^3 \\
&= (7.970828885817127*10^{-109})^3 \\
&= 5.064195*10^{2}*10^{-327} \\
&= 5.064195*10^{-325}\end{aligned}</math>

Because this is less than the minimum subnormal, it returns a value of 0. 

This can occur in '''any''' root finding technique, not just the bisection method, and it is only the fact that the return conditions include the information about what stopping criteria was achieved that the problem can be diagnosed.

The use of the relative error as a stopping condition allows us to determine how accurate a solution can be obtained.

Consider what happens on trying to achieve 8 significant figures:

<pre>bisect(lambda x: (x - 1.23456789012345e-100)**3, 0, 1, 5e-8)
[1.2345678980942788e-100, 357, 'Converged', 'f(c) = 0']
</pre>
<math>f(c) = 0</math> Indicates that eight digits of accuracy have not been achieved, so try

<pre>bisect(lambda x: (x - 1.23456789012345e-100)**3, 0, 1, 5e-4)
[1.2347947281308757e-100, 344, 'Converged', 'Tolerance']
</pre>
At least four digits have been achieved and
<pre>
bisect(lambda x: (x - 1.23456789012345e-100)**3, 0, 1, 5e-6)
[1.2345658202098768e-100, 351, 'Converged', 'Tolerance']

6 digit convergence
</pre>
<pre>bisect(lambda x: (x - 1.23456789012345e-100)**3, 0, 1, 5e-7)
[1.2345677277758852e-100, 354, 'Converged', 'Tolerance']

7 digit convergence
</pre>

A similar problem can arise if there are two small roots close together:
<pre>
bisect(lambda x: (x - 1.23456789012345e-23)*x, 1e-300, 1, 5e-15)
[1.2345678901234481e-23, 125, 'Converged', 'Tolerance']
</pre>
15 digit convergence
<pre>bisect(lambda x: (x - 1.23456789012345e-24)*x, 1e-300, 1e-20, 5e-1)
[1.5509016039626554e-300, 931, 'Converged', 'f(c) = 0']

Final interval [1.2754508019813276e-300, 1.8263524059439830e-300]
relative error = 3.5521376891678086e-1 -- 1 digit convergence
</pre>

<pre>bisect(lambda x: (x - 1.23456789012345e-23)*x, 1e-300, 1, 5e-1)
[1.1580528575742387e-23, 79, 'Converged', 'Tolerance']

Final interval [1.0753347963189360e-23, 1.2407709188295415e-23]
relative error = 1.4285714285714285e-1 -- 1 digit convergence
</pre>


(The following has not been changed.)