Method of False Position (Regula Falsi)

Goal of this chapter

Understand the principle of the method of false position (Regula Falsi), how it differs from bisection, how its convergence speed is improved, and improved variants such as the Illinois method.

Prerequisites

Contents

1. Definition and Principle

Regula Falsi (Latin for "false rule") starts, like bisection, from an interval $[a,b]$ satisfying $f(a)\cdot f(b) < 0$, but takes as the next approximation an estimate obtained by linear interpolation rather than the midpoint of the interval.

Basic idea

Take the point where the straight line (secant) joining the two endpoints $(a, f(a))$ and $(b, f(b))$ crosses the $x$-axis as the next approximation $c$. If $f$ is roughly linear across the interval, $c$ gives a better approximation to the root than the midpoint.

This is an ancient technique going back to Babylonian mathematics, and it was widely used by medieval Arab and European mathematicians.

0 / 0
Figure 1. Principle of Regula Falsi ($f(x) = x^3 - x - 2$, interval $[1, 2]$). The secant joining the two points $(a, f(a))$, $(b, f(b))$ meets the $x$-axis at $c = \dfrac{a\,f(b) - b\,f(a)}{f(b) - f(a)}$, which becomes the next approximation; the endpoint whose sign matches $f(c)$ is replaced by $c$, keeping the sign-change bracket (the bar below). Use "▶ Auto-play" or "Next / Prev" to check one step at a time; the true root $x^*$ is shown only at the end, after convergence.

2. Derivation of the Formula

The line through the two points $(a, f(a))$ and $(b, f(b))$ has the equation

$$y - f(a) = \dfrac{f(b) - f(a)}{b - a}(x - a)$$

Setting $y = 0$ and solving for $x$ gives the next approximation $c$.

$$c = \dfrac{a \cdot f(b) - b \cdot f(a)}{f(b) - f(a)}$$

This can be read as a weighted average of $a$ and $b$ by their function values: when $|f(a)|$ is small, $c$ moves toward $a$; when $|f(b)|$ is small, $c$ moves toward $b$. An equivalent form is

$$c = a - f(a) \cdot \dfrac{b - a}{f(b) - f(a)}$$

This is identical to the formula of the secant method, but Regula Falsi differs in that it always preserves the sign change.

Difference from the secant method (same formula, different choice of points)

Both compute the next approximation with the same intersection formula $c = \dfrac{a\,f(b)-b\,f(a)}{f(b)-f(a)}$. The only difference is which two points are kept for the next iteration.

  • Secant method: always uses the two most recent points (the older one is dropped unconditionally). It has no guarantee of bracketing the root and may diverge, but it uses the latest information and is fast (order $\varphi \approx 1.618$).
  • Regula Falsi: keeps the two points of opposite sign (the pair that brackets the root). The endpoint that ends up with the same sign is replaced by $c$, so the root is always bracketed and convergence is guaranteed. However, one endpoint can stay fixed, leading to stagnation.

For the same $f(x)=x^3-x-2$ and the same initial points $1, 2$, the first step gives $c=1.333$ in both. But the secant method then also uses the same-sign point $(1.333,\,1.463)$ and reaches the root $1.5214$ quickly via $1.531 \to \cdots$, whereas Regula Falsi keeps the endpoint $b=2$ to bracket the root, so only the $a$ side creeps up as $1.333 \to 1.463 \to 1.504 \to \cdots$ (stagnation). The improvement that breaks this stagnation is the Illinois method of the next section.

3. Algorithm

Regula Falsi (basic form)

  1. Choose an initial interval $[a, b]$ with $f(a) \cdot f(b) < 0$.
  2. Compute $c = \dfrac{a \cdot f(b) - b \cdot f(a)}{f(b) - f(a)}$.
  3. If $|f(c)| < \varepsilon$ or $|b - a| < \delta$, return $c$ as the root.
  4. If $f(a) \cdot f(c) < 0$, set $b \leftarrow c$; otherwise set $a \leftarrow c$.
  5. Repeat 2--4 until the iteration count reaches the limit $N_{\max}$.

Pseudocode follows.

function regulaFalsi(f, a, b, tol, maxIter):
    assert f(a) * f(b) < 0
    fa = f(a)
    fb = f(b)
    for i = 1 to maxIter:
        c  = (a * fb - b * fa) / (fb - fa)
        fc = f(c)
        if |fc| < tol:
            return c
        if fa * fc < 0:
            b  = c
            fb = fc
        else:
            a  = c
            fa = fc
    return c

4. Comparison with Bisection

PropertyBisectionRegula Falsi
Next approximationMidpoint $(a+b)/2$Linear interpolation $\dfrac{af(b)-bf(a)}{f(b)-f(a)}$
Use of function valuesSign onlySign and magnitude
Convergence guaranteeAlwaysAlways
Convergence speed (ideal case)Linear (1.0)Superlinear (~1.618)
Possibility of stagnationNoneYes (one endpoint fixed)
Monotone shrinking of the intervalGuaranteedNot guaranteed
Worst-case convergence speedLinearCan be slower than linear

Because Regula Falsi uses information about the slope of the function, it is far faster than bisection when $f$ is roughly linear across the interval. However, when $f$ has strong convexity, stagnation (see the next section) occurs and it can become slower than bisection.

5. The Stagnation Problem and the Illinois Method

Stagnation

In Regula Falsi, when the function is convex (or concave), one endpoint may go many iterations without being updated, staying fixed. This is called stagnation.

For example, if $f$ is convex with $f(a) < 0$, $f(b) > 0$, the secant runs above the curve and therefore always crosses the $x$-axis on the left of the root, so the endpoint $b$ stays fixed while only $a$ is updated. Because the interval width does not shrink efficiently, convergence slows markedly.

Illustration of stagnation. For the convex function f(x)=x³−x−2 on the interval [1,2], the endpoint b stays fixed while only the a side updates, and the secant's x-axis intersection c approaches the root x* slowly from the left.
Figure 2. Illustration of stagnation ($f(x)=x^3-x-2$, interval $[1,2]$). For this convex function the secant runs above the curve and therefore always crosses the $x$-axis on the left of the root, so the endpoint $b$ stays fixed while only the $a$ side updates. The intersections $c_0, c_1, \ldots$ approach the root $x^*$ slowly from the left, and because the interval width does not shrink efficiently, convergence becomes very slow.

The Illinois Method

The Illinois method (Illinois algorithm) is an improvement that detects stagnation and halves the function value at the fixed endpoint to avoid it. Concretely, when the same endpoint is kept for two consecutive iterations, its function value is halved.

Principle of the Illinois method. Halving the function value f(b)=4 at the fixed endpoint b to 2 tilts the secant (orange) downward, moving its x-axis intersection from c (left of the root, plain Regula Falsi) to c′ (right of the root). This updates b and resolves the stagnation.
Figure 3. How the Illinois method resolves stagnation ($f(x)=x^3-x-2$). During stagnation, plain Regula Falsi uses the point $(b,\,f(b))$ at the fixed endpoint $b$, so the intersection $c$ of the secant (grey dashed) always falls on the left of the root and only $a$ moves. The Illinois method uses the point $(b,\,f(b)/2)$ with $f(b)$ halved, so the secant (orange) tilts downward and the intersection $c'$ moves to the right of the root. The sign of $f(c')$ then changes, so this time $b$ is updated and the stagnation is resolved.

Illinois method

  1. Choose an initial interval $[a, b]$ with $f(a) \cdot f(b) < 0$. Set $\text{side} = 0$.
  2. Compute $c = \dfrac{a \cdot f(b) - b \cdot f(a)}{f(b) - f(a)}$ and evaluate $f(c)$.
  3. If $|f(c)| < \varepsilon$, return $c$ as the root.
  4. If $f(a) \cdot f(c) < 0$:
    • $b \leftarrow c$, $f(b) \leftarrow f(c)$
    • If $\text{side} = -1$ (the previous step also updated $b$), set $f(a) \leftarrow f(a)/2$
    • Set $\text{side} = -1$
  5. Otherwise:
    • $a \leftarrow c$, $f(a) \leftarrow f(c)$
    • If $\text{side} = +1$ (the previous step also updated $a$), set $f(b) \leftarrow f(b)/2$
    • Set $\text{side} = +1$
  6. Repeat 2--5 until the iteration count reaches the limit.

Besides the Illinois method, there are other improvements such as the Pegasus method (weighting by $f(b) \cdot f(c) / (f(c) + f(b))$) and the Anderson-Bjorck method (a more refined weight adjustment).

The improvements differ only in the "stagnation weight"

All of these improvements are the same method of false position (same intersection formula, always bracketing the root); the only difference is the weight $g$ applied to the function value at the fixed endpoint when the same endpoint is kept twice in a row (i.e. the other side has stagnated). The more adaptively the weight responds to the function values, the sooner the secant moves to the opposite side of the root, and the faster the convergence.

MethodWeight $g$ on the fixed endpointOrder (simple root)Notes
Regula Falsi (basic)$1$ (no shrinking)Degrades to linear when stagnatingStagnates
Illinois$\dfrac{1}{2}$ (fixed)$\sqrt[3]{3} \approx 1.442$Simplest
Pegasus$\dfrac{f_2}{f_2 + f_c}$$\approx 1.642$Adaptive weight from function values
King (improved Pegasus)Pegasus weight + removal of slow sub-steps$\approx 1.839$Among the fastest
Anderson-Björck$1 - \dfrac{f_c}{f_2}$ (use $\tfrac{1}{2}$ if $\le 0$)$\approx 1.7$More refined and robust

Here $f_2$ is the function value remembered at the stagnant endpoint and $f_c$ is the current $f(c)$. Because all of them keep the bracket, convergence is always guaranteed, unlike the pure secant method ($\varphi \approx 1.618$ but possibly divergent). It is a competition over how far one can combine "the speed of the secant method with the safety of bisection" by clever choice of weight.

6. Convergence

Basic convergence guarantee

Like bisection, Regula Falsi maintains $f(a)\cdot f(b) < 0$ at every iteration, so convergence is always guaranteed. However, there is no monotone guarantee on the rate of shrinking of the interval width as there is for bisection.

Order of convergence

When $f$ is $C^2$ near a simple root $x^*$, the asymptotic order of convergence of Regula Falsi is as follows.

  • No stagnation (both endpoints update alternately): superlinear convergence, order $\approx 1.618$ (the golden ratio $\varphi$). This is the same order as the secant method.
  • With stagnation: drops to linear convergence. In the worst case it can be slower than bisection.
  • Illinois method: order $\approx 1.442$ ($\sqrt[3]{3}$). Because stagnation is avoided, it shows stable superlinear convergence.

Error recurrence

When no stagnation occurs, the error $e_n = |c_n - x^*|$ approximately satisfies

$$e_{n+1} \approx C \cdot e_n \cdot e_{n-1}$$

(where $C$ is a constant depending on $f''(x^*) / (2f'(x^*))$). This recurrence yields the order of convergence $\varphi = (1+\sqrt{5})/2 \approx 1.618$.

7. Worked Examples

Example 1: find the middle root $x^* = 2$ of $f(x) = (x-1)(x-2)(x-3)$ on $[1.3, 2.5]$

Since $f(1.3) = +0.357$ and $f(2.5) = -0.375$ have opposite signs, Regula Falsi applies (the only root in the interval is $x^* = 2$). The interval contains an inflection point of the curve, so both endpoints update alternately and no stagnation occurs.

$n$$a_n$$b_n$$c_n$$f(c_n)$
01.3000002.5000001.885246+0.113243
11.8852462.5000002.027832−0.027810
21.8852462.0278321.999719+0.000281
31.9997192.0278322.000000$-2.2\times 10^{-7}$

The true root is $x^* = 2$. The endpoints $a$ and $b$ update alternately, so no stagnation occurs, and just three iterations reach about 7-digit accuracy. Compare this with bisection over the same interval: four steps shrink the width only to $1.2 / 2^4 = 0.075$ (about one digit), which makes the effect of linear interpolation clear.

Example 2: a case where stagnation occurs — $f(x) = x^{10} - 1$ on $[0, 1.3]$

Here $f(0) = -1$ and $f(1.3) \approx 12.786$, and $f$ is strongly convex over the interval.

In basic Regula Falsi the endpoint $b = 1.3$ stays fixed while $a$ approaches the root $x^* = 1$ very slowly from $0$. Because $f$ is nearly flat over a long stretch, the updates of $a$ are extremely slow; even dozens of iterations fail to reach adequate accuracy, showing convergence slower than bisection.

By contrast, applying the Illinois method halves the function value at the fixed endpoint $b$, so both endpoints start moving alternately and adequate accuracy is obtained in about ten iterations.

8. FAQ

Q1. What is the difference between Regula Falsi and bisection?

Bisection takes the midpoint of the interval as the next approximation, whereas Regula Falsi takes the intersection of the $x$-axis with the line joining the function values at the two endpoints. Because it uses information about the slope of the function it is usually faster than bisection, but one endpoint can become fixed, causing stagnation.

Q2. What is stagnation?

When the function is convex (or concave), Regula Falsi may keep one endpoint fixed without updating it for many iterations. Improvements such as the Illinois method avoid stagnation by halving the function value at the fixed endpoint.

Q3. What is the order of convergence?

For a simple root, the ideal case with no stagnation is superlinear convergence (order $\approx 1.618$, the golden ratio). When stagnation occurs it drops to linear or worse. The Illinois method stabilises the order at $\approx 1.442$.

9. References

  • Wikipedia, "Regula falsi"
  • Wikipedia, "Illinois algorithm"
  • R. L. Burden & J. D. Faires, Numerical Analysis, 10th ed., Cengage, 2016.
  • W. H. Press et al., Numerical Recipes, 3rd ed., Cambridge, 2007.
  • M. Dowell & P. Jarratt, "The Pegasus method for computing the root of an equation," BIT 12 (1972), 503–508. (the Pegasus method and its order of convergence)
  • R. F. King, "An improved Pegasus method for root finding," BIT 13 (1973), 423–427. (King's method, an improved Pegasus, order $\approx 1.839$)
  • R. G. Bartle & D. R. Sherbert, Introduction to Real Analysis, 4th ed., Wiley, 2011.

Implementation in sangi

Each method in this article is available in sangi's root-finding module (Roots). Note that some names differ slightly from the article:

Method in the articlesangi functionNotes
Regula Falsi (basic form, can stagnate)regula_falsiBasic form without stagnation avoidance
Illinois methodillinois_methodAvoids stagnation with weight 1/2 (practical choice)
Pegasus methodking_methodKing-Pegasus (King 1973 is an improvement of Pegasus)
Anderson-Björck methodanderson_bjork_methodImproved Illinois type