Intuition The big pictureTo solve f ( x ) = 0 f(x)=0 f ( x ) = 0 x = g ( x ) x = g(x) x = g ( x ) g g g x 0 → x 1 = g ( x 0 ) → x 2 = g ( x 1 ) → … x_0 \to x_1 = g(x_0) \to x_2 = g(x_1) \to \dots x 0 → x 1 = g ( x 0 ) → x 2 = g ( x 1 ) → … x ∗ x^* x ∗ x ∗ = g ( x ∗ ) x^* = g(x^*) x ∗ = g ( x ∗ ) fixed point — a value the machine g g g does this chain settle down to x ∗ x^* x ∗ The answer is governed by one number — ==how steep g g g ∣ g ′ ( x ∗ ) ∣ |g'(x^*)| ∣ g ′ ( x ∗ ) ∣ shrinks distances, iterates collapse onto the root. If it stretches them, they escape.
A point x ∗ x^* x ∗ fixed point of g g g x ∗ = g ( x ∗ ) x^* = g(x^*) x ∗ = g ( x ∗ ) f ( x ) = 0 f(x)=0 f ( x ) = 0 g ( x ) g(x) g ( x ) g g g f f f
Definition Fixed-point iterationGiven x 0 x_0 x 0 x n + 1 = g ( x n ) x_{n+1} = g(x_n) x n + 1 = g ( x n ) x n → x ∗ x_n \to x^* x n → x ∗
WHY rewrite f ( x ) = 0 f(x)=0 f ( x ) = 0 x = g ( x ) x=g(x) x = g ( x ) Because iteration is dead simple to program (just re-apply g g g art is choosing a g g g
Let e n = x n − x ∗ e_n = x_n - x^* e n = x n − x ∗ error at step n n n e n + 1 e_{n+1} e n + 1 e n e_n e n
Start from the iteration and the fixed-point property:
x n + 1 = g ( x n ) , x ∗ = g ( x ∗ ) . x_{n+1} = g(x_n), \qquad x^* = g(x^*). x n + 1 = g ( x n ) , x ∗ = g ( x ∗ ) . e n + 1 = x n + 1 − x ∗ = g ( x n ) − g ( x ∗ ) . e_{n+1} = x_{n+1}-x^* = g(x_n) - g(x^*). e n + 1 = x n + 1 − x ∗ = g ( x n ) − g ( x ∗ ) .
Now apply the Mean Value Theorem : there is some ξ n \xi_n ξ n x n x_n x n x ∗ x^* x ∗ g ( x n ) − g ( x ∗ ) = g ′ ( ξ n ) ( x n − x ∗ ) . g(x_n) - g(x^*) = g'(\xi_n)\,(x_n - x^*). g ( x n ) − g ( x ∗ ) = g ′ ( ξ n ) ( x n − x ∗ ) .
Taking absolute values: ∣ e n + 1 ∣ = ∣ g ′ ( ξ n ) ∣ ∣ e n ∣ |e_{n+1}| = |g'(\xi_n)|\,|e_n| ∣ e n + 1 ∣ = ∣ g ′ ( ξ n ) ∣ ∣ e n ∣ ∣ g ′ ( x ) ∣ ≤ k < 1 |g'(x)| \le k < 1 ∣ g ′ ( x ) ∣ ≤ k < 1 ∣ e n + 1 ∣ ≤ k ∣ e n ∣ ≤ k 2 ∣ e n − 1 ∣ ≤ ⋯ ≤ k n + 1 ∣ e 0 ∣ → 0. |e_{n+1}| \le k\,|e_n| \le k^2 |e_{n-1}| \le \dots \le k^{n+1}|e_0| \to 0. ∣ e n + 1 ∣ ≤ k ∣ e n ∣ ≤ k 2 ∣ e n − 1 ∣ ≤ ⋯ ≤ k n + 1 ∣ e 0 ∣ → 0.
WHY < 1 <1 < 1 Each step multiplies the error by roughly ∣ g ′ ∣ |g'| ∣ g ′ ∣ shrinks error geometrically; above 1 grows it.
Plot y = g ( x ) y=g(x) y = g ( x ) y = x y=x y = x ∣ g ′ ∣ < 1 |g'|<1 ∣ g ′ ∣ < 1 inward to the crossing; a steep curve (∣ g ′ ∣ > 1 |g'|>1 ∣ g ′ ∣ > 1 outward .
Definition Contraction on[ a , b ] [a,b] [ a , b ] g g g contraction if it maps [ a , b ] [a,b] [ a , b ] g ( [ a , b ] ) ⊆ [ a , b ] g([a,b])\subseteq[a,b] g ([ a , b ]) ⊆ [ a , b ] k < 1 k<1 k < 1 ∣ g ( x ) − g ( y ) ∣ ≤ k ∣ x − y ∣ |g(x)-g(y)|\le k|x-y| ∣ g ( x ) − g ( y ) ∣ ≤ k ∣ x − y ∣ x , y x,y x , y ∣ g ′ ( x ) ∣ ≤ k < 1 |g'(x)|\le k<1 ∣ g ′ ( x ) ∣ ≤ k < 1 [ a , b ] [a,b] [ a , b ]
The second (a posteriori) bound lets you stop iterating once ∣ x n − x n − 1 ∣ |x_n-x_{n-1}| ∣ x n − x n − 1 ∣ .
Worked example Example 1 — choosing agood g g g x 2 − x − 2 = 0 x^2 - x - 2 = 0 x 2 − x − 2 = 0 x = 2 , − 1 x=2,-1 x = 2 , − 1 Choice A: g ( x ) = x 2 − 2 g(x)=x^2-2 g ( x ) = x 2 − 2 g ′ ( x ) = 2 x g'(x)=2x g ′ ( x ) = 2 x g ′ ( 2 ) = 4 g'(2)=4 g ′ ( 2 ) = 4 ∣ 4 ∣ > 1 |4|>1 ∣4∣ > 1 diverges from near 2.
Why this step? We test ∣ g ′ ∣ |g'| ∣ g ′ ∣ Choice B: g ( x ) = x + 2 g(x)=\sqrt{x+2} g ( x ) = x + 2 g ′ ( x ) = 1 2 x + 2 g'(x)=\frac{1}{2\sqrt{x+2}} g ′ ( x ) = 2 x + 2 1 g ′ ( 2 ) = 1 4 < 1 g'(2)=\frac{1}{4}<1 g ′ ( 2 ) = 4 1 < 1 Converges to 2.
Iterate from x 0 = 1 x_0=1 x 0 = 1 x 1 = 3 ≈ 1.732 x_1=\sqrt3\approx1.732 x 1 = 3 ≈ 1.732 x 2 = 3.732 ≈ 1.932 x_2=\sqrt{3.732}\approx1.932 x 2 = 3.732 ≈ 1.932 x 3 ≈ 1.983 x_3\approx1.983 x 3 ≈ 1.983 → 2 \to 2 → 2 Lesson: Same equation, two g g g
Worked example Example 2 — using the stopping boundg ( x ) = cos x g(x)=\cos x g ( x ) = cos x [ 0 , 1 ] [0,1] [ 0 , 1 ] g ′ ( x ) = − sin x g'(x)=-\sin x g ′ ( x ) = − sin x ∣ g ′ ∣ ≤ sin 1 ≈ 0.841 = k < 1 |g'|\le \sin 1\approx0.841=k<1 ∣ g ′ ∣ ≤ sin 1 ≈ 0.841 = k < 1 x 0 = 0.5 x_0=0.5 x 0 = 0.5 x 1 = cos 0.5 = 0.8776 x_1=\cos0.5=0.8776 x 1 = cos 0.5 = 0.8776 x 2 = cos 0.8776 = 0.6390 x_2=\cos0.8776=0.6390 x 2 = cos 0.8776 = 0.6390 x ∗ ≈ 0.739 x^*\approx0.739 x ∗ ≈ 0.739 Why this step? Once ∣ x n − x n − 1 ∣ < ε 1 − k k |x_n-x_{n-1}|<\varepsilon\frac{1-k}{k} ∣ x n − x n − 1 ∣ < ε k 1 − k ∣ x n − x ∗ ∣ < ε |x_n-x^*|<\varepsilon ∣ x n − x ∗ ∣ < ε
Worked example Example 3 — Newton as fixed-pointFor f ( x ) = x 2 − 2 f(x)=x^2-2 f ( x ) = x 2 − 2 g ( x ) = x − x 2 − 2 2 x = x 2 + 1 x g(x)=x-\dfrac{x^2-2}{2x}=\dfrac{x}{2}+\dfrac1x g ( x ) = x − 2 x x 2 − 2 = 2 x + x 1 g ′ ( x ) = 1 2 − 1 x 2 g'(x)=\frac12-\frac1{x^2} g ′ ( x ) = 2 1 − x 2 1 x ∗ = 2 x^*=\sqrt{2} x ∗ = 2 g ′ ( 2 ) = 1 2 − 1 2 = 0 g'(\sqrt2)=\frac12-\frac12=0 g ′ ( 2 ) = 2 1 − 2 1 = 0 quadratic — digits roughly double each step. From x 0 = 1 x_0=1 x 0 = 1 1.5 , 1.41 6 ‾ , 1.41421568 … 1.5,\ 1.41\overline{6},\ 1.41421568\ldots 1.5 , 1.41 6 , 1.41421568 …
Common mistake "Any rearrangementx = g ( x ) x=g(x) x = g ( x ) Why it feels right: Algebraically all rearrangements are equivalent equations with the same roots, so surely all iterate to the root.
The fix: Equivalence of equations ≠ equivalence of iterations . Convergence depends on ∣ g ′ ( x ∗ ) ∣ |g'(x^*)| ∣ g ′ ( x ∗ ) ∣ differs between rearrangements. Always check the derivative (see Example 1).
Common mistake "It converged once, so∣ g ′ ∣ < 1 |g'|<1 ∣ g ′ ∣ < 1 Why it feels right: The theorem states ∣ g ′ ∣ ≤ k < 1 |g'|\le k<1 ∣ g ′ ∣ ≤ k < 1 The fix: Local convergence only needs ∣ g ′ ( x ∗ ) ∣ < 1 |g'(x^*)|<1 ∣ g ′ ( x ∗ ) ∣ < 1 at the root plus a starting guess close enough. The global Banach version needs ∣ g ′ ∣ < 1 |g'|<1 ∣ g ′ ∣ < 1 [ a , b ] [a,b] [ a , b ] and g g g [ a , b ] [a,b] [ a , b ] into-itself condition!
g ′ ( x ∗ ) = 0 g'(x^*)=0 g ′ ( x ∗ ) = 0 Why it feels right: Zero slope sounds like nothing happens.
The fix: g ′ ( x ∗ ) = 0 g'(x^*)=0 g ′ ( x ∗ ) = 0 best case — super-fast quadratic convergence. The error formula e n + 1 ≈ 1 2 g ′ ′ e n 2 e_{n+1}\approx\frac12 g''e_n^2 e n + 1 ≈ 2 1 g ′′ e n 2
What defines a fixed point of g g g A value
x ∗ x^* x ∗ with
x ∗ = g ( x ∗ ) x^*=g(x^*) x ∗ = g ( x ∗ ) (input left unchanged by
g g g ).
Iteration formula for fixed-point method? x n + 1 = g ( x n ) x_{n+1}=g(x_n) x n + 1 = g ( x n ) .
Local convergence condition? ∣ g ′ ( x ∗ ) ∣ < 1 |g'(x^*)|<1 ∣ g ′ ( x ∗ ) ∣ < 1 near the root.
Derive the error recurrence. e n + 1 = g ( x n ) − g ( x ∗ ) = g ′ ( ξ n ) e n e_{n+1}=g(x_n)-g(x^*)=g'(\xi_n)e_n e n + 1 = g ( x n ) − g ( x ∗ ) = g ′ ( ξ n ) e n by the Mean Value Theorem.
Why does ∣ g ′ ∣ < 1 |g'|<1 ∣ g ′ ∣ < 1 Each step multiplies error by
≈ ∣ g ′ ∣ < 1 \approx|g'|<1 ≈ ∣ g ′ ∣ < 1 , so
∣ e n ∣ ≤ k n ∣ e 0 ∣ → 0 |e_n|\le k^n|e_0|\to0 ∣ e n ∣ ≤ k n ∣ e 0 ∣ → 0 .
When is convergence quadratic instead of linear? When
g ′ ( x ∗ ) = 0 g'(x^*)=0 g ′ ( x ∗ ) = 0 (and
g ′ ′ ≠ 0 g''\neq0 g ′′ = 0 ); then
e n + 1 ≈ 1 2 g ′ ′ ( x ∗ ) e n 2 e_{n+1}\approx\frac{1}{2} g''(x^*)e_n^2 e n + 1 ≈ 2 1 g ′′ ( x ∗ ) e n 2 .
Two conditions for the contraction (Banach) theorem? g g g maps
[ a , b ] [a,b] [ a , b ] into itself AND
∣ g ′ ( x ) ∣ ≤ k < 1 |g'(x)|\le k<1 ∣ g ′ ( x ) ∣ ≤ k < 1 on
[ a , b ] [a,b] [ a , b ] .
A posteriori error bound? ∣ x n − x ∗ ∣ ≤ k 1 − k ∣ x n − x n − 1 ∣ |x_n-x^*|\le \frac{k}{1-k}|x_n-x_{n-1}| ∣ x n − x ∗ ∣ ≤ 1 − k k ∣ x n − x n − 1 ∣ .
Why is Newton's method fast as a fixed-point map? g ( x ) = x − f / f ′ g(x)=x-f/f' g ( x ) = x − f / f ′ gives
g ′ ( x ∗ ) = 0 g'(x^*)=0 g ′ ( x ∗ ) = 0 , hence quadratic convergence.
Same f f f g A = x 2 − 2 g_A=x^2-2 g A = x 2 − 2 g B = x + 2 g_B=\sqrt{x+2} g B = x + 2 g B g_B g B (
g B ′ ( 2 ) = 1 / 4 < 1 g_B'(2)=1/4<1 g B ′ ( 2 ) = 1/4 < 1 );
g A g_A g A diverges (
g A ′ ( 2 ) = 4 g_A'(2)=4 g A ′ ( 2 ) = 4 ).
Recall Feynman: explain to a 12-year-oldImagine a calculator button that does some operation g g g fixed point is a magic number that the button leaves unchanged. If pressing the button each time brings you closer to the magic number (the button "shrinks" gaps), you'll land on it — that's when the button isn't too "steep" (∣ g ′ ∣ < 1 |g'|<1 ∣ g ′ ∣ < 1 further away , you'll never reach it. So the trick is to design a button that pulls you in, not pushes you out.
"Slope below one, the iteration's won; slope above, give the map a shove (away)." And g ′ = 0 g'=0 g ′ = 0 quadratic boost (think Newton).
Newton-Raphson method — special fixed-point map with g ′ ( x ∗ ) = 0 g'(x^*)=0 g ′ ( x ∗ ) = 0 Mean Value Theorem — engine behind the error recurrence.Banach Fixed-Point Theorem — global existence + uniqueness.Order of convergence — linear vs quadratic classification.Cobweb diagrams — graphical view of iteration dynamics.Gauss-Seidel iteration — multidimensional contraction (spectral radius < 1 <1 < 1
Fixed point x* where x*=g(x*)
Error recurrence e_n+1 = g'(xi) e_n
Unique fixed point, global convergence
Intuition Hinglish mein samjhoDekho, fixed-point iteration ka idea simple hai: f ( x ) = 0 f(x)=0 f ( x ) = 0 x = g ( x ) x=g(x) x = g ( x ) x 0 x_0 x 0 g g g x 1 x_1 x 1 x n + 1 = g ( x n ) x_{n+1}=g(x_n) x n + 1 = g ( x n ) x ∗ = g ( x ∗ ) x^*=g(x^*) x ∗ = g ( x ∗ ) g g g
Ab asli sawaal: ye chain settle hoga ya udd jayega? Iska boss ek number hai — root ke paas g g g ∣ g ′ ( x ∗ ) ∣ |g'(x^*)| ∣ g ′ ( x ∗ ) ∣ e n = x n − x ∗ e_n = x_n - x^* e n = x n − x ∗ e n + 1 = g ′ ( ξ ) e n e_{n+1} = g'(\xi)\,e_n e n + 1 = g ′ ( ξ ) e n ∣ g ′ ∣ |g'| ∣ g ′ ∣ ∣ g ′ ( x ∗ ) ∣ < 1 |g'(x^*)| < 1 ∣ g ′ ( x ∗ ) ∣ < 1 > 1 >1 > 1
Ek important baat: same equation ke bahut saare g g g x 2 − x − 2 = 0 x^2-x-2=0 x 2 − x − 2 = 0 g = x 2 − 2 g=x^2-2 g = x 2 − 2 g = x + 2 g=\sqrt{x+2} g = x + 2 ∣ g ′ ∣ |g'| ∣ g ′ ∣ g ′ ( x ∗ ) = 0 g'(x^*)=0 g ′ ( x ∗ ) = 0
Practical tip: stopping ke liye dekho ∣ x n − x n − 1 ∣ |x_n - x_{n-1}| ∣ x n − x n − 1 ∣
