Solving nonlinear equations · Lecture 10

Secant Method and Nonlinear Systems

Newton without derivatives, a final comparison of all five root-finding methods, and Newton's method for several equations at once: the idea behind GPS.

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: a function with no formula

The game designer from Lecture 6 asks: at what launch speed $v$ does the ball land after exactly 3 seconds?

Define $T(v)$ = landing time for launch speed $v$ . We need $T(v) - 3 = 0$
But $T(v)$ has no formula: every evaluation is a whole bisection run (Lecture 6)
So there is no derivative $T'(v)$ for Newton, and each evaluation is expensive
We need a fast method that uses only values of the function

$v$ (m/s)	$T(v)$ (s)
10	2.7752
15	3.3912
20	4.0025

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

2 / 22

Today's goals

Derive the secant method from Newton's method and from the chord
Carry out the secant method by hand and compare it with false position
Compare all five methods: order, cost, safety; choose one for a given problem
Apply Newton's method to systems using the Jacobian matrix
Choose the right root-finding method for a problem: best and worst cases of all five

Last time

Newton: $x_{n+1} = x_n - f(x_n)/f'(x_n)$ , quadratic, but needs $f'$ and a good start.

Today

Replace $f'$ by a slope through two points (secant), then generalise Newton to vectors.

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: L7, L9

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

3 / 22

Start here

The idea in one picture

Like Newton, but we do not know the slope (derivative).Take two starting points on the curve.Draw the straight line through them.Where it crosses the axis is the next point x₂.Forget the oldest point; keep the two newest.Line through the two newest points …… gives x₃.Drop the oldest again.The line through x₂ and x₃ is almost the tangent.x₄ = 1.531 (root 1.521): nearly as fast as Newton, with no derivative.

In plain words

Newton needs the derivative, which we often do not have
Replace the tangent by the line through the two latest points
Almost as fast, and only function values are needed

New words today

secant: a line through two points of a curve
open method: no bracket: fast, but not guaranteed
superlinear: faster than linear, slower than quadratic
Jacobian: the table of slopes used for systems of equations

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

4 / 22

The secant method

Replace the derivative by a slope through the last two points

f'(x_n) \approx \frac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}}

Secant iteration

x_{n+1} = x_n - f(x_n)\,\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}

Same formula as false position, but no bracket: always use the two most recent points
Needs two starting values $x_0$ , $x_1$ (they need not bracket the root)
One new function evaluation per step (Newton needs $f$ and $f'$ )
Order $\phi = \frac{1 + \sqrt5}{2} \approx 1.618$ : superlinear

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

5 / 22

The method, step by step

The secant algorithm

Choose two starting values $x_0$ , $x_1$ near the root (they need not bracket it)
Compute $x_{n+1} = x_n - f(x_n)\,\dfrac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}$
If $f(x_n) = f(x_{n-1})$ (flat secant), stop
Drop the oldest point: the pair $(x_{n-1}, x_n)$ becomes $(x_n, x_{n+1})$
Repeat until $|x_{n+1} - x_n| < \varepsilon$ ; the answer is the last $x$

Pseudocode

input f, x0, x1, tol, N
f0 ← f(x0);  f1 ← f(x1)
repeat up to N times:
    if f1 = f0: stop (flat secant)
    x2 ← x1 − f1·(x1 − x0) / (f1 − f0)
    if |x2 − x1| < tol:
        return x2
    x0, f0 ← x1, f1
    x1, f1 ← x2, f(x2)
stop: no convergence

Step 4 is the only difference from false position: no sign test, just keep the newest two points.

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

6 / 22

Explore: secant lines

The dashed line passes through the last two points
Its crossing is the next point; the oldest point is dropped
The first two steps equal false position; from step 3 the secant pulls ahead
Try $x_0 = 0$ , $x_1 = 0.5$ : both on the same side of the root

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

7 / 22

Problem 1: $x^3 - x - 2 = 0$ , $x_0 = 1$ , $x_1 = 2$

$n$	$x_{n-1}$	$x_n$	$f(x_{n-1})$	$f(x_n)$	$x_{n+1}$	$f(x_{n+1})$
1	1	2	−2	4	1.333333	−0.962963
2	2	1.333333	4	−0.962963	1.462687	−0.333339
3	1.333333	1.462687	−0.962963	−0.333339	1.531169	+0.058626
4	1.462687	1.531169	−0.333339	+0.058626	1.520926	−0.002693
5	1.531169	1.520926	+0.058626	−0.002693	1.521376	−0.000020
6	1.520926	1.521376	−0.002693	−0.000020	1.521380	0.000000

Row 3 uses two points with $f < 0$ : false position would never do that. Root 1.521380 after 6 steps (false position: 12 steps for the same accuracy).

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

8 / 22

How fast is "superlinear"?

Secant on $e^{x} - 3x$ from $0, 1$ : errors $1.6\times10^{-1}$ , $1.2\times10^{-1}$ , $1.7\times10^{-2}$ , $1.5\times10^{-3}$ , $2.1\times10^{-5}$ , $2.6\times10^{-8}$ , $4.4\times10^{-13}$
Each error ≈ (previous)^1.6: between linear (×constant) and quadratic (squared)
Efficiency per function evaluation: Newton gains order 2 per 2 evaluations ( $\sqrt2 = 1.41$ per evaluation); secant gains 1.618 per evaluation
So when $f'$ costs as much as $f$ , secant is often faster than Newton in practice

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

9 / 22

Systems: Newton's method in two variables

Solve $f_1(x, y) = 0$ , $f_2(x, y) = 0$ simultaneously. Linearise both with Taylor series:

Jacobian matrix

J = \begin{pmatrix} \partial f_1/\partial x & \partial f_1/\partial y \\ \partial f_2/\partial x & \partial f_2/\partial y \end{pmatrix}

Newton step

J(\mathbf{x}_n)\,\Delta = -\mathbf{F}(\mathbf{x}_n), \qquad \mathbf{x}_{n+1} = \mathbf{x}_n + \Delta

One-variable Newton: divide by $f'$ . Many variables: solve a linear system with $J$
For 2×2, solve $J\Delta = -F$ with the school formula (Cramer's rule); larger systems: Lectures 11–14
Still quadratic near a solution where $\det J \ne 0$
For $n$ unknowns, each step costs an $n\times n$ solve (Lectures 11–14)

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

10 / 22

The method, step by step

Newton for systems, step by step

Write $\mathbf{F} = (f_1, f_2)$ and the Jacobian $J$ (four partial derivatives)
Choose a starting guess $(x_0, y_0)$
Evaluate $\mathbf{F}$ and $J$ at the current point
Solve the linear system $J\,\Delta = -\mathbf{F}$ (2×2: Cramer's rule)
Update $\mathbf{x}_{n+1} = \mathbf{x}_n + \Delta$
Repeat until $\|\Delta\| < \varepsilon$ ; the answer is the last $\mathbf{x}$

Pseudocode

input F, J, x0, tol, N
x ← x0
repeat up to N times:
    solve J(x)·Δ = −F(x)
    x ← x + Δ
    if ‖Δ‖ < tol:
        return x
stop: no convergence

Same loop as one-variable Newton; "divide by $f'$ " became "solve with $J$ " (step 4).

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

11 / 22

Problem 2: one Newton step for $x^2 + y^2 = 4$ , $xy = 1$

Start from

(x_0, y_0) = (2, 0.5)

. Do one Newton step.

1

F = \begin{pmatrix} x^2 + y^2 - 4 \\ xy - 1 \end{pmatrix} = \begin{pmatrix} 0.25 \\ 0 \end{pmatrix}

,

\quad J = \begin{pmatrix} 2x & 2y \\ y & x \end{pmatrix} = \begin{pmatrix} 4 & 1 \\ 0.5 & 2 \end{pmatrix}

2

Solve

\begin{pmatrix} 4 & 1 \\ 0.5 & 2 \end{pmatrix}\begin{pmatrix} \Delta x \\ \Delta y\end{pmatrix} = \begin{pmatrix} -0.25 \\ 0 \end{pmatrix}

;

\det J = 8 - 0.5 = 7.5

3

Cramer:

\Delta x = \dfrac{(-0.25)(2) - (1)(0)}{7.5} = -0.066667

,

\;\Delta y = \dfrac{(4)(0) - (0.5)(-0.25)}{7.5} = 0.016667

4

(x_1, y_1) = (1.933333, 0.516667)

; two more steps give

\left(\sqrt{2+\sqrt3}, \sqrt{2-\sqrt3}\right)

Solution

(1.931852, 0.517638)

in three steps: quadratic convergence again.

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

12 / 22

Classical vs numerical

Same system, two approaches: $x^2 + y^2 = 4$ , $xy = 1$

Algebra

Classical (exact formula)

Substitute $y = 1/x$ : $x^2 + 1/x^2 = 4 \Rightarrow x^4 - 4x^2 + 1 = 0$
Quadratic in $x^2$ : $x^2 = 2 \pm \sqrt3$
$(x, y) = \left(\sqrt{2+\sqrt3}, \sqrt{2-\sqrt3}\right) = (1.931852, 0.517638)$

vs

Algorithm

Numerical (Newton for systems)

Jacobian $\begin{pmatrix} 2x & 2y \\ y & x\end{pmatrix}$ , start $(2, 0.5)$
3 iterations: $(1.931852, 0.517638)$
No substitution trick needed: the same code works for any 2×2 system

When the classical approach cannot work

Landing time $T(v) = 3$ : a function with no formula

Each value of $T(v)$ comes from running bisection; there is nothing to substitute or rearrange. Secant: $v = 11.8267$ m/s in 4 steps. Most real systems (circuits, GPS, robots) are like this: many equations, no substitution trick.

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

13 / 22

Newton for systems in Python and C

Each step: evaluate $F$ and $J$ , solve the 2×2 system by Cramer's rule
Stop when the step $\|\Delta\|$ is tiny
Try the start $(0.5, 2)$ : a different solution
Change to $x^2 + y = 11$ , $x + y^2 = 7$ from $(3.5, 1.5)$ : converges to $(3, 2)$

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

14 / 22

Practice

Practice problem

Problem 3"Explain how the Secant method removes the requirement of an analytical derivative and identify one drawback it introduces in exchange." Also: compare the iteration methods for solving

f(x) = 0

.

How to write a complete answer

Secant replaces $f'(x_n)$ by the finite-difference slope $\dfrac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}}$ through the last two iterates
Drawbacks (any one): needs two starting values; order drops from 2 to 1.618; no bracket, so it can diverge; $f(x_n) \approx f(x_{n-1})$ causes division by a tiny number
Comparison: use the five-row table (needs, order, cost, guarantee)
Mention the efficiency index: per function evaluation, secant (1.618) beats Newton (1.414)

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

15 / 22

When the secant method fails

Divergence: $\tan^{-1}x$ from 2, 3 jumps to −5.80, −1.15, 6.15, … 38.6
Flat secant: $\cos(-1) = \cos(1)$ , the line is horizontal: division by zero
Wandering: $x^3 - 2x + 2$ from 0, 0.5 jumps around for many steps before settling
No bracket means no guarantee: same weakness as Newton

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

16 / 22

When to use it

Secant method: method profile

Best case

Smooth $f$ , two good starting values: superlinear, order 1.618; $x^3 - x - 2$ in 7 steps
Expensive $f$ with no derivative: one evaluation per step, the most efficient per evaluation
The ball problem: 4 steps, each a full simulation

Worst case

$f(x_n) \approx f(x_{n-1})$ : a nearly flat secant throws the next point far away
Poor starting values: divergence ( $\tan^{-1}x$ from 2, 3)
Cancellation in $f(x_n) - f(x_{n-1})$ near convergence limits the final accuracy slightly

Best suited for

Black-box functions: simulations, measurements, outputs of other solvers
Inside hybrid solvers (Brent's method, scipy.optimize.brentq)
When $f'$ costs as much as $f$

Avoid when

A guaranteed result is needed (bracket it, or use Brent)
The function is noisy (secant slopes amplify noise; use bisection)
A cheap derivative is available and starts are good (Newton is slightly faster per iteration)

Rule of thumb: no derivative → secant; no guarantee needed → plain; guarantee needed → Brent (bracket + secant + bisection).

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

17 / 22

All five methods side by side

Method	Needs	Order	Per step	Guaranteed?	Iterations for $x^3 - x - 2$ , $10^{-6}$
Bisection	bracket	1 (rate ½)	1 eval	yes	20 from [1, 2]
False position	bracket	1 (often fast)	1 eval	yes (can be slow)	12 from [1, 2]
Fixed point	$x = g(x)$ , $x_0$	1 (rate $\|g'(r)\|$ )	1 eval	only if $\|g'\| < 1$	7 with $g = (x+2)^{1/3}$
Newton–Raphson	$f'$ , $x_0$	2	2 evals	no (needs good $x_0$ )	3 from 1.5
Secant	$x_0$ , $x_1$	1.618	1 eval	no	7 from 1, 2

Practical choice: bracketing when safety matters or $f$ is noisy; Newton when $f'$ is cheap and $x_0$ is good; secant when $f'$ is unavailable. Libraries (e.g. Brent's method, scipy.optimize.brentq) combine bisection's safety with secant-like speed.

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

18 / 22

Roadmap

End of Module 2: what is still missing

We can now solve any single equation, and small systems. Large systems need new tools:

What it does well (keep this)

Five root-finding methods with known best and worst cases
Hybrid strategy: bracket, then a fast method
Newton for systems: linearise, solve, repeat
Convergence orders 1, 1.618 and 2

LimitationHow it is overcomeWhere

Each Newton step for

n

equations needs an

n\times n

linear solve

→

Gaussian elimination, LU and Cholesky

Lecture 12 →

Cramer's rule is far too slow beyond 3×3

→

Cost analysis of Cramer and the inverse

Lecture 11 →

Huge sparse systems (millions of unknowns)

→

Iterative methods: Jacobi, Gauss–Seidel (fixed point with matrices)

Lecture 14 →

Finding the best parameters for data, not a root

→

Least squares, then optimisation for ML

Lecture 23 →

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

19 / 22

Applications

Where this method runs in the real world

Click a card to see Newton's method for systems, or the secant idea, inside a real system.

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

20 / 22

Checkpoint

Checkpoint · think, then discuss with your neighbourSecant method with

x_0 = 1

,

x_1 = 2

for

f(x) = x^2 - 3

. What is

x_2

?

A1.5

B1.6667

C1.7321

D1.75

B.

f(1) = -2

,

f(2) = 1

:

x_2 = 2 - 1\cdot\dfrac{2 - 1}{1 - (-2)} = 2 - \tfrac13 = 1.6667

. Then

x_3 = 1.7273

,

x_4 = 1.7321 = \sqrt3

.

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

21 / 22

Summary

Key points

Secant: $x_{n+1} = x_n - f(x_n)\dfrac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}$ ; no derivative, order 1.618
Like false position but uses the latest two points: faster, not guaranteed
Choose: bracketing for safety; Newton when $f'$ is cheap; secant otherwise; hybrids in libraries
Systems: solve $J\Delta = -F$ each step; quadratic near a solution with $\det J \ne 0$

Opening problem: solved

Secant on $T(v) - 3$ from $v = 10, 20$ : 11.8317, 11.8267, 11.826709 m/s. Four steps, each a full bisection run inside; no derivative was needed.

Homework

Solve $x^3 - 5x + 1 = 0$ by the secant method with $x_0 = 0$ , $x_1 = 1$ , to 5 decimal places.
Do two Newton steps for $x^2 + y = 11$ , $x + y^2 = 7$ from $(3.5, 1.5)$ by hand.
Modify the secant program to stop when $|f(x_n)| < 10^{-10}$ and count evaluations. Compare with Newton.
Write a one-page comparison of the five root-finding methods (use the table and your own examples).

Next lecture

Module 3: systems of linear equations. $A\mathbf{x} = \mathbf{b}$ with Cramer's rule and the inverse, and why both are too slow for real problems.

Md Mahbub E Noor

Lecture 10: Secant Method and Nonlinear Systems

University of Barishal

22 / 22

Secant Method and Nonlinear Systems

The problem: a function with no formula

Today's goals

The idea in one picture

The secant method

The secant algorithm

Explore: secant lines

Problem 1: $x^3 - x - 2 = 0$ , $x_0 = 1$ , $x_1 = 2$

How fast is "superlinear"?

Systems: Newton's method in two variables

Newton for systems, step by step

Problem 2: one Newton step for $x^2 + y^2 = 4$ , $xy = 1$

Same system, two approaches: $x^2 + y^2 = 4$ , $xy = 1$

Classical (exact formula)

Numerical (Newton for systems)

Landing time $T(v) = 3$ : a function with no formula

Newton for systems in Python and C

Practice problem

When the secant method fails

Secant method: method profile

All five methods side by side

End of Module 2: what is still missing

Where this method runs in the real world

📍 Positioning from distances (GPS idea)

🤖 Robot arm: inverse kinematics

🐍 SciPy brentq

⚡ Circuit simulation (SPICE)

Checkpoint

Summary

Secant Method and Nonlinear Systems

The problem: a function with no formula

Today's goals

The idea in one picture

The secant method

The secant algorithm

Explore: secant lines

Problem 1: x3−x−2=0x^3 - x - 2 = 0x3−x−2=0, x0=1x_0 = 1x0​=1, x1=2x_1 = 2x1​=2

How fast is "superlinear"?

Systems: Newton's method in two variables

Newton for systems, step by step

Problem 2: one Newton step for x2+y2=4x^2 + y^2 = 4x2+y2=4, xy=1xy = 1xy=1

Same system, two approaches: x2+y2=4x^2 + y^2 = 4x2+y2=4, xy=1xy = 1xy=1

Classical (exact formula)

Numerical (Newton for systems)

Landing time T(v)=3T(v) = 3T(v)=3: a function with no formula

Newton for systems in Python and C

Practice problem

When the secant method fails

Secant method: method profile

All five methods side by side

End of Module 2: what is still missing

Where this method runs in the real world

📍 Positioning from distances (GPS idea)

🤖 Robot arm: inverse kinematics

🐍 SciPy brentq

⚡ Circuit simulation (SPICE)

Checkpoint

Summary

Problem 1: $x^3 - x - 2 = 0$ , $x_0 = 1$ , $x_1 = 2$

Problem 2: one Newton step for $x^2 + y^2 = 4$ , $xy = 1$

Same system, two approaches: $x^2 + y^2 = 4$ , $xy = 1$

Landing time $T(v) = 3$ : a function with no formula