Foundations — LU decomposition (numerical)

4.8.19 · D1 · Maths › Numerical Methods › LU decomposition (numerical)

Is page par assume kiya gaya hai ki tum kuch nahi jaante. Hum har symbol earn karenge — $A$, $\mathbf{x}$, $\mathbf{b}$, "triangular", $L$, $U$, ${\ell }_{ij}$, $u_{ij}$, $P$ — usse pehle ki parent note unhe use kare.

1. "Linear system" kya hota hai? ($A\mathbf{x}=\mathbf{b}$)

Maan lo do mystery numbers hain, jinhe hum $x_1$ aur $x_2$ kehte hain, jo do rules follow karte hain:

$2x_1+3x_2=5,6x_1+13x_2=35.$

Har rule linear hai: unknowns sirf fixed numbers se multiply hokar aur add hokar aate hain — koi squares nahi, koi unknowns ka product nahi. Woh pair $(x_1,x_2)$ dhundhna jo dono ko satisfy kare, yahi ek linear system solve karna hai.

Multipliers, unknowns aur answers ko alag-alag likhne se teen objects milte hain.

Humare example ke liye: $A=\left(\begin{array}{cc}2& 3\\ 6& 13\end{array}\right),\mathbf{x}=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right),\mathbf{b}=\left(\begin{array}{c}5\\ 35\end{array}\right).$

Poora system ek single line $A\mathbf{x}=\mathbf{b}$ mein compress ho jaata hai.

Picture kya dikhati hai: $A$ ki row $i$ ko $\mathbf{x}$ ke saath pair karne se equation $i$ ki left side milti hai; red column $\mathbf{b}$ answers rakhta hai. Toh $A\mathbf{x}=\mathbf{b}$ exactly woh do equations hain, bas saaf karke likhi hui.

Row-phir-column ka order matter karta hai — har baar ise "row $i$, column $j$" bolke yaad karo.

2. Matrix ko vector se multiply karna — "row dot" picture

$A$ ko factor karne se pehle hume jaanna hai ki $A\mathbf{x}$ ek operation ke roop mein kya hai.

Humare $A$ ki row 1 deti hai $2x_1+3x_2$ — yahi equation 1 ki left side hai. Yahi puri wajah hai ki matrix form faithful hai.

Matrix-times-matrix ($LU$, aage aayega) same move hai baar baar: product ki entry $(i,j)$ pehle matrix ki row $i$ aur doosre matrix ki column $j$ ka dot product hai.

Picture kya dikhati hai: red row black column ke upar slide karti hai; har aligned pair multiply hoti hai aur products ek single output slot mein sum hote hain. Is ek motion ko master karo aur har LU formula readable ban jaayega.

3. "Triangular" ka matlab kya hai, aur hum ise kyun chahte hain?

Picture kya dikhati hai: black cells = numbers jo nonzero ho sakte hain, white cells = forced zeros. $L$ lower wedge fill karta hai, $U$ upper wedge; jahaan woh overlap karte hain (diagonal par) dono mein numbers hote hain.

Hum triangular systems kyun chahte hain. Ek upper-triangular system dekho: $\begin{array}{rl}4x_2& =20\\ 2x_1+3x_2& =5\end{array}$ Aakhri equation mein sirf ek unknown hai: $x_2=5$ ek dam se. Ise upar feed karo aur agli equation mein bhi ek hi unknown hoga. Koi grind nahi — bas ek variable ek time par padho. Is process ko back substitution kehte hain ($U$ ke liye bottom-up) aur iska twin forward substitution ($L$ ke liye top-down) hai. Dekho Forward and Back Substitution.

Toh agar hum mushkil matrix $A$ ko do triangular matrices mein rewrite kar sakein, to solve karna effortless ho jaayega. Yahi wish exactly LU decomposition hai.

4. Elimination move (jahaan ${\ell }_{ij}$ paida hota hai)

Triangle banana ke liye hum Gaussian Elimination ka ek legal move use karte hain:

Example: row 2 hai $(6,13)$, row 1 hai $(2,3)$. Leading $6$ ko zero karne ke liye $m=6/2=3$ chahiye, jisse naya row 2 $=(6,13)-3(2,3)=(0,4)$ banta hai. System ab triangular hai.

Isliye parent note keh sakta hai "${\ell }_{ij}$ Gaussian-elimination multipliers hain." Ab yeh phrase ek picture carry karta hai: $m$'s ki ek table.

5. Jab move fail hota hai: zero pivot aur $P$

Agar woh pivot $0$ hai, to division explode ho jaata hai. Lekin all-zero column zaroori nahi hai — kabhi-kabhi humne rows sirf ek unlucky order mein choose ki hoti hain. Ilaaj yeh hai ki rows swap karo taaki ek nonzero (ideally sabse bada) number pivot par aa jaaye. Dekho Partial Pivoting.

Swaps ke saath honest statement ban jaata hai $PA=LU$: pehle reorder karo, phir factor karo. Sabse bada pivot choose karna har $|{\ell }_{ij}|\le 1$ bhi rakhta hai, jo rounding errors ko balloon hone se rokta hai — Condition Number and Numerical Stability ki accuracy concern.

6. Do free gifts jo yeh symbols dete hain

• Determinant. Ek triangular matrix ka determinant sirf uski diagonal ka product hota hai. Kyunki Doolittle ke $L$ ki diagonal all-1 hai ($\det L=1$), $\det A=(-1{)}^{\text{swaps}}{\prod }_i{u}_{ii}$.
• Reuse. Kyunki $L$ aur $U$ sirf $A$ par depend karte hain (na ki $\mathbf{b}$ par), ek naya right-hand side sirf do triangular solves ki cost leta hai. Ek baar factor karo, kai baar solve karo.

Prerequisite map

Equipment checklist

Right side cover karo aur khud ko test karo. Agar koi bhi answer fuzzy lage, parent note se pehle woh section dobara padho.

Connections

• Parent topic ↑
• Gaussian Elimination · Forward and Back Substitution · Partial Pivoting · Permutation Matrices
• Determinants · Condition Number and Numerical Stability · Crout Decomposition · Cholesky Decomposition