'''
To find a solution to f(x) = 0 given the continuous function f on the interval [a,b], where f(a) and f(b) have opposite signs:
INPUT endpoints a,b; tolerance TOL; maximum number of iterations N₀.
OUTPUT approximate solution p or message of failure.
Step 1 Set i = 1;
FA = f(a).
Step 2 While i ≤ N₀ do Steps 3–6.
Step 3 Set p = a + (b − a)/2; (Compute pᵢ.)
FP = f(p).
Step 4 If FP = 0 or (b − a)/2 < TOL then
OUTPUT (p); (Procedure completed successfully.)
STOP.
Step 5 Set i = i + 1.
Step 6 If FA · FP > 0 then set a = p; (Compute aᵢ ,bᵢ .)
FA = FP
else set b = p. (FA is unchanged.)
Step 7 OUTPUT (‘Method failed after N₀ iterations, N₀ =’, N₀ );
(The procedure was unsuccessful.)
STOP.
'''
import pandas as pd
def Bisection(a, b, f, tolerance=0.000001, max_iterations=100, output='answer', stopping_criterion='tolerance', iteration=100):
"""The Bisection Algorithm
Keyword arguments:
a (double) -- starting interval
b (double) -- ending interval
f (function) -- function defined on interval
tolerance (double) -- error tolerance (default = 0.000001)
max_iterations (int) -- number of maximum iterations (default = 100)
output (string) -- how to output the result (default = 'answer')
possible values are:
- 'answer' : to show the value of "p"
- 'table' : to show all the values in tabular form
stopping_criterion (string) -- when to stop the processing (default = 'tolerance')
possible vaulse are:
- 'tolerance' : to stop at a certain tolerance level
- 'iteration' : to stop at a certain iteration (must provide value for 'iteration' argument)
iteration (int) -- on which iteration to stop the processing (default = 100)
Returns:
bool: False if there's a problem
Otherwise it will return the value according to the value in 'output' argument.
If value of output is 'answer', it will return a float. If it is 'table', it will return a DataFrame.
"""
# check if 'f' is a function
if(not callable(f)):
print ("Please provide a function 'f'")
return False
fa = f(a)
fb = f(b)
# check if fa and fb have the same signs
if ((fa > 0 and fb > 0) or (fa < 0 and fb < 0)):
print ("This problem is unsolvable as")
print ("f(a) = ", fa)
print ("f(b) = ", fb)
print ("They are both ", "negative." if fa < 0 else "positive.")
return False
if (output == "table"):
A = list()
B = list()
P = list()
FA = list()
FB = list()
FP = list()
for i in range(1, max_iterations):
p = round(a + (b - a)/2, 9)
fp = f(p)
if (output == "table"):
A.append(a)
B.append(b)
P.append(p)
FA.append(fa)
FB.append(fb)
FP.append(fp)
if (fp == 0 or (b-a)/2 < tolerance or (stopping_criterion == 'iteration' and iteration == i)):
if (output == 'answer'):
return p
if (output == 'table'):
# create a table and return it
d = {'a': A, 'f(a)': FA, 'b' : B, 'f(b)' : FB, 'p' : P, 'f(p)': FP}
df = pd.DataFrame(data=d, columns=['a', 'f(a)', 'b', 'f(b)', 'p', 'f(p)'])
df.index = df.index + 1
return df
if (fa * fp > 0):
a = p
fa = fp
else:
b = p
fb = fp
print ("Method failed after ", max_iterations, " iterations.")
return False
Show that f(x) = x³ + 4x² − 10 = 0 has a root in [1,2], and use the Bisection method to determine an approximation to the root that is accurate to at least within 10⁻⁴
def f(x):
return pow(x, 3) + 4 * pow(x, 2) - 10
Bisection(1, 2, f, pow(10, -4), output="table")
print("The answer is : " , Bisection(1, 2, f, pow(10, -4), output="answer"))
import math
def f(x):
return math.sqrt(x) - math.cos(x)
Bisection(0, 1, f, output="table", stopping_criterion='iteration', iteration=3)
print("The answer is : " , Bisection(0, 1, f, output="answer", stopping_criterion='iteration', iteration=3))
def f(x):
return 3*(x + 1)*(x-(1/2))*(x-1)
Bisection(-2, 1.5, f, output="table", stopping_criterion='iteration', iteration=3)
print("The answer is : " , Bisection(-2, 1.5, f, output="answer", stopping_criterion='iteration', iteration=3))
Bisection(-1.25, 2.5, f, output="table", stopping_criterion='iteration', iteration=3)
print("The answer is : " , Bisection(-1.25, 2.5, f, output="answer", stopping_criterion='iteration', iteration=3))
def f(x):
return pow(x, 3) - 7*pow(x, 2) + 14*x - 6
Bisection(0, 1, f, tolerance=pow(10, -2), output="table")
print("The answer is : " , Bisection(0, 1, f, tolerance=pow(10, -2), output="answer"))
Bisection(1, 3.2, f, tolerance=pow(10, -2), output="table")
print("The answer is : " , Bisection(1, 3.2, f, tolerance=pow(10, -2), output="answer"))
Bisection(3.2, 4, f, tolerance=pow(10, -2), output="table")
print("The answer is : " , Bisection(3.2, 4, f, tolerance=pow(10, -2), output="answer"))
def f(x):
return pow(x, 4) - 2*pow(x, 3) - 4*pow(x, 2) + 4*x + 4
Bisection(-2, -1, f, tolerance=pow(10, -2), output="table")
print("The answer is : " , Bisection(-2, -1, f, tolerance=pow(10, -2), output="answer"))
Bisection(0, 2, f, tolerance=pow(10, -2), output="table")
print("The answer is : " , Bisection(0, 2, f, tolerance=pow(10, -2), output="answer"))
Bisection(2, 3, f, tolerance=pow(10, -2), output="table")
print("The answer is : " , Bisection(2, 3, f, tolerance=pow(10, -2), output="answer"))
Bisection(-1, 0, f, tolerance=pow(10, -2), output="table")
print("The answer is : " , Bisection(-1, 0, f, tolerance=pow(10, -2), output="answer"))
def f(x):
return x - pow(2, -x)
Bisection(0, 1, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(0, 1, f, tolerance=pow(10, -5), output="answer"))
import math
def f(x):
return math.exp(x) - pow(x, 2) + 3*x - 2
Bisection(0, 1, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(0, 1, f, tolerance=pow(10, -5), output="answer"))
import math
def f(x):
return 2*x*math.cos(2*x) - pow(x + 1, 2)
Bisection(-3, -2, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(-3, -2, f, tolerance=pow(10, -5), output="answer"))
Bisection(-1, 0, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(-1, 0, f, tolerance=pow(10, -5), output="answer"))
import math
def f(x):
return x * math.cos(x) - 2*pow(x, 2) + 3*x - 1
Bisection(0.2, 0.3, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(0.2, 0.3, f, tolerance=pow(10, -5), output="answer"))
Bisection(1.2, 1.3, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(1.2, 1.3, f, tolerance=pow(10, -5), output="answer"))
import math
def f(x):
return 3*x - math.exp(x)
Bisection(1, 2, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(1, 2, f, tolerance=pow(10, -5), output="answer"))
import math
def f(x):
return 2*x + 3*math.cos(x) - math.exp(x)
Bisection(0, 1, f, tolerance=pow(10, -5), output="table")
import math
def f(x):
return pow(x, 2) - 4*x + 4 - math.log(x)
Bisection(1, 2, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(1, 2, f, tolerance=pow(10, -5), output="answer"))
Bisection(2, 4, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(2, 4, f, tolerance=pow(10, -5), output="answer"))
import math
def f(x):
return x + 1 - 2*math.sin(math.pi * x)
Bisection(0, 0.5, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(0, 0.5, f, tolerance=pow(10, -5), output="answer"))
Bisection(0.5, 1, f, tolerance=pow(10, -5), output="table")
print("The answer is : " , Bisection(0.5, 1, f, tolerance=pow(10, -5), output="answer"))