LU decomposition (numerical) — Hinglish notes

4.8.19 · Maths › Numerical Methods

LU decomposition HAI kya?

DO triangular matrices kyun? Kyunki triangular systems solve karna bahut aasaan hai:

$L y = b$ → upar se neeche solve karo (forward substitution).
$U x = y$ → neeche se upar solve karo (back substitution).

Toh $A x = b$ ban jaata hai $LU x = b$ , set karo $U x = y$ , aur do aasaan hisson ko solve karo.

Hum isse DERIVE kaise karte hain? (Doolittle, scratch se)

Machinery samajhne ke liye ek general $3 \times 3$ lo. $L$ ko unit diagonal ke saath aur $U$ ko general likhte hain:

A = a_{11} a_{21} a_{31} a_{12} a_{22} a_{32} a_{13} a_{23} a_{33} = L 1 ℓ_{21} ℓ_{31} 01 ℓ_{32} 001 U u_{11} 00 u_{12} u_{22} 0 u_{13} u_{23} u_{33}

$LU$ multiply karo aur entries ko $A$ ke saath match karo. Trick yeh hai: $U$ ki row by row, phir $L$ ki column by column jaao, kyunki har nayi equation mein exactly ek nayi unknown aati hai.

$U$ ki Row 1 ( $L$ ki pehli row $(1, 0, 0)$ hai): $u_{11} = a_{11}, u_{12} = a_{12}, u_{13} = a_{13} .$

$L$ ka Column 1 (doosri/teesri entries row·col se aati hain): $a_{21} = ℓ_{21} u_{11} \Rightarrow ℓ_{21} = a_{21} / u_{11}$ , aur $ℓ_{31} = a_{31} / u_{11}$ .

$U$ ki Row 2: $a_{22} = ℓ_{21} u_{12} + u_{22} \Rightarrow u_{22} = a_{22} - ℓ_{21} u_{12}$ , $a_{23} = ℓ_{21} u_{13} + u_{23} \Rightarrow u_{23} = a_{23} - ℓ_{21} u_{13}$ .

$L$ ka Column 2: $a_{32} = ℓ_{31} u_{12} + ℓ_{32} u_{22} \Rightarrow ℓ_{32} = \frac{a _{32} - ℓ _{31} u _{12}}{u _{22}}$ .

$U$ ki Row 3: $a_{33} = ℓ_{31} u_{13} + ℓ_{32} u_{23} + u_{33} \Rightarrow u_{33} = a_{33} - ℓ_{31} u_{13} - ℓ_{32} u_{23}$ .

Is pattern ko generalize karne se milte hain Doolittle formulas:

YEH sirf Gaussian elimination ka disguise kyun hai?

Har elimination step "row $_{i} \leftarrow$ row $_{i} - m_{ik} \cdot$ row $_{k}$ " ek elementary matrix $E_{ik}$ se multiply karna hai. Poori elimination ke baad $U = E_{n} \dots E_{1} A$ , toh $A = (E_{n} \dots E_{1})^{- 1} U = LU$ . Jo multipliers $m_{ik}$ hum plain elimination mein discard kar dete hain, wahi LU mein $ℓ_{ik}$ entries ke roop mein save ho jaate hain.

Worked Example 1 — factor aur solve karo

$A x = b$ solve karo jahaan $A = (26313), b = (535) .$

Step 1: $u_{11} = 2, u_{12} = 3$ . Kyun? $L$ ki Row 1 hai $(1, 0)$ , toh $U$ ki top row = $A$ ki top row.

Step 2: $ℓ_{21} = a_{21} / u_{11} = 6/2 = 3$ . Kyun? $(2, 1)$ entry ko zero karne ka multiplier.

Step 3: $u_{22} = a_{22} - ℓ_{21} u_{12} = 13 - 3 \cdot 3 = 4$ . Kyun? Column-1 elimination ka contribution subtract karo.

Toh $L = (1301), U = (2034) .$ Check: $LU = (26313) = A .$ ✓

Forward solve $L y = b$ : $y_{1} = 5$ ; $3 y_{1} + y_{2} = 35 \Rightarrow y_{2} = 35 - 15 = 20$ . Upar se kyun? $L$ lower triangular hai, pehli equation mein ek hi unknown hai.

Back solve $U x = y$ : $4 x_{2} = 20 \Rightarrow x_{2} = 5$ ; $2 x_{1} + 3 x_{2} = 5 \Rightarrow 2 x_{1} = 5 - 15 = - 10 \Rightarrow x_{1} = - 5$ . Neeche se kyun? $U$ upper triangular hai.

$x = (- 5, 5)^{⊤}$

Worked Example 2 — pivoting kyun zaroori hai

Is matrix ko factor karne ki koshish karo: $A = (0111) .$ $u_{11} = a_{11} = 0$ , phir $ℓ_{21} = a_{21} / u_{11} = 1/0$ — blast ho jaata hai! Kyun? Pivot zero hai, bhaale hi $A$ invertible ho.

Fix: partial pivoting. Rows swap karo taaki sabse bade magnitude wali entry pivot par aa jaaye. Swaps ko ek permutation matrix $P$ mein record karte hain aur $P A = LU$ factor karte hain. Yahaan dono rows swap karo: $P A = (1011) = (1001) (1011) .$ $A x = b$ solve karne ke liye tum $LU x = P b$ solve karte ho ( $b$ ko usi tarah permute karo).

Ek kaam ka bonus: determinant

Kyunki $det L = 1$ (unit diagonal) aur $det U = \prod u_{ii}$ , $det A = det (LU) = \prod_{i = 1}^{n} u_{ii} \times (- 1)^{# row swaps} .$ Kyun? Triangular matrix ka determinant uski diagonal ka product hota hai; permutations har swap par sign flip karte hain.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho ek maze solve karne mein bahut saare careful steps lagte hain. Har baar jab koi tumhe nayi "exit" de, toh poora maze dobara solve karne ki bajaye, pehli baar hi moves ki ek cheat sheet likh lo. $L$ aur $U$ wahi cheat sheet hain. Ek baar mil gayi, toh kisi bhi exit tak pahunchna super fast hai: neeche chalo ( $L$ , forward), phir wapas upar ( $U$ , back). Agar koi turn "blocked" ho (zero pivot), toh bas paths ka order swap karo (pivoting) aur chalte raho.

Flashcards

LU decomposition

A

ko kismein factor karta hai?

Ek lower-triangular

L

times ek upper-triangular

U

A = LU

Doolittle convention mein kaunsi matrix ki diagonal par 1's hote hain?

L

(lower-triangular factor) ki.

L, U

compute karne ke baad

A x = b

kaise solve karte hain?

Forward-solve

L y = b

, phir back-solve

U x = y

Entries

ℓ_{ij}

kiske barabar hote hain?

Gaussian elimination ke woh multipliers jo entry

(i, j)

ko zero karne mein use hue the.

u_{ij}

(

j \geq i

) ka Doolittle formula?

u_{ij} = a_{ij} - \sum_{k = 1}^{i - 1} ℓ_{ik} u_{k j}

ℓ_{ij}

(

i > j

) ka Doolittle formula?

ℓ_{ij} = \frac{1}{u _{j j}} (a_{ij} - \sum_{k = 1}^{j - 1} ℓ_{ik} u_{k j})

Baar baar elimination ki bajaye LU kyun use karte hain?

Ek baar factor karo, phir har nayi right-hand side par sirf do saste triangular solves lagte hain.

Pivot

u_{j j} = 0

hone par kya gadbad hoti hai?

Division by zero / instability; fix hai partial pivoting (

P A = LU

Partial pivoting multipliers ke baare mein kya guarantee deta hai?

∣ ℓ_{ij} ∣ \leq 1

, jisse rounding errors bounded rehti hain.

LU se

det A

kaise milta hai?

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

Doolittle form mein

det L = 1

kyun hota hai?

Triangular determinant = diagonal ka product, aur

L

ki diagonal mein sab 1's hain.

Connections

Gaussian Elimination — LU uske multipliers store karta hai.
Forward and Back Substitution — do solve phases.
Partial Pivoting / Permutation Matrices — stability aur $P A = LU$ .
Cholesky Decomposition — symmetric positive-definite $A$ ke liye special LU ( $A = L L^{⊤}$ ).
Crout Decomposition — sister convention ( $U$ mein 1's).
Determinants — $U$ se saste mein compute hota hai.
Condition Number and Numerical Stability — pivoting kyun matter karta hai.