2.1 Bisection Method

The bisection method is a simple procedure that we have learned to find roots. It computes a sequence of values that converges to the root. We need two initial values \( a \) and \( b \) between which the root lies. We then calculate the mean value \( m \) and determine whether the root lies between \( a \) and \( m \), or between \( m \) and \( b \). We then replace the value \( a \) or \( b \) with \( m \) and repeat the process until we want to terminate or have reached a desired level of accuracy.

We have the following function given and want to find the root:

import Pkg
Pkg.instantiate()

using Plots
f(x)= -26 + 85 * x - 91 * x^2 +44 * x^3 -8 * x^4 + x^5
plot(f, [0.0:0.01:1.5], label="f")

To determine between which values the root lies, we can evaluate the sign. If the signs are different, we know that a root must lie between them. For this purpose, we define a function that returns whether two functions have the same sign.

# Funktion die testet ob a und b das gleiche Vorzeichen haben
function samesign(a, b)
    return a * b > 0
end

samesign (generic function with 1 method)

Now for the method itself. We provide the method with our function and the interval within which we suspect the root to be. Then, the interval is halved, and it is determined in which subinterval the root lies. This subinterval is then halved again, and so on.

function bisect(func, low, high)
    #Find root of continuous function where f(low) and f(high) have opposite signs

    if samesign(func(low), func(high))
        return "Error: No root found"
    end
    midpoint = (low + high) / 2.0
    for n in 1:20 # Wir nehmen einfach mal ein paar Iterationen 
        midpoint = (low + high) / 2.0
        println("Iteration: ", n, " Midpoint: ", midpoint)
        if samesign(func(low), func(midpoint))
            low = midpoint
        else
            high = midpoint
        end
    end
    return midpoint
end

bisect (generic function with 1 method)

x = bisect(f, 0, 1)
println("x = ", x)

Iteration: 1 Midpoint: 0.5
Iteration: 2 Midpoint: 0.75
Iteration: 3 Midpoint: 0.625
Iteration: 4 Midpoint: 0.5625
Iteration: 5 Midpoint: 0.53125
Iteration: 6 Midpoint: 0.546875
Iteration: 7 Midpoint: 0.5546875
Iteration: 8 Midpoint: 0.55859375
Iteration: 9 Midpoint: 0.556640625
Iteration: 10 Midpoint: 0.5576171875
Iteration: 11 Midpoint: 0.55712890625
Iteration: 12 Midpoint: 0.556884765625
Iteration: 13 Midpoint: 0.5570068359375
Iteration: 14 Midpoint: 0.55706787109375
Iteration: 15 Midpoint: 0.557037353515625
Iteration: 16 Midpoint: 0.5570220947265625
Iteration: 17 Midpoint: 0.5570297241210938
Iteration: 18 Midpoint: 0.5570259094238281
Iteration: 19 Midpoint: 0.5570240020751953
Iteration: 20 Midpoint: 0.5570249557495117
x = 0.5570249557495117

Can we extend the function so that we terminate as soon as we have reached a certain accuracy to zero? Say 0.0001? Therefore, we must incorporate the termination condition by calculating the function at the point \( x \).

function bisect(func, low, high, tolerance)
    # Find root of continuous function where f(low) and f(high) have opposite signs

    if samesign(func(low), func(high))
        return "Error: No root found"
    end
    midpoint = (low + high) / 2.0
    for n in 1:1000 # Wir nehmen einfach mal ein paar Iterationen 
        midpoint = (low + high) / 2.0
        println("Iteration: ", n, " Midpoint: ", midpoint)
        if samesign(func(low), func(midpoint))
            low = midpoint
        else
            high = midpoint
        end
        if abs(high - low) < tolerance
            break
        end
    end
    return midpoint
end

bisect (generic function with 2 methods)

x = bisect(f, 0, 1, 0.0001)
println("x = ", x)

Iteration: 1 Midpoint: 0.5
Iteration: 2 Midpoint: 0.75
Iteration: 3 Midpoint: 0.625
Iteration: 4 Midpoint: 0.5625
Iteration: 5 Midpoint: 0.53125
Iteration: 6 Midpoint: 0.546875
Iteration: 7 Midpoint: 0.5546875
Iteration: 8 Midpoint: 0.55859375
Iteration: 9 Midpoint: 0.556640625
Iteration: 10 Midpoint: 0.5576171875
Iteration: 11 Midpoint: 0.55712890625
Iteration: 12 Midpoint: 0.556884765625
Iteration: 13 Midpoint: 0.5570068359375
Iteration: 14 Midpoint: 0.55706787109375
x = 0.55706787109375