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 :
| 1 | 0.875000 | 0.800000 |
| 2 | 0.330078 | 0.609756 |
| 3 | 0.964037 | 0.728968 |
| 4 | 0.104054 | 0.653000 |
| 5 | 0.998873 | 0.701061 |
| 6 | 0.003376 | 0.670472 |
| 7 | → bounces between 0 and 1 | 0.689878 |
| 8 | ✗ diverges | 0.677538 → 0.682328 ✓ |
⚠️ 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
- Maps into itself: is decreasing, , → ✓
- 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 root | Order |
|---|---|
| 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
| Strengths | Weaknesses |
|---|---|
| Simple to implement and understand | Slow convergence in some cases |
| Convergence guaranteed under the theorem’s conditions | May fail to converge, or converge to an unwanted root, with a bad or initial guess |