Fixed-point iteration — convergence conditions

4.8.7 · Maths › Numerical Methods

WHAT is a fixed point?

WHY $f (x) = 0$ ko $x = g (x)$ ke roop mein kyun likhein? Kyunki iteration program karna bahut simple hai (bas $g$ ko baar baar apply karo), aur yeh Newton's method, Gauss–Seidel, wagera ka base hai. Art yeh hai ki aisa $g$ choose karo jo converge kare.

HOW convergence works — scratch se derive karo

Maano $e_{n} = x_{n} - x^{*}$ step $n$ par error hai. Hum jaanna chahte hain ki $e_{n + 1}$ ka $e_{n}$ se kya relation hai.

Iteration aur fixed-point property se shuru karo: $x_{n + 1} = g (x_{n}), x^{*} = g (x^{*}) .$ Subtract karo: $e_{n + 1} = x_{n + 1} - x^{*} = g (x_{n}) - g (x^{*}) .$

Ab Mean Value Theorem lagao: koi $ξ_{n}$ , $x_{n}$ aur $x^{*}$ ke beech mein hoga jiske liye $g (x_{n}) - g (x^{*}) = g^{'} (ξ_{n}) (x_{n} - x^{*}) .$

Absolute values lete hain: $∣ e_{n + 1} ∣ = ∣ g^{'} (ξ_{n}) ∣ ∣ e_{n} ∣$ . Agar root ke paas $∣ g^{'} (x) ∣ \leq k < 1$ ho, to $∣ e_{n + 1} ∣ \leq k ∣ e_{n} ∣ \leq k^{2} ∣ e_{n - 1} ∣ \leq \dots \leq k^{n + 1} ∣ e_{0} ∣ \to 0.$

WHY $< 1$ ? Har step mein error roughly $∣ g^{'} ∣$ se multiply hoti hai. 1 se neeche ka factor error ko geometrically shrink karta hai; 1 se upar ka factor use badhata hai.

Figure — Fixed-point iteration — convergence conditions

Global guarantee — Contraction Mapping

Doosra (a posteriori) bound tumhe iterating band karne deta hai jab $∣ x_{n} - x_{n - 1} ∣$ kaafi chhota ho jaaye.

Order / speed of convergence

Worked examples

Common mistakes (Steel-manned)

Flashcards

g

ka fixed point kya define karta hai?

Ek value

x^{*}

jahan

x^{*} = g (x^{*})

ho (

g

ke through input unchanged rahta hai).

Fixed-point method ka iteration formula?

x_{n + 1} = g (x_{n})

Local convergence condition?

Root ke paas

∣ g^{'} (x^{*}) ∣ < 1

ho.

Error recurrence derive karo.

e_{n + 1} = g (x_{n}) - g (x^{*}) = g^{'} (ξ_{n}) e_{n}

Mean Value Theorem se.

∣ g^{'} ∣ < 1

convergence kyun deta hai?

Har step mein error

\approx ∣ g^{'} ∣

se multiply hoti hai, to

∣ e_{n} ∣ \leq k^{n} ∣ e_{0} ∣ \to 0

Convergence quadratic kab hoti hai linear ki jagah?

Jab

g^{'} (x^{*}) = 0

ho (aur

g^{''} \neq = 0

); tab

e_{n + 1} \approx \frac{1}{2} g^{''} (x^{*}) e_{n}^{2}

Contraction (Banach) theorem ke do conditions?

g

[a, b]

ko apne andar map kare AUR

[a, b]

par

∣ g^{'} (x) ∣ \leq k < 1

ho.

A posteriori error bound?

∣ x_{n} - x^{*} ∣ \leq \frac{k}{1 - k} ∣ x_{n} - x_{n - 1} ∣

Newton's method fixed-point map ke roop mein fast kyun hai?

g (x) = x - f / f^{'}

g^{'} (x^{*}) = 0

milta hai, isliye quadratic convergence hoti hai.

Same

f

g_{A} = x^{2} - 2

g_{B} = x + 2

root 2 par — kaun converge karta hai?

g_{B}

(

g_{B}^{'} (2) = 1/4 < 1

);

g_{A}

diverge karta hai (

g_{A}^{'} (2) = 4

Recall Feynman: 12-saal ke bacche ko samjhao

Socho ek calculator button hai jo kuch operation $g$ karta hai. Tum ek number type karo, button dabaao, naya number aata hai, phir dabaao, phir... Fixed point ek jadui number hai jise button unchanged chhod deta hai. Agar button dabane se har baar tum us jadui number ke paas aate ho (button "gaps shrink" karta hai), to tum wahan pahunch jaoge — yahi hota hai jab button zyada "steep" na ho ( $∣ g^{'} ∣ < 1$ ). Agar dabane se tum door jaate ho, to tum kabhi nahi pahunchoge. To trick yeh hai ki aisa button design karo jo tumhe andar kheenche, bahar dhakele nahi.

Connections

Newton-Raphson method — special fixed-point map jahan $g^{'} (x^{*}) = 0$ .
Mean Value Theorem — error recurrence ka engine.
Banach Fixed-Point Theorem — global existence + uniqueness.
Order of convergence — linear vs quadratic classification.
Cobweb diagrams — iteration dynamics ka graphical view.
Gauss-Seidel iteration — multidimensional contraction (spectral radius $< 1$ ).