- Define a root and apply the Intermediate Value Theorem to determine bracketing intervals ($f(a)f(b) < 0$).
- State the Bisection algorithm, prove its guaranteed convergence, and calculate the minimum iteration bound $n \ge \log_2((b-a)/\epsilon) - 1$.
- Derive the Regula-Falsi (False Position) formula algebraically using the two-point chord equation.
- Derive the Newton-Raphson formula using Taylor series expansion and prove its Quadratic Order of Convergence ($p = 2$).
- Analyze the 3 critical failure conditions of Newton-Raphson ($f'(x_n) = 0$, inflection points, poor initial guess).
- Apply Descartes' Rule of Signs to bound the number of positive, negative, and complex roots.
In school, we solve quadratic equations $ax^2 + bx + c = 0$ easily using the quadratic formula $x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$. But what if you encounter an equation like: $$x e^x - 1 = 0 \quad \text{or} \quad x^3 - x - 11 = 0 \quad \text{or} \quad \cos(x) - x = 0$$ By the Abel-Ruffini theorem, general polynomials of degree 5 or higher (and transcendental equations mixing algebra with trigonometry/exponentials) have **no closed-form algebraic formula**!
**Numerical Methods** solve this by starting with a rough guess and generating a sequence of approximations $x_0, x_1, x_2, \dots \to \alpha$ that zoom in on the true root with pinpoint decimal precision!
A real number $\alpha$ is defined as a root (or zero) of an equation $f(x) = 0$ if and only if $f(\alpha) = 0$. Geometrically, a real root is the $x$-coordinate where the graph $y = f(x)$ crosses or touches the $x$-axis.
Let $f(x)$ be a continuous function on a closed interval $[a, b]$. If the function values at the endpoints have opposite algebraic signs: $$f(a) \cdot f(b) < 0$$ then there exists at least one real root $\alpha \in (a, b)$ such that $f(\alpha) = 0$.
Every bracketing algorithm (Bisection, Regula-Falsi) requires an initial sign-changing bracket $[a, b]$ before beginning iterations.
The Bisection Method (or Interval Halving Method) repeatedly divides a bracketing interval $[a, b]$ in half and selects the sub-interval that maintains opposite signs.
- Choose initial endpoints $a$ and $b$ such that $f(a) \cdot f(b) < 0$.
- Calculate the interval midpoint: $c = \frac{a + b}{2}$.
- Evaluate $f(c)$. If $f(c) = 0$, then $c$ is the exact root; stop.
- If $f(a) \cdot f(c) < 0$, the root lies in $[a, c]$; set $b = c$.
- If $f(c) \cdot f(b) < 0$, the root lies in $[c, b]$; set $a = c$.
- Check stopping criteria: If $|b - a| < \epsilon$ or $|f(c)| < \delta$, stop.
- Otherwise, repeat Steps 2–6 until required decimal accuracy is reached.
Proof of Guaranteed Convergence (CSJMU 2018):
Let $[a_n, b_n]$ denote the bracket at the $n$-th iteration. At each step, the interval width is halved:
$$b_n - a_n = \frac{b - a}{2^n}$$As $n \to \infty$, since $\lim_{n \to \infty} \frac{b - a}{2^n} = 0$, the interval width shrinks to zero.
The lower bounds form a bounded, monotonically non-decreasing sequence: $a_1 \le a_2 \le a_3 \le \dots \le b_1$.
The upper bounds form a bounded, monotonically non-increasing sequence: $b_1 \ge b_2 \ge b_3 \ge \dots \ge a_1$.
By the Bolzano-Weierstrass Monotone Convergence Theorem, both sequences converge to a common limit $\alpha$:
Since $f$ is continuous and $f(a_n) \cdot f(b_n) \le 0$ for all $n$, taking limits yields $f(\alpha) \cdot f(\alpha) \le 0 \implies [f(\alpha)]^2 \le 0$. Since a real square cannot be negative, $f(\alpha) = 0$. Hence, the Bisection Method is mathematically guaranteed to converge!
Error Bound and Iteration Count Formula:
The maximum error after $n$ iterations is bounded by: $E_n = |c_n - \alpha| \le \frac{b - a}{2^{n+1}}$. To guarantee error strictly less than tolerance $\epsilon$:
$$\frac{b - a}{2^{n+1}} < \epsilon \implies 2^{n+1} > \frac{b - a}{\epsilon} \implies n > \log_2\left(\frac{b - a}{\epsilon}\right) - 1 = \frac{\ln((b-a)/\epsilon)}{\ln 2} - 1$$Step-by-Step Solved University Exam Numerical
Problem (CSJMU 2024–25): Find a real root of $f(x) = x^3 - x - 11 = 0$ using the Bisection method correct to 2 decimal places.
• Initial Testing: $f(2) = 2^3 - 2 - 11 = 8 - 13 = -5 < 0$.
• $f(3) = 3^3 - 3 - 11 = 27 - 14 = +13 > 0$.
Since $f(2) \cdot f(3) < 0$, a root lies in $[2, 3]$.
| Iteration $n$ | $a$ | $b$ | $c = \frac{a+b}{2}$ | $f(c) = c^3 - c - 11$ | Sign of $f(c)$ | Next Interval |
|---|---|---|---|---|---|---|
| 1 | 2.0000 | 3.0000 | 2.5000 | +2.1250 | Positive (+) | $[2.0, 2.5]$ |
| 2 | 2.0000 | 2.5000 | 2.2500 | $-1.8594$ | Negative (-) | $[2.25, 2.5]$ |
| 3 | 2.2500 | 2.5000 | 2.3750 | +0.0215 | Positive (+) | $[2.25, 2.375]$ |
| 4 | 2.2500 | 2.3750 | 2.3125 | $-0.9460$ | Negative (-) | $[2.3125, 2.375]$ |
| 5 | 2.3125 | 2.3750 | 2.3438 | $-0.4690$ | Negative (-) | $[2.3438, 2.375]$ |
Continuing iterations yields the root $\mathbf{\alpha \approx 2.374}$ correct to 3 decimal places.
The Regula-Falsi Method improves on Bisection by taking into account the actual magnitudes of $f(a)$ and $f(b)$. Instead of choosing the midpoint, it connects $(a, f(a))$ and $(b, f(b))$ by a straight chord and takes the $x$-intercept of that chord as the next approximation.
The two-point equation of the straight secant line passing through $(a, f(a))$ and $(b, f(b))$ is: $$\frac{y - f(a)}{x - a} = \frac{f(b) - f(a)}{b - a}$$ To find the $x$-intercept, set $y = 0$: $$\frac{-f(a)}{x - a} = \frac{f(b) - f(a)}{b - a} \implies x - a = -\frac{f(a)(b - a)}{f(b) - f(a)}$$ $$x = a - \frac{f(a)(b - a)}{f(b) - f(a)} = \frac{a[f(b) - f(a)] - f(a)(b - a)}{f(b) - f(a)} = \mathbf{\frac{a f(b) - b f(a)}{f(b) - f(a)}}$$
Step-by-Step Solved University Numerical
Problem: Find the positive root of $f(x) = x^2 - 5 = 0$ (i.e. $\sqrt{5}$) using Regula-Falsi on $[2, 3]$.
• $f(2) = 2^2 - 5 = -1 < 0$
• $f(3) = 3^2 - 5 = +4 > 0$
$f(2) \cdot f(3) < 0 \implies$ Bracket is $[2, 3]$ with $a = 2, f(a) = -1$ and $b = 3, f(b) = 4$.
Iteration 1:
$$x_1 = \frac{a f(b) - b f(a)}{f(b) - f(a)} = \frac{(2)(4) - (3)(-1)}{4 - (-1)} = \frac{8 + 3}{5} = \frac{11}{5} = \mathbf{2.2000}$$ $$f(2.2) = (2.2)^2 - 5 = 4.84 - 5 = -0.16 < 0$$ Since $f(2.2)$ is negative, replace $a$ with $2.2000$. New bracket is $[2.2000, 3.0000]$.Iteration 2:
$$x_2 = \frac{(2.2)(4) - (3)(-0.16)}{4 - (-0.16)} = \frac{8.8 + 0.48}{4.16} = \frac{9.28}{4.16} \approx \mathbf{2.2308}$$ $$f(2.2308) = (2.2308)^2 - 5 = 4.9765 - 5 = -0.0235$$ Since $\sqrt{5} \approx 2.2360$, Regula-Falsi approaches the root much faster than Bisection in fewer steps!The Newton-Raphson Method is an open root-finding method that uses the tangent line to the function at the current point $x_n$ to estimate the next point $x_{n+1}$.
Let $x_n$ be an approximation to the root $\alpha$. Let $h = x_{n+1} - x_n$ be the correction. Expanding $f(x_n + h)$ by Taylor series: $$f(x_n + h) = f(x_n) + h f'(x_n) + \frac{h^2}{2} f''(x_n) + \dots = 0$$ Assuming $h$ is small, neglect second- and higher-order terms: $$f(x_n) + h f'(x_n) \approx 0 \implies h = -\frac{f(x_n)}{f'(x_n)}$$ Since $x_{n+1} = x_n + h$, we obtain the celebrated **Newton-Raphson Iterative Formula**: $$\mathbf{x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}}$$
Complete Proof of Quadratic Convergence ($p = 2$):
Let $\alpha$ be the true root such that $f(\alpha) = 0$ and $f'(\alpha) \ne 0$. Let $e_n = x_n - \alpha$ be the error at step $n$, so $x_n = \alpha + e_n$ and $x_{n+1} = \alpha + e_{n+1}$. Substituting into the formula:
$$\alpha + e_{n+1} = \alpha + e_n - \frac{f(\alpha + e_n)}{f'(\alpha + e_n)}$$ $$e_{n+1} = e_n - \frac{f(\alpha + e_n)}{f'(\alpha + e_n)}$$Expanding $f(\alpha + e_n)$ and $f'(\alpha + e_n)$ using Taylor series about $\alpha$ (remembering $f(\alpha) = 0$):
$$f(\alpha + e_n) = e_n f'(\alpha) + \frac{e_n^2}{2} f''(\alpha) + O(e_n^3)$$ $$f'(\alpha + e_n) = f'(\alpha) + e_n f''(\alpha) + O(e_n^2) = f'(\alpha)\left[1 + e_n \frac{f''(\alpha)}{f'(\alpha)}\right]$$Dividing numerator by denominator using binomial expansion $(1 + z)^{-1} \approx 1 - z$:
$$\frac{f(\alpha + e_n)}{f'(\alpha + e_n)} = \left[e_n + \frac{e_n^2}{2} \frac{f''(\alpha)}{f'(\alpha)}\right] \cdot \left[1 - e_n \frac{f''(\alpha)}{f'(\alpha)}\right] = e_n - \frac{e_n^2}{2}\frac{f''(\alpha)}{f'(\alpha)} + O(e_n^3)$$Now substitute back into the error equation:
$$e_{n+1} = e_n - \left[e_n - \frac{e_n^2}{2}\frac{f''(\alpha)}{f'(\alpha)}\right] = \mathbf{\left[\frac{f''(\alpha)}{2 f'(\alpha)}\right] e_n^2}$$Hence, $e_{n+1} \propto e_n^2$. The order of convergence is strictly **$p = 2$ (Quadratic)**! The number of correct decimal places doubles at each subsequent iteration!
The 3 Critical Failure Conditions of Newton-Raphson:
- Zero Derivative ($f'(x_n) = 0$): Tangent is horizontal and parallel to the $x$-axis; division by zero occurs and the method crashes.
- Inflection Point ($f''(x) = 0$ near root): The method can oscillate indefinitely in an infinite 2-cycle loop ($x_0 \to x_1 \to x_0 \to x_1$).
- Poor Initial Guess: If $x_0$ is chosen too far from $\alpha$, the tangent shoots off towards infinity, diverging away from the root.
Step-by-Step Solved University Numerical
Problem: Find $\sqrt{12}$ correct to 4 decimal places using Newton-Raphson.
Let $x = \sqrt{12} \implies x^2 - 12 = 0$. Hence $f(x) = x^2 - 12$ and $f'(x) = 2x$.
$$x_{n+1} = x_n - \frac{x_n^2 - 12}{2x_n} = \frac{2x_n^2 - x_n^2 + 12}{2x_n} = \mathbf{\frac{1}{2}\left(x_n + \frac{12}{x_n}\right)}$$Take initial guess $x_0 = 3.5$ (since $3^2 = 9$ and $4^2 = 16$):
• Iteration 1: $x_1 = \frac{1}{2}\left(3.5 + \frac{12}{3.5}\right) = \frac{1}{2}(3.5 + 3.42857) = \mathbf{3.46429}$
• Iteration 2: $x_2 = \frac{1}{2}\left(3.46429 + \frac{12}{3.46429}\right) = \frac{1}{2}(3.46429 + 3.46391) = \mathbf{3.46410}$
Notice that in just 2 iterations, we have achieved $\sqrt{12} \approx \mathbf{3.4641}$ correct to 5 significant digits!
Descartes' Rule of Signs provides an upper bound on the number of positive and negative real roots of a polynomial equation with real coefficients without needing to solve it:
- Positive Real Roots: The number of positive real roots of $P(x) = 0$ is either equal to the number of sign variations in the coefficients of $P(x)$, or less than it by an even integer.
- Negative Real Roots: The number of negative real roots of $P(x) = 0$ is either equal to the number of sign variations in the coefficients of $P(-x)$, or less than it by an even integer.
- Complex Roots: If a polynomial of degree $n$ has $p$ positive roots and $q$ negative roots, the remaining roots $n - (p + q)$ are complex conjugate pairs!
Solved Example:
Consider $P(x) = x^4 - 3x^3 + 7x^2 - 5x + 2 = 0$ (Degree $n = 4$):
1. Sign sequence of $P(x)$: $+1, -3, +7, -5, +2$.
• $+ \to -$ (1), $- \to +$ (2), $+ \to -$ (3), $- \to +$ (4) $\implies \mathbf{4}$ sign changes.
Therefore, there are either $4$, $2$, or $0$ positive real roots.
2. Substitute $-x$: $P(-x) = (-x)^4 - 3(-x)^3 + 7(-x)^2 - 5(-x) + 2 = x^4 + 3x^3 + 7x^2 + 5x + 2$.
• All coefficients are positive: $+1, +3, +7, +5, +2 \implies \mathbf{0}$ sign changes.
Therefore, there are zero negative real roots!
| Evaluation Factor | Bisection Method | Regula-Falsi Method | Newton-Raphson Method |
|---|---|---|---|
| Type of Method | Bracketing (Closed) | Bracketing (Closed) | Open (Single-point tangent) |
| Order of Convergence ($p$) | $p = 1$ (Linear) | $p = 1$ (Linear / $1.618$) | $p = 2$ (Quadratic) |
| Convergence Guarantee | 100% Guaranteed if $f(a)f(b) < 0$. | Guaranteed if $f(a)f(b) < 0$. | Not guaranteed; can diverge if $f'(x) = 0$ or poor $x_0$. |
| Rate of Convergence | Very slow (gain 1 bit per step). | Faster than bisection, but can have slow one-sided stagnancy. | Extremely rapid; error doubles in precision each step. |
| Derivative Needed? | No ($f$ only). | No ($f$ only). | Yes ($f'(x)$ is mandatory). |
- Geometric Diagram (2 Marks): Draw axes, curve $y = f(x)$, root $\alpha$, point $(x_0, f(x_0))$, and tangent line intersecting the $x$-axis at $x_1$.
- Taylor Series Derivation (3 Marks): Write $f(x_n + h) = f(x_n) + h f'(x_n) + \dots = 0$. Solve for $h = -f(x_n)/f'(x_n)$ to give $x_{n+1} = x_n - f(x_n)/f'(x_n)$.
- Quadratic Convergence Proof (3 Marks): Substitute $x_n = \alpha + e_n$, expand $f(\alpha + e_n)$ and $f'(\alpha + e_n)$, use binomial expansion to arrive at $e_{n+1} \approx \frac{f''(\alpha)}{2f'(\alpha)} e_n^2$. Clearly state $p = 2$.
- Failure Pitfalls (2 Marks): List $f'(x_n) = 0$ (division by zero), point of inflection, and poor initial guess.
• Forgetting Derivative in Newton-Raphson: Newton-Raphson requires computing $f'(x)$. If the derivative is hard to compute or zero, the method cannot be used.
• Using Radian Mode in Trigonometric Numericals: If solving $f(x) = \cos x - x = 0$, your scientific calculator MUST be set to RADIANS, not DEGREES! Entering degrees results in completely wrong answers!
Verify your conceptual understanding across Bisection, Regula-Falsi, Newton-Raphson, and Descartes' Rule with this 10-question quiz.