home
Mission
////////
home
////////

Numerical Root Finding Techniques (AI-friendly)

Tags

Bisection Method

Numerical technique that approximates the root (zero) of a given function by finding values of xx for which f(x)=0f(x)=0.
The bisection method repeatedly bisects an interval and determines which subinterval the root lies in, eventually narrowing down the interval that the zero resides in to a desired level of precision.
While it is robust and guaranteed to converge to a solution as long as the function is continuous and changes sign over the interval, the bisection method converges slowly compared to other methods.
Algorithm
For any continuous function f(x)f(x), there must exist at least one zero within a closed interval [x1,x2][x_1,x_2], where f(x1)⋅f(x2)<0f(x_1)\cdot f(x_2)<0 (function values are opposite signs at the ends of the interval, so the continuous graph must have crossed the x-axis at at least one point.)
1.
xi+2=xi+xi+12x_{i+2}=\frac{x_i+x_{i+1}}2 to find the midpoint of the current interval
2.
If f(xi+2)=0,(xi+2,0)f(x_{i+2})=0, (x_{i+2},0) is the function’s root (zero).
3.
If f(xi+2)≠0f(x_{i+2})\neq 0,
a.
If f(xi)f(xi+2)<0f(x_i)f(x_{i+2})<0, the function’s root (zero) lies in [xi,xi+2][x_i,x_{i+2}]. Repeat step 1 for interval [xi,xi+2][x_i,x_{i+2}].
b.
Otherwise, if f(xi+2)f(xi+1)<0f(x_{i+2})f(x_{i+1})<0, the function’s root (zero) lies in [xi+2,xi+1][x_{i+2},x_{i+1}]. Repeat step 1 for interval [xi+2,xi+1][x_{i+2},x_{i+1}].
4.
Repeat process until f(xi)=0f(x_i)=0 or f(xi)<εf(x_i)<ε, where εε is a predefined threshold condition for terminating the bisection algorithm.
Investigation
Zero of function lies in closed interval [x3,x2] as f(x3) and f(x2) are opposite signs.Bisect the [x3,x2] into two subintervals, [x3,x4] and [x4,x2].Zero of function lies in closed interval [x3,x4] as f(x3) and f(x4) are opposite signs.Repeat process until sufficiently precise interval containing zero is obtained.\begin{align*} &\text{Zero of function lies in closed interval } [x_3, x_2] \text{ as } f(x_3) \text{ and } f(x_2) \text{ are opposite signs.} \\ &\text{Bisect the } [x_3, x_2] \text{ into two subintervals, } [x_3, x_4] \text{ and } [x_4, x_2]. \\ &\text{Zero of function lies in closed interval } [x_3, x_4] \text{ as } f(x_3) \text{ and } f(x_4) \text{ are opposite signs.} \\ &\text{Repeat process until sufficiently precise interval containing zero is obtained.} \end{align*}
Extension
•
What other numerical algorithms exist for finding the zero of a function? (Newton-Raphson Method)
•
Can numerical algorithms be used for other tasks, like finding the maximum or minimum point of a function?
•
How would numerical algorithms work for multivariate functions?
•
What are the pitfalls of numerical algorithms? Are there cases where they fail to converge/terminate? When is it disadvantageous to use numerical techniques compared to analytical methods?
•
How do we define and compare the performance of numerical algorithms?