1. Newton–Raphson Method
Idea
One of the most powerful root-finding methods. At each step, replace with its first-order Taylor expansion (the tangent line) at the current point and solve that instead:
Algorithm
This is a fixed-point iteration with .
Example (extra) – ,
, , .
Convergence check: ✓
| 0 | 1 | 1 | 4 | 0.75 | |
| 1 | 0.75 | 0.171875 | 2.6875 | 0.686047 | |
| 2 | 0.686047 | 0.008941 | 2.411979 | 0.682340 | |
| 3 | 0.682340 | 2.396762 | 0.6823278039 |
The number of correct digits roughly doubles each step (2 → 5 → 10).
2. Convergence of Newton–Raphson
Theorem – Sufficient condition
If , is a root, and and have constant sign on , then choosing with
makes Newton–Raphson converge.
Theorem – Quadratic convergence (simple root)
With , the method is quadratically convergent if
For a simple root (), this limit is (extra).
Check on the example (extra): , , and the formula gives ✓
Theorem – Multiple root (linear convergence)
If is times continuously differentiable and is a root of multiplicity (so ), Newton is still locally convergent, but only linearly:
Example (extra)
(double root, ): , so → ✓
⚠️ Newton is sensitive to . It can diverge if isn’t close enough to the root, and it fails outright if (horizontal tangent).
3. Secant Method
Idea
When is hard or expensive to compute, replace it with a backward difference through the last two iterates:
Algorithm
It needs two initial points (no sign condition, unlike bisection).
Example (extra) – , ,
| 1 | 0 | 1 | 0.5 | |
| 2 | 1 | 0.5 | 0.636364 | |
| 3 | 0.5 | 0.636364 | 0.690052 | |
| 4 | 0.636364 | 0.690052 | 0.682020 | |
| 5 | 0.690052 | 0.682020 | 0.682326 | |
| 6 | 0.682020 | 0.682326 | 0.6823278044 |
First step: .
⚠️ Extra: the secant method’s order is (superlinear). It’s slower per step than Newton, but each step needs only one new -evaluation and no derivative.
4. Comparison of the Methods
| Method | Strengths | Weaknesses |
|---|---|---|
| Bisection | Guaranteed to converge; number of iterations for a given precision known in advance | Slow; the error doesn’t necessarily decrease every iteration |
| Fixed point | Simple to implement and understand; convergence guaranteed under conditions () | Slow in some cases; may not converge, or converge to an undesired root with a bad /guess |
| Newton–Raphson | Fast (quadratic) convergence; extends to several variables | Needs ; sensitive to the initial guess, can diverge if not close enough |
| Secant | Simple; no derivative needed; acceptable (superlinear) speed | Slower than Newton; can diverge with poorly chosen initial points |
| Method | Order | Points needed | Needs | Bracketing |
|---|---|---|---|---|
| Bisection | 1, | 2 (sign change) | no | yes |
| Fixed point | 1 (usually) | 1 | no (but needs ) | no |
| Newton | 2 | 1 | yes | no |
| Secant | ≈ 1.618 | 2 | no | no |