Visual walkthrough — Solving nonlinear systems — Newton's method in n dimensions

4.8.29 · D2 · Maths › Numerical Methods › Solving nonlinear systems — Newton's method in n dimensions

Hum poori method ko us case ke liye build karenge jo ek samajhdar 12-saal-ka baccha dekh sake: do equations, do unknowns ($n=2$). Sab kuch $n$ dimensions mein generalise hota hai — bas "$2$" ki jagah "$n$" rakh do — hum bilkul wahi jagah batayenge.

Step 1 — "$\mathbf{F}(\mathbf{x})=0$" dikhta kaisa hai?

KYA HAI. Hamare paas do knobs hain — unhe $x$ aur $y$ bulao. Dono ko ek arrow (ek point) mein bundle karo jise $\mathbf{x}=(x,y)$ kehte hain. Do rules hain jo dono ek saath zero aani chahiye:

Har rule flat $(x,y)$ plane mein ek curve hai: un points ka set jahan woh rule zero read karta hai. Ek root ${\mathbf{x}}^{\ast }$ woh jagah hai jahan dono curves cross karti hain.

KYO. Koi bhi calculus touch karne se pehle hume target pata hona chahiye: "ek cheez zero karo" nahi balki "kai cheezein simultaneously zero karo" — ek crossing point. Aage ka sab kuch usi crossing ko dhoondne ki machine hai.

PICTURE.

Step 2 — Itna zoom karo jab tak curve seedha na lage

KYA HAI. Ek guess ${\mathbf{x}}_k=(x_k,y_k)$ lo. Yeh crossing par nahi hai. Ab ek rule ki curve ko ${\mathbf{x}}_k$ ke paas hard zoom karo. Koi bhi smooth curve, kaafi close dekhi jaaye, ek straight line jaisi lagti hai — uski tangent.

KYO. Straight cheezein hum exactly solve kar sakte hain (woh sirf algebra hai, koi guessing nahi). Curved cheezein nahi kar sakte. Toh poori trick hai: curve ko uski tangent line se replace karo guess ke paas, aasaan straight problem solve karo, aur ek chhoti si error accept karo kyunki hum sirf locally pretend kar rahe hain.

PICTURE.

Step 3 — Har direction mein slope measure karo: the Jacobian

KYA HAI. Plane mein ek curve ka slope hota hai, lekin $f_1$ actually do knobs par depend karta hai, toh ${\mathbf{x}}_k$ par uske do slopes hain: kitni tezi se change hota hai agar $x$ nudge karein ($y$ ko fixed rakh ke), aur kitni tezi se agar $y$ nudge karein. Yeh do numbers hain partial derivatives $\frac{\partial f_1}{\partial x}$ aur $\frac{\partial f_1}{\partial y}$.

Dono rules ke liye yahi karo aur chaar numbers ko ek box mein stack karo — Jacobian:

Row $i$ hai "rule $i$ kaise tilt karta hai". Column $j$ hai "agar mein knob $j$ push karun toh kya hoga".

KYO. 1-D mein, ek slope number $f^{\prime }$ ne hume bata diya tha root ki taraf kaise slide karein. 2-D mein do rules hain aur do knobs, toh "slope" ko $2\times 2=4$ numbers chahiye. Jacobian exactly $f^{\prime }$ ka $n$-D upgrade hai — Jacobian matrix.

PICTURE.

Step 4 — Flat ramp likho: the linear model

KYA HAI. Maano $\mathbf{h}=(h_x,h_y)$ guess se ek chhota step hai. Multivariable Taylor's theorem (multivariable) kehta hai ki har rule, ${\mathbf{x}}_k$ ke paas, apni value plus slopes times step plus ek tiny leftover ke barabar hai:

Dono rules stack karo aur "slope × step" part exactly Jacobian times step ban jaata hai:

KYO. Hum tiny leftover $O(\Vert \mathbf{h}{\Vert }^2)$ jaanbujh ke drop karte hain — yahi Newton's method mein ek maatra approximation hai. Jo bacha woh ek flat ramp hai (ek linear map): woh straight hai, toh hum ise exactly solve kar sakte hain. Jo hum ne throw away kiya uski size $\Vert \mathbf{h}{\Vert }^2$ hai; woh number Step 8 mein blazing speed explain karega.

PICTURE.

Step 5 — Ramp ko zero par demand karo, aur solve karo

KYA HAI. Hum chahte hain ki true $\mathbf{F}$ zero ho. Hum curve par yeh force nahi kar sakte, lekin apne flat ramp par kar sakte hain. Model ko $0$ set karo aur step $\mathbf{h}$ ke liye solve karo:

Box padhte hain: "Jacobian, unknown step $\mathbf{h}$ par apply hoke, current miss $\mathbf{F}({\mathbf{x}}_k)$ undo kare." Yeh ek plain linear system $A\mathbf{h}=\mathbf{b}$ hai jahan $A=J$, $\mathbf{b}=-\mathbf{F}$ — exactly waisa jaisa Gaussian elimination aur LU decomposition khel khelte hain.

KYO. Yeh step saari zooming ka payoff hai: humne ek impossible nonlinear demand ko ek solvable straight demand mein convert kar diya. Hum ise solve karte hain ($J$ invert nahi — mistake box dekho), answer ko $\Delta {\mathbf{x}}_k=\mathbf{h}$ rename karte hain, aur step lete hain:

PICTURE.

Step 6 — Ek poora iteration closer land hote dekho

KYA HAI. Step lene ke baad, ${\mathbf{x}}_{k+1}$ wahan baith jaata hai jahan tangent zero cross karta hai. Real curve perfectly straight nahi thi, toh hum exactly root par nahi hain — lekin bahut karib hain. Wahan naye slopes measure karo, fresh ramp banao, phir step lo.

KYO. "Zoom → flatten → solve → step" ka ek step hi poora algorithm hai. Ise repeat karna hume crossing par walk karta hai. Dekho kaise miss $\Vert \mathbf{F}\Vert$ collapse hoti hai.

PICTURE.

Step 7 — Degenerate case: flat ya crossing-slope Jacobian

KYA HAI. Ramp ka ek jagah zero hit karna tab hi hota hai jab woh actually tilt kare. Agar $J({\mathbf{x}}_k)$ singular ho ($\det J=0$), toh dono rows parallel hain — ramp ek valley ya flat sheet hai, single point nahi. Tab $J\Delta \mathbf{x}=-\mathbf{F}$ ka koi solution nahi ya infinitely many hain: step undefined hai ya infinity jaata hai.

KYO. Yeh exactly scalar Newton ka twin hai jo flat spot par $f^{\prime }=0$ se divide karta hai. Yeh hota hai (a) jab dono curves cleanly cross karne ki jagah tangentially touch karein (double root), ya (b) mid-iteration jab guess kisi bure ridge par land ho jaaye. Ilaaj: ${\mathbf{x}}_0$ change karo, ya damped Newton use karo (step ka ek fraction lo) — practical fixes ke liye Convergence order of iterative methods aur Broyden's method dekho. Jab root par $J({\mathbf{x}}^{\ast })$ singular ho, toh Step 8 ki quadratic speed slow crawling mein downgrade ho jaati hai.

PICTURE.

Step 8 — Error har step square kyun hoti hai

KYA HAI. Error ko ${\mathbf{e}}_k={\mathbf{x}}_k-{\mathbf{x}}^{\ast }$ maano (guess true crossing se kitni door hai). Hum ne jo ek hi cheez throw away ki thi woh Step 4 ka $O(\Vert \mathbf{h}{\Vert }^2)$ leftover tha. Wahi leftover naya error ban jaata hai:

Agar aaj ki error $10^{-2}$ hai, kal ki $\sim 10^{-4}$ hogi, phir $10^{-8}$, phir $10^{-16}$ — correct digits ki count har step double hoti hai.

KYO. Yeh "error ko square karna" behavior quadratic convergence kehlaata hai (dekho Convergence order of iterative methods). Yeh tab hold karta hai jab (1) ${\mathbf{x}}_0$ kaafi close ho aur (2) $J({\mathbf{x}}^{\ast })$ nonsingular ho (Step 7). Yahi reason hai ki Newton slow methods jaise Fixed-point iteration se better hai, jinki error sirf ek constant factor se shrink hoti hai har step (linear convergence).

PICTURE.

Ek-picture summary

Sab ek saath: true curve (cyan), guess ${\mathbf{x}}_k$, flat tangent ramp (white), step $\Delta \mathbf{x}$ jo wahan land karta hai jahan ramp zero hit karta hai, aur root ${\mathbf{x}}^{\ast }$ (amber) ki taraf shrinking hop. $J\Delta \mathbf{x}=-\mathbf{F}$ solve karo, add karo, repeat karo.

Quick self-check