41.2: Solve Linear Systems
( \newcommand{\kernel}{\mathrm{null}\,}\)
When we have the same number of equations as unknowns, we have the following system Ax=b with a square matrix A. In this section, we assume that the matrix A has full rank. That is the system has an unique solution. We talked about many ways to solve this system of equations. Some examples are:
- Jacobian iteration/ Gauss-Seidel iteration
- x=A−1b
- Gaussian elimination
- LU decomposition
In this assignment, we will show that we can solve it by QR decomposion.
Consider the following system of equations:
[5−224−344−67][x1x2x3]=[123]
Back substitution
Let’s first implement the back substitution in Python. The back substitution function back_subst
solves the system Rx=b where R is an upper-triangular matrix.
When we solve for x, we start with xn: xn=bnRn,n. Then we solve for xn−1 as xn−1=bn−1−Rn−1,nxnRn−1,n−1. Then we can find xn−2,⋯,x1: xn−2=bn−2−Rn−2,n−1xn−1−Rn−2,nxnRn−2,n−2. We can solve for all components of x in the reversed order. So this is called back substitution.
Complete the following code for back substitution.
When we solve for Ax=b with QR decomposition. We have the following steps:
- Find the QR decomposition of A
- From QRx=b, we obtain Rx=Q⊤b
- Solve for x using back substitution.
Use these steps to solve Ax=b with the given A and b. Compare the result with np.linalg.solve
.