Solving nonlinear systems — Newton's method in n dimensions

4.8.29 · Maths › Numerical Methods

HUM KYA solve kar rahe hain?

Scalar Newton method $x_{k+1}=x_k-f(x_k)/f^{\prime }(x_k)$ ka $n=1$ wala case hai. Sirf ek conceptual upgrade: derivative $f^{\prime }$ ek matrix (Jacobian) ban jaati hai, aur "$f^{\prime }$ se divide karo" ka matlab ho jaata hai "ek linear system solve karo."

KAISE — first principles se derivation

Step 1 — Linearize karo. Current guess ${\mathbf{x}}_k$ lo aur har component $f_i$ ka first-order Taylor expansion ${\mathbf{x}}_k$ ke around likho: $f_i({\mathbf{x}}_k+\mathbf{h})\approx f_i({\mathbf{x}}_k)+{\sum }_{j=1}^n\frac{\partial f_i}{\partial x_j}({\mathbf{x}}_k)h_j.$ Yeh step kyun? Multivariable Taylor's theorem kehta hai ki kisi point ke paas ek smooth function apni value plus displacement ke saath gradient ka dot product equals hoti hai, plus higher order terms. Hum linear term ke baad truncate karte hain — yahi approximation problem ko solvable banati hai.

Step 2 — Matrix form mein stack karo. Saare $n$ rows collect karo. Partials ki matrix Jacobian hai: $J(\mathbf{x})=\left(\begin{array}{ccc}\frac{\partial f_1}{\partial x_1}& \cdots & \frac{\partial f_1}{\partial x_n}\\ ⋮& \ddots & ⋮\\ \frac{\partial f_n}{\partial x_1}& \cdots & \frac{\partial f_n}{\partial x_n}\end{array}\right),J_{ij}=\frac{\partial f_i}{\partial x_j}.$ Toh $\mathbf{F}({\mathbf{x}}_k+\mathbf{h})\approx \mathbf{F}({\mathbf{x}}_k)+J({\mathbf{x}}_k)\mathbf{h}$. Yeh step kyun? Jacobian, $\mathbf{F}$ ko ${\mathbf{x}}_k$ par approximate karne wali best linear map hai — yeh derivative $f^{\prime }$ ka $n$-D analogue hai.

Step 3 — Linear model ko zero pe lao. Hum chahte hain $\mathbf{F}({\mathbf{x}}_k+\mathbf{h})=0$. Approximation ko zero set karo: $\mathbf{F}({\mathbf{x}}_k)+J({\mathbf{x}}_k)\mathbf{h}=0⟹J({\mathbf{x}}_k)\mathbf{h}=-\mathbf{F}({\mathbf{x}}_k).$ Yeh step kyun? Ab yeh ek linear system $A\mathbf{h}=\mathbf{b}$ hai — exactly woh type jise hum LU/Gaussian elimination se solve kar sakte hain.

Step 4 — Solve karo aur update karo.

ITNA fast kyun converge karta hai

Reason: humne linear term rakha aur $O(\Vert \mathbf{h}{\Vert }^2)$ remainder phenk diya. Toh naya error us bache hue quadratic term se govern hota hai: $\Vert {\mathbf{e}}_{k+1}\Vert \le C\Vert {\mathbf{e}}_k{\Vert }^2,$ bas tab jab (1) ${\mathbf{x}}_0$, ${\mathbf{x}}^{\ast }$ ke kafi paas ho, aur (2) $J({\mathbf{x}}^{\ast })$ nonsingular (invertible) ho. Agar $J$ root par singular hai, toh convergence slow ho jaati hai — waise hi jaise scalar Newton double root par creep karta hai jahan $f^{\prime }=0$.

Worked Example 1 — circle ∩ parabola ($n=2$)

Solve karo $f_1=x^2+y^2-4=0,f_2=y-x^2=0.$

Jacobian. $J=\left(\begin{array}{cc}2x& 2y\\ -2x& 1\end{array}\right).$ Yeh step kyun? Har $f_i$ ko har variable ke w.r.t. differentiate karo; row $i$ hai $\nabla f_i$.

Start ${\mathbf{x}}_0=(1,2)$.

• $\mathbf{F}=(1+4-4,2-1)=(1,1)$. Kyun? Bas plug in karo; batata hai hum zero se kitna door hain.
• $J=\left(\begin{array}{cc}2& 4\\ -2& 1\end{array}\right)$, $\det =2+8=10$.
• $J\Delta \mathbf{x}=-\mathbf{F}=(-1,-1)$ solve karo: $\Delta \mathbf{x}=\frac{1}{10}\left(\begin{array}{cc}1& -4\\ 2& 2\end{array}\right)\left(\begin{array}{c}-1\\ -1\end{array}\right)=\frac{1}{10}\left(\begin{array}{c}3\\ -4\end{array}\right)=(0.3,-0.4).$ Yeh step kyun? $2\times 2$ ke liye, $J^{-1}=\frac{1}{\det }\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$; $-\mathbf{F}$ se multiply karo.
• ${\mathbf{x}}_1=(1.3,1.6)$.

Agla ${\mathbf{x}}_1=(1.3,1.6)$: $\mathbf{F}=(1.69+2.56-4,1.6-1.69)=(0.25,-0.09)$ — pehle se kaafi chhota. Iterate karte rahe toh converge hoga ${\mathbf{x}}^{\ast }\approx (1.2496,1.5616)$ par. Kyun chhota hua: linear model root ke paas accurate tha.

Worked Example 2 — linear case check karna

Linear system $\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right)\mathbf{x}=\left(\begin{array}{c}5\\ 6\end{array}\right)$ solve karo, yaani $\mathbf{F}(\mathbf{x})=A\mathbf{x}-\mathbf{b}$.

• $J=A$ (constant!). Kyun? $\partial (A\mathbf{x}-\mathbf{b})/\partial \mathbf{x}=A$.
• Kisi bhi ${\mathbf{x}}_0$ se: $\Delta \mathbf{x}=-A^{-1}(A{\mathbf{x}}_0-\mathbf{b})=A^{-1}\mathbf{b}-{\mathbf{x}}_0$, toh ${\mathbf{x}}_1=A^{-1}\mathbf{b}$ — ek step mein exact.
• Yeh kyun important hai: Newton linear systems ek hi iteration mein solve kar leta hai. Yeh ek sanity-check hai (Forecast-then-verify): agar tumhara code linear $\mathbf{F}$ par kai steps le raha hai, toh tumhara Jacobian galat hai.

Algorithm (pseudo)

given F, J, x0, tol
for k = 0,1,2,...
    compute F(xk), J(xk)
    solve  J(xk) Δx = -F(xk)        # LU, NOT inverse
    xk+1 = xk + Δx
    if ||F(xk+1)|| < tol and ||Δx|| < tol: stop

Flashcards

Connections

• Newton's method (1-D) — $n=1$ special case; same logic with $f^{\prime }$ instead of $J$.
• Jacobian matrix — multivariable derivative jo linearization ko power deti hai.
• Taylor's theorem (multivariable) — linear model ka source.
• LU decomposition / Gaussian elimination — har step ka linear solve aise hota hai.
• Fixed-point iteration — Newton as a fixed-point map $\mathbf{g}(\mathbf{x})=\mathbf{x}-J^{-1}\mathbf{F}$.
• Broyden's method — quasi-Newton: $J$ approximate karo taaki derivatives recompute na karni padein.
• Convergence order of iterative methods — linear/quadratic rates define karta hai.

Concept Map