Foundations — Solving nonlinear systems — Newton's method in n dimensions

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

Is page par kuch bhi assumed nahi hai. parent topic padhne se pehle, tumhe usmein likhe har squiggle ko pehchaanna hoga. Neeche, har symbol ko teen cheezein di gayi hain: simple words mein kya matlab hai, uski picture, aur method ko uske bina kyun aage nahi chal sakta. Yeh is order mein hain ki har ek sirf upar walon par depend karta hai.

1. Number line, ek plane, aur ${\mathbb{R}}^n$

Picture. Figure s01 dekho: ek single point plane mein baitha hai, apne do coordinates se describe ho raha hai.

Topic ko yeh kyun chahiye. Saara problem hai "woh special point ${\mathbf{x}}^{\ast }$ ${\mathbb{R}}^n$ mein dhundho jahan sab kuch zero ho jaata hai." Agar yeh nahi pata ki $\mathbf{x}$ ek point hai jo $n$ numbers se bana hai, toh neeche wala boldface jaadoo lagta hai.

2. Bold letter $\mathbf{x}$ — ek vector

Picture. Figure s01 mein origin se point tak ka arrow wahi vector $\mathbf{x}=(x_1,x_2)$ hai. Uske do numbers hain — kitna right aur kitna upar chalna hai.

Topic ko yeh kyun chahiye. Ek dimension mein ek unknown $x$ tha. Yahan ek saath $n$ unknowns hain, aur unhe ek bold $\mathbf{x}$ mein bundle karne se hum $n$ equations ko ek single clean line mein likh sakte hain.

3. Kai variables ka ek function: $f_i(x_1,\dots ,x_n)$

Picture. Isko ek point on paper do, ek height milegi. Agar tum har point ke upar woh height plot karo, toh ek landscape milega — ek pahadi surface jo plane ke upar float kar rahi hai. Jahan height exactly $0$ hai, woh jagahein floor par ek curve banati hain: us landscape ki "sea-level line".

Topic ko yeh kyun chahiye. Har equation $f_i=0$ aslmein hai "landscape $i$ ki sea-level line par chalo." System solve karna = woh point dhundho jahan sab sea-level lines cross hoti hain.

4. Bold $\mathbf{F}$ aur equation $\mathbf{F}(\mathbf{x})=0$

Picture. Figure s02 do curves draw karta hai — ek circle ($f_1=0$) aur ek parabola ($f_2=0$). Har ek ek landscape ki sea-level line hai. Red dot jahan yeh cross hote hain woh ${\mathbf{x}}^{\ast }$ hai: woh akela jagah jahan dono ek saath zero hain.

Topic ko yeh kyun chahiye. Yeh crossing point poora goal hai. Newton jo kuch bhi karta hai woh is red dot ko dhundne ki machinery hai.

5. Curved rule ki slope: partial derivative $\frac{\partial f_i}{\partial x_j}$

Matrix se pehle, hume ek honest sub-idea chahiye: ek landscape kitna steep hai agar main sirf ek direction mein chalu?

Yeh tool kyun, ordinary derivative kyun nahi? Ordinary derivative $f^{\prime }$ ko ek variable ke function ki zaroorat hoti hai. Yahan $f_i$ kai par depend karta hai. Toh hum slope ek direction at a time poochte hain, aur curly $\partial$ exactly woh notation hai "slope jabki baaki sab fixed hai." Yeh $f^{\prime }$ ka sabse chhota honest generalisation hai.

Picture. Pahaad par khado. East ki taraf munh karo aur paon ke neeche tilt feel karo — woh hai $\partial f/\partial x$. Ab north ki taraf munh karo aur woh tilt feel karo — woh hai $\partial f/\partial y$. Ek hi jagah par do alag steepnesses. Figure s03 ek surface slice par dono slope arrows dikhata hai.

Topic ko yeh kyun chahiye. Ek curved rule ki ek single slope nahi hoti. Ise flat ramp pretend karne ke liye hume har input direction mein uski tilt jaanni hogi — aur har tilt ek partial derivative hai.

6. Saari slopes ko collect karna: Jacobian $J$

Picture. $J$ ko ek jagah par poore system ki "steepness report card" socho: ek row per equation, ek column per unknown. Yeh bumpy landscapes ka flat-ramp stand-in hai — Jacobian matrix literally number $f^{\prime }$ ka $n$-dimensional version hai.

Topic ko yeh kyun chahiye. Newton curved $\mathbf{F}$ ko ek ramp se replace karta hai. $n$ dimensions mein ek ramp exactly is grid of slopes se describe hota hai. Jacobian nahi ⇒ ramp nahi ⇒ method nahi.

7. Matrix ka vector par kaam karna: $J\mathbf{h}$

Picture. $J\mathbf{h}$ kehta hai: "agar main chhote vector $\mathbf{h}$ se step karun, toh ramp predict karta hai ki meri outputs itni change hongi." Yeh flat-ramp ka estimate hai ki $\mathbf{F}$ kaise move karta hai.

Topic ko yeh kyun chahiye. Core Newton equation $J\Delta \mathbf{x}=-\mathbf{F}$ ek matrix-times-vector statement hai. Ise solve karne se pehle tum ise padhna toh jaante ho.

8. Linear system $A\mathbf{h}=\mathbf{b}$ aur ise kaise crackte hain

Topic ko yeh kyun chahiye. Har Newton step ek aisa linear solve hai. Linearizing karne ka point precisely yahi tha ki ek aisi problem tak pahuncho jo yeh toolbox pehle se crush kar leta hai.

9. Distance aur error: $\Vert {\mathbf{e}}_k\Vert$ aur quadratic shrinking

Picture. Figure s04 error ko shrink hote dikhata hai $10^{-1}\to 10^{-2}\to 10^{-4}\to 10^{-8}$: yeh sirf girta nahi, gota lagata hai, kyunki har step pichle ke square par feed karta hai.

Topic ko yeh kyun chahiye. Yahi payoff hai — woh reason jiske liye hum Jacobians build karna aur systems solve karna tolerate karte hain. Plain Fixed-point iteration se compare karo, jo error ko har step mein sirf ek fixed fraction se shrink karta hai (linear). ${\mathbf{x}}_k$, ${\mathbf{e}}_k$ par subscript $k$ sirf iterations count karta hai: $k=0$ start hai, $k=1$ ek step ke baad, aur aise hi.

Yeh method ko kaise feed karta hai

Ise upar se neeche padho: numbers vectors bante hain, vectors $\mathbf{F}$ ko feed karte hain; slopes Jacobian mein stack hoti hain; Jacobian plus "zero hit karo" ki wish ek linear model deta hai; linear solver ise ek step mein badal deta hai; repeat karo, aur norm hume error ko crash hote dekhne deta hai.

Equipment checklist

Self-test: right side cover karo aur reveal karne se pehle dekho ki answer aa raha hai ya nahi.