Regula Falsi
Fundamental Principles
The Regula Falsi method, or Method of False Position, is an ancient root-finding algorithm that improves upon Bisection by using the magnitude of function values.
Theoretical Basis
Based on Linear Interpolation using Similar Triangles. It assumes the function is approximately linear near the root.
Core Concept
Instead of blindly bisecting the interval, it draws a secant line connecting endpoints \( (a, f(a)) \) and \( (b, f(b)) \) and finds where this line crosses zero.
Prerequisites & Conditions
Similar to Bisection, Regula Falsi requires specific conditions to function:
Continuity
The function \( f(x) \) must be continuous on the interval \( [a, b] \).
Bracketing
The root must be bracketed by the interval endpoints:
Convexity Consideration
While not required for convergence, if the function is highly convex or concave, one endpoint may remain fixed, slowing convergence.
The Algorithm
The process uses the Secant formula to find the next approximation \( c \):
Calculate Root Estimate
$$ c = \frac{a f(b) – b f(a)}{f(b) – f(a)} $$
Check Exact Root
If \( f(c) = 0 \), stop.
Sign Test
If \( f(a) \cdot f(c) < 0 \): New Interval \([a, c]\).
Else: New Interval \([c, b]\).
Interactive Simulator (Regula Falsi)
Simulate for \( f(x) = x^3 – x – 2 \) on \([1, 2]\).
Notice how the yellow line is NOT in the center!
Calculated c: 1.3333
f(c) = -1.037 (Negative)
Next: Right Side [1.3333, 2.0]
Convergence & Performance
Properties
- Rate: Linear. Generally faster than Bisection, but can be slower in pathological cases.
- One-Sided Convergence: A major drawback. If the function curve is convex or concave, one endpoint (e.g., \(b\)) might stay fixed forever, while \(a\) slowly approaches the root.
- Modification: “Modified Regula Falsi” (Illinois Algorithm) exists to fix this stagnation.
Simulated Error Reduction
Approaches zero, but often not by exactly half each time.
Formulas & Derivation
The False Position Formula
Derived from the equation of the secant line passing through \((a, f(a))\) and \((b, f(b))\):
Alternative form to reduce round-off error:
Why no standard Error Formula?
Unlike Bisection where error is exactly \( \frac{L}{2^n} \), Regula Falsi’s error reduction depends on the function’s shape. It does not guarantee halving the interval length every step.
Stopping Criteria
Since the interval length might not shrink fast (one-sided convergence), we often check if the function value is close to zero.
1. Interval or Step Size
Stop if \( |c_{new} – c_{old}| < \epsilon \). (Better than checking \( |b-a| \) for this method).
2. Function Value
Stop if \( |f(c)| < \text{tolerance} \).