Solving nonlinear equations · Lecture 7

The False Position Method

Bisection ignores how big f(a) and f(b) are. False position draws the straight line between them and takes its crossing: usually much faster, still safely bracketed.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: bisection throws information away

Bisection needed 20 steps for $x^3 - x - 2 = 0$ on $[1, 2]$ . Look at what it ignored.

$f(1) = -2$ and $f(2) = 4$ : the function is twice as far from zero at $x = 2$ as at $x = 1$
Common sense: the root should be about one third of the way from 1 to 2, not in the middle
Bisection used only the signs $-$ and $+$ ; the sizes 2 and 4 were thrown away
Today: use the sizes too, and see whether that is always a good idea

$x$	$f(x)$
1	−2
2	+4
bisection guess	1.5
"proportional" guess	$1 + \tfrac{2}{2+4} = 1.333$
true root	1.5214

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

2 / 21

Today's goals

Derive the false position formula from the chord through $(a, f(a))$ and $(b, f(b))$
Carry out false position by hand and present the iteration table
Give an honest error bound after $n$ iterations
Compare false position with bisection, including its one-sided weakness and the Illinois fix
Know its best and worst cases, and which later methods remove its limitations

Last time

Bisection: halve the bracket each time. Safe, error bound $(b-a)/2^n$ , but only one bit per step.

Today

Keep the bracket (safety) but choose a smarter point inside it (speed).

Solving nonlinear equations · you are here

L6 · Root Finding and the Bisection Method→L7 · False Position Method→L8 · Fixed-Point Iteration→L9 · Newton–Raphson Method→L10 · Secant Method and Nonlinear Systems

Builds on: L6

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

3 / 21

Start here

The idea in one picture

Same start as bisection: a bracket with a sign change.But now look at the sizes: A is 2 below the axis, B is 4 above.Join A and B with a straight line (a chord).Where the chord crosses the axis is our estimate: nearer to A.f(c₁) is negative, so c₁ replaces A.Draw the new chord from the new point to B.Its crossing c₂ is closer again.The estimates creep towards the root from one side.

In plain words

Bisection ignores how big f is at the two ends
A straight line between the end points gives a smarter guess
Keep the part with the sign change, as before

New words today

chord: the straight line joining two points of a curve
false position: where that line crosses the axis
linear interpolation: pretending the curve is straight between two points
bracket: still kept, so the root cannot escape

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

4 / 21

The idea: follow the chord

Join $(a, f(a))$ and $(b, f(b))$ with a straight line; take the point $c$ where it crosses the $x$ -axis.

Line through the two points

y - f(b) = \frac{f(b) - f(a)}{b - a}\,(x - b)

Set y = 0 and solve for x

c = b - f(b)\,\frac{b - a}{f(b) - f(a)} \;=\; \frac{a\,f(b) - b\,f(a)}{f(b) - f(a)}

Same bracketing rule as bisection: keep the sub-interval where $f$ changes sign
If $|f(a)| \ll |f(b)|$ , then $c$ lands close to $a$ , as common sense suggests
The second form is easiest by calculator; the first is safer in code (less cancellation)
It is linear interpolation: we pretend $f$ is a straight line between $a$ and $b$

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

5 / 21

The method, step by step

The false position algorithm

Start with $[a, b]$ where $f(a)\,f(b) < 0$
Chord point $c = \dfrac{a\,f(b) - b\,f(a)}{f(b) - f(a)}$ ; compute $f(c)$
If $f(a)\,f(c) < 0$ , the root is in $[a, c]$ : set $b = c$
Otherwise the root is in $[c, b]$ : set $a = c$ (if $f(c) = 0$ , stop: $c$ is the root)
Repeat until two successive $c$ agree: $|c_n - c_{n-1}| < \varepsilon$ ; the answer is the last $c$

Pseudocode

input f, a, b, tol
fa ← f(a);  fb ← f(b)
if fa·fb > 0: stop (no bracket)
c_old ← a
repeat up to N times:
    c  ← (a·fb − b·fa) / (fb − fa)
    fc ← f(c)
    if fc = 0 or |c − c_old| < tol:
        return c
    if fa·fc < 0:  b ← c;  fb ← fc
    else:          a ← c;  fa ← fc
    c_old ← c

Only step 2 differs from bisection. The stopping test changes too, because one end of the bracket may never move, so $(b - a)$ need not shrink.

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

6 / 21

Explore: chord after chord

The orange chord joins the current endpoints
Its crossing is the new point $c$
Watch which endpoint moves: here only $a$ moves, $b = 2$ never changes
Compare the speed with bisection (previous lecture)

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

7 / 21

Problem 1: $x^3 - x - 2 = 0$ on $[1, 2]$ , three iterations

Problem 1"Using the False Position method, find the root of

f(x) = x^3 - x - 2 = 0

, taking the initial bracketing interval

[1, 2]

. Perform three iterations, tabulating

x_1, x_2, x_3

and

f(x)

at each step, and report the absolute error bound after the third iteration."

$n$	$a$	$b$	$f(a)$	$f(b)$	$x_n = \dfrac{af(b) - bf(a)}{f(b) - f(a)}$	$f(x_n)$
1	1	2	−2	4	$\frac{1(4) - 2(-2)}{4 + 2} = 1.333333$	−0.962963
2	1.333333	2	−0.962963	4	1.462687	−0.333339
3	1.462687	2	−0.333339	4	1.504019	−0.101818

Every $f(x_n) < 0$ , so $a$ moves and $b = 2$ stays. Next slide: the error bound.

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

8 / 21

The error bound after three iterations

Problem 2After

x_3 = 1.504019

with

f(x_3) = -0.101818

, how far can we be from the true root?

1

Bracket bound (always valid): the root is in

[x_3, 2]

, so

|r - x_3| \le 2 - 1.504019 = 0.496

. True, but useless: the bracket does not shrink to zero

2

Change between iterates (an estimate, not a guarantee):

|x_3 - x_2| = 0.041

3

Mean value bound (rigorous and sharp):

f(x_3) = f(x_3) - f(r) = f'(\xi)(x_3 - r)

, so

|r - x_3| \le \dfrac{|f(x_3)|}{\min |f'|}

on

[x_3, 2]

4

f'(x) = 3x^2 - 1

is increasing, so

\min f' = f'(1.504019) = 5.786

:

\;|r - x_3| \le \dfrac{0.101818}{5.786} = 0.0176

Absolute error bound ≈ 0.018 (true root 1.5213797, actual error 0.01736 ✓). The bracket width alone (0.496) would be a very poor bound.

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

9 / 21

Problem 3: $e^{x} - 3x = 0$ on $[0, 1]$

Problem 3"Find out the root of the following equation using the false position method:

e^{x} - 3x = 0

in

[0, 1]

."

$n$	$b$	$f(a)$	$f(b)$	$x_n$	$f(x_n)$
1	1	1	−0.281718	0.780203	−0.158694
2	0.780203	1	−0.158694	0.673347	−0.059252
3	0.673347	1	−0.059252	0.635682	−0.018736
4	0.635682	1	−0.018736	0.623991	−0.005611
5	0.623991	1	−0.005611	0.620509	−0.001653
6	0.620509	1	−0.001653	0.619485	−0.000484

Here $b$ moves and $a = 0$ is stuck. Root ≈ 0.6195 after 6 steps (true 0.6190613). Converging, but only about one digit every two steps.

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

10 / 21

Problem 4: $x^3 + x^2 - 3x - 3 = 0$ between 1 and 2

Problem 4"Establish the method of false position for finding roots of algebraic equations. Find by the method of Regula Falsi a root of

x^3 + x^2 - 3x - 3 = 0

lying between 1 and 2."

$n$	$a$	$b$	$f(a)$	$f(b)$	$x_n$	$f(x_n)$
1	1	2	−4	3	1.571429	−1.364431
2	1.571429	2	−1.364431	3	1.705411	−0.247745
3	1.705411	2	−0.247745	3	1.727883	−0.039340
4	1.727883	2	−0.039340	3	1.731405	−0.006111
5	1.731405	2	−0.006111	3	1.731951	−0.000946

Bonus check: $x^3 + x^2 - 3x - 3 = (x + 1)(x^2 - 3)$ , so the exact root is $\sqrt{3} = 1.7320508$ . After 5 steps: 1.7320 (4 correct decimals).

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

11 / 21

Classical vs numerical

Same problem, two approaches: $x^3 + x^2 - 3x - 3 = 0$

Algebra

Classical (exact formula)

Spot the factor: $x^2(x+1) - 3(x+1) = (x+1)(x^2 - 3)$
Roots $-1$ and $\pm\sqrt3$ ; in $[1, 2]$ : $x = \sqrt3$
Works only because a factorisation happens to exist

vs

Algorithm

Numerical (false position)

Bracket $[1, 2]$ : $f(1) = -4$ , $f(2) = 3$
9 iterations for $10^{-6}$ : $x \approx 1.732051$
Matches $\sqrt3 = 1.7320508$ , and needed no clever factoring

When the classical approach cannot work

$e^{x} = 3x$ (Problem 3)

Mixing $e^x$ with a polynomial in $x$ leaves no algebraic route; the root has no expression in elementary functions. False position: $x = 0.619061$ in 12 iterations.

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

12 / 21

False position in Python and C

Same structure as bisection; only the formula for $c$ changes
Stops when two successive $c$ agree within tol, or when $f(c) = 0$
The C version stores $f(a)$ and $f(b)$ so each step costs one evaluation
Try $x^{10} - 1$ on $[0, 1.3]$ and count the iterations

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

13 / 21

Practice

Practice problem

Problem 5"Discuss the method of False Position to find an approximate root of an equation

f(x) = 0

."

How to write a complete answer

Start from a bracket $[a, b]$ with $f(a)f(b) < 0$ (IVT guarantees a root)
Replace the curve by the chord; derive $c = \dfrac{af(b) - bf(a)}{f(b) - f(a)}$ with a small sketch
Keep the sub-interval with the sign change; repeat until $|c_n - c_{n-1}| < \varepsilon$
Advantages: always converges, usually faster than bisection. Limitation: one endpoint can stay fixed, convergence becomes slow (linear) for strongly curved $f$

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

14 / 21

The weakness: one endpoint gets stuck

$f(x) = x^{10} - 1$ on $[0, 1.3]$ : root at 1
$f(1.3) = 12.8$ is huge, $f(0) = -1$ ; the chords all cross far left
False position needs 57 iterations for $10^{-6}$ ; bisection needs 21
Fix (Illinois method): when the same end is kept twice, halve its stored $f$ value; this restores fast convergence (14 steps here instead of 57)

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

15 / 21

When to use it

False position: method profile

Best case

$f$ nearly straight on the bracket: on a straight line it is exact in 1 step (bisection needs 20)
Smooth, gently curved $f$ : $x^3 - x - 2$ and $e^x - 3x$ need 12 steps for $10^{-6}$ , bisection 20
Keeps the bracket: it can never lose the root

Worst case

Strong curvature with the root near one end: $x^{10} - 1$ on $[0, 1.3]$ needs 57 steps (bisection 21)
One endpoint stays fixed, so the bracket never shrinks and gives no useful error bound
Same as bisection: needs a sign change, fooled by poles

Best suited for

Smooth monotone functions where a bracket is available
Inverting tables and calibration curves (one step = linear interpolation)
The Illinois variant: a cheap, safe default for 1-D problems

Avoid when

$f$ is strongly convex or concave on the bracket
You need an error bound at every step (use bisection)
$f'$ is available and you want quadratic speed (use Newton)

Rule of thumb: prefer Illinois to plain false position; it keeps the speed on easy problems and fixes the stall on hard ones.

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

16 / 21

Comparison

Comparative analysis: bisection, false position, Illinois

$f(x)$ , bracket	Bisection	False position	Illinois	Winner
$x^3 - x - 2$ , $[1, 2]$	20	12	8	Illinois
$e^x - 3x$ , $[0, 1]$	20	12	8	Illinois
$x^2 - 4x - 10$ , $[5, 6]$	20	5	5	false position / Illinois
$x^{10} - 1$ , $[0, 1.3]$	21	57	14	Illinois (plain FP loses)

Iterations to reach $10^{-6}$ . Bisection never wins on speed but never loses badly; plain false position can be the best or the worst; Illinois is never bad on these problems.

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

17 / 21

Roadmap

Limitations, and where we fix them

False position keeps bisection's safety and adds speed on easy problems. What is still missing:

What it does well (keep this)

Bracketing: always converges
Uses function values, so fast on nearly linear $f$
No derivative needed
Exact in one step for linear $f$

LimitationHow it is overcomeWhere

One endpoint gets stuck (slow on curved

f

)

→

Illinois: halve the stuck

f

value

this lecture

Still linear convergence

→

Use the tangent: quadratic convergence

Lecture 9 →

Needs a bracket with a sign change

→

Open methods start from a guess: fixed point

Lecture 8 →

Keeping old points slows it down

→

Always use the two newest points: the secant method

Lecture 10 →

One equation only

→

Newton for systems

Lecture 10 →

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

18 / 21

Applications

Where this method runs in the real world

Click a card to see where "follow the chord" is used.

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

19 / 21

Checkpoint

Checkpoint · think, then discuss with your neighbourFalse position on

[1, 2]

with

f(1) = -3

and

f(2) = 1

. What is the first estimate

x_1

?

A1.25

B1.5

C1.75

D1.333

C.

x_1 = \dfrac{1(1) - 2(-3)}{1 - (-3)} = \dfrac{7}{4} = 1.75

. The root is closer to

b

because

|f(b)| < |f(a)|

.

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

20 / 21

Summary

Key points

False position: $c = \dfrac{af(b) - bf(a)}{f(b) - f(a)}$ , the root of the chord; keep the sign-change half
Always converges (bracketing), usually faster than bisection
One endpoint often stays fixed: the bracket does not shrink to zero; error bound via $|f(c)|/\min|f'|$
Very slow for strongly curved $f$ (e.g. $x^{10} - 1$ ); the Illinois fix halves the stuck $f$ value

Opening problem: solved

The proportional guess 1.333 was the first false-position point. Continuing gives the root 1.521380 in 12 steps (bisection: 20; Illinois: 8).

Homework

Find the root of $x \log_{10} x - 1.2 = 0$ in $[2, 3]$ by false position, 4 iterations.
Repeat Problem 1 by bisection for 3 iterations. Which method is closer to the true root 1.52138 after 3 steps?
Implement the Illinois modification in the Python code and count iterations for $x^{10} - 1$ on $[0, 1.3]$ .
Lab: solve $x^3 - 5x + 1 = 0$ in $[0, 1]$ with both methods in the solver tab.

Next lecture

Fixed-point iteration. Rewrite $f(x) = 0$ as $x = g(x)$ and simply repeat. When does that work? (Often called the "iteration method".)

Md Mahbub E Noor

Lecture 7: False Position (Regula Falsi)

University of Barishal

21 / 21

The False Position Method

The problem: bisection throws information away

Today's goals

The idea in one picture

The idea: follow the chord

The false position algorithm

Explore: chord after chord

Problem 1: $x^3 - x - 2 = 0$ on $[1, 2]$ , three iterations

The error bound after three iterations

Problem 3: $e^{x} - 3x = 0$ on $[0, 1]$

Problem 4: $x^3 + x^2 - 3x - 3 = 0$ between 1 and 2

Same problem, two approaches: $x^3 + x^2 - 3x - 3 = 0$

Classical (exact formula)

Numerical (false position)

$e^{x} = 3x$ (Problem 3)

False position in Python and C

Practice problem

The weakness: one endpoint gets stuck

False position: method profile

Comparative analysis: bisection, false position, Illinois

Limitations, and where we fix them

Where this method runs in the real world

🧮 Ancient algebra: double false position

🖼️ Graphics: parallax occlusion mapping

🐍 SciPy brentq

Checkpoint

Summary

The False Position Method

The problem: bisection throws information away

Today's goals

The idea in one picture

The idea: follow the chord

The false position algorithm

Explore: chord after chord

Problem 1: x3−x−2=0x^3 - x - 2 = 0x3−x−2=0 on [1,2][1, 2][1,2], three iterations

The error bound after three iterations

Problem 3: ex−3x=0e^{x} - 3x = 0ex−3x=0 on [0,1][0, 1][0,1]

Problem 4: x3+x2−3x−3=0x^3 + x^2 - 3x - 3 = 0x3+x2−3x−3=0 between 1 and 2

Same problem, two approaches: x3+x2−3x−3=0x^3 + x^2 - 3x - 3 = 0x3+x2−3x−3=0

Classical (exact formula)

Numerical (false position)

ex=3xe^{x} = 3xex=3x (Problem 3)

False position in Python and C

Practice problem

The weakness: one endpoint gets stuck

False position: method profile

Comparative analysis: bisection, false position, Illinois

Limitations, and where we fix them

Where this method runs in the real world

🧮 Ancient algebra: double false position

🖼️ Graphics: parallax occlusion mapping

🐍 SciPy brentq

Checkpoint

Summary

Problem 1: $x^3 - x - 2 = 0$ on $[1, 2]$ , three iterations

Problem 3: $e^{x} - 3x = 0$ on $[0, 1]$

Problem 4: $x^3 + x^2 - 3x - 3 = 0$ between 1 and 2

Same problem, two approaches: $x^3 + x^2 - 3x - 3 = 0$

$e^{x} = 3x$ (Problem 3)