1. Fixed Points

Definition – Fixed point

is a fixed point of if

i.e. applying leaves the value unchanged. Graphically, it’s where crosses the line .

Theorem – Root-finding ⇔ fixed-point problem

  • Given , define e.g. : then .
  • Given a fixed point , define : then .

So finding a fixed point of is the same as finding a root of . Fixed-point form is easier to analyze, and choosing well makes root-finding methods more powerful (Newton is one particular choice of ).


2. Fixed-Point Iteration (Open Method)

Algorithm


If the sequence converges to and is continuous, then solves .

Stop when or after iterations.

Building from

Every equation can be rewritten as , in many different ways.

Example (slides + extra) –

Rewriting,
(slides)
(extra)

Iterating both from :

10.8750000.800000
20.3300780.609756
30.9640370.728968
40.1040540.653000
50.9988730.701061
60.0033760.670472
7→ bounces between 0 and 10.689878
8✗ diverges0.677538 → 0.682328 ✓

g(x)=1/(1+x²): |g′(r)|≈0.64 < 1 → converges00.250.50.75100.250.50.751xyy = xy = g(x)

g(x)=1−x³: |g′(r)|≈1.40 > 1 → diverges00.250.50.75100.250.50.751xyy = xy = g(x)

⚠️ The same equation can give a convergent or a divergent iteration depending on how you write . Always check near the root before iterating.

⚠️ makes the iterates oscillate around (a spiral cobweb); gives a monotone staircase.


3. Fixed-Point Theorem

Theorem – Existence

If is continuous on and for all ( maps the interval into itself), then has at least one fixed point in .

Theorem – Uniqueness and convergence

If in addition exists on and there is a constant with

then for any the sequence converges to the unique fixed point .

Example (extra) – check the theorem for on

  1. Maps into itself: is decreasing, , → ✓
  2. Contraction: peaks at with value → ✓

So the iteration converges from any start in .

⚠️ Extra (standard consequence of the theorem): the error shrinks roughly like . For example , so a close to means slow convergence.


4. Order of Convergence

Theorem

If

then the fixed-point iteration has order . In other words, the order equals the order of the first derivative that is nonzero at .

At the rootOrder
1 (linear),
2 (quadratic)
3 (cubic)

Example (extra)

  • : → linear, each step multiplies the error by about .
  • Newton’s choice gives → at least quadratic (see 2.3).

5. Strengths and Weaknesses

StrengthsWeaknesses
Simple to implement and understandSlow convergence in some cases
Convergence guaranteed under the theorem’s conditionsMay fail to converge, or converge to an unwanted root, with a bad or initial guess