LU decomposition — algorithm, applications

4.5.26 · Maths › Linear Algebra (Full)

YEH HAI KYA?

$U$ ki entries exactly Gaussian elimination ke pivots hain, aur $L$ ki entries exactly woh multipliers hain jo aapne har pivot ke neeche eliminate karne ke liye use kiye the.

KAISE: algorithm ko scratch se derive karna

Gaussian elimination har pivot ke neeche wale column ko row operations se clear karta hai. Ek row operation "row $k$ ka $m$ guna row $i$ se subtract karo" khud left par ek matrix multiplication hai.

Multiplier matrix

Entry $a_{ik}$ ko pivot $a_{k k}$ se eliminate karne ke liye, multiplier hai $m_{ik} = \frac{a _{ik}}{a _{k k}} (after previous steps) .$ Jo elementary matrix "row $_{i} \leftarrow$ row $_{i} - m_{ik}$ row $_{k}$ " karta hai woh identity hai jisme position $(i, k)$ par $- m_{ik}$ hai.

Figure — LU decomposition — algorithm, applications

Worked Example 1 — basic factorisation

Factor karo $A = (2437) .$

Step 1. Pivot $= 2$ . Multiplier $m_{21} = \frac{4}{2} = 2$ . Yeh step kyun? Pehle pivot ke neeche wale $4$ ko khatam karna hai; $m_{21} = a_{21} / a_{11}$ .

Step 2. Row $_{2} \leftarrow$ Row $_{2} - 2 \cdot$ Row $_{1}$ : $(4, 7) - (4, 6) = (0, 1)$ . Toh $U = (2031)$ . Kyun? Yeh upper-triangular $U$ produce karta hai jiske diagonal par pivots hain.

Step 3. Multiplier ko $L$ mein daalo: $L = (1201)$ . Kyun? $L$ record karta hai ki hum $U$ tak kaise pahunche, $+ m_{21}$ ke saath.

Check: $LU = (1201) (2031) = (2437) = A .$ ✓

Worked Example 2 — $A x = b$ solve karne ke liye LU use karna

$A x = b$ solve karo upar wale $A$ ke saath aur $b = (818)$ .

Forward: $L y = b$ : $y_{1} = 8, 2 y_{1} + y_{2} = 18 \Rightarrow y_{2} = 18 - 16 = 2.$ Kyun? Row 1 se $y_{1}$ turant milta hai; row 2 mein substitute karo.

Back: $U x = y$ : $2 x_{1} + 3 x_{2} = 8, x_{2} = 2 \Rightarrow 2 x_{1} = 8 - 6 \Rightarrow x_{1} = 1.$ Answer: $x = (1, 2)^{⊤}$ . Itna fast kyun? Koi nayi elimination nahi — sirf substitution.

Worked Example 3 — ek $3 \times 3$ aur pivot ki warning

$A = 124136158 .$

$m_{21} = 2, m_{31} = 4$ . Column 1 clear karne ke baad: $100112134 .$
Naya pivot $= 1$ (row 2). $m_{32} = 2$ . Clear karo: row $_{3} - 2 \cdot$ row $_{2} = (0, 0, - 2)$ . $U = 100110 13 - 2, L = 124012001 .$

Applications (80/20 payoff)

Cost (yeh number kyun matter karta hai)

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho ek lamba messy LEGO instructions ka stack hai. Puzzle ek baar solve karna slow hai. Lekin agar aap apne use kiye steps likh lo (woh hai $L$ ) aur half-bana model rakh lo (woh hai $U$ ), toh agli baar jab koi thoda alag goal de, aap naye sire se shuru nahi karte — bas apne saved steps ko aage-peeche replay karte ho. LU = "apna homework save karo taaki kabhi dobara na karna pade."

Matrix A ki LU decomposition kya hoti hai?

Ek factorisation

A = LU

jisme

L

unit lower triangular hai (diagonal par 1's) aur

U

upper triangular hai.

Gaussian elimination mein

U

ki entries kya represent karti hain?

The pivots.

L

ki off-diagonal entries kya represent karti hain?

The multipliers

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

jo har pivot ke neeche eliminate karne ke liye use hue.

L

ki diagonal mein sab ones kyun hain?

Kyunki

L

inverse elementary elimination matrices ka product hai, jinmein se har ek diagonal entries

1

chhod deta hai.

LU ke zariye

A x = b

solve karne ke liye do steps kya hain?

Forward-solve

L y = b

, phir back-solve

U x = y

LU se

det (A)

kaise compute karte ho?

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

(pivots ka product), times

(- 1)

per row swap agar pivoting use ki.

Plain

A = LU

kab fail karta hai aur fix kya hai?

Jab pivot zero/tiny ho; partial pivoting use karo jisse

P A = LU

milta hai permutation matrix

P

ke saath.

LU factorisation ki cost ek triangular solve se compare mein?

Factorisation

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

flops; har solve

\approx n^{2}

Plain Gaussian elimination ke muqable mein LU ka main advantage?

L, U

ko bahut saare right-hand sides ke liye reuse karo

O (n^{2})

each mein, instead of

O (n^{3})

elimination dobara karne ke.

Connections

Gaussian Elimination — LU elimination hai jisme steps yaad rakhe jaate hain.
Permutation Matrices — $P A = LU$ mein pivoting ke liye use hota hai.
Determinants — pivots ka product.
Matrix Inverse — identity columns ke against solve karo.
Cholesky Decomposition — symmetric positive-definite special case $A = L L^{⊤}$ .
Triangular Systems & Substitution — saste solves.