LU decomposition — algorithm, applications: Question bank

4.5.26 · D5 · Maths › Linear Algebra (Full) › LU decomposition — algorithm, applications

Yeh bank LU decomposition — algorithm, applications ko support karta hai aur Gaussian Elimination, Permutation Matrices, Determinants, Matrix Inverse, Cholesky Decomposition, aur Triangular Systems & Substitution se link karta hai. Jo kuch bhi tumhe chahiye woh yahan defined hai — tumhe is page ko chhodna nahi chahiye.

Pehle ek picture-based refresher (traps se pehle padho)

Figure — LU decomposition — algorithm, applications

Definition Is page ke terms (doosre notes pe jaane ki zaroorat nahi)

Pivot: diagonal entry $a_{k k}$ (pehle ke steps ke baad) jisse tum neeche ka column clear karne ke liye divide karte ho.
Multiplier: $m_{ik} = a_{ik} / a_{k k}$ , "row $i$ se kitni pivot-rows subtract karni hain". Ye $L$ ke below-diagonal entries ban jaate hain.
Leading principal submatrix of order $k$ : $A$ ka top-left $k \times k$ block (rows $1.. k$ , columns $1.. k$ ). Iska picture corner mein shrinking square hai (agla figure dekho). Plain $A = LU$ exactly tab exist karta hai jab har aisa block, $k = 1, \dots, n$ ke liye, nonsingular ho (nonzero determinant).
Partial pivoting: har step pe current column mein largest-magnitude entry wali row swap karo, aur swap ko ek permutation matrix $P$ mein record karo, jisse $P A = LU$ milta hai. Sirf rows move karti hain.
Full (complete) pivoting: pivot ke liye remaining block mein kahin bhi sabse badi entry laane ke liye ek row aur ek column dono swap karo — do permutations ke saath $P A Q = LU$ ke roop mein record hota hai. Zyada stable hai, par cost rarely worth it hoti hai.

True ya false — justify karo

Setup yaad raho: $A = LU$ ka matlab hai $L$ unit lower triangular hai (diagonal pe 1's, upar zeros) aur $U$ upper triangular hai (diagonal ke neeche zeros). Har claim judge karo, phir reveal karo.

L

ke diagonal entries koi bhi nonzero numbers ho sakte hain

False — standard (Doolittle) LU mein

L

ki diagonal forced hoti hai ki sab 1's hon; wahi 1's hain jo ek diye gaye

A

ke liye factorisation ko unique banati hain.

U

ke diagonal pe hamesha Gaussian elimination ke pivots hote hain

True — har column clear karne par pivot diagonal pe untouched rehta hai, isliye

u_{ii}

i

-th pivot hai.

Har square matrix ka

A = LU

factorisation bina kisi row swap ke hota hai

False — agar ek pivot position zero pe hit kare (jaise

a_{11} = 0

), to plain

A = LU

break ho jaata hai; tumhe permutation

P

ke saath

P A = LU

chahiye.

Agar

A

invertible hai to

A = LU

(bina permutation ke) guaranteed hai

False — invertibility kaafi nahi hai; tumhe yeh bhi chahiye ki har leading principal submatrix (har top-left

k \times k

block) nonsingular ho.

(0110)

invertible hai lekin uska

1 \times 1

block

0

hai, isliye iska plain LU nahi hai.

det A

barabar hai

L

ke diagonal entries ka product times

U

ke diagonal entries ka product

True lekin trivial —

det L = 1

(1's ka product), isliye

det A = \prod_{i} u_{ii}

, pivots ka product.

Pivoting ke dauran do rows swap karna kabhi

det A

ki value nahi badalta

False — har row swap determinant ko

- 1

se multiply karta hai, isliye

det A = (- 1)^{# swaps} \prod_{i} u_{ii}

Lower- aur upper-triangular matrix ka product

LU

hamesha triangular hota hai

False — woh product generally ek full matrix hota hai (yahi poori baat hai:

LU

dense

A

ko rebuild karta hai). Sirf

L \cdot L^{'}

U \cdot U^{'}

triangular rehta hai.

Ek symmetric positive-definite matrix ke liye,

L

aur

U

koi shared information nahi rakhte

False — SPD matrices ke liye

U = D L^{⊤}

ek diagonal

D

ke liye, jo exactly Cholesky factorisation

A = L L^{⊤}

hai scaling tak;

U

essentially

L

ka transpose hai.

Ek diye gaye

A

ki LU factorisation (ek baar jab tum "

L

ki diagonal pe 1's" fix kar do) unique hoti hai

True —

L

ki diagonal 1's pe pin hone aur saare pivots nonzero hone ke saath,

L

aur

U

uniquely determined hain.

Sirf square matrices ko LU-factorise kiya ja sakta hai

False — rectangular

A

bhi factor hota hai, trapezoidal

L

U

ke saath; isliye least-squares problems LU (ya

A^{⊤} A

ke Cholesky) par lean kar sakti hain.

Error dhundho

Har line ek plausible-sounding move batati hai. Flaw dhundho.

A x = b

solve karne ke liye, pehle

L y = b

back-solve karo, phir

U x = y

forward-solve karo."

Ulta hai —

L

lower triangular hai isliye isko forward substitution chahiye;

U

upper triangular hai isliye isko back substitution chahiye. Naam se pata chalta hai ki pehle kaun sa corner known hai.

"Mere paas

A = LU

hai, isliye

A x = b

solve karne ke liye main

L

aur

U

invert karta hoon aur

U^{- 1} L^{- 1} b

compute karta hoon."

Symbols mein sahi hai lekin do fronts pe self-defeating — inverses banana

O (n^{3})

cost karta hai (speed win barbad ho jaata hai), aur ek explicit inverse round-off spread aur amplify karta hai:

A^{- 1}

se multiply karna input error ko

A

ke condition number se magnify karta hai, jabki triangular substitution us growth ko bahut kam rakhti hai. Kabhi invert mat karo; substitute karo.

"Multiplier hai

m_{ik} = a_{ik} / a_{ii}

Wrong index — tum pivot

a_{k k}

se divide karte ho (jo column clear ho raha hai uska diagonal entry),

a_{ii}

se nahi:

m_{ik} = a_{ik} / a_{k k}

L

mein

- m_{ik}

store hota hai kyunki elimination ek row ka

m_{ik}

times subtract karta hai."

Wrong sign — elimination matrix mein

- m_{ik}

hota hai, lekin

L

iska inverse hai, jo sign wapas flip kar ke

+ m_{ik}

bana deta hai.

L

multipliers ko plus ke saath store karta hai.

"Jab ek pivot exactly zero ho to mujhe bas usme ek tiny

ε

add karni chahiye aur aage badhna chahiye."

Dangerous — near-zero pivot se divide karna kisi multiplier

m_{ik} = a_{ik} / ε

ko enormous bana deta hai, aur woh huge factor baad ki har entry mein magnified round-off inject karta hai. Sahi fix hai partial pivoting (ek row swap

P

mein record hua), jo exact aur free hai.

"Kyunki

det A = \prod u_{ii}

hai, ek zero pivot matlab maine galat algorithm choose kiya."

Nahi — ek singular

A

ke liye mid-elimination zero pivot honest information hai:

det A = 0

. Algorithm sahi hai; matrix ka simply koi inverse nahi hai.

"Partial pivoting answer

x

badal deta hai, isliye jab possible ho avoid karo."

False —

A

aur

b

ki rows ko saath permute karna wohi solution

x

deta hai; sirf numerical rounding path badalta hai, aur better ke liye.

"Ek baar factor karne ke baad, ek naye

b

ke saath solve karne ke liye Gaussian elimination dobara chalani padti hai."

Yeh LU ka purpose hi defeat kar deta hai — elimination (woh

O (n^{3})

kaam) already

L, U

mein bake ho chuka hai. Ek naye

b

ko sirf do

O (n^{2})

substitutions chahiye.

Why questions

Hum sirf row-reduced

U

store karne ki jagah

L

aur

U

dono kyun rakhte hain?

U

akela record kho deta hai ki tum wahan kaise pahunche;

L

multipliers rakhta hai, jisse tum kisi bhi naye

b

ke liye

L y = b

ke through elimination re-apply kar sakte ho bina reduction dobara kiye.

"Top-down, left-to-right" eliminate karna hume multipliers ko

L

mein bina extra kaam ke seedha likhne kyun deta hai?

Kyunki baad ke har elimination step ke columns pehle wale se right ki taraf hain, ya rows neeche hain — inverse elementary matrices overlap nahi karte, isliye unka product bas har

m_{ik}

ko slot

(i, k)

mein deposit kar deta hai.

L

ki diagonal 1's kyun hoti hain, pivots kyun nahi?

Har elimination step pivot row ko unscaled chhodta hai (hum usme multiples subtract karte hain, use kabhi rescale nahi karte), isliye corresponding elementary matrices — aur unka product

L

— diagonal pe 1's rakhte hain. Pivots

U

mein rehte hain.

Systems solve karne ke liye LU decomposition ko explicitly

A^{- 1}

compute karne ke upar kyun prefer kiya jaata hai?

A^{- 1}

banana zyada arithmetic aur numerically worse hai — ek explicit inverse se multiply karna error ko

A

ke condition number se amplify karta hai, jabki triangular solves tighter rehte hain. LU cheaply aur zyada accurately solve karta hai.

Partial pivoting naye pivot ke liye sabse badi candidate entry kyun choose karta hai?

a_{ik}

ko largest available entry se divide karna har multiplier ko

∣ m_{ik} ∣ \leq 1

force karta hai; chhote multipliers existing round-off ko blow up nahi kar sakte, isliye accumulated error (aur solve ki effective conditioning) controlled rehti hai — yeh stability ke baare mein hai, correctness ke nahi.

Hum

det A

seedha pivots se kyun padh sakte hain?

Triangular determinants bas diagonal products hote hain, aur

det (LU) = det L \cdot det U = 1 \cdot \prod u_{ii}

; elimination is tarah engineered hai ki pivots us product ke barabar hon (har swap ke liye

- 1

se adjust ho ke).

Bahut saare right-hand sides hone se LU repeated Gaussian elimination se itna sasta kyun ho jaata hai?

Expensive factorisation (

\approx \frac{2}{3} n^{3}

) ek baar hoti hai; har extra

b

ke liye do substitutions

\approx n^{2}

each mein hoti hain, isliye

k

solves ki cost

\frac{2}{3} n^{3} + k \cdot O (n^{2})

hoti hai,

k \cdot O (n^{3})

ki jagah.

Least-squares problems LU ya Cholesky kyun use karte hain jabki

A

rectangular hai?

Tum tall

A

ko directly solve karne ke liye factor nahi karte; tum square symmetric positive-definite

A^{⊤} A

banate ho aur us ko LU- (ya Cholesky-) factor karte ho taaki normal equations

A^{⊤} A x = A^{⊤} b

solve ho sakein.

Edge cases

A

ki har diagonal nonzero hai — kya yeh guarantee karta hai ki koi permutation nahi chahiye?

Nahi — ek pivot mid-elimination zero ho sakta hai even jab original diagonal theek ho, kyunki baad ki entries update hoti hain. Sirf running pivots matter karte hain.

Ek matrix jo already upper triangular hai uska LU factorisation kya hoga?

L = I

(koi elimination nahi chahiye, saare multipliers 0 hain) aur

U = A

. Identity degenerate unit-lower-triangular matrix hai.

Jab

A

already lower triangular ho (diagonal nahi) to

L

aur

U

kya honge?

Diagonal ke upar elimination kuch nahi karta (woh entries already 0 hain), isliye

U

diagonal nikalta hai,

A

ke diagonal entries hold karta hai, aur

L

barabar hai

A

ke har column ko uske diagonal pivot se divide karne ke (isliye

L

ki diagonal 1's ban jaati hai). Concretely

A = LU

ke saath

U = diag (a_{11}, \dots, a_{nn})

aur

ℓ_{ik} = a_{ik} / a_{k k}

. Sirf jab

A

diagonal ho to ye

L = I, U = A

mein collapse ho jaate hain.

Kya ek singular matrix kabhi valid

A = LU

rakh sakti hai?

Haan — zero ek late pivot ke roop mein appear ho sakta hai (

u_{nn} = 0

) jabki earlier pivots theek hain, ek legitimate

LU

deta hai jisme

det A = \prod u_{ii} = 0

ho. Isko sirf ek unique

x

solve karne ke liye use nahi kiya ja sakta.

Agar

U

ki diagonal pe zero ho to do substitutions ka kya hoga?

Back-substitution us zero pivot par division se takrata hai — signal deta hai ki

A

singular hai, isliye ya to koi solution nahi hai ya infinitely many hain.

1 \times 1

matrix

A = (a)

ke liye

a \neq = 0

ke saath,

L

aur

U

kya hain?

L = (1)

aur

U = (a)

— unit-diagonal convention

L

ki single entry ko 1 pe force karta hai, isliye akela pivot

a

U

mein baithta hai.

Ek tall

3 \times 2

matrix ke liye,

L

aur

U

ke shapes kya hain?

L

3 \times 2

unit-lower-trapezoidal hai (apne do diagonal spots pe 1's ke saath) aur

U

2 \times 2

upper triangular hai —

m \geq n

ke saath general rectangular case.

Agar

A

symmetric hai lekin positive-definite nahi hai, to kya hum phir bhi LU ki jagah Cholesky use kar sakte hain?

Safely nahi — Cholesky (

A = L L^{⊤}

) ko positive pivots chahiye (woh unhe square root karta hai); positive-definiteness ke bina ek pivot negative ya zero ho sakta hai aur square root fail ho jaata hai, isliye tum pivoting ke saath LU pe fall back karte ho.

Agar

A

mein poora zero column ho, to elimination kya reveal karta hai?

Us column mein pivot 0 hai aur kisi bhi row swap se fix nahi ho sakta (poora column zero hai), isliye

A

singular hai — koi unique

LU

solve exist nahi karta,

det A = 0

se match karta hai.

Recall Ek-line takeaways

$L$ lower hai ⇒ forward-solve. $U$ upper hai ⇒ back-solve. $L$ $+ m_{ik}$ store karta hai apni diagonal pe 1's ke saath, $U$ pivots store karta hai. Zero pivot ka matlab permute karo (agar fixable ho) ya singular hai (agar nahi). Rectangular $A$ phir bhi factor hota hai — trapezoidal $L$ ya $U$ — $A^{⊤} A$ ke through least-squares ko power karta hai.