Using bisection method

Question

I have created the following code which does the bisection method. I am trying to use it to find the root for the function $f(x)=x^7-6x^6-28x^5+232x^4-336x^3-544x^2+1728x-1152$ on the interval $[1, 3.1]$ I have been given a hint that $x_0 = 2$ is a root for this function on the interval. Heres my code below: I am getting that there is no root, I was hoping someone could help me fix this! thanks

import math
import numpy as np
def root(x):
    return (x**7-6*x**6-28*x**5+232*x**4-336*x**3-544*x**2+1728*x-1152)

def bisection_method(f, a, b, tol):
    if f(a)*f(b) > 0:
        #end function, no root.
        print("No root found.")
    else:
        iter = 0
        while (b - a)/2.0 > tol:
            midpoint = (a + b)/2.0

            if f(a)*f(midpoint) < 0: # Increasing but below 0 case
                b = midpoint
            else:
                a = midpoint

            iter += 1
        return(midpoint, iter)

answer, iterations = bisection_method(root, 1, 3.1, 10**(-14))
print("Answer:", answer, "\nfound in", iterations, "iterations")

This is the output I am getting:

No root found.

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-6-ecdc56120415> in <module>()
 21         return(midpoint, iter)
 22 
---> 23 answer, iterations = bisection_method(root, 1, 3.1, 10**(-14))
 24 print("Answer:", answer, "\nfound in", iterations, "iterations")

TypeError: 'NoneType' object is not iterable

Answer 1

Bisection doesn't work when you have even-multiplicity roots (because $f$ has the same sign either side), which is the case here.

$$f(x)=(x - 2)^4 (x + 2) (x - 6) (x + 6)$$

Your program falls in the first test if f(a)*f(b)>0: $f(1)=-105$ and $f(3.1)\approx -197$ so it immediately exit with no value returned.

By the way, iter is a Python built-in function returning an iterator object, so you shouldn't use it for a variable name.

Answer 2

For the comment on gcd of the polynomial and its derivative

The gcd turns out to be $$ \left( x^{3} - 6 x^{2} + 12 x - 8 \right) $$ Once you figure out that this is $(x-2)^3,$ you should check about $(x-2)^4$ dividing the original, which does happen.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

$$ \left( x^{7} - 6 x^{6} - 28 x^{5} + 232 x^{4} - 336 x^{3} - 544 x^{2} + 1728 x - 1152 \right) $$

$$ \left( 7 x^{6} - 36 x^{5} - 140 x^{4} + 928 x^{3} - 1008 x^{2} - 1088 x + 1728 \right) $$

$$ \left( x^{7} - 6 x^{6} - 28 x^{5} + 232 x^{4} - 336 x^{3} - 544 x^{2} + 1728 x - 1152 \right) = \left( 7 x^{6} - 36 x^{5} - 140 x^{4} + 928 x^{3} - 1008 x^{2} - 1088 x + 1728 \right) \cdot \color{magenta}{ \left( \frac{ 7 x - 6 }{ 49 } \right) } + \left( \frac{ - 608 x^{5} + 4032 x^{4} - 3840 x^{3} - 25088 x^{2} + 66048 x - 46080 }{ 49 } \right) $$ $$ \left( 7 x^{6} - 36 x^{5} - 140 x^{4} + 928 x^{3} - 1008 x^{2} - 1088 x + 1728 \right) = \left( \frac{ - 608 x^{5} + 4032 x^{4} - 3840 x^{3} - 25088 x^{2} + 66048 x - 46080 }{ 49 } \right) \cdot \color{magenta}{ \left( \frac{ - 6517 x - 9702 }{ 11552 } \right) } + \left( \frac{ - 41552 x^{4} + 206976 x^{3} - 244608 x^{2} - 175616 x + 338688 }{ 361 } \right) $$ $$ \left( \frac{ - 608 x^{5} + 4032 x^{4} - 3840 x^{3} - 25088 x^{2} + 66048 x - 46080 }{ 49 } \right) = \left( \frac{ - 41552 x^{4} + 206976 x^{3} - 244608 x^{2} - 175616 x + 338688 }{ 361 } \right) \cdot \color{magenta}{ \left( \frac{ 727054 x - 1199964 }{ 6744409 } \right) } + \left( \frac{ 13307904 x^{3} - 79847424 x^{2} + 159694848 x - 106463232 }{ 137641 } \right) $$ $$ \left( \frac{ - 41552 x^{4} + 206976 x^{3} - 244608 x^{2} - 175616 x + 338688 }{ 361 } \right) = \left( \frac{ 13307904 x^{3} - 79847424 x^{2} + 159694848 x - 106463232 }{ 137641 } \right) \cdot \color{magenta}{ \left( \frac{ - 357453677 x - 364198086 }{ 300259584 } \right) } + \left( 0 \right) $$ $$ \frac{ 0}{1} $$ $$ \frac{ 1}{0} $$ $$ \color{magenta}{ \left( \frac{ 7 x - 6 }{ 49 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 7 x - 6 }{ 49 } \right) }{ \left( 1 \right) } $$ $$ \color{magenta}{ \left( \frac{ - 6517 x - 9702 }{ 11552 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ - 931 x^{2} - 588 x + 12740 }{ 11552 } \right) }{ \left( \frac{ - 6517 x - 9702 }{ 11552 } \right) } $$ $$ \color{magenta}{ \left( \frac{ 727054 x - 1199964 }{ 6744409 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ - 19133 x^{3} + 19494 x^{2} + 596372 x - 701784 }{ 2202256 } \right) }{ \left( \frac{ - 133931 x^{2} + 21660 x + 2531332 }{ 2202256 } \right) } $$ $$ \color{magenta}{ \left( \frac{ - 357453677 x - 364198086 }{ 300259584 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 137641 x^{4} - 5505640 x^{2} + 19820304 }{ 13307904 } \right) }{ \left( \frac{ 963487 x^{3} + 825846 x^{2} - 25876508 x - 29730456 }{ 13307904 } \right) } $$ $$ \left( x^{4} - 40 x^{2} + 144 \right) \left( \frac{ - 371 x^{2} + 60 x + 7012 }{ 589824 } \right) - \left( 7 x^{3} + 6 x^{2} - 188 x - 216 \right) \left( \frac{ - 53 x^{3} + 54 x^{2} + 1652 x - 1944 }{ 589824 } \right) = \left( 1 \right) $$ $$ \left( x^{7} - 6 x^{6} - 28 x^{5} + 232 x^{4} - 336 x^{3} - 544 x^{2} + 1728 x - 1152 \right) = \left( x^{4} - 40 x^{2} + 144 \right) \cdot \color{magenta}{ \left( x^{3} - 6 x^{2} + 12 x - 8 \right) } + \left( 0 \right) $$ $$ \left( 7 x^{6} - 36 x^{5} - 140 x^{4} + 928 x^{3} - 1008 x^{2} - 1088 x + 1728 \right) = \left( 7 x^{3} + 6 x^{2} - 188 x - 216 \right) \cdot \color{magenta}{ \left( x^{3} - 6 x^{2} + 12 x - 8 \right) } + \left( 0 \right) $$ $$ \mbox{GCD} = \color{magenta}{ \left( x^{3} - 6 x^{2} + 12 x - 8 \right) } $$ $$ \left( x^{7} - 6 x^{6} - 28 x^{5} + 232 x^{4} - 336 x^{3} - 544 x^{2} + 1728 x - 1152 \right) \left( \frac{ - 371 x^{2} + 60 x + 7012 }{ 589824 } \right) - \left( 7 x^{6} - 36 x^{5} - 140 x^{4} + 928 x^{3} - 1008 x^{2} - 1088 x + 1728 \right) \left( \frac{ - 53 x^{3} + 54 x^{2} + 1652 x - 1944 }{ 589824 } \right) = \left( x^{3} - 6 x^{2} + 12 x - 8 \right) $$