LU decomposition (numerical): Question bank — Hinglish deep dive

4.8.19 · D5 · Maths › Numerical Methods › LU decomposition (numerical)

Vocabulary ka reminder jo aapko chahiye (sab parent note mein build hua hai): $A = LU$ matlab hum ek square matrix ko split karte hain ek lower-triangular $L$ (diagonal ke upar sirf zeros) aur ek upper-triangular $U$ (diagonal ke neeche sirf zeros) ke product mein. Doolittle convention mein $L$ ki diagonal par $1$ 's hote hain. $L$ ke diagonal ke neeche ke entries ko == $ℓ_{ij}$ == likha jaata hai (row $i$ , column $j$ , jahan $i > j$ ) — yeh elimination multipliers hain, yaani humne ek upar wali row ka kitna part subtract kiya taaki entry $(i, j)$ zero ho jaaye. Pivots woh hain jo $U$ ke diagonal entries $u_{j j}$ hain. Partial pivoting (Partial Pivoting) rows ko reorder karta hai ek permutation matrix $P$ (Permutation Matrices) ke zariye, jisse $P A = LU$ milta hai.

Agla picture woh asli engine dikhata hai jo Doolittle ordering ke peeche hai — kyun row of $U$ solve karo, phir column of $L$ , repeat karne par kabhi bhi ek saath do unknowns nahi milte. Orange highlight follow karo: har nayi equation mein exactly ek aisa entry hota hai jo aapko abhi tak pata nahi.

True or false — justify

Kya kisi bhi invertible square

A

ke liye

A = LU

bina kisi row swap ke hamesha possible hai?

False — ek leading principal submatrix (ek top-left square block) singular ho sakta hai, jo ek zero pivot force karta hai aur factorization tod deta hai chahe

A

khud invertible ho;

P A = LU

(swaps ke saath) hamesha exist karta hai.

Doolittle form mein, kya kisi matrix ka LU factorization jab exist karta hai toh unique hota hai?

True —

L

ki diagonal ko saare

1

's fix karne se

L

aur

U

ke beech wali ek scaling freedom hat jaati hai, isliye entries forced aur unique hain.

True or false: agar

A

symmetric hai, toh Doolittle factorization mein automatically

L = U^{⊤}

hoga.

False — Doolittle

L

ki diagonal par

1

's force karta hai, isliye generally

L \neq = U^{⊤}

; symmetric analogue hai Cholesky Decomposition

A = L L^{⊤}

, jiske liye

A

symmetric positive-definite hona zaroori hai.

Kya yeh sach hai ki har LU decomposition mein

det L = 1

hota hai?

Sirf Doolittle convention mein —

L

ki diagonal par

1

's hone se uska diagonal-product determinant

1

hota hai; Crout Decomposition mein

1

U

par hote hain, isliye wahan

det U = 1

hota hai.

True or false: ek lower-triangular aur upper-triangular matrix ka product hamesha triangular hota hai.

False — product

LU

generally har entry fill kar deta hai; yahi reason hai ki

A

(ek full matrix)

LU

ke barabar ho sakta hai.

Kya yeh sach hai ki partial pivoting kis matrix ko factor karte hain yeh badal sakta hai lekin final solution

x

kabhi nahi badalta?

True —

A

ki rows aur

b

ki matching entries ko swap karna sirf equations ko reorder karna hai, jo solution set ko kabhi nahi badalta; yeh sirf stability ke liye arithmetic reorder karta hai.

True or false:

A^{- 1}

compute karke

A^{- 1} b

banana LU-solve jaisi hi accuracy deta hai.

False — explicit inversion zyada arithmetic karta hai aur rounding zyada amplify karta hai, isliye LU-solve dono — faster bhi hai aur zyada accurate bhi (dekho Condition Number and Numerical Stability).

Kya LU with pivoting mein use hone wale row swaps ki number uniquely determined hoti hai?

Nahi — alag valid pivoting choices alag tarike se swap kar sakti hain, lekin swaps ki parity (even vs odd) fixed hoti hai kyunki ise

det A

ke sign se Determinants ke zariye match karna hota hai.

Spot the error

"Kyunki

L

aur

U

dono triangular hain, main safe rehne ke liye

U

aur

L

dono par

1

's rakh doonga." — kya galat hai?

Aap dono diagonals fix nahi kar sakte: yeh system ko over-constrain karta hai aur factorization destroy kar deta hai. Aap exactly ek convention choose karte ho (Doolittle:

1

L

mein; Crout:

1

U

mein).

"Maine

P A = LU

solve kiya lekin original

b

directly

L y = b

mein plug kar diya." — bug kya hai?

P

mein stored row swaps ko right-hand side par bhi apply karna zaroori hai; aapko

L y = P b

solve karna chahiye, warna equations apni reordered rows se match nahi karengi.

u_{11} = a_{11} = 0

hai, toh maine

ℓ_{21} = a_{21} / u_{11}

set kiya aur ek bada number aaya — matrix singular hona chahiye." — kya yeh diagnosis sahi hai?

Zaroor nahi — ek zero pivot ek bilkul invertible matrix mein bhi aa sakta hai (jaise

(0111)

); ilaaj hai ek row swap,

A

ko singular declare karna nahi. (Yahan

ℓ_{21}

woh multiplier hai jo

(2, 1)

entry ko zero karta — zero pivot se divide karna hi explode kiya.)

det A

nikalne ke liye maine

U

ka diagonal multiply kiya aur wahin rok diya." — kya bhool gaye?

Pivoting se aane wala sign:

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

. Agar koi rows swap hui hain, toh

(- 1)^{# swaps}

chhodna galat sign dega.

"Maine

L y = b

par back substitution bottom row se start karke kiya." — yeh kyun fail hota hai?

L

lower-triangular hai, isliye iski pehli row mein single unknown hai; aapko top-to-bottom jaana chahiye (forward substitution). Bottom-first upper-triangular

U

ke liye hota hai.

"Gaussian elimination ke dauran jo multipliers main discard karta hoon woh LU ke liye irrelevant hain." — sahi hai?

Galat — woh discarded multipliers hi

L

ke entries

ℓ_{ij}

hain (row

i

, column

j

); LU ka poora trick unhe throw away karne ki jagah rakhne mein hai.

"Partial pivoting remaining poore matrix mein sabse bada entry pivot ke roop mein choose karta hai." — accurate hai?

Nahi — partial pivoting sirf current column mein (diagonal ke neeche) largest magnitude dhundta hai; poori submatrix search karna complete pivoting hai, ek alag aur costly scheme.

Why questions

Triangular factors solve karna itna cheap kyun ho jaata hai?

Ek triangular system ek order mein har row mein ek unknown reveal karta hai, isliye har equation already-known values back-substitute karne ke baad sirf ek division se solve ho jaati hai — koi elimination sweep nahi chahiye.

Hum sabse bada available pivot kyun choose karte hain, koi bhi nonzero ek kyun nahi?

Ek bada pivot har multiplier

∣ ℓ_{ij} ∣ \leq 1

rakhta hai, jo chhote rounding errors ko elimination ke dauran bade errors mein multiply hone se rokta hai.

LU tab hi payoff karta hai jab hum kaafi saare right-hand sides ke saath resolve karein — kyun?

Expensive elimination ek baar hoti hai

L

aur

U

build karne ke liye; har nayi

b

ke liye phir sirf do saste triangular substitutions lagte hain, isliye setup cost kai solves mein amortise ho jaati hai.

Ek triangular matrix ka determinant sirf uske diagonal ka product kyun hota hai?

Har baar us column (ya row) ke along expand karne par jo sirf ek nonzero entry rakhta hai, sirf diagonal factors multiply hokar bacha rehta hai, saare off-diagonal cofactors zero hote hain.

Doolittle mein row-by-

U

, column-by-

L

ordering itni smoothly kyun kaam karti hai?

A = LU

ko ek entry at a time match karne ki picture banao (doosri figure dekho): har nayi entry equation already-known products ka sum hai plus exactly ek brand-new unknown, kyunki row/column snake mein jo bhi "pehle" hai woh already solve ho chuka hai. Toh ek tangled simultaneous system ki jagah aapko ek clean chain milti hai jahan ek variable per equation solve hota hai — bilkul dominoes ko order mein giraaane jaisa.

Ek nearly-zero pivot almost exactly-zero jaisa bura kyun ho sakta hai?

Ek tiny pivot se divide karne par enormous multipliers bante hain jo floating-point rounding amplify karte hain, isliye accuracy collapse ho jaati hai chahe literally division-by-zero na ho.

P A = LU

(jahan

P

ek permutation hai) har invertible

A

ke liye factorization guarantee karne ke liye kyun kaafi hai?

Kyunki kisi bhi invertible

A

ke liye hamesha ek aisi row ordering hoti hai jo har leading pivot ko nonzero rakhti hai, aur

P

exactly wahi reordering record karta hai.

Edge cases

Identity matrix

I

ka LU decomposition kya hoga?

L = U = I

: yeh already dono lower- aur upper-triangular hai unit diagonal ke saath, isliye koi elimination nahi chahiye aur

I = I \cdot I

Jab aap ek aisi matrix ko LU-factor karo jo already upper-triangular hai toh kya hoga?

U = A

aur

L = I

: diagonal ke neeche eliminate karne ke liye kuch nahi hai, isliye saare multipliers

ℓ_{ij}

zero hain.

Agar ek matrix

1 \times 1

hai, maano

A = (a)

jahan

a \neq = 0

, toh

L

aur

U

kya honge?

Doolittle form mein

L = (1)

aur

U = (a)

; koi off-diagonal entries nahi hain, isliye factorization trivial hai.

U

ki diagonal par zero kya batata hai

A

ke baare mein (yeh maante hue ki aap already jitna ho sake pivot kar chuke ho)?

Saare valid row swaps ke baad bhi agar ek pivot zero force ho jaaye toh

\prod u_{ii} = 0

, isliye

det A = 0

aur

A

genuinely singular hai — koi swap ise bacha nahi sakta kyunki rows linearly dependent hain. (Pivoting se pehle zero pivot alag hai: use ek row swap fix kar sakta hai.)

Nonzero entries wali ek diagonal matrix

D

ke LU factors kya honge?

L = I

aur

U = D

: ek diagonal matrix simultaneously lower- aur upper-triangular hoti hai, isliye saare off-diagonal multipliers vanish ho jaate hain.

(0111)

mein sabse chhota change kya hai jo Doolittle ko bina kisi swap ke kaam karne deta hai, aur factorization kya ban jaata hai?

(1, 1)

wali zero ko kisi bhi nonzero value

ε

se replace karo, jisse

(ε 1 11)

milta hai; phir

u_{11} = ε

ℓ_{21} = 1/ ε

u_{22} = 1 - 1/ ε

, toh yeh factor ho jaata hai — lekin jaise

ε \to 0

, multiplier

1/ ε

blow up karta hai, yeh dikhata hai ki "just non-zero" breakdown toh fix karta hai phir bhi tiny

ε

numerical accuracy barbad kar deta hai (isliye hum swap prefer karte hain).

Recall Ek line ka summary yaad rakhne ke liye

LU Gaussian elimination hai jo data ke roop mein save ki gayi hai: $L$ multipliers $ℓ_{ij}$ rakhta hai, $U$ pivots $u_{j j}$ rakhta hai, $P$ (jab zaroori ho) swaps rakhta hai — aur upar ke har "trap" mein ya toh ek convention slip hai (kiski diagonal par $1$ 's jaate hain), ek bookkeeping slip hai ( $b$ bhi permute karo), ya ek stability slip hai (tiny pivots se bachо).