MSE3114 Computational Methods for Physicists and Materials Engineers - Assignment 4: LU decomposition and QR decomposition

Q1. (LU decomposition) Write a python code for solving a system of linear equations by LU decomposition. Written in matrix form, a system of linear equations is expressed as $Ax=b$. The pivoted LU decomposition on $A$ gives $A=PLU$. Then, the equations become $PLUx=b$. We can firstly solve $Lz=P^{T}b$ for $z$ by the forward substitution, and finally solve $Ux=z$ for $x$ by the backward substitution. CourseNana.COM

1. Define a function plu_decomposition(A) which takes in $A$, does pivoted LU decomposition by scipy.linalg.lu(), and returns the permutation matrix $P$, the lower triangular matrix $L$ and the upper triangular matrix $U$. 
2. Define a function forward_subs(L, PTb) which takes in $L$ and $P^{T}b$, does forward substitution, and returns the result $z$ after forward substitution. 
3. Define a function backward_subs(U, z) which takes in $U$ and $z$, does backward substitution, and returns the result $x$ after backward substitution. 
4. Define a function solve_by_lu_decomp(A, b) which takes in $A$ and $b$, does LU decomposition by calling plu_decomposition(A) defined in Q1.1, print out the result of LU decomposition (i.e., $P$, $L$ and $U$), does forward substitution by calling forward_subs() defined in Q1.2 on $L$ and $P^{T}b$ and returns $z$, does backward_substitution by calling backward_subs() defined in Q1.3 on $U$ and $z$ and returns the solution $x$. 
5. Apply the function solve_by_lu_decomp(A, b) defined in Q1.4 to solve the following equations:$$\left(\begin{array}{ccc}3& 2& -3\\ 1& -4& -1\\ 7& 1& 31\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}1\\ 9\\ -12\end{array}\right).$$
6. Solve the same equations in Q1.5 by scipy.linalg.solve() directly. 

(60 marks) CourseNana.COM

Q2. (QR decomposition) Write a python code for solving a system of linear equations by QR decomposition. Written in matrix form, a system of linear equations is expressed as $Ax=b$. The QR decomposition on $A$ gives $A=QR$. Then, the equations become $QRx=b$. We can solve $Rx=Q^{T}b$ for $x$ by the backward substitution. CourseNana.COM

1. Define a function qr_decomposition(A) which takes in $A$, does QR decomposition by scipy.linalg.qr(), and returns the orthogonal matrix $Q$ and the upper triangular matrix $R$. 
2. Define a function solve_by_qr_decomp(A, b) which takes in $A$ and $b$, does QR decomposition by calling qr_decomposition(A) defined in Q2.1, print out the result of QR decomposition (i.e., $Q$ and $R$), does backward_substitution by calling backward_subs() defined in Q1.3 on $R$ and $Q^{T}b$ and returns the solution $x$. 
3. Apply the function solve_by_qr_decomp(A, b) defined in Q2.2 to solve the following equations:$$\left(\begin{array}{ccc}13& 2& -3\\ 1& -44& -1\\ 7& 1& 1\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}1\\ 0.9\\ -1\end{array}\right).$$
4. Solve the same equations in Q2.3 by scipy.linalg.solve() directly. 

(40 marks) CourseNana.COM