Everything You Need To Know
my blog
Bisection Method: An Effective Approach for Finding Function Roots
What Is A Bisection Method?
The Bisection Method is a mathematical technique used to find the roots (zero solutions) of a function within a closed interval.The Bisection Method proceeds by dividing the initial interval containing the function's root into two equal parts. Then, the signs of the function values at the midpoint of the new interval are checked. If the function value at the midpoint is zero or has a different sign than the function value at one of the interval's endpoints, then the root lies within the corresponding subinterval. This process is repeated on the subinterval containing the root until the root is found with the desired precision.
The bisection method is one of the popular numerical methods used to find the root (solution) of a nonlinear equation.
Basic Concept
The bisection method works by repeatedly dividing the search interval into two parts. In each iteration, the method determines the midpoint of the interval and checks whether the function value at that point has a different sign compared to the function value at the endpoints of the interval. If there is a sign difference, then the root lies between the two points.
Guaranteed Convergence
The bisection method guarantees convergence because it always narrows down the search interval that contains the root. If the function is continuous within the interval and has a sign difference at the endpoints, then the bisection method will keep converging towards the root.
Advantage on Monotonic Functions
The bisection method is highly efficient when used on monotonic functions within the search interval. A monotonic function is a function that is always increasing or always decreasing throughout its domain. In such cases, the bisection method can quickly approach the root by dividing the interval efficiently.
Regularly Decreasing Interval
Each iteration in the bisection method divides the search interval into two parts, effectively reducing the interval's length by half at each step. This process narrows down the interval and directs the method towards the root more quickly.
Avoiding Divergence Problems
The bisection method can avoid divergence problems that may occur in some other numerical methods. In the bisection method, the interval is always narrowed down, ensuring that no solutions are "skipped" or that solutions fail to reach the desired value.
Bisection Method Limitations
The bisection method requires a sign difference at the endpoints of the search interval to work effectively. If the function does not change sign within the interval, the method may not be able to find the root accurately. Additionally, the bisection method can converge slowly, especially for complex functions and large search intervals.
Example
You are a mathematician on an exciting quest to find the roots of a mysterious polynomial equation. The equation is x^2 + 3x - 6, and you are determined to use the bisection method to unveil its roots. Luckily, you have two initial guesses: x1 = 1 and x2 = 2. Your mission is to apply the bisection method and find the approximate value of the root within a tolerance error (galat) of e = 0.00001. The bisection method is known for its guaranteed convergence, and you are confident that it will lead you to the answer.
Can you solve this captivating problem and discover the hidden roots of the polynomial equation? Good luck on your mathematical journey!
Solved:
Step 1: Define the function and initial guesses
Given equation: f(x) = x^2 + 3x - 6
Initial guesses: x1 = 1 and x2 = 2
Tolerance error (galat): e = 0.00001
Step 2: Check if f(x1) and f(x2) have different signs
Let's calculate f(x1) and f(x2) to check if they have different signs:
f(1) = 1^2 + 3(1) - 6 = -2
f(2) = 2^2 + 3(2) - 6 = 4
Since f(x1) = -2 and f(x2) = 4, they have different signs, which means there is a root between x1 and x2.
Step 3: Implement the bisection method
Now, we'll apply the bisection method to find the approximate root of the equation. The bisection method involves repeatedly dividing the interval [x1, x2] in half and checking which half contains the root until the desired tolerance error is achieved.
Bisection Method Algorithm:
-
Set a counter (n) to keep track of the number of iterations.
Repeat the following steps until the difference between x1 and x2 is less than the tolerance error (e).
-
a. Calculate the midpoint: xt = (x1 + x2) / 2
b. Calculate f(xt)
c. If |f(xt)| is less than or equal to the tolerance error (e), then xm is the approximate root. Stop the process.
d. Otherwise, check if f(xt) and f(x1) have the same sign.
-
If they have the same sign, update x1 to xt.
If they have different signs, update x2 to xt.
-
e. Increment the counter (n) by 1.
Step 4: Perform the iterations
Let's perform the iterations using the bisection method:
Step 5: Final Result
After several iterations, the bisection method will converge, and you will find an approximate root within the tolerance error. The approximate root of the equation x^2 + 3x - 6 using the bisection method with the given initial guesses x1 = 1 and x2 = 2 is approximately:
x ≈ 1.3722801
Congratulations! You have successfully solved the problem and found the hidden root using the bisection method.
In the usage of Microsoft Excel:
Source Code:
# Mencetak Judul Metode
print("\nMETODE BISECTION \n")
#! Lambda merupakan function anonymous dalam python {tidak memiliki nama, seperti def fungsi() }
#* f = lambda x : x**2+3*x-6 ----> Secara matematis f(x) = x**2+3*x-6
#? Keunggulan lambda, memiliki banyak argumen, namun memiliki satu ekspresi.
#TODO Berguna dalam fungsi untuk melakukan proses subsitusi, dan sangat efisiensi dalam koding
# Misalnya f(x) = x**2+3*x-6, ketika memanggil fungsi f(x1) menjadi f(x1)=x1**2+3*x1-6 untuk dilakukan subsitusi
f = lambda x : x**2+3*x-6
#? Menentukan nilai x1 dan x2, serta nilai acuan toleransi (eror)
x1 = 1
x2 = 2
e = 0.00001
fx1 = f(x1)
fx2 = f(x2)
#! Cek, jika memenuhi maka persamaan tidak memiliki akar, dan proses stop
if (fx1 * fx2 >= 0):
print("Persamaan tidak memiliki akar")
exit
#! Cek, jika memenuhi maka menghitung nilai xt, serta f(xt)
if (fx1 * fx2 < 0):
xt = (x1+x2)/2
fxt = f(xt)
#TODO Melakukan pengulangan, dengan iterasi maksimal 100
for i in range(1, 100):
# Mencetak semua proses pengulangan { iterasi, nilai x1, x2, xt, f(x1), f(x2), f(xt), f(x1)*f(xt), dan |f(xt)| }
print("Iterasi ", i)
print("x1 \t\t=", x1)
print("x2 \t\t=", x2)
print("xt \t\t=", xt)
print("f(x1) \t\t=", fx1)
print("f(x2) \t\t=", fx2)
print("f(xt) \t\t=", fxt)
print("f(x1)*f(xt)\t=", fx1*fxt)
print("|f(xt)| \t=", abs(fxt))
#TODO Cek, jika memenuhi maka akan berhenti
if abs(fxt) <= e:
print("Keterangan \t= Berhenti\n")
break
#TODO Cek, jika tidak memenuhi akan melanjutkan perhitungan iterasi selanjutnya
else:
print("Keterangan \t= Lanjutkan Iterasi \n")
#* Untuk iterasi selanjutnya, cek jika memenuhi, maka nilai x1 baru adalah xt, dan nilai x2 tetap
if (fx1 * fxt > 0):
x1 = xt
x2 = x2
#* Untuk iterasi selanjutnya, cek jika memenuhi, maka nilai x2 baru adalah xt, dan nilai x1 tetap
elif (fx1 * fxt < 0):
x2 = xt
x1 = x1
#TODO Perhitungan nilai xt, f(xt), f(x1), dan f(x2) dalam pengulangan
xt = (x1 + x2) / 2
fxt = f(xt)
fx1 = f(x1)
fx2 = f(x2)
Program Result:
METODE BISECTION
Iterasi 1
x1 = 1
x2 = 2
xt = 1.5
f(x1) = -2
f(x2) = 4
f(xt) = 0.75
f(x1)*f(xt) = -1.5
|f(xt)| = 0.75
Keterangan = Lanjutkan Iterasi
Iterasi 2
x1 = 1
x2 = 1.5
xt = 1.25
f(x1) = -2
f(x2) = 0.75
f(xt) = -0.6875
f(x1)*f(xt) = 1.375
|f(xt)| = 0.6875
Keterangan = Lanjutkan Iterasi
Iterasi 3
x1 = 1.25
x2 = 1.5
xt = 1.375
f(x1) = -0.6875
f(x2) = 0.75
f(xt) = 0.015625
f(x1)*f(xt) = -0.0107421875
|f(xt)| = 0.015625
Keterangan = Lanjutkan Iterasi
Iterasi 4
x1 = 1.25
x2 = 1.375
xt = 1.3125
f(x1) = -0.6875
f(x2) = 0.015625
f(xt) = -0.33984375
f(x1)*f(xt) = 0.233642578125
|f(xt)| = 0.33984375
Keterangan = Lanjutkan Iterasi
Iterasi 5
x1 = 1.3125
x2 = 1.375
xt = 1.34375
f(x1) = -0.33984375
f(x2) = 0.015625
f(xt) = -0.1630859375
f(x1)*f(xt) = 0.055423736572265625
|f(xt)| = 0.1630859375
Keterangan = Lanjutkan Iterasi
Iterasi 6
x1 = 1.34375
x2 = 1.375
xt = 1.359375
f(x1) = -0.1630859375
f(x2) = 0.015625
f(xt) = -0.073974609375
f(x1)*f(xt) = 0.012064218521118164
|f(xt)| = 0.073974609375
Keterangan = Lanjutkan Iterasi
Iterasi 7
x1 = 1.359375
x2 = 1.375
xt = 1.3671875
f(x1) = -0.073974609375
f(x2) = 0.015625
f(xt) = -0.02923583984375
f(x1)*f(xt) = 0.0021627098321914673
|f(xt)| = 0.02923583984375
Keterangan = Lanjutkan Iterasi
Iterasi 8
x1 = 1.3671875
x2 = 1.375
xt = 1.37109375
f(x1) = -0.02923583984375
f(x2) = 0.015625
f(xt) = -0.0068206787109375
f(x1)*f(xt) = 0.00019940827041864395
|f(xt)| = 0.0068206787109375
Keterangan = Lanjutkan Iterasi
Iterasi 9
x1 = 1.37109375
x2 = 1.375
xt = 1.373046875
f(x1) = -0.0068206787109375
f(x2) = 0.015625
f(xt) = 0.004398345947265625
f(x1)*f(xt) = -2.999970456585288e-05
|f(xt)| = 0.004398345947265625
Keterangan = Lanjutkan Iterasi
Iterasi 10
x1 = 1.37109375
x2 = 1.373046875
xt = 1.3720703125
f(x1) = -0.0068206787109375
f(x2) = 0.004398345947265625
f(xt) = -0.0012121200561523438
f(x1)*f(xt) = 8.267481462098658e-06
|f(xt)| = 0.0012121200561523438
Keterangan = Lanjutkan Iterasi
Iterasi 11
x1 = 1.3720703125
x2 = 1.373046875
xt = 1.37255859375
f(x1) = -0.0012121200561523438
f(x2) = 0.004398345947265625
f(xt) = 0.001592874526977539
f(x1)*f(xt) = -1.9307551610836526e-06
|f(xt)| = 0.001592874526977539
Keterangan = Lanjutkan Iterasi
Iterasi 12
x1 = 1.3720703125
x2 = 1.37255859375
xt = 1.372314453125
f(x1) = -0.0012121200561523438
f(x2) = 0.001592874526977539
f(xt) = 0.00019031763076782227
f(x1)*f(xt) = -2.3068781729307375e-07
|f(xt)| = 0.00019031763076782227
Keterangan = Lanjutkan Iterasi
Iterasi 13
x1 = 1.3720703125
x2 = 1.372314453125
xt = 1.3721923828125
f(x1) = -0.0012121200561523438
f(x2) = 0.00019031763076782227
f(xt) = -0.0005109161138534546
f(x1)*f(xt) = 6.192916686131866e-07
|f(xt)| = 0.0005109161138534546
Keterangan = Lanjutkan Iterasi
Iterasi 14
x1 = 1.3721923828125
x2 = 1.372314453125
xt = 1.37225341796875
f(x1) = -0.0005109161138534546
f(x2) = 0.00019031763076782227
f(xt) = -0.00016030296683311462
f(x1)*f(xt) = 8.190136885355415e-08
|f(xt)| = 0.00016030296683311462
Keterangan = Lanjutkan Iterasi
Iterasi 15
x1 = 1.37225341796875
x2 = 1.372314453125
xt = 1.372283935546875
f(x1) = -0.00016030296683311462
f(x2) = 0.00019031763076782227
f(xt) = 1.5006400644779205e-05
f(x1)*f(xt) = -2.405570544844471e-09
|f(xt)| = 1.5006400644779205e-05
Keterangan = Lanjutkan Iterasi
Iterasi 16
x1 = 1.37225341796875
x2 = 1.372283935546875
xt = 1.3722686767578125
f(x1) = -0.00016030296683311462
f(x2) = 1.5006400644779205e-05
f(xt) = -7.264851592481136e-05
f(x1)*f(xt) = 1.1645772638770036e-08
|f(xt)| = 7.264851592481136e-05
Keterangan = Lanjutkan Iterasi
Iterasi 17
x1 = 1.3722686767578125
x2 = 1.372283935546875
xt = 1.3722763061523438
f(x1) = -7.264851592481136e-05
f(x2) = 1.5006400644779205e-05
f(xt) = -2.8821115847676992e-05
f(x1)*f(xt) = 2.093811293630795e-09
|f(xt)| = 2.8821115847676992e-05
Keterangan = Lanjutkan Iterasi
Iterasi 18
x1 = 1.3722763061523438
x2 = 1.372283935546875
xt = 1.3722801208496094
f(x1) = -2.8821115847676992e-05
f(x2) = 1.5006400644779205e-05
f(xt) = -6.907372153364122e-06
f(x1)*f(xt) = 1.9907817303512545e-10
|f(xt)| = 6.907372153364122e-06
Keterangan = Berhenti
[Done] exited with code=0 in 0.953 seconds