implement partial row pivoting on a coefficient matrix during LU factorization

In this assignment you will implement partial row pivoting on a coefficient matrix during LU factorization. In notebook #21, we show an algorithm to transform a square coefficient matrix into upper triangular form U. Then we show a modified algorithm that transforms a square coefficient matrix into L+U+I form, where L is a canonical lower triangular matrix, U is the upper triangular form from the first algorithm, and I is the identity. Consider the coefficient matrix

$�=\left[\begin{array}{cccc}1& 0& 3& 0\\ 0& 1& 3& -1\\ 3& -3& 0& 6\\ 0& 2& 4& -6\end{array}\right]$

1. (20 points) Apply the initial upper triangular algorithm to this system. What issue do you observe? Demonstrate the problem in your notebook and explain the problem in a Markdown cell.

2. (20 points) Implement partial row pivoting in the upper triangular algorithm. The idea is to search all rows below the current row i in the row iteration to find the row j such that if rows i and j were swapped (exchanged), the swapped in row would have the largest diagonal element in absolute value.

3. (20 points) Implement partial row pivoting in the L+U+I form algorithm and save the indices of the rows that are pivoted in a data structure.

4. (20 points) Show A = LU. Note you need to first apply the same pivots to A.

5. (20 points) Use factors L and U to solve Ax = b for x where

$�=\left[\begin{array}{c}6\\ 0\\ 4\\ 3\end{array}\right]$

using the forward and backward substitution methods shown in notebook #21.