LU decomposition — algorithm, applications: Foundations

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

Yeh page assume karta hai ke tumne pehle kuch nahi dekha. Har woh symbol jo parent note tumhare saamne phenkta hai — $A$ , $L$ , $U$ , $ℓ_{ij}$ , $x$ , $b$ , multiplier $m_{ik}$ , "pivot", "triangular", $det$ , $P$ — yahan build kiya gaya hai, ek picture se, ek aisi order mein jahan har ek brick pichle wale par tikti hai.

1. Ek number, numbers ki list, numbers ka grid

Kisi bhi letter ke fancy subscripts se pehle, teen objects.

Figure — LU decomposition — algorithm, applications

Figure 1 — Scalar vs vector vs matrix. Ek yellow dot ek scalar hai (akela number,

7

). Ek blue column of dots jo ek stroke se jude hain woh ek vector hai (stacked list,

x_{1}

over

x_{2}

). Ek green

2 \times 2

block of dots ek matrix hai (poora grid). Left se right padho: complexity badhti hai ek number se, list tak, grid tak.

2. Matrix ko padhna: rows, columns, aur subscript $a_{ij}$

Grid ki har entry ko ek address chahiye.

Figure 2 — Address $a_{ij}$ . $3 \times 3$ grid of blue dots, har ek apne address ke saath labelled. Yellow arrows do counting directions dikhate hain: rows neeche count hoti hain, columns daayein count hote hain. Red dot $a_{21}$ ko mark karta hai — row $2$ , column $1$ — "row pehle, column doosra" rule ko action mein dikhata hua.

Figure mein, $a_{21}$ (red highlighted) row 2, column 1 mein baitha hai. Yeh ordering kabhi nahi badlti: row pehle, column doosra. Parent note mein $a_{ik}$ aur $u_{ij}$ aur $ℓ_{ij}$ likhte hain — yeh sab usi rule ka paalan karte hain.

3. Diagonal, aur "triangular" ka matlab

Top-left corner se bottom-right corner tak line kheencho. Is line se guzarne wale entries — $a_{11}, a_{22}, a_{33}, \dots$ — diagonal hain.

Figure 3 — Lower vs upper triangular. Left grid: non-zero entries (marked $*$ ) lower-left triangle mein bhare hain, zeros yellow dashed diagonal ke upar baithe hain — lower triangular. Right grid: non-zeros upper-right triangle mein bhare hain, zeros diagonal ke neeche baithe hain — upper triangular. Har ek mein dashed yellow line woh diagonal hai jo grid ko aadhe mein split karti hai.

Figure dono dikhata hai. "Triangular" word literally hai: non-zero numbers ek triangle mein bharte hain, grid ka ek aadha.

4. Matrix ko vector se multiply karna — $A x$ actually kya karta hai

$A x$ "sab kuch sab kuch se multiply karo" nahi hai. Iska ek precise recipe hai.

$2 \times 2$ example ke liye ( $n = 2$ ): $(2437) (x_{1} x_{2}) = (2 x_{1} + 3 x_{2} 4 x_{1} + 7 x_{2}) .$

Matrix times matrix — hamare liye Section 3 mein defined do half-grids ka product $LU$ — usi row-walks-column rule ko follow karta hai, doosri matrix ke har column ke liye done. Isliye parent ka check $LU = A$ sense banata hai: do half-grids ko waapas multiply karo aur original rebuild ho jaata hai.

5. Pivot aur multiplier — woh do numbers jo elimination produce karta hai

Ab poore topic ke do starring symbols.

Figure 4 — Pivot aur multiplier action mein. Green dot pivot $a_{11} = 2$ hai; uske neeche red dot woh entry $a_{21} = 4$ hai jo hum erase karna chahte hain. Yellow arrow pivot se target tak point karta hai. Formula $m_{21} = a_{21} / a_{11} = 4/2 = 2$ ratio dikhata hai, aur bottom line row operation $(4, 7) - 2 (2, 3) = (0, 1)$ dikhata hai jo red entry ko zero kar deta hai.

Parent jo rely karta hai woh punchline: yeh multipliers, upar ke rule se diagonal par $1$ 's ke saath ek grid mein likhe hue, hain $L$ . Pivots, cleaned-up grid ke diagonal par baithe hue, hain $U$ ka diagonal. Kuch extra compute nahi hota — tum bas woh save karte ho jo tum pehle se kar chuke the. Woh saving hai Gaussian Elimination with a memory, jo LU ka poora idea hai.

6. Determinant $det A$ aur pivots ise kyun dete hain

7. Permutation matrix $P$ — jab koi row move karni padti hai

Kabhi kabhi pivot $0$ par land karta hai. Tum zero se divide nahi kar sakte, isliye tum ek accha pivot upar laane ke liye rows swap karte ho. Kaun si rows swap huin yeh record karna $P$ ka kaam hai.

Isliye pivoting $A = LU$ ko $P A = LU$ mein badal deta hai. Poori detail Permutation Matrices mein hai.

Intuition Zero pivots ke agey: partial pivoting aur stability

Swapping sirf exactly zero pivot ke liye nahi hai. Ek tiny pivot bhi dangerous hai: ek number ke kareeb $0$ se divide karna multiplier $m_{ik} = a_{ik}^{(k)} / a_{k k}^{(k)}$ ko enormous bana deta hai, aur enormous multipliers un chhoti rounding errors ko magnify karte hain jo computer hamesha carry karta hai — answer bahut galat aa sakta hai. Standard cure partial pivoting hai: column $k$ eliminate karne se pehle, us column mein $k$ se neeche ki saari rows dekho, largest absolute value wali entry dhundo, aur us row ko swap karke pivot bana do. Yeh har multiplier ko size $\leq 1$ par rakhta hai, isliye errors kabhi blow up nahi hote. Practice mein, LU hamesha partial pivoting ke saath ki jaati hai, giving $P A = LU$ ; plain $A = LU$ woh ideal case hai jahan koi swap ki zaroorat nahi padi. Jab matrix symmetric positive-definite hoti hai, split aur simplify ho ke Cholesky Decomposition ban jaati hai (koi pivoting needed nahi), aur $A$ ka inverse solve-by-solve assemble kiya ja sakta hai jaise Matrix Inverse mein hai.

a_{ij}

subscript kisi ko kya point karta hai?

Row

i

, column

j

mein entry — row pehle, column doosra.

n

kya stand karta hai?

Ek square matrix ki rows aur columns ki common count (

n \times n

); saath hi

x

aur

b

ki length bhi.

A x = b

mein

x

aur

b

kya hain?

x

woh unknown vector hai jiske liye hum solve karte hain;

b

known right-hand-side vector hai — dono length

n

LU ke liye

A

square kyun honi chahiye?

Tumhe per column ek diagonal pivot chahiye, jo equal row aur column counts (

n \times n

) maangta hai.

Matrix ki diagonal entries kahan rehti hain?

Top-left se bottom-right tak ki line par, jahan row number column number ke barabar hoti hai (

a_{ii}

Matrix ko lower triangular kya banata hai?

Diagonal ke upar ki har entry zero hai.

"Unit lower triangular" isme kya add karta hai?

Diagonal entries sab

1

hain.

A x

ki entry

i

tum kaise compute karte ho?

A

ki row

i

x

ke against chalo, matched pairs multiply karo, unhe sum karo.

A x = b

equations ke system ke same kyun hai?

Product ki har row exactly ek equation spell karta hai.

Stage index

k

kis range mein chalta hai?

k = 1, \dots, n - 1

— ek stage per column,

n

se ek pehle rok ke.

Pivot kya hai?

Diagonal anchor entry

a_{k k}^{(k)}

jisse tum divide karte ho uske neeche column eliminate karne ke liye;

U

ka diagonal.

Multiplier

m_{ik}

kya hai aur kyun ratio hai?

m_{ik} = a_{ik}^{(k)} / a_{k k}^{(k)}

; yeh woh egymaatra number hai jo row

_{i} - m_{ik}

row

_{k}

position

(i, k)

ko zero karta hai.

L

ki entries kaise assemble hoti hain?

ℓ_{ii} = 1

ℓ_{ik} = m_{ik}

for

i > k

, aur

ℓ_{ik} = 0

for

i < k

Factors se

det A

kaise padho (no swaps)?

Pivots ka product

\prod_{i} u_{ii}

(kyunki

det L = 1

Ek row swap

det A

ko kaise badalta hai?

sign (P) = (- 1)^{# swaps}

se multiply karta hai, toh

det A = sign (P) \prod_{i} u_{ii}

Permutation matrix

P

kya karta hai?

A

ki rows shuffle karta hai (identity with rows swapped), use tab kiya jaata hai jab pivot zero ya tiny ho.

Partial pivoting kya hai aur kyun karte hain?

Largest-magnitude entry wali row ko pivot position mein swap karo, taaki har multiplier

\leq 1

rahe aur rounding errors blow up na karein.

Connections

Gaussian Elimination — woh elimination process jo pivots aur multipliers spits out karta hai.
Triangular Systems & Substitution — triangular grids turant kyun solve hote hain.
Determinants — product-of-pivots shortcut.
Permutation Matrices — row-swap bookkeeping $P$ .
Matrix Inverse — $A^{- 1}$ ko $L, U$ se column by column assemble karna.
Cholesky Decomposition — symmetric positive-definite special case.
LU decomposition — algorithm, applications — woh parent topic jise yeh foundations feed karte hain.

Foundations — LU decomposition — algorithm, applications