Exercises — LU decomposition (numerical)

• $P$: diagonal ke upar entries $0$ hain → lower triangular. Diagonal hai $(1,1)$ → haan, ek valid Doolittle $L$ hai.
• $Q$: diagonal ke neeche entries $0$ hain → upper triangular. (Ye ek $U$ hai, $L$ nahi.)
• $R$: below-diagonal entry $1\ne 0$ hai, above-diagonal entry $0$ hai → lower triangular, lekin diagonal $(2,2)\ne (1,1)$ hai → ye Doolittle $L$ nahi hai (ye ek Crout-style $L$ hogi, dekho Crout Decomposition).
• $S$: upar aur neeche dono jagah nonzero entries hain → na upper na lower.

Ek triangular matrix ka determinant uski diagonal ka product hota hai (dekho Determinants). Toh $\det L=1\cdot 1\cdot 1=1,\det U=5\cdot 3\cdot (-2)=-30.$ Doolittle form mein $\det L=1$ hamesha hota hai, aur isliye $\det A=\det U=\prod u_{ii}$ hota hai.

$U$ ki Row 1 ($L$ ki top row $(1,0)$ hai): $u_{11}=4$, $u_{12}=3$. $L$ ka Column 1: ${\ell }_{21}=a_{21}/u_{11}=8/4=2$. $U$ ki Row 2: $u_{22}=a_{22}-{\ell }_{21}{u}_{12}=7-2\cdot 3=1$. $L=\left(\begin{array}{cc}1& 0\\ 2& 1\end{array}\right),U=\left(\begin{array}{cc}4& 3\\ 0& 1\end{array}\right).$ Check: $LU=\left(\begin{array}{cc}4& 3\\ 8& 7\end{array}\right)=A.$ ✓

Forward solve $L\mathbf{y}=\mathbf{b}$ (top-down, ek unknown per row): $y_1=10$; $2y_1+y_2=18\Rightarrow y_2=18-20=-2$. Back solve $U\mathbf{x}=\mathbf{y}$ (bottom-up): $1\cdot x_2=-2\Rightarrow x_2=-2$; $4x_1+3x_2=10\Rightarrow 4x_1=10-3(-2)=16\Rightarrow x_1=4$. $\boxed{\mathbf{x}=(4,-2{)}^{\top }}$ Sanity check: $A\mathbf{x}=(4\cdot 4+3(-2),8\cdot 4+7(-2))=(10,18)=\mathbf{b}.$ ✓

$U$ ki Row 1: $u_{11}=2,u_{12}=1,u_{13}=1$. $L$ ka Column 1: ${\ell }_{21}=4/2=2$, ${\ell }_{31}=8/2=4$. $U$ ki Row 2: $u_{22}=3-2\cdot 1=1$, $u_{23}=3-2\cdot 1=1$. $L$ ka Column 2: ${\ell }_{32}=\frac{a_{32}-{\ell }_{31}{u}_{12}}{u_{22}}=\frac{7-4\cdot 1}{1}=3$. $U$ ki Row 3: $u_{33}=a_{33}-{\ell }_{31}{u}_{13}-{\ell }_{32}{u}_{23}=9-4\cdot 1-3\cdot 1=2$. $L=\left(\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 4& 3& 1\end{array}\right),U=\left(\begin{array}{ccc}2& 1& 1\\ 0& 1& 1\\ 0& 0& 2\end{array}\right).$ Check: $LU=A$ (multiply karke confirm karo). ✓

Failure: $u_{11}=a_{11}=0$, toh ${\ell }_{21}=a_{21}/u_{11}=3/0$ — division by zero. Plain LU khatam ho jaata hai, even though $A$ perfectly invertible hai; problem sirf zero pivot ki hai, singularity ki nahi. Repair: rows swap karo taaki larger-magnitude entry ($3>0$) pivot par aa jaye. Ye swap permutation matrix hai (dekho Permutation Matrices) $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),PA=\left(\begin{array}{cc}3& 1\\ 0& 2\end{array}\right).$ Ab $PA$ par Doolittle karo: $u_{11}=3,u_{12}=1$; ${\ell }_{21}=0/3=0$; $u_{22}=2-0\cdot 1=2$. $L=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),U=\left(\begin{array}{cc}3& 1\\ 0& 2\end{array}\right),PA=LU.$ $A\mathbf{x}=\mathbf{b}$ solve karne ke liye tum $L\mathbf{y}=P\mathbf{b}$ solve karte, phir $U\mathbf{x}=\mathbf{y}$.

$|a_{21}|=3>|a_{11}|=1$, toh rows swap karo: $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, $PA=\left(\begin{array}{cc}3& 4\\ 1& 2\end{array}\right)$. $u_{11}=3,u_{12}=4$; ${\ell }_{21}=1/3$; $u_{22}=2-\frac{1}{3}\cdot 4=\frac{2}{3}$. $L=\left(\begin{array}{cc}1& 0\\ \frac{1}{3}& 1\end{array}\right),U=\left(\begin{array}{cc}3& 4\\ 0& \frac{2}{3}\end{array}\right).$ Multiplier $|{\ell }_{21}|=\frac{1}{3}\le 1$. ✓ Pivoting ke bina ${\ell }_{21}=3/1=3>1$ hota — pivoting ne multiplier ko chhota kar diya, jo rounding errors ko bounded rakhta hai (dekho Condition Number and Numerical Stability).

$A=LU$ (wahan koi swap nahi hua), toh $\det A=\det L\cdot \det U$. Doolittle form mein $\det L=1$ hota hai (ones ka product). Isliye $\det A=\det U={\prod }_i{u}_{ii}$. Agar $k$ row swaps use hue hote, toh har swap sign ek baar flip karta, jo $(-1{)}^k$ factor deta. Exercise 2.3 ke liye: $u_{11}{u}_{22}{u}_{33}=2\cdot 1\cdot 2=4$, aur koi swap nahi, toh $\det A=4$.

Yahi toh LU ka poora point hai: ek baar factor karo, kai baar solve karo (dekho Gaussian Elimination).

RHS 1. Forward $L\mathbf{y}={\mathbf{b}}^{(1)}$: $y_1=5$; $2\cdot 5+y_2=13\Rightarrow y_2=3$; $4\cdot 5+3\cdot 3+y_3=29\Rightarrow y_3=29-20-9=0$. Back $U\mathbf{x}=\mathbf{y}$: $2x_3=0\Rightarrow x_3=0$; $x_2+x_3=3\Rightarrow x_2=3$; $2x_1+x_2+x_3=5\Rightarrow 2x_1=5-3=2\Rightarrow x_1=1$. ${\mathbf{x}}^{(1)}=(1,3,0{)}^{\top }.$

RHS 2. Forward: $y_1=2$; $2\cdot 2+y_2=6\Rightarrow y_2=2$; $4\cdot 2+3\cdot 2+y_3=16\Rightarrow y_3=16-8-6=2$. Back: $2x_3=2\Rightarrow x_3=1$; $x_2+x_3=2\Rightarrow x_2=1$; $2x_1+x_2+x_3=2\Rightarrow 2x_1=2-2=0\Rightarrow x_1=0$. ${\mathbf{x}}^{(2)}=(0,1,1{)}^{\top }.$ Notice karo ki humne $L,U$ dono ke liye reuse kiye — koi elimination dobara nahi ki.