LU decomposition — algorithm, applications: Exercises

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

Yeh page tumhara self-test hai LU decomposition — algorithm, applications ke liye. Har problem clearly batata hai kya karna hai, phir ek complete worked solution hide karta hai. Pehle khud try karo, tab callout kholo. Levels "sirf pieces pehchano" se lekar "sab kuch ek saath jodo" tak jaate hain.

Shuru karne se pehle, ek word hai jo is page par sabse zyada kaam karta hai, toh aao use seedhi bhaasha mein samajhte hain.

Definition Pivot (yeh word ka matlab, use karne se pehle)

Pivot woh diagonal entry hai jis par tum elimination ke dauran abhi khade ho — woh number jisse tum divide karte ho column ke neeche clear karne ke liye. Concretely, jab tum column $k$ par kaam karte ho, pivot woh entry hai position $(k, k)$ par jo matrix mein abhi hai (pehle ke columns clear hone ke baad). "Ek pivot ke neeche ki entries ko kill karna" matlab row operations use karna taaki us diagonal entry ke neeche har number $0$ ban jaaye. Woh pivots $U$ ki diagonal ban jaate hain; jo numbers tumne column clear karne ke liye multiply kiye the woh $L$ mein multipliers ban jaate hain.

Figure dekho: magenta diagonal cells pivots hain, orange lower-left cells woh entries hain jo hum clear karte hain (aur unhe clear karne wale multipliers $L$ mein jaate hain).

Yahan sab kuch sirf parent note ke tools use karta hai: elimination multipliers $m_{ik} = a_{ik} / a_{k k}$ , unit-lower-triangular $L$ , upper-triangular $U$ , forward/back substitution, permutations $P$ , aur product-of-pivots rule.

Figure — LU decomposition — algorithm, applications

Yeh figure tumhare liye map hai neeche har solution ke liye: jab bhi koi solution "pivot" kahe toh magenta diagonal cell dekho; jab bhi woh multiplier $m_{ik}$ compute kare aur $L$ mein store kare, woh number orange lower-left cell mein position $(i, k)$ par rehta hai; violet upper cells woh entries hain jo $U$ mein survive karti hain. Is picture ko khula rakho jab tum Exercises 2.3, 4.1 aur 4.2 karo — wahan har row operation literally "orange cell $\to$ $0$ banta hai, uska multiplier $L$ mein record hota hai" hai.

Level 1 — Recognition

Exercise 1.1

In mein se kaun se valid $L$ (unit lower triangular) hain aur kaun se valid $U$ (upper triangular)?

M_{1} = (1301), M_{2} = (2051), M_{3} = (1021), M_{4} = (1302) .

Recall Solution

Parent note se do rules yaad karo:

Unit lower triangular $L$ : diagonal ke upar zeros, aur diagonal par 1's.
Upper triangular $U$ : diagonal ke neeche zeros (diagonal kuch bhi ho sakti hai).
$M_{1}$ : diagonal ke upar zeros ✓, diagonal $= (1, 1)$ ✓ → valid $L$ .
$M_{2}$ : diagonal ke neeche zero ✓ → valid $U$ (diagonal $(2, 1)$ $U$ ke liye theek hai).
$M_{3}$ : diagonal ke neeche zero ✓ → valid $U$ . (Iske diagonal par bhi 1's hain, toh kya yeh bhi valid $L$ hai? Nahi — $L$ ko upar zeros chahiye, lekin $M_{3}$ mein upar $2$ hai. Toh yeh sirf valid $U$ hai.)
$M_{4}$ : upar zeros ✓ lekin diagonal $= (1, 2)$ , aur $2 \neq = 1$ → NOT unit lower triangular. Yeh ek valid lower triangular matrix hai, bas woh unit type nahi jaise LU use karta hai.

Exercise 1.2

Is factorisation mein

(39620) = L (1301) U (3062),

(a) do pivots, (b) single multiplier $m_{21}$ , aur (c) $det A$ seedha $U$ se batao.

Recall Solution

(a) Pivots $U$ ki diagonal hain (figure mein magenta cells): $u_{11} = 3$ aur $u_{22} = 2$ .
(b) Multiplier $L$ ki off-diagonal entry hai (ek orange cell): $m_{21} = 3$ . Sanity check: $m_{21} = a_{21} / a_{11} = 9/3 = 3$ ✓.
(c) $det A = \prod_{i} u_{ii} = 3 \cdot 2 = 6$ . (Koi row swaps nahi, toh koi sign flip nahi.)

Level 2 — Application

Exercise 2.1

$A = (26415)$ ko $LU$ mein factor karo.

Recall Solution

Step 1 (WHY): hum pivot $a_{11} = 2$ par khade hain (top-left magenta cell). Matrix ko upper-triangular banane ke liye hume iske neeche wale $6$ ko $0$ banana hoga. Multiplier hai "row 1 ke kitne copies row 2 se subtract karne hain": $m_{21} = \frac{a _{21}}{a _{11}} = \frac{6}{2} = 3.$ Step 2 (WHAT + WHY): row $_{2} \leftarrow$ row $_{2} - 3 \cdot$ row $_{1}$ deta hai $(6, 15) - (6, 12) = (0, 3)$ . Leading $0$ exactly cleared entry hai; yahi wajah hai ki operation $U$ ki upper-triangular shape produce karta hai: $U = (2043) .$ Step 3 (WHY): $L$ ko record karna chahiye ki hum $U$ tak kaise pahunche taaki $LU = A$ . Parent note dikhata hai ki har multiplier $+$ sign ke saath drop hota hai, toh $+ m_{21} = 3$ orange $(2, 1)$ cell mein store karo: $L = (1301) .$ Check: $LU = (1301) (2043) = (26415) = A$ ✓.

Exercise 2.2

2.1 se $A$ aur factors use karke, $A x = b$ solve karo jahan $b = (830)$ ho, two-solve method se.

Recall Solution

Forward solve $L y = b$ (row by row, top-down): $y_{1} = 8, 3 y_{1} + y_{2} = 30 \Rightarrow y_{2} = 30 - 24 = 6.$ Back solve $U x = y$ (row by row, bottom-up): $3 x_{2} = 6 \Rightarrow x_{2} = 2, 2 x_{1} + 4 x_{2} = 8 \Rightarrow 2 x_{1} = 8 - 8 = 0 \Rightarrow x_{1} = 0.$ Answer: $x = (0, 2)^{⊤}$ . Verify karo $A x = (2 \cdot 0 + 4 \cdot 2 6 \cdot 0 + 15 \cdot 2) = (830)$ ✓.

Exercise 2.3

$3 \times 3$ matrix ko factor karo $A = 123258137 .$

Recall Solution

Column 1 (WHY): hum pivot $a_{11} = 1$ par khade hain aur iske neeche dono entries ko zero karna hai (column 1 mein do orange cells). Har multiplier woh entry hai pivot se divided karke: $m_{21} = \frac{2}{1} = 2, m_{31} = \frac{3}{1} = 3.$ Subtract karo row 1 ke woh multiples — yahi wajah hai ki pivot ke neeche pura pehla column zero ho jaata hai:

row $_{2} - 2$ row $_{1} = (0, 1, 1)$
row $_{3} - 3$ row $_{1} = (0, 2, 4)$ $\to 100212114 .$ Column 2 (WHY): ab hum position $(2, 2)$ mein naye pivot par khade hain, jo hai $1$ (ise matrix se padhte hain jaise woh abhi hai, na ki original $5$ ). Sirf ek entry, $(3, 2)$ par $2$ , iske neeche hai, toh $m_{32} = \frac{2}{1} = 2, row_{3} - 2 row_{2} = (0, 0, 2) .$ Yeh last sub-diagonal entry ko zero karta hai, upper-triangular shape complete karta hai:

L=\begin{pmatrix}1&0&0\\2&1&0\\3&2&1\end{pmatrix}.$$ **WHY $L$ aisa dikhta hai:** har multiplier jo humne use kiya woh (+ sign ke saath) orange cell mein store hota hai jiska position us entry se match karta hai jise usne clear kiya — $m_{21}\to(2,1)$, $m_{31}\to(3,1)$, $m_{32}\to(3,2)$ — jo exactly *batata hai ki hum $U$ tak kaise pahunche*. **Full check** — $LU$ ki **har** entry multiply karo, sirf ek row nahi: $$LU=\begin{pmatrix}1&0&0\\2&1&0\\3&2&1\end{pmatrix}\begin{pmatrix}1&2&1\\0&1&1\\0&0&2\end{pmatrix} =\begin{pmatrix} 1 & 2 & 1\\ 2 & 2{+}1 & 2{+}1\\ 3 & 6{+}2 & 3{+}2{+}2 \end{pmatrix} =\begin{pmatrix}1&2&1\\2&5&3\\3&8&7\end{pmatrix}=A\ ✓.$$ (Row 2: $2\cdot(1,2,1)=(2,4,2)$ plus $1\cdot(0,1,1)$ deta hai $(2,5,3)$. Row 3: $3\cdot(1,2,1)+2\cdot(0,1,1)+1\cdot(0,0,2)=(3,8,7)$. Har entry match karti hai.)

Level 3 — Analysis

Exercise 3.1

$A = (0324)$ ko factor karne ki koshish karo. Agar plain $LU$ fail ho, toh $P A = LU$ produce karo.

Recall Solution

Plain $LU$ kyun fail hota hai: pehla pivot $a_{11} = 0$ hai. Multiplier $m_{21} = a_{21} / a_{11} = 3/0$ undefined hai — zero se division. Koi bhi algebra yeh fix nahi kar sakta; hume pivot slot mein ek nonzero entry move karni hogi.

Partial pivoting: rows 1 aur 2 swap karo. Permutation matrix jo $2 \times 2$ ki rows swap karta hai woh hai $P = (0110), P A = (3042) .$ Ab pivot $= 3$ hai, aur iske neeche entry already $0$ hai, toh $m_{21} = 0/3 = 0$ . Isliye $L = (1001), U = (3042), P A = LU .$ Check: $LU = U = P A$ ✓.

Exercise 3.2

3.1 ki factorisation se $det A$ padhte hain. Sign rule yaad rakhna.

Recall Solution

$det U = 3 \cdot 2 = 6$ , aur $det L = 1$ . Lekin humne ek row swap kiya, toh $det A = (- 1)^{# swaps} det U = (- 1)^{1} \cdot 6 = - 6.$ Direct check: $det (0324) = 0 \cdot 4 - 2 \cdot 3 = - 6$ ✓.

Exercise 3.3

Exercise 2.3 ki $3 \times 3$ matrix $A$ ke liye (jiska $U$ diagonal $1, 1, 2$ hai), $det A$ compute karo, aur batao ki factorisation mein $n = 3$ ke liye $\frac{2}{3} n^{3}$ estimate se roughly kitne flops lage.

Recall Solution

Determinant: koi swaps nahi use hue, toh $det A = \prod_{i} u_{ii} = 1 \cdot 1 \cdot 2 = 2.$ Flop estimate: $\frac{2}{3} n^{3} = \frac{2}{3} \cdot 27 = 18$ flops (ek order-of-magnitude estimate, exact nahi). Baat exact count ki nahi hai — baat yeh hai ki cost $n^{3}$ ki tarah badhti hai, toh $10 \times$ bada matrix factor karne mein $\sim 1000 \times$ zyada kharch hoga.

Level 4 — Synthesis

Exercise 4.1

Tumhe $A x = b_{i}$ solve karna hai teen right-hand sides ke liye

\mathbf{b}_2=\begin{pmatrix}0\\1\end{pmatrix},\quad \mathbf{b}_3=\begin{pmatrix}2\\1\end{pmatrix},\qquad A=\begin{pmatrix}2&1\\4&5\end{pmatrix}.$$ **Ek baar** factor karo, phir reuse karo. ($A\mathbf{x}=\mathbf{e}_1$ aur $A\mathbf{x}=\mathbf{e}_2$ solve karna tumhe [[Matrix Inverse|inverse]] columns bhi de deta hai.) > [!recall]- Solution > **Ek baar factor karo (WHY yeh steps).** Hum pivot $a_{11}=2$ par khade hain aur iske neeche $4$ ko zero karna hai, toh $m_{21}=4/2=2$; row$_2$ se $2\,$row$_1$ subtract karne par $(4,5)-(4,2)=(0,3)$ milta hai — woh leading $0$ cleared orange cell hai, upper-triangular $U$ produce karta hai. Multiplier $L$ mein $(2,1)$ par store hota hai: > $$L=\begin{pmatrix}1&0\\2&1\end{pmatrix},\quad U=\begin{pmatrix}2&1\\0&3\end{pmatrix}.$$ > Kyunki $A$ kabhi nahi badlata, hum is **ek** factorisation ko teeno $\mathbf{b}$'s ke liye reuse karte hain — yahi is exercise ka pura point hai. > > **$\mathbf{b}_1=(1,0)^\top$:** forward $y_1=1,\ 2y_1+y_2=0\Rightarrow y_2=-2$. Back $3x_2=-2\Rightarrow x_2=-\tfrac23$; $2x_1+x_2=1\Rightarrow 2x_1=1+\tfrac23=\tfrac53\Rightarrow x_1=\tfrac56$. > $$\mathbf{x}_1=\left(\tfrac56,\,-\tfrac23\right)^\top.$$ > > **$\mathbf{b}_2=(0,1)^\top$:** forward $y_1=0,\ y_2=1-0=1$. Back $3x_2=1\Rightarrow x_2=\tfrac13$; $2x_1+\tfrac13=0\Rightarrow x_1=-\tfrac16$. > $$\mathbf{x}_2=\left(-\tfrac16,\,\tfrac13\right)^\top.$$ > Yeh dono $A^{-1}$ ke columns hain: > $$A^{-1}=\begin{pmatrix}\tfrac56&-\tfrac16\\[2pt]-\tfrac23&\tfrac13\end{pmatrix}.$$ > **Check:** $\det A=2\cdot5-1\cdot4=6$, aur $A^{-1}=\tfrac16\begin{pmatrix}5&-1\\-4&2\end{pmatrix}$ ✓ match karta hai. > > **$\mathbf{b}_3=(2,1)^\top$:** forward $y_1=2,\ 2\cdot2+y_2=1\Rightarrow y_2=-3$. Back $3x_2=-3\Rightarrow x_2=-1$; $2x_1-1=2\Rightarrow x_1=\tfrac32$. > $$\mathbf{x}_3=\left(\tfrac32,\,-1\right)^\top.$$ > **Cost story:** humne $\approx\tfrac23n^3$ factorisation ki **ek baar** keemat chukaayi, phir teeno solves mein se har ek sirf $\approx n^2$ cost kiya — LU ka pura point yahi hai. ### Exercise 4.2 Pivoted case $PA=LU$ ke liye jahan $$P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad A=\begin{pmatrix}0&2\\3&4\end{pmatrix},$$ $A\mathbf{x}=\mathbf{b}$, $\mathbf{b}=(4,6)^\top$ solve karo. Dhyan rakho: permutation $\mathbf{b}$ par bhi lagni chahiye. > [!recall]- Solution > Exercise 3.1 se humhare paas already $PA=LU$ hai jahan $L=I$, $U=\begin{pmatrix}3&4\\0&2\end{pmatrix}$ — factorisation *isliye* exist karta hai kyunki humne pehle zero pivot ko raaste se hataaya (WHY pivoting step zaroori tha). > **Key idea (WHY $\mathbf{b}$ permute karein):** $A\mathbf{x}=\mathbf{b}$ matlab $PA\mathbf{x}=P\mathbf{b}$, yaani $LU\mathbf{x}=P\mathbf{b}$. $L$ aur $U$ ki rows *swapped* rows hain, toh right-hand side bhi identically swap hona chahiye warna equations line up nahi hongi: > $$P\mathbf{b}=\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}4\\6\end{pmatrix}=\begin{pmatrix}6\\4\end{pmatrix}.$$ > Forward $L\mathbf{y}=P\mathbf{b}$ (yahaan $L=I$, toh yeh step sirf copy karta hai): $\mathbf{y}=(6,4)^\top$. > Back $U\mathbf{x}=\mathbf{y}$ (bottom-up, WHY: $U$ upper-triangular hai toh last equation mein ek unknown hai): $2x_2=4\Rightarrow x_2=2$; $3x_1+4x_2=6\Rightarrow 3x_1=6-8=-2\Rightarrow x_1=-\tfrac23$. > $$\mathbf{x}=\left(-\tfrac23,\,2\right)^\top.$$ > **Original $A$ par check:** row 1 $=0\cdot(-\tfrac23)+2\cdot2=4$ ✓; row 2 $=3\cdot(-\tfrac23)+4\cdot2=-2+8=6$ ✓. > [!mistake] L4 trap — right-hand side permute karna bhool jaana > $PA=LU$ ke saath, tempting move hai **original** $\mathbf{b}$ ke saath $L\mathbf{y}=\mathbf{b}$ forward-solve karna. Yeh sahi lagta hai kyunki $\mathbf{b}$ "problem se belong karta hai." **Lekin jo equation tumne actually factor ki woh $PA\mathbf{x}=P\mathbf{b}$ hai.** Agar tum $\mathbf{b}$ par $P$ nahi lagate, toh $L$ ki rows tumhare data ki rows se align nahi hongi aur answer galat hoga. **Fix:** jab bhi $A$ ki rows swap karo, forward substitution se pehle $\mathbf{b}$ ki same rows swap karo. --- ## Level 5 — Mastery ### Exercise 5.1 Prove karo ki **kisi bhi** unit-lower-triangular $L$ aur kisi bhi upper-triangular $U$ ke liye, product $A=LU$ ka $\det A=\prod_i u_{ii}$ hota hai. Phir ise explain karne ke liye use karo ki **saare nonzero pivots** wala LU factorisation kyun guarantee karta hai ki $A$ invertible hai. > [!recall]- Solution > **Triangular matrix ka determinant** uski diagonal entries ka product hota hai — yeh ek standard fact hai (pehle column ke along repeatedly expand karo; har off-diagonal term ek zero se kill ho jaata hai). Dono par apply karo: > $$\det L=\prod_i \ell_{ii}=\prod_i 1=1,\qquad \det U=\prod_i u_{ii}.$$ > [[Determinants|Determinant]] ki multiplicativity se, > $$\det A=\det(LU)=\det L\cdot\det U=1\cdot\prod_i u_{ii}=\prod_i u_{ii}.$$ > **Invertibility:** $A$ invertible hai $\iff\det A\neq0$. Kyunki $\det A=\prod_i u_{ii}$, yeh product nonzero hai **exactly tab jab har pivot $u_{ii}\neq0$ ho**. Toh "saare pivots nonzero" $\Rightarrow$ $\det A\neq0$ $\Rightarrow$ [[Matrix Inverse|$A^{-1}$ exist karta hai]]. Conversely ek zero pivot $\det A=0$ force karta hai, toh $A$ singular hai. $\blacksquare$ ### Exercise 5.2 Ek symmetric positive-definite $A$ ka special factorisation $A=LL^\top$ ([[Cholesky Decomposition|Cholesky]]) hota hai, jahan $L$ lower triangular hai **positive diagonal** ke saath (necessarily 1's nahi). Ke liye $$A=\begin{pmatrix}4&2\\2&5\end{pmatrix},$$ woh lower-triangular $L$ dhundho jahan $A=LL^\top$. > [!recall]- Solution > $L=\begin{pmatrix}\ell_{11}&0\\\ell_{21}&\ell_{22}\end{pmatrix}$ likho. Phir > $$LL^\top=\begin{pmatrix}\ell_{11}^2 & \ell_{11}\ell_{21}\\ \ell_{11}\ell_{21} & \ell_{21}^2+\ell_{22}^2\end{pmatrix} > \overset{!}{=}\begin{pmatrix}4&2\\2&5\end{pmatrix}.$$ > Entries match karo, top-left pehle: > - $\ell_{11}^2=4\Rightarrow \ell_{11}=2$ (positive root lo). > - $\ell_{11}\ell_{21}=2\Rightarrow 2\ell_{21}=2\Rightarrow \ell_{21}=1$. > - $\ell_{21}^2+\ell_{22}^2=5\Rightarrow 1+\ell_{22}^2=5\Rightarrow \ell_{22}=2$. > $$L=\begin{pmatrix}2&0\\1&2\end{pmatrix},\qquad LL^\top=\begin{pmatrix}2&0\\1&2\end{pmatrix}\begin{pmatrix}2&1\\0&2\end{pmatrix}=\begin{pmatrix}4&2\\2&5\end{pmatrix}=A\ ✓.$$ > **Diagonal 1's kyun nahi hai yahan:** Cholesky $A$ ko $L$ aur uske *apne transpose* mein split karta hai, toh pivots $\sqrt{\text{pivot}}$ ke roop mein dono par share hote hain — diagonal unhe absorb kar leti hai alag $U$ mein factor out karne ki bajaye. ### Exercise 5.3 Ek paragraph mein explain karo ki $n\times n$ matrix par $k$ alag right-hand sides ke saath LU kyun lagbhag $\tfrac23n^3+k\,n^2$ operations cost karta hai, jabki har system par naive Gaussian elimination lagbhag $k\cdot\tfrac23n^3$ cost karta hai. LU kab worth it nahi rehta? > [!recall]- Solution > [[Gaussian Elimination|Elimination]] expensive part hai: $A$ ko $U$ tak reduce karna lagbhag $\tfrac23n^3$ entries touch karta hai kyunki $n$ pivots mein se har ek ke liye tum neeche aur daayein taraf ek $\sim n\times n$ block of entries clear karte ho. LU mein hum yeh **ek baar** karte hain aur multipliers ko $L$ mein *yaad rakhte hain* instead of throw away karne ke. Har baad ka right-hand side phir sirf ek [[Triangular Systems & Substitution|forward solve]] ($\approx\tfrac12n^2$ operations) plus ek back solve ($\approx\tfrac12n^2$), yaani $\approx n^2$ total — bilkul re-elimination nahi. Toh $k$ systems cost karte hain $\tfrac23n^3+k\,n^2$: ek badi upfront keemat, phir saste repeats. Naive elimination ki bajaye har **$\mathbf{b}$** ke liye pura $\tfrac23n^3$ reduction dobara karta hai, jo deta hai $k\cdot\tfrac23n^3$. Dono compare karne par, LU decisively jeet jaata hai jab bhi tumhare paas **ek se zyada** right-hand sides hain jo same $A$ share karte hain (extreme case $A^{-1}$ hai, jo $n$ right-hand sides $\mathbf{e}_1,\dots,\mathbf{e}_n$ hai). **Single** solve ke liye ($k=1$) dono costs essentially equal hain — LU *hai hi* elimination with bookkeeping — toh LU extra storage worth karna band ho jaata hai exactly tab jab tum jaante ho ki $A$ kabhi reuse nahi hoga. > [!mistake] L5 trap — yeh sochna ki LU hamesha ek Gaussian pass se faster hai > Students conclude karte hain "LU always beats elimination." **Single system ke liye yeh nahi hota** — LU *hai hi* elimination plus bookkeeping, toh ek solve ko same $\tfrac23n^3$ cost hota hai. Saving sirf **repeated** right-hand sides par (ya $A^{-1}$ build karne par, jo $n$ right-hand sides $\mathbf{e}_1,\dots,\mathbf{e}_n$ hai) dikhti hai. **Fix:** LU tab use karo jab $A$ reuse hogi; ek-off solve ke liye, plain elimination theek hai. --- > [!recall] Active recall > - Jab ek pivot zero ho, exactly kya break hota hai, aur kaun sa object usse repair karta hai? > - Jab tum $PA=LU$ use karte ho toh $\mathbf{b}$ permute kyun karna chahiye? > - Flop wajah do ki LU repeated Gaussian elimination se kyun behtar hai — aur woh ek case batao jahan yeh nahi hota.