86. LU Decomposition

Given a matrix , LU decomposition aims to express as:

Where:

• : Lower triangular matrix (all elements above the diagonal are zero)
• : Upper triangular matrix (all elements below the diagonal are zero)

1. Solve Using Forward Substitution

Where:

• : Lower triangular matrix (all elements above the diagonal are zero)
• : Intermediate vector we are solving for
• : Right-hand side vector

• First row: , so

• Second row: , substitute into this equation and solve for :

• Third row: , substitute and into this equation, solve for :

2. Solve Using Backward Substitution

Where:

• : Upper triangular matrix (all elements below the diagonal are zero)
• : Vector of unknowns (solution)
• : Vector computed from the forward substitution step

• Third row: , so

• Second row: , substitute from the previous step and solve for :

• First row: , substitute and from the previous step and solve for :