Bisection Method
Fundamental Principles
The Bisection Method, also known as the Interval Halving Method, is a robust root-finding algorithm.
Theoretical Basis
Based on the Intermediate Value Theorem (IVT).
Core Concept
If a continuous function \( f(x) \) has opposite signs at endpoints \( [a, b] \), it must cross the x-axis at least once.
Prerequisites & Conditions
To apply the method successfully, the following three conditions must be met:
Continuity
The function \( f(x) \) must be continuous on the interval \( [a, b] \).
Bracketing
The initial interval must bracket the root. Mathematical verification:
Product of function values at endpoints must be negative.
Failure Condition
The method fails to start if the initial guess does not bracket a root (i.e., signs are the same).
The Algorithm
The iterative process consists of three main steps:
Calculate Midpoint
$$ x_{new} = \frac{a + b}{2} $$
Check Exact Root
If \( f(x_{new}) = 0 \), stop.
Sign Test
If \( f(a) \cdot f(x_{new}) < 0 \): Left Half.
Else: Right Half.
Interactive Simulator
Simulate the algorithm for \( f(x) = x^3 – x – 2 \). Root is approx 1.52.
Midpoint: 1.5
f(1.5) = -0.125 (Negative)
Next: Right Side [1.5, 2.0]
Convergence & Performance
Key Properties
- Rate: Linear (Slow).
- Robustness: Highly Reliable. Guaranteed to converge if bracketed.
- Comparison vs Newton-Raphson: Slower, but doesn’t diverge and needs no derivatives.
- Comparison vs Regula Falsi: Slower, but avoids getting stuck on one side.
Visualizing Error Reduction
The error halves with every single step.
Mathematical Formulas
Reference for calculations involved in the method.
Interval Reduction
Length after \( n \) iterations:
Maximum Error
Upper bound of error at step \( n \):
Required Iterations
To achieve tolerance \( \epsilon \):
Stopping Criteria
The algorithm terminates when one of the following conditions is met:
1. Tolerance Met
The interval length \( |b – a| \) is smaller than a specified tolerance \( \epsilon \).
2. Exact Root
The function value at the midpoint is exactly zero: \( f(c) = 0 \).