Solving nonlinear systems — Newton's method in n dimensions: Question bank

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

Definition Is page par use ki gayi Notation

$F : R^{n} \to R^{n}$ hamara system hai, component-by-component $F = (f_{1}, \dots, f_{n})$ likha gaya hai: har $f_{i} (x_{1}, \dots, x_{n})$ ek scalar equation hai, aur ek root $x^{*}$ unhe saare ek saath zero kar deta hai, $F (x^{*}) = 0$ .
$J (x)$ Jacobian matrix hai jo $x$ par evaluate ki gayi hai, entries ke saath $J_{ij} = \partial f_{i} / \partial x_{j}$ ; row $i$ $i$ -th component function ka gradient $\nabla f_{i}$ hai.
$Δ x_{k}$ iterate $x_{k}$ par Newton step hai, jo $J (x_{k}) Δ x_{k} = - F (x_{k})$ solve karta hai. Har quantity current iterate $x_{k}$ par evaluate hoti hai — arguments matter karte hain, isliye hum unhe rakhte hain.
$e_{k} := x_{k} - x^{*}$ step $k$ par error vector hai — current guess true root se kitni door hai.
$∥ \cdot ∥$ koi bhi fixed vector norm hai (jaise Euclidean length); neeche ke saare statements kisi bhi consistent choice ke liye hold karte hain — bas ek hi use karo poore time.
$t_{k} \in (0, 1]$ ek step-length (damping) factor hai: full step ki jagah hum sirf part-way move karte hain, $x_{k + 1} = x_{k} + t_{k} Δ x_{k}$ .
Quadratic-convergence bound hai $∥ e_{k + 1} ∥ \leq C ∥ e_{k} ∥^{2}$ , jahan $C$ concretely $C = \frac{1}{2} ∥ J (x^{*})^{- 1} ∥ \cdot L$ hai, jisme $L$ $x^{*}$ ke paas $J$ ka Lipschitz constant hai (Jacobian kitni tezi se change hota hai) aur $∥ J (x^{*})^{- 1} ∥$ measure karta hai ki $J$ singular se kitna door hai. Ye sirf root ke paas hold karta hai, jahan $J (x^{*})$ nonsingular hai taaki inverse exist kare.

Do tasveerein jo dhyan mein rakhni chahiye

Neeche ke saare traps do behaviors se jude hain. Jawab dene se pehle dono figures dekho.

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

Overshoot. Left side par $x_{k}$ par linear model (tangent ramp) ek achha guide hai aur full step root ke paas land karta hai. Right side par wohi full step overshoot karta hai kyunki true curve bend ho jaati hai — damping factor $t_{k}$ step ko trustworthy zone mein wapas chhota kar deta hai.

Basins of attraction. Newton kaun sa root reach karta hai ye start par wildly sensitive, fractal tarike se depend karta hai — isliye "nearest root tak converge karta hai" bilkul galat hai.

Sahi hai ya galat — justify karo

Newton step direction

Δ x_{k}

hamesha residual

∥ F ∥

ke liye "downhill" point karta hai.

Do counts par Galat. Pehla, Newton squared residual

ϕ = \frac{1}{2} ∥ F ∥^{2}

ka descent guarantee karta hai,

∥ F ∥

ka nahi. Iska gradient hai

\nabla ϕ = J^{⊤} F

, to Newton step ke along directional derivative hai

\nabla ϕ^{⊤} Δ x_{k} = (J^{⊤} F)^{⊤} (- J^{- 1} F) = - F^{⊤} F = - ∥ F ∥^{2} < 0

— genuinely downhill, lekin sirf tab jab

J

nonsingular ho taaki

Δ x_{k} = - J^{- 1} F

exist kare. Doosra, tab bhi ek full step overshoot kar sakta hai (s01 dekho), isliye damped Newton ise

t_{k}

se scale karta hai.

Agar

F

linear hai, to Newton kisi bhi start se exactly ek iteration mein converge karta hai.

Sahi. Tab

F (x) = A x - b

ek fixed matrix

A

aur constant vector

b

ke liye, to

J (x) = A

constant hai, linear model hi

F

hai, aur pehla solve exactly root

x^{*} = A^{- 1} b

par land karta hai.

Quadratic convergence ka matlab hai ki error har step mein square hoti hai chahe tum kahin se bhi start karo.

Galat. Bound

∥ e_{k + 1} ∥ \leq C ∥ e_{k} ∥^{2}

(jisme

e_{k} = x_{k} - x^{*}

aur

C = \frac{1}{2} ∥ J (x^{*})^{- 1} ∥ L

) local hai — ye tabhi kaam aata hai jab

x_{k}

itna close ho ki

C ∥ e_{k} ∥ < 1

; door se Newton crawl, cycle, ya diverge kar sakta hai.

Sirf

∥Δ x_{k} ∥

par stopping test kaafi hai.

Galat. Almost-singular

J (x_{k})

ke paas ek tiny step ho sakta hai jabki

∥ F (x_{k}) ∥

abhi bhi bada ho; tumhe residual

∥ F (x_{k}) ∥

bhi check karna chahiye ki wo chhota hai.

Newton's method ke liye

F

differentiable hona zaroori hai.

Sahi. Poora method first-order Taylor model

F (x_{k} + h) \approx F (x_{k}) + J (x_{k}) h

par bana hai; Jacobian ke bina koi linear model nahi hai solve karne ke liye.

Agar

J (x^{*})

singular hai, to Newton simply fail ho jaata hai aur kuch nahi produce karta.

Galat. Ye usually tab bhi converge karta hai, bas slower — rate quadratic se linear ho jaati hai (jaise scalar Newton double root par jahan

f^{'} = 0

Newton iteration ek special case hai Fixed-point iteration ka.

Sahi. Ye fixed-point map

g (x) = x - J (x)^{- 1} F (x)

hai; iska fast convergence is baat se aata hai ki us map ki derivative

x^{*}

par vanish ho jaati hai.

n

(unknowns) ko double karne se per-step cost roughly unchanged rehti hai.

Galat. Dominant cost linear solve hai,

O (n^{3} /3)

via LU decomposition, isliye

n

double karne se kaam lagbhag

8

guna ho jaata hai.

Newton hamesha starting point ke sabse nearest root tak converge karta hai.

Galat. Aisi koi guarantee nahi hai — Newton ke "basins of attraction" famously fractal hain (s02 dekho), to ek start ek door ke root tak jump kar sakta hai ya poori tarah diverge kar sakta hai.

Error dhundho

"Update karne ke liye,

J^{- 1}

compute karo phir

x_{k + 1} = x_{k} - J (x_{k})^{- 1} F (x_{k})

set karo."

J^{- 1}

explicitly form karna error hai. Solve karo

J (x_{k}) Δ x_{k} = - F (x_{k})

ek LU factorization se — invert karne se lagbhag

3 \times

sasta aur kaafi zyada stable.

"Jacobian ki rows column

j

ke gradients

\nabla f_{j}

hain."

Ulta ho gaya. Row

i

hai

\nabla f_{i}

(

i

-th component function ke partials); entry

J_{ij} = \partial f_{i} / \partial x_{j}

equation $i$ saare variables $j$ ke across run karta hai.

"Kyunki Newton quadratically converge karta hai, ek iteration kisi bhi tolerance ke liye kaafi hai."

Nahi — quadratic ka matlab hai correct digits ki sankhya double hoti hai per step, to fir bhi un digits ko build up karne ke liye kaafi steps chahiye (jaise

2 \to 4 \to 8 \to 16

"Hum

F (x_{k}) + J (x_{k}) h = F (x_{k + 1})

set karte hain aur solve karte hain."

Right-hand side

0

hona chahiye,

F (x_{k + 1})

nahi. Hum linear model ko zero hit karne ki demand karte hain, jisse

J (x_{k}) h = - F (x_{k})

milta hai.

"Broyden's method sirf Newton hai ek better convergence rate ke saath."

Ulta hai. Broyden refactorizing skip karne ke liye

J

ko approximate karta hai, Newton ki quadratic rate ke badle ek sasta superlinear rate lete hue — per step faster, lekin zyada steps.

"Ek bada residual

∥ F (x_{k}) ∥

matlab

x_{k}

root se door hai."

Zaroor nahi. Agar

J (x_{k})

ill-conditioned hai, ek small residual ek bade error

∥ e_{k} ∥

ko hide kar sakta hai aur vice-versa; residual aur error sirf loosely linked hain.

Why questions

Hum Taylor ko linear term ke baad truncate kyun karte hain, quadratic term rakhne ki jagah?

Sirf linear term rakhne se model ek solvable linear system

J (x_{k}) h = - F (x_{k})

ban jaata hai; quadratic term rakhne se hame solve karne ke liye ek aur nonlinear system milega — koi progress nahi.

O (∥ h ∥^{2})

remainder discard karne se quadratic convergence kyun milti hai?

Kyunki wo discarded remainder hi leftover error hai, aur ye

∥ h ∥^{2} \approx ∥ e_{k} ∥^{2}

(jahan

e_{k} = x_{k} - x^{*}

) ki tarah scale karta hai, isliye next error current error ke square ke proportional hai — wo proportionality factor constant

C = \frac{1}{2} ∥ J (x^{*})^{- 1} ∥ L

hai.

Fast convergence ke liye

J (x^{*})

nonsingular kyun hona chahiye?

Singular

J

ka koi unique step nahi hota (linear model kisi direction mein flat hai), isliye update direction blow up ho jaata hai ya undefined ho jaata hai — aur bound ka factor

∥ J (x^{*})^{- 1} ∥

infinite ho jaata. Ye scalar Newton ke stall hone jaisa hai jahan

f^{'} = 0

J

invert karne ki jagah linear system solve karna kyun prefer kiya jaata hai, jabki formula

J^{- 1}

dikhata hai?

Solving ke liye ek factorization aur back-substitution chahiye (

\approx n^{3} /3

flops); inverting lagbhag

3 \times

itna expensive hai aur rounding error amplify karta hai — formula mein

J^{- 1}

notation hai, instruction nahi.

Newton sirf locally convergent kyun kehlata hai?

Linear model sirf

x_{k}

ke paas trustworthy hai; root se door neglected higher-order terms dominate karte hain, isliye guarantee sirf

x^{*}

ke ek neighbourhood ke andar hold karti hai (exactly s01 mein dikhaya gaya overshoot risk).

Damped Newton kyun help karta hai jab full step overshoot karta hai?

Ek line-search step-length

t_{k} \in (0, 1]

step ko tab tak chhota karta hai jab tak squared residual

\frac{1}{2} ∥ F ∥^{2}

actually decrease na ho — jo Newton direction hamesha allow karta hai kyunki iska directional derivative

- ∥ F ∥^{2} < 0

hai — tumhe us region ke andar rakhta hai jahan linear model abhi bhi ek decent guide hai.

Newton ek linear

F

ko ek step mein solve kyun kar sakta hai lekin nonlinear ek nahi?

Linear

F

ke liye model ka discarded remainder zero hai, isliye pehla solve exact hai; nonlinear

F

ke liye remainder nonzero hai, isliye har step sirf approximate karta hai aur repeat karna padta hai.

Edge cases

Kya hoga agar tum exactly root par start karo,

x_{0} = x^{*}

Tab

F (x_{0}) = 0

, isliye

Δ x_{0} = 0

aur tum wahi rahte ho — method recognize karta hai ki ye already done hai.

Agar

J (x_{k})

mid-iteration singular ho jaaye (root par nahi)?

Solve

J (x_{k}) Δ x_{k} = - F (x_{k})

ka koi unique solution nahi hoga; method break down kar deta hai aur fix chahiye (perturb karo

x_{k}

, regularisation add karo, ya globalised variant par switch karo).

Agar do roots bahut paas paas hoon?

Unke basins finely interleave karte hain (s02 ka extreme version), isliye same

x_{0}

tiny perturbations ke under roots ke beech flip kar sakta hai, aur convergence slow ho sakti hai kyunki

J

unke beech chhota hai.

Agar

F

ka koi real root hi nahi hai?

Newton ek aise root tak converge nahi kar sakta jo exist hi nahi karta; iterates typically diverge, wander, ya cycle karte hain — ek residual

∥ F ∥

jo kabhi zero ke paas nahi aata wo tell hai.

Agar

n = 1

ho?

Sab kuch scalar Newton's method (1-D) mein collapse ho jaata hai:

J (x_{k})

single number

f^{'} (x_{k})

ban jaata hai aur solve division

x_{k + 1} = x_{k} - f (x_{k}) / f^{'} (x_{k})

ban jaata hai.

Agar root ek poori curve of solutions ho (infinitely many roots)?

Tab

J

us set ke along singular hai (koi direction

F

ko unchanged chhod deti hai), isliye quadratic convergence lost ho jaati hai aur Newton ek point pin karne ki jagah solution manifold ke along drift kar sakta hai.

Recall Ek-line self-test

Ek sentence jo yahan ke zyaadatar traps se bachata hai ::: "Linear model $J (x_{k}) Δ x_{k} = - F (x_{k})$ sirf linear $F$ ke liye exact hai aur sirf $x_{k}$ ke paas trustworthy hai — Newton jo kuch karta hai (aur karne mein fail hota hai) sab usi se follow karta hai."