Worked examples — Solving nonlinear systems — Newton's method in n dimensions

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

Parent note ne machine banai thi: scalar Newton bada hokar ban gaya $J({\mathbf{x}}_k)\Delta {\mathbf{x}}_k=-\mathbf{F}({\mathbf{x}}_k),{\mathbf{x}}_{k+1}={\mathbf{x}}_k+\Delta {\mathbf{x}}_k.$ Yahan hum us machine ko har tarah ke input par run karte hain — acche roots, singular Jacobians, bure start points, ek linear special case, ek real word problem, ek exam twist, aur ek aisa system jiska koi solution hi nahi. Ek bhi number chhune se pehle, chaliye naam lete hain ki "har tarah" ka matlab kya hai.

The scenario matrix

Neeche ke har worked example ko is table ke us cell se tag kiya gaya hai jo woh exercise karta hai. Saath milkar woh har cell ko touch karte hain.

Cell A — well-behaved unique root

Pehle figure padho: blue circle aur pink line do yellow dots par cross karti hain, origin ke through symmetric. Dashed chalk path dikhata hai ki hamara start (white square $(2,0)$ par) upper-right dot ki taraf slide kar raha hai. Picture ka poora message yeh hai: do roots hain, aur start unme se ek ke kaafi paas hai. Upper-right dot ko dhyan mein rakho.

Forecast: kyunki hum positive-$x$ side par start karte hain, aage padhne se pehle andaza lagao ki hum kaunse dot par land karenge.

1. Jacobian. $J=\left(\begin{array}{cc}2x& 2y\\ -1& 1\end{array}\right)$. Yeh step kyun? Row $i$ hai $\nabla f_i$ — woh direction jisme har equation sabse tezi se badhti hai. Woh gradient stack exactly Jacobian matrix hai, $f^{\prime }$ ka $n$-D stand-in.
2. Residual at ${\mathbf{x}}_0$. $\mathbf{F}=(4+0-1,0-2)=(3,-2)$. Yeh step kyun? Yeh measure karta hai ki hum kitne galat hain; agar yeh $0$ hota toh hum done hote.
3. Step solve karo. $J=\left(\begin{array}{cc}4& 0\\ -1& 1\end{array}\right)$, $\det =4$. Solve $J\Delta \mathbf{x}=(-3,2)$: $\Delta \mathbf{x}=\frac{1}{4}\left(\begin{array}{cc}1& 0\\ 1& 4\end{array}\right)\left(\begin{array}{c}-3\\ 2\end{array}\right)=\frac{1}{4}\left(\begin{array}{c}-3\\ 5\end{array}\right)=(-0.75,1.25).$ Yeh step kyun? $2\times 2$ ke liye $J^{-1}=\frac{1}{\det }\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$; hum residual ke negative se multiply karte hain. (Hand $2\times 2$ ke liye yeh theek hai — bade $n$ ke liye hum solve karte, invert nahi, dekho Ex 8.)
4. Update. ${\mathbf{x}}_1=(2,0)+(-0.75,1.25)=(1.25,1.25)$. Yeh step kyun? Tangent model ke saath slide karo jahan woh zero predict karta hai — yeh figure mein dashed jump hai.
5. Ek baar aur iterate karo: $(1.25,1.25)$ par, $\mathbf{F}=(1.5625+1.5625-1,0)=(2.125,0)$… iterate karte rehne se converge hota hai ${\mathbf{x}}^{\ast }=(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})\approx (0.7071,0.7071)$ par.

Verify: $x^{\ast 2}+y^{\ast 2}=0.5+0.5=1$ ✓ aur $y^{\ast }-x^{\ast }=0$ ✓. Hum positive (upper-right) intersection par land kiye — positive $x$ par start ne hamein wahan steered kiya (Cell B ki foreshadowing).

Cell B — do roots, start point choose karta hai

Same figure apply hoti hai: ab imagine karo white square $(-2,0)$ par left par rakha gaya hai; picture ki mirror symmetry se path lower-left yellow dot ki taraf slide karta hai.

Forecast: $x\to -x,y\to -y$ symmetry se, ab kaun sa root milega?

1. Residual. $\mathbf{F}=(4-1,0-(-2))=(3,2)$. Yeh step kyun? Pehle start plug karo — yeh bataata hai hum kitne off hain, aur yahan sirf doosra component sign flip karta hai Ex 1 ke comparison mein, jo mirror ka algebraic fingerprint hai.
2. Jacobian. $J=\left(\begin{array}{cc}-4& 0\\ -1& 1\end{array}\right)$, $\det =-4$. Yeh step kyun? Jacobian ko naye point $(-2,0)$ par re-evaluate karna padega — $J$ $\mathbf{x}$ par depend karta hai, isliye $2x=-4$ ab.
3. Step. Solve $J\Delta \mathbf{x}=(-3,-2)$: $\Delta \mathbf{x}=\frac{1}{-4}\left(\begin{array}{cc}1& 0\\ 1& -4\end{array}\right)\left(\begin{array}{c}-3\\ -2\end{array}\right)=\frac{1}{-4}\left(\begin{array}{c}-3\\ 5\end{array}\right)=(0.75,-1.25)$. Yeh step kyun? Step ke liye linear model solve karo — yeh Ex 1 ke step ka mirror nikalta hai, exactly jaisa picture ki symmetry ne promise kiya tha.
4. Update. ${\mathbf{x}}_1=(-1.25,-1.25)$ → converges to ${\mathbf{x}}^{\ast }=(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}})$. Yeh step kyun? Behtar guess ki taraf move karne ke liye step add karo; yeh lower-left dot ki taraf jaata hai.

Verify: $0.5+0.5=1$ ✓, equal coords ✓. Lesson (Cell B): Newton ek koi root dhundhta hai, jo is baat se decide hota hai ki start kaunse basin of attraction mein hai. Same equations, mirrored start, mirrored root.

Cell C — linear $\mathbf{F}$, one-step exact

Forecast: exact answer hit karne ke liye kitne Newton steps?

1. Jacobian. $J=\frac{\partial (A\mathbf{x}-\mathbf{b})}{\partial \mathbf{x}}=A$ — constant. Yeh step kyun? Ek linear map ka derivative woh map khud hai; koi $\mathbf{x}$ dependence nahi, isliye hum $J$ kabhi recompute nahi karte.
2. Residual at $0$. $\mathbf{F}=A0-\mathbf{b}=(-5,-10)$. Yeh step kyun? Evaluate karo start $A\mathbf{x}=\mathbf{b}$ solve karne se kitna door hai; origin par yeh sirf $-\mathbf{b}$ hai.
3. Step. Solve $A\Delta \mathbf{x}=(5,10)$. $\det A=5$, $A^{-1}=\frac{1}{5}\left(\begin{array}{cc}3& -1\\ -1& 2\end{array}\right)$: $\Delta \mathbf{x}=\frac{1}{5}\left(\begin{array}{cc}3& -1\\ -1& 2\end{array}\right)\left(\begin{array}{c}5\\ 10\end{array}\right)=\frac{1}{5}\left(\begin{array}{c}5\\ 15\end{array}\right)=(1,3)$. Yeh step kyun? Step ke liye linear model solve karo; kyunki model yahan exactly $\mathbf{F}$ ke barabar hai, yeh step hume ek shot mein true solution par le jaata hai.
4. Update. ${\mathbf{x}}_1=(1,3)$. Yeh step kyun? Start $(0,0)$ mein step add karo — directly answer par pahunch jaate hain.

Verify: $A(1,3{)}^{\top }=(2+3,1+9)=(5,10)=\mathbf{b}$ ✓. Residual ab exactly zero hai — koi rounding nahi, koi doosra step nahi. Lesson (Cell C): linear $\mathbf{F}$ par tangent model hi $\mathbf{F}$ hai, isliye ek step exact hai. Yeh aapka code ka sanity check hai (Fixed-point iteration contrast se: fixed-point crawl karta).

Cell D — singular Jacobian (curves tangent)

Pehle figure padho: pink line $y=1$ blue circle ko cross nahi karti — woh use ek single yellow dot $(0,1)$ par kiss karti hai. Kyunki do curves wahan ek tangent direction share karti hain, row-gradients parallel ho jaate hain aur $\det J\to 0$. White squares ki row dikhati hai ki $x$-coordinate $0.5\to 0.25\to 0.125$ crawl kar raha hai — halving, squaring nahi. Woh crawl ek singular Jacobian ka visible symptom hai.

Forecast: sach wala root $(0,1)$ hai. Root par $\det J$ kya hai — aur zero determinant hamari fast convergence ko kya karta hai?

1. Jacobian. $J=\left(\begin{array}{cc}2x& 2y\\ 0& 1\end{array}\right)$, $\det =2x$. Yeh step kyun? Har equation differentiate karo; root par $x^{\ast }=0$, isliye $\det J^{\ast }=0$ — singular. Geometrically dono curves wahan horizontal hain (tangent), figure mein "kiss" se match karta hai.
2. Start ${\mathbf{x}}_0=(0.5,1)$. $\mathbf{F}=(0.25+1-1,0)=(0.25,0)$, $J=\left(\begin{array}{cc}1& 2\\ 0& 1\end{array}\right)$, $\det =1$ (root se door theek hai). Yeh step kyun? Start par residual aur Jacobian evaluate karo; tangent point se door $\det$ abhi healthy hai, isliye pehla step well-defined hai.
3. Step. Solve $J\Delta \mathbf{x}=(-0.25,0)$: row 2 se, $\Delta y=0$; row 1 se, $\Delta x+2(0)=-0.25\Rightarrow \Delta x=-0.25$. Toh ${\mathbf{x}}_1=(0.25,1)$. Yeh step kyun? Step ke liye solve karo; dekho $x$-error $0.5\to 0.25$ — woh sirf halved hua, square nahi hua.
4. Agle: $\mathbf{F}=(0.0625,0)$, $\Delta x=-0.125$ → $x=0.125$. Errors $0.5,0.25,0.125,\dots$ — linear, ratio $\frac{1}{2}$.

Verify: predicted linear decay $x_{k+1}=x_k/2$: $0.5\to 0.25\to 0.125$ ✓. Lesson (Cell D): jab $J({\mathbf{x}}^{\ast })$ singular hota hai, Newton quadratic speed kho deta hai aur linearly creep karta hai — exactly wahi $n$-D echo hai ek scalar double root ka jahan $f^{\prime }=0$. Ek cure hai modified Newton ya equations ko dobara state karna.

Cell E — bad start → divergence, damping save karta hai

Forecast: near-flat gradient ka matlab hai tangent ramp almost horizontal hai — kya plain step overshoot karega?

1. Jacobian. $J=\left(\begin{array}{cc}2x& -1\\ 1& -1\end{array}\right)$, $\det =-2x+1$. ${\mathbf{x}}_0$ par: $\det =0.8$. Yeh step kyun? Hume har direction mein slope chahiye; chhota $2x=0.2$ warn karta hai ki model $x$ mein almost flat hai, jo step ko lamba banayega.
2. Residual. $\mathbf{F}=(0.01-0-3,0.1-0+1)=(-2.99,1.1)$. Yeh step kyun? Step lene se pehle measure karo hum kitne off hain.
3. Plain step. $J=\left(\begin{array}{cc}0.2& -1\\ 1& -1\end{array}\right)$. Solve $J\Delta \mathbf{x}=(2.99,-1.1)$. $J^{-1}=\frac{1}{0.8}\left(\begin{array}{cc}-1& 1\\ -1& 0.2\end{array}\right)$: $\Delta \mathbf{x}=\frac{1}{0.8}\left(\begin{array}{cc}-1& 1\\ -1& 0.2\end{array}\right)\left(\begin{array}{c}2.99\\ -1.1\end{array}\right)=\frac{1}{0.8}\left(\begin{array}{c}-4.09\\ -3.21\end{array}\right)=(-5.1125,-4.0125)$. Yeh step kyun? Near-flat linear model solve karne se ek bada jump milta hai ($\Vert \Delta \mathbf{x}\Vert \approx 6.5$) true root ke paas ke start se — ek classic overshoot warning.
4. Damp karo. $t=0.25$ lo: ${\mathbf{x}}_1={\mathbf{x}}_0+0.25\Delta \mathbf{x}=(0.1-1.278,0-1.003)=(-1.178,-1.003)$. Yeh step kyun? Damped Newton step ko tab tak chota karta hai jab tak $\Vert \mathbf{F}\Vert$ actually drop na kare, overshoot ko tame karta hai.

Verify (residual damping ke neeche sach mein shrinks karta hai): $\Vert \mathbf{F}({\mathbf{x}}_0)\Vert =\sqrt{2.99^2+1.1^2}=\sqrt{10.15}\approx 3.187$. Damped ${\mathbf{x}}_1=(-1.178,-1.003)$ par: $f_1=1.388-(-1.003)-3=-0.609$, $f_2=-1.178-(-1.003)+1=0.825$, $\Vert \mathbf{F}\Vert =\sqrt{0.371+0.681}=\sqrt{1.052}\approx 1.026<3.187$ ✓. Lesson (Cell E): Newton sirf locally convergent hai; step-length $t\in (0,1]$ jo residual decrease kare practical rescue hai. (Is system ke exact roots cleanly Ex 7 mein compute kiye gaye hain.)

Cell F — real-world word problem

Forecast: parallel mein do resistors ka equivalent resistance hamesha chhote resistor se neeche hota hai. Kyunki parallel value $2\Omega$ hai, chhota resistor $2\Omega$ se upar hona chahiye. Andaza lagao ki $y$ thoda upar $2$ se aayega ya nahi.

1. $\mathbf{F}$ banao (fraction saaf karo). $f_1=xy-2(x+y)=0$, $f_2=x-y-5=0$. Yeh step kyun? Multiply out karne se division remove hota hai taaki Jacobian entries polynomial aur well-defined rahe (units: ${\Omega }^2$ aur $\Omega$).
2. Jacobian. $J=\left(\begin{array}{cc}y-2& x-2\\ 1& -1\end{array}\right)$. Yeh step kyun? $f_1=xy-2x-2y$ differentiate karo toh ${\partial }_x=y-2,{\partial }_y=x-2$; row 2 linear equation ka constant gradient hai. Yahi matrix hai jiske against hum solve karte hain.
3. $(8,3)$ par. $\mathbf{F}=(24-22,8-3-5)=(2,0)$. $J=\left(\begin{array}{cc}1& 6\\ 1& -1\end{array}\right)$, $\det =-1-6=-7$. Yeh step kyun? Linear system form karne ke liye residual aur Jacobian guess par evaluate karo; $f_2$ already satisfied hai ($0$), isliye guess line $x-y=5$ par baith rahi hai.
4. Step. Solve $J\Delta \mathbf{x}=(-2,0)$: $J^{-1}=\frac{1}{-7}\left(\begin{array}{cc}-1& -6\\ -1& 1\end{array}\right)$, $\Delta \mathbf{x}=\frac{1}{-7}\left(\begin{array}{cc}-1& -6\\ -1& 1\end{array}\right)\left(\begin{array}{c}-2\\ 0\end{array}\right)=\frac{1}{-7}\left(\begin{array}{c}2\\ 2\end{array}\right)=(-0.2857,-0.2857)$. Yeh step kyun? Correction ke liye linear model solve karo; dono components saath neeche move karte hain, $x-y=5$ intact rakhte hue.
5. Update. ${\mathbf{x}}_1=(7.714,2.714)$. Yeh step kyun? Guess mein step add karo. Iterate karte rehne se neeche exact root par converge hota hai.

Exact root. $x=y+5$ substitute karo $f_1$ mein: $(y+5)y-2(y+5)-2y=0\Rightarrow y^2+y-10=0$, toh $y^{\ast }=\frac{-1+\sqrt{41}}{2}\approx 2.7016,x^{\ast }=y^{\ast }+5=\frac{9+\sqrt{41}}{2}\approx \mathrm{7.7016.}$

Verify: $x^{\ast }-y^{\ast }=5$ ✓ (difference construction se $5$ hai). Parallel: $\frac{7.7016\cdot 2.7016}{7.7016+2.7016}=\frac{20.807}{10.403}\approx 2.000\Omega$ ✓. Units consistent (sab $\Omega$). Hamara forecast sach nikla: chhota resistor $y^{\ast }\approx 2.70\Omega$ sach mein parallel value $2\Omega$ se upar hai, jaisa physics demand karta hai.

Cell G — exam twist: $\mathbf{F}$ mein ek linear equation chhupa hua

Forecast: pehle haath se do equations subtract karo — kya yeh secretly ek single quadratic hai?

1. Reduce karo. $f_2$ se: $y=x+1$. $f_1$ mein sub karo: $x^2-(x+1)-3=x^2-x-4=0$. Yeh step kyun? Exam twist yeh hai ki ek equation linear hai, isliye ek variable eliminate karna $2\times 2$ ko ek hand-solvable quadratic mein collapse kar deta hai — exact answer ke liye koi Jacobian nahi chahiye.
2. Exact roots. $x=\frac{1\pm \sqrt{17}}{2}$, toh $x^{\ast }\approx 2.5616$ ya $-1.5616$, $y^{\ast }=x^{\ast }+1$ ke saath. Yeh step kyun? Quadratic formula dono roots exactly deta hai; yeh hamaara ground truth hai iteration ke against test karne ke liye.
3. Newton check $(3,4)$ se. $\mathbf{F}=(9-4-3,3-4+1)=(2,0)$. $J=\left(\begin{array}{cc}6& -1\\ 1& -1\end{array}\right)$, $\det =-6+1=-5$. Solve $J\Delta \mathbf{x}=(-2,0)$: $\Delta \mathbf{x}=\frac{1}{-5}\left(\begin{array}{cc}-1& 1\\ -1& 6\end{array}\right)\left(\begin{array}{c}-2\\ 0\end{array}\right)=\frac{1}{-5}\left(\begin{array}{c}2\\ 2\end{array}\right)=(-0.4,-0.4)$. Yeh step kyun? Ek nearby start se ek Newton step run karo aur correction solve karo, dekho ki woh exact quadratic root ki taraf march karta hai.
4. Update. ${\mathbf{x}}_1=(2.6,3.6)$ — already true $(2.5616,3.5616)$ ke $0.04$ ke andar. Yeh step kyun? Step add karo; closeness confirm karti hai ki elimination answer aur iteration agree karte hain.

Verify: $x^{\ast 2}-x^{\ast }-4$ at $x^{\ast }=\frac{1+\sqrt{17}}{2}$ equals $0$ ✓ quadratic formula se. Aur $y^{\ast }-x^{\ast }=1$ ✓. Lesson (Cell G): hamesha ek linear component scan karo jo aap eliminate kar sako — yeh ek $2\times 2$ Newton ko ek hand-solvable quadratic mein badal deta hai aur aapko code ka root check karne deta hai.

Cell H — $n=3$: solve karo, invert nahi

Forecast: $3\times 3$ ke saath hum $J^{-1}$ form nahi karte. Hum forward-elimination karte hain. Andaza lagao kitne exact operations ek step mein lagte hain, given $f_1$ linear hai.

1. Jacobian. $J=\left(\begin{array}{ccc}1& 1& 1\\ 2x& 1& -1\\ 1& -2y& 1\end{array}\right)$. $(1,1,1)$ par: $J=\left(\begin{array}{ccc}1& 1& 1\\ 2& 1& -1\\ 1& -2& 1\end{array}\right)$. Yeh step kyun? Har row ek gradient hai; mixed signs $\pm z$ aur $-y^2$ terms se aate hain. Yahi matrix hai jis par hum eliminate karte hain.
2. Residual. $\mathbf{F}=(1+1+1-6,1+1-1,1-1+1+6)=(-3,1,7)$. Yeh step kyun? Har equation mein start plug karo right-hand side $-\mathbf{F}$ linear solve ke liye.
3. Gaussian elimination se $J\Delta \mathbf{x}=(3,-1,-7)$ solve karo. Augment $[J|3,-1,-7]$ aur column 1 eliminate karo: $R_2\leftarrow R_2-2R_1$: $(0,-1,-3|-7)$. $R_3\leftarrow R_3-R_1$: $(0,-3,0|-10)$. Column 2 eliminate karo, $R_3\leftarrow R_3-3R_2$: $(0,0,9|11)$ → $\Delta z=11/9$. Back-sub: $-\Delta y-3\Delta z=-7\Rightarrow \Delta y=7-3(11/9)=7-\frac{33}{9}=\frac{30}{9}=\frac{10}{3}$. $\Delta x=3-\Delta y-\Delta z=3-\frac{10}{3}-\frac{11}{9}=\frac{27-30-11}{9}=-\frac{14}{9}$. Yeh step kyun? Ek LU-style forward sweep + back-substitution $O(n^3/3)$ cost karta hai — $J^{-1}$ banana se sasta aur steadier (parent ka "Just Solve, Don't Invert").
4. Update. ${\mathbf{x}}_1=(1-\frac{14}{9},1+\frac{10}{3},1+\frac{11}{9})=(-\frac{5}{9},\frac{13}{3},\frac{20}{9})$. Yeh step kyun? Solved step add karo; yahan se iterate karne par true root $(1,2,3)$ par converge hota hai.

Verify (do cheezein). (a) Exact root: $f_1(1,2,3)=1+2+3-6=0$ ✓, $f_2=1+2-3=0$ ✓, $f_3=1-4+3+6=6$… toh in coefficients ke saath $f_3(1,2,3)=6\ne 0$. $(1,2,3)$ ko genuine root banane ke liye hum $f_3=x-y^2+z$ use karte hain ($+6$ drop karo); phir $1-4+3=0$ ✓. (b) Jo step humne solve kiya woh $J\Delta \mathbf{x}=-\mathbf{F}$ satisfy karta hai: row 1 $=-\frac{14}{9}+\frac{10}{3}+\frac{11}{9}=\frac{-14+30+11}{9}=\frac{27}{9}=3$ ✓; row 2 $=2(-\frac{14}{9})+\frac{10}{3}-\frac{11}{9}=\frac{-28+30-11}{9}=-1$ ✓; row 3 $=-\frac{14}{9}-2(\frac{10}{3})+\frac{11}{9}=\frac{-14-60+11}{9}=\frac{-63}{9}=-7$ ✓.

Cell I — ek system jiska koi solution nahi

Forecast: unit circle par ek point ka $x^2+y^2=1$ hai; doosre par yeh $4$ hona chahiye. Kya koi ek point dono satisfy kar sakta hai? Predict karo residual kya karta hai.

1. Contradiction pakdo. Subtract karo: $f_2-f_1=(x^2+y^2-4)-(x^2+y^2-1)=-3$. Yeh har $\mathbf{x}$ ke liye $-3$ hai — kabhi zero nahi. Yeh step kyun? Iterate karne se pehle ek algebraic combination dhundho jo constant ho; ek nonzero constant prove karta hai ki do equations inconsistent hain, isliye $\mathbf{F}=0$ ka koi solution nahi.
2. Newton's step kya karta hai. $J=\left(\begin{array}{cc}2x& 2y\\ 2x& 2y\end{array}\right)$ — do rows identical hain, isliye $\det J=0$ har jagah. Yeh step kyun? Dono equations ka same gradient hai (concentric circles radial direction share karti hain), $J$ ko har point par singular banata hai — aap literally $J\Delta \mathbf{x}=-\mathbf{F}$ ko unique step ke liye solve nahi kar sakte.
3. Consequence. Residual ka difference $-3$ par pinned rehta hai chahe aap kahan bhi jao: $\Vert \mathbf{F}\Vert$ ko $0$ tak drive nahi kiya ja sakta. Newton ya toh stall karta hai (singular $J$) ya, pseudo-inverse ke saath, bina residual vanish hue wander karta hai. Yeh step kyun? Yeh "koi root nahi" ka honest failure signature hai: residual ek positive value par floor out karta hai.

Verify: $f_2-f_1=-3$ identically ✓, aur do Jacobian rows equal hain isliye $\det J=0$ ✓. Lesson (Cell I): Newton assume karta hai ki ek root exist karta hai; jab curves kabhi nahi milti, koi step residual zero nahi kar sakta. Isse non-vanishing residual floor aur/ya persistently singular $J$ se detect karo — phir ruko aur model dobara examine karo, iterations burn mat karo.

Newton jahan update matrix har step recompute karne ki jagah approximate ki jaati hai woh Broyden's method hai — ek cost-saving cousin jo next deep dive ke kabil hai.

Flashcards