The scalar Newton method xk+1=xk−f(xk)/f′(xk) is the n=1 case. The only conceptual upgrade: the derivative f′ becomes a matrix (the Jacobian), and "divide by f′" becomes "solve a linear system."
Step 1 — Linearize. Take a current guess xk and write the first-order Taylor expansion of each component fi around xk:
fi(xk+h)≈fi(xk)+∑j=1n∂xj∂fi(xk)hj.Why this step? Multivariable Taylor's theorem says a smooth function near a point equals its value plus its gradient dotted with the displacement, plus higher order. We truncate after the linear term — that's the approximation that makes the problem solvable.
Step 2 — Stack into matrix form. Collect all n rows. The matrix of partials is the Jacobian:
J(x)=∂x1∂f1⋮∂x1∂fn⋯⋱⋯∂xn∂f1⋮∂xn∂fn,Jij=∂xj∂fi.
So F(xk+h)≈F(xk)+J(xk)h.
Why this step? The Jacobian is the n-D analogue of the derivative f′: it is the best linear map approximating F at xk.
Step 3 — Demand the linear model hits zero. We wantF(xk+h)=0. Set the approximation to zero:
F(xk)+J(xk)h=0⟹J(xk)h=−F(xk).Why this step? This is now a linear system Ah=b — exactly the kind we can solve with LU/Gaussian elimination.
Reason: we kept the linear term and threw away the O(∥h∥2) remainder. So the new error is governed by that leftover quadratic term:
∥ek+1∥≤C∥ek∥2,provided (1) x0 is close enough to x∗, and (2) J(x∗) is nonsingular (invertible). If J is singular at the root, convergence degrades — same way scalar Newton crawls at a double root where f′=0.
Jacobian.J=(2x−2x2y1).Why this step? Differentiate each fi w.r.t. each variable; row i is ∇fi.
Startx0=(1,2).
F=(1+4−4,2−1)=(1,1). Why? Just plug in; tells us how far from zero we are.
J=(2−241), det=2+8=10.
Solve JΔx=−F=(−1,−1):
Δx=101(12−42)(−1−1)=101(3−4)=(0.3,−0.4).Why this step? For 2×2, J−1=det1(d−c−ba); multiply by −F.
x1=(1.3,1.6).
Nextx1=(1.3,1.6): F=(1.69+2.56−4,1.6−1.69)=(0.25,−0.09) — already much smaller. Iterating converges to x∗≈(1.2496,1.5616). Why it shrank: the linear model was accurate near the root.
Solve the linear system (1324)x=(56), i.e. F(x)=Ax−b.
J=A (constant!). Why?∂(Ax−b)/∂x=A.
From any x0: Δx=−A−1(Ax0−b)=A−1b−x0, so x1=A−1b — exact in one step.
Why this matters: Newton solves linear systems in a single iteration. This is a sanity-check (Forecast-then-verify): if your code needs many steps on a linear F, your Jacobian is wrong.
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
Recall Feynman: explain to a 12-year-old
Imagine you're blindfolded on a bumpy hill and want the lowest valley point where the ground is flat. You feel the slope under your feet (that's the Jacobian — slope in every direction at once). You pretend the hill is a flat ramp with that slope, slide straight to where that ramp would hit the bottom, and take one step there. The hill isn't really flat, so you're not exactly right — but you're much closer. Feel the slope again, slide again. Each guess is way better than the last, and soon you're standing right on the spot.
Dekho, ek nonlinear system F(x)=0 solve karna seedha mushkil hai kyunki equations curved hote hain. Newton ka idea simple hai: kisi bhi smooth function ko apne current guess ke paas dekho toh woh ek straight (linear) map jaisa lagta hai. Toh hum curve ko uske tangent se replace karte hain, aur tangent ko zero karna toh ek linear system solve karna hai — jo hume aata hai (LU/Gaussian elimination se).
1-D wale Newton mein humne f′ se divide kiya tha. n-D mein f′ ki jagah Jacobian matrixJ aa jaati hai (har fi ka har variable ke saath partial derivative). Step nikalne ke liye hum JΔx=−F ko solve karte hain, phir xk+1=xk+Δx. Yaad rakhna: kabhi bhi J−1 literally mat banao — solve karna sasta aur stable hota hai.
Sabse mast baat: convergence quadratic hota hai, matlab har step mein sahi digits roughly double ho jaate hain — 10−2→10−4→10−8. Par yeh tabhi hota hai jab starting guess x0 root ke paas ho aur J singular na ho. Agar guess door hai ya J flat hai, Newton diverge ya cycle kar sakta hai — tab damped Newton (chhota step tk with line search) lagao.
Exam tip / sanity check: agar F linear hai (yaani Ax−b), toh Newton sirf ek hi step mein exact answer de dega, kyunki J=A constant hai aur linear model bilkul exact hai. Agar tumhare code ko linear case mein bhi bahut iterations lag rahe hain, toh samajh jao Jacobian galat hai.
