Solving nonlinear equations · Lecture 8

Fixed-Point Iteration

Rewrite f(x) = 0 as x = g(x), then just repeat x ← g(x). It works beautifully, or explodes, depending on one number: the slope of g at the root.

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: why does the cos button settle?

Set your calculator to radians, type 1, and press cos again and again.

1 → 0.5403 → 0.8576 → 0.6543 → 0.7935 → 0.7014 → … → 0.739085, then it stops changing
That number solves $x = \cos x$ , an equation with no formula
Now try the tan button from 1: 1.557, 74.69, −0.84, … it never settles
Why does one repeated function find an answer and the other does not? Today's theorem answers it

press	$x$
0	1.000000
1	0.540302
2	0.857553
3	0.654290
…	…
36	0.739085

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

2 / 21

Today's goals

Rewrite $f(x) = 0$ in the form $x = g(x)$ , in several ways
Carry out the method of iteration by hand
State and use the convergence condition $|g'(x)| < 1$ near the root
Read cobweb diagrams: staircase vs spiral, convergence vs divergence
Explain linear convergence and estimate the number of iterations
Know its best and worst cases, and which methods remove its limitations

Last time

Bracketing methods (bisection, false position) trap the root and never lose it.

Today

The first open method: one starting point, no bracket, very simple; it may converge or diverge.

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: L3, L6

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

3 / 21

Start here

The idea in one picture

We want the x where the curve y = cos x meets the line y = x.Pick a starting value x₀.Go up to the curve: that height is cos x₀.Go across to the line y = x: this turns the height into the next x.Up (or down) to the curve again …… and across to the line again.The path winds inwards like a spiral.Every loop lands closer.Up to the curve …… across to the line.It settles at 0.739: the fixed point, where x = cos x.

In plain words

Rewrite the equation as x = g(x)
Put a guess into g; the result is the next guess
If g is "flat enough" near the answer, the guesses settle down

New words today

fixed point: a value that g leaves unchanged: r = g(r)
iterate: one of the successive guesses x₀, x₁, x₂, …
cobweb diagram: the up-and-across picture on the left
converges if: |g′(x)| < 1 near the root
contraction: a g that pulls any two points closer together

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

4 / 21

The idea: a fixed point of $g$

Rewrite

f(x) = 0 \;\Longleftrightarrow\; x = g(x)

Iterate

x_{n+1} = g(x_n), \qquad n = 0, 1, 2, \dots

A fixed point $r$ satisfies $r = g(r)$ : $g$ leaves it unchanged
Geometrically: where $y = g(x)$ meets the line $y = x$
If the iterates converge to some $r$ and $g$ is continuous, then $r = g(r)$ , so $f(r) = 0$
Example: $x = \cos x$ is already in this form; $g(x) = \cos x$

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

5 / 21

One equation, many rearrangements: $x^2 - 4x - 10 = 0$

Rearrangement $x = g(x)$	how	$g'(x)$	$\|g'(r)\|$ at $r = 5.7417$	verdict
$x = \sqrt{4x + 10}$	move $x^2$ , take root	$\dfrac{2}{\sqrt{4x+10}}$	0.348	converges
$x = \dfrac{x^2 - 10}{4}$	solve for the $4x$ term	$\dfrac{x}{2}$	2.871	diverges
$x = \dfrac{10}{x - 4}$	factor $x(x-4) = 10$	$\dfrac{-10}{(x-4)^2}$	3.297	diverges (goes to the other root)
$x = 4 + \dfrac{10}{x}$	divide by $x$	$\dfrac{-10}{x^2}$	0.303	converges (spirals)

Roots: $x = 2 \pm \sqrt{14}$ , i.e. $5.741657$ and $-1.741657$ . Every rearrangement has the same fixed points, but only some lead there.

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

6 / 21

When does it converge?

Error recursion (mean value theorem)

x_{n+1} - r = g(x_n) - g(r) = g'(\xi_n)(x_n - r)

Convergence condition

|g'(x)| \le L < 1 \text{ near } r \;\Longrightarrow\; |x_n - r| \le L^{n}\,|x_0 - r| \to 0

Each step multiplies the error by about $g'(r)$ : linear convergence, rate $|g'(r)|$
$|g'(r)| > 1$ : errors grow, the iteration moves away from $r$
Smaller $|g'(r)|$ = faster; $g'(r) = 0$ is very fast (that is Newton, next lecture)
Sign of $g'$ : positive → staircase (one-sided); negative → spiral (alternating sides)

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

7 / 21

The method, step by step

The fixed-point iteration algorithm

Rewrite $f(x) = 0$ as $x = g(x)$ (there are many ways)
Pick a $g$ with $|g'(x)| < 1$ near the root; choose a starting value $x_0$
Compute $x_{n+1} = g(x_n)$
Repeat until $|x_{n+1} - x_n| < \varepsilon$ ; the answer is the last $x$
If the values grow or jump about, stop and choose a different $g$

Pseudocode

input g, x0, tol, N
x ← x0
repeat up to N times:
    x_new ← g(x)
    if |x_new − x| < tol:
        return x_new
    x ← x_new
stop: no convergence (try another g)

The loop is the shortest in the course. All the skill is in step 2: choosing a $g$ that contracts.

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

8 / 21

Explore: cobweb diagrams

From $x_n$ go up to the curve $y = g(x)$ , then across to $y = x$ : that is $x_{n+1}$
Try the four rearrangements of $x^2 - 4x - 10 = 0$ (chips)
$|g'| < 1$ : the web closes in; $|g'| > 1$ : it opens out
Watch $4 + 10/x$ spiral, $\sqrt{4x+10}$ climb a staircase

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

9 / 21

Problem 1: $x^2 - 4x - 10 = 0$ by the iteration method

Problem 1"Find out the root of the following equation using the iteration method:

x^2 - 4x - 10 = 0

."

1

Locate:

f(5) = -5

,

f(6) = 2

: a root lies in

(5, 6)

. Take

x_0 = 5

2

Choose

g(x) = \sqrt{4x + 10}

; check

|g'(x)| = \dfrac{2}{\sqrt{4x+10}} \le \dfrac{2}{\sqrt{30}} = 0.365 < 1

on

[5, 6]

✓

3

Iterate:

x_1 = \sqrt{30} = 5.477226

,

x_2 = \sqrt{31.908904} = 5.648797

,

x_3 = 5.709219

, …

4

Continue until

|x_{n+1} - x_n| < 0.00005

:

x_{10} = 5.741637

x \approx 5.7416

(true

2 + \sqrt{14} = 5.7416574

). Ten iterations: convergence is linear with rate 0.348.

$n$	$x_n$	$\|x_n - x_{n-1}\|$
0	5.000000	—
1	5.477226	0.477
2	5.648797	0.172
3	5.709219	0.0604
4	5.730347	0.0211
5	5.737716	0.00737
6	5.740284	0.00257
7	5.741179	0.000895
8	5.741491	0.000312
9	5.741599	0.000109
10	5.741637	0.0000378

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

10 / 21

Classical vs numerical

Same problem, two approaches: $x^2 - 4x - 10 = 0$

Algebra

Classical (exact formula)

Quadratic formula: $x = \dfrac{4 \pm \sqrt{16 + 40}}{2} = 2 \pm \sqrt{14}$
Both roots at once: $5.741657$ and $-1.741657$
Exists for degree 2 (and, with effort, degrees 3 and 4)

vs

Algorithm

Numerical (fixed point)

$x = \sqrt{4x+10}$ from $x_0 = 5$
14 iterations for $10^{-6}$ : $5.741657$
One root per run; the other root needs a different $g$ ( $10/(x-4)$ )

When the classical approach cannot work

$x = \cos x$ and Kepler’s equation $E = M + e\sin E$

No formula gives $x$ or $E$ in closed form. Fixed-point iteration: $x = 0.739085$ (36 iterations for 6 decimals); Kepler with $M = 1$ , $e = 0.1$ : $E = 1.088598$ in 5.

When a closed form exists and is cheap, use it. Numerical methods are for the (much larger) set of problems without one.

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

11 / 21

Linear convergence: how many iterations?

Errors shrink by the factor $L = |g'(r)|$ each step: $e_n \approx L^n e_0$
For $\sqrt{4x+10}$ : measured ratios $e_{n+1}/e_n$ = 0.351, 0.349, 0.349, 0.348, … → $g'(r) = 0.3483$ ✓
Steps for tolerance $\varepsilon$ : $n \approx \dfrac{\ln(\varepsilon / e_0)}{\ln L}$ ; here $\dfrac{\ln(0.00005/0.742)}{\ln 0.348} \approx 9.1$ → 10 ✓
Compare: $x = \cos x$ has $L = \sin(0.739) = 0.674$ : 36 iterations for 6 decimals
$L$ close to 1 means painfully slow; $L > 1$ means divergence

Rule of thumb

Digits per iteration

Each iteration gains about $-\log_{10} L$ correct decimal digits.
$L = 0.348$ : 0.46 digits per step.
$L = 0.1$ : one digit per step.
Bisection ( $L = \tfrac12$ ): 0.3 digits per step.

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

12 / 21

Fixed-point iteration in Python and C

A guard on $|x|$ stops runaway (divergent) iterations
Change g to the other three rearrangements
Print the ratio of successive differences: it approaches $g'(r)$
Try $g(x) = \cos x$ and $g(x) = e^{-x}$

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

13 / 21

Choosing $g$ for $x^3 + x - 1 = 0$ (root 0.6823)

$g(x)$	$\|g'(r)\|$	result from $x_0 = 0.5$
$1 - x^3$	1.397	diverges (oscillates and grows)
$\dfrac{1}{1 + x^2}$	0.635	converges: 21 iterations to 4 dp
$(1 - x)^{1/3}$	0.716	converges, slower
Newton: $x - \dfrac{x^3 + x - 1}{3x^2 + 1}$	0	converges fast: 4 iterations

The last row is a sneak preview: choosing $g$ cleverly makes $g'(r) = 0$ . That choice is Newton's method (Lecture 9).

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

14 / 21

When to use it

Fixed-point iteration: method profile

Best case

$|g'(r)|$ small: Kepler's equation $E = 1 + 0.1\sin E$ converges in 5 steps
$g'(r) = 0$ : much faster than linear (this is Newton's method, L9)
The problem is already in the form $x = g(x)$ : no derivative, one line of code

Worst case

$|g'(r)|$ close to 1: $x = \cos x$ needs 36 steps; Kepler with $e = 0.9$ needs 11
$|g'(r)| > 1$ : diverges, e.g. $x = (x^2 - 10)/4$ for the root 5.7417
The choice of $g$ is guesswork without the $|g'| < 1$ test

Best suited for

Equilibrium problems: PageRank, Bellman value iteration, EM, Kepler's equation
Large linear systems (Jacobi, Gauss–Seidel are fixed-point iterations, L14)
Quick prototypes where a contraction $g$ is obvious

Avoid when

No rearrangement with $|g'| < 1$ is known
High accuracy is needed quickly (linear convergence)
You need a guarantee from any start (use bracketing)

Rule of thumb: check $|g'|$ before iterating; the smaller it is, the fewer steps you need (about $-1/\log_{10}|g'|$ steps per digit).

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

15 / 21

Comparison

Comparative analysis so far: $x^2 - 4x - 10 = 0$ (root 5.741657)

Method	Start	Iterations for $10^{-6}$	Needs	Guaranteed?
Bisection	$[5, 6]$	20	sign change	yes
False position	$[5, 6]$	5	sign change	yes
Fixed point, $g = \sqrt{4x+10}$	$x_0 = 5$	14	a good $g$	only if $\|g'\| < 1$
Fixed point, $g = (x^2 - 10)/4$	$x_0 = 5$	diverges from 5.74	a good $g$	no

Fixed-point iteration is not faster here than false position, and it can fail. Its value is the idea: Lecture 9 builds the best possible $g$ , with $g'(r) = 0$ .

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

16 / 21

Roadmap

Limitations, and where we fix them

Fixed-point iteration introduced open methods and the convergence rate $|g'(r)|$ . Its weaknesses point to the next lectures:

What it does well (keep this)

No bracket: one starting value
Very simple: one line per step
Convergence test $|g'(r)| < 1$ predicts the speed
The same idea scales to huge systems

LimitationHow it is overcomeWhere

The choice of

g

is guesswork; may diverge

→

Build

g

systematically from the tangent:

g = x - f/f'

Lecture 9 →

Only linear convergence

→

Make

g'(r) = 0

: quadratic convergence (Newton)

Lecture 9 →

Converges only near the root

→

Start with a few bisection steps, then switch (hybrid)

Lecture 10 →

Large linear systems

→

Jacobi and Gauss–Seidel: fixed-point iteration with matrices

Lecture 14 →

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

17 / 21

Applications

Where this method runs in the real world

Click a card: each one is literally $x \leftarrow g(x)$ repeated until it stops changing.

Page	A	B	C
rank after convergence	0.3878	0.2148	0.3974

iteration	1	2	3	4	5
$E$ ( $M = 1$ , $e = 0.1$ )	1.084147	1.088390	1.088588	1.088597	1.088598

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

18 / 21

Practice

Practice problem

Problem 2"State the condition of convergence of the iteration method

x_{n+1} = g(x_n)

and explain why the choice of

g

matters. Illustrate with

x^2 - 4x - 10 = 0

."

How to write a complete answer

Condition: $|g'(x)| < 1$ in an interval around the root containing all iterates (sufficient)
Reason in one line: $e_{n+1} = g'(\xi)e_n$ (mean value theorem)
Illustrate: $\sqrt{4x+10}$ ( $|g'| = 0.35$ , converges) vs $(x^2-10)/4$ ( $|g'| = 2.87$ , diverges)
Mention: convergence is linear; the smaller $|g'(r)|$ , the faster

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

19 / 21

Checkpoint

Checkpoint · think, then discuss with your neighbourFor

x = g(x)

with

g(x) = \dfrac{x^2 + 2}{3}

, does iteration converge to the root

r = 1

?

AYes,

|g'(1)| = 2/3 < 1

BNo,

|g'(1)| = 2/3

CYes,

g(1) = 1

DNo,

|g'(1)| > 1

A.

g'(x) = 2x/3

, so

|g'(1)| = 2/3 < 1

: converges (staircase, since

g' > 0

). The other root

r = 2

has

g'(2) = 4/3 > 1

: iteration moves away from it.

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

20 / 21

Summary

Key points

Rewrite $f(x) = 0$ as $x = g(x)$ and iterate $x_{n+1} = g(x_n)$
Converges if $|g'(x)| < 1$ near the root; diverges if $|g'(r)| > 1$
Linear convergence: error × $|g'(r)|$ per step; steps ≈ $\ln(\varepsilon/e_0)/\ln L$
The rearrangement decides everything; always check $|g'|$ before iterating
Choosing $g$ with $g'(r) = 0$ gives fast convergence: Newton's method

Opening problem: solved

cos settles because near 0.739 its slope is $|-\sin x| = 0.674 < 1$ (a contraction); tan never settles because its slope $\sec^2 x \ge 1$ everywhere.

Homework

Solve $x = e^{-x}$ by iteration from $x_0 = 0.5$ to 4 decimal places. How many iterations?
Find two rearrangements of $x^3 - 2x - 5 = 0$ : one that converges near $x = 2.09$ and one that does not. Justify with $g'$ .
Write a C program that reads $x_0$ and prints the iterates of $g(x) = \cos x$ until 6 decimals agree.
Lab: in the cobweb tab, find a $g$ whose iterates oscillate between two values forever.

Next lecture

Newton–Raphson. Use the tangent line: the fastest of the classical methods, with digits doubling each step, and some spectacular failures.

Md Mahbub E Noor

Lecture 8: Fixed-Point Iteration

University of Barishal

21 / 21

Fixed-Point Iteration

The problem: why does the cos button settle?

Today's goals

The idea in one picture

The idea: a fixed point of $g$

One equation, many rearrangements: $x^2 - 4x - 10 = 0$

When does it converge?

The fixed-point iteration algorithm

Explore: cobweb diagrams

Problem 1: $x^2 - 4x - 10 = 0$ by the iteration method

Same problem, two approaches: $x^2 - 4x - 10 = 0$

Classical (exact formula)

Numerical (fixed point)

$x = \cos x$ and Kepler’s equation $E = M + e\sin E$

Linear convergence: how many iterations?

Digits per iteration

Fixed-point iteration in Python and C

Choosing $g$ for $x^3 + x - 1 = 0$ (root 0.6823)

Fixed-point iteration: method profile

Comparative analysis so far: $x^2 - 4x - 10 = 0$ (root 5.741657)

Limitations, and where we fix them

Where this method runs in the real world

🌐 PageRank

🛰️ Kepler's equation: satellite positions

🎮 Reinforcement learning: value iteration

🧮 Jacobi iteration for big linear systems

Practice problem

Checkpoint

Summary

Fixed-Point Iteration

The problem: why does the cos button settle?

Today's goals

The idea in one picture

The idea: a fixed point of ggg

One equation, many rearrangements: x2−4x−10=0x^2 - 4x - 10 = 0x2−4x−10=0

When does it converge?

The fixed-point iteration algorithm

Explore: cobweb diagrams

Problem 1: x2−4x−10=0x^2 - 4x - 10 = 0x2−4x−10=0 by the iteration method

Same problem, two approaches: x2−4x−10=0x^2 - 4x - 10 = 0x2−4x−10=0

Classical (exact formula)

Numerical (fixed point)

x=cos⁡xx = \cos xx=cosx and Kepler’s equation E=M+esin⁡EE = M + e\sin EE=M+esinE

Linear convergence: how many iterations?

Digits per iteration

Fixed-point iteration in Python and C

Choosing ggg for x3+x−1=0x^3 + x - 1 = 0x3+x−1=0 (root 0.6823)

Fixed-point iteration: method profile

Comparative analysis so far: x2−4x−10=0x^2 - 4x - 10 = 0x2−4x−10=0 (root 5.741657)

Limitations, and where we fix them

Where this method runs in the real world

🌐 PageRank

🛰️ Kepler's equation: satellite positions

🎮 Reinforcement learning: value iteration

🧮 Jacobi iteration for big linear systems

Practice problem

Checkpoint

Summary

The idea: a fixed point of $g$

One equation, many rearrangements: $x^2 - 4x - 10 = 0$

Problem 1: $x^2 - 4x - 10 = 0$ by the iteration method

Same problem, two approaches: $x^2 - 4x - 10 = 0$

$x = \cos x$ and Kepler’s equation $E = M + e\sin E$

Choosing $g$ for $x^3 + x - 1 = 0$ (root 0.6823)

Comparative analysis so far: $x^2 - 4x - 10 = 0$ (root 5.741657)