# Mandatory exercises

Consider the system $Ax = b$ where
\begin{equation}
    A=\begin{bmatrix}
        2 & 1 & 2\\
        1 & 0 & 3\\
        4 & -3 & -1
    \end{bmatrix}
    \text{ and }
    b=\begin{bmatrix}
        -3\\
        1\\
        -6
    \end{bmatrix}
\end{equation}

1. Perform the $LU$-factorization of the matrix $A$ by using Gaussian elimination with partial pivoting. Conclude by specifying $L$, $U$, and the permutation matrix $P$ . How is $A$ related to the matrices $L, U$ and $P$?


```python
import scipy.linalg
import scipy
import numpy as np

A = np.array([[2, 1, 2],
     [1, 0, 3],
     [4, -3, -1]])
P, L, U = scipy.linalg.lu(A)

print('A='+str(A))
print('P='+str(P))
print('L='+str(L))
print('U='+str(U))

print(scipy.dot(P.T,A))
print(scipy.dot(L,U))
```

    A=[[ 2  1  2]
     [ 1  0  3]
     [ 4 -3 -1]]
    P=[[0. 1. 0.]
     [0. 0. 1.]
     [1. 0. 0.]]
    L=[[1.   0.   0.  ]
     [0.5  1.   0.  ]
     [0.25 0.3  1.  ]]
    U=[[ 4.  -3.  -1. ]
     [ 0.   2.5  2.5]
     [ 0.   0.   2.5]]
    [[ 4. -3. -1.]
     [ 2.  1.  2.]
     [ 1.  0.  3.]]
    [[ 4.00000000e+00 -3.00000000e+00 -1.00000000e+00]
     [ 2.00000000e+00  1.00000000e+00  2.00000000e+00]
     [ 1.00000000e+00  1.11022302e-16  3.00000000e+00]]


2. Use $L$, $U$, and $P$ to solve the system $Ax = b$.

3. Suppose that you have represented the system of equations $Ax = b$ by storing variables $A$ and $b$.
    1. Write the Matlab/Python command that solves the system using Matlab’s 'backslash' operator/ Python function scipy.linalg.solve(), and stores the result in the variable $x$.
    2. Write the Matlab/Python command that LU-factorizes the matrix. Then, write the commands that use the result of the LU-factorization to solve $Ax = b$.

## If you have time

4. Perform the LU-factorization as in Exercise 1 above. However, instead of the permutation matrix $P$ , you should use a vector `piv` to keep track of the pivoting information. Write a script that uses `L`, `U` and `piv` to solve $Ax = b$. 

5. It is important that computational algorithms are efficient with regard to both (1) floating point operations and (2) memory requirements, and that they (3) are stable. For each of these aspects, mention some feature(s) of the algorithm used in Exercise 1 relating to that aspect.

6. True or false? (Give arguments to support your claim):
    1. You can improve the conditioning of a coefficient matrix by increasing the precision in the floating point number representation.
    2. Pivoting improves the condition number of the coefficient matrix.
    3. Pivoting improves the accuracy of the solution obtained.

# Non-mandatory exercises

7. Suppose that you are going to compute the forces in a truss structure. This leads to a system of linear equations, where the right-hand side contains the external forces acting on the truss. We consider a case where the coefficient matrix has condition number cond$_1(A)\approx10^3$ and the right-hand side is as follows (only two external forces acting on the truss):
\begin{equation}
    b=\begin{bmatrix}
        0\\
        \vdots\\
        0\\
        5000\\
        0\\
        6000\\
        0\\
        \vdots\\
        0
    \end{bmatrix}
\end{equation}
    1. The forces are measured in Newton (N), with an accuracy of $\pm$ 0.005N. What is the upper bound of the relative error in the right-hand side, in the 1-norm?
    2. Suppose that you want the solution to be computed with a relative error no larger than 1%, using the 1-norm. Can that be guaranteed in this case?
    3. What would be the upper bound of the relative error in the solution if the condition number was ca. $10^6$?

8. In what situations will you get a shorter execution time by using LU-factorization? Express the time gain as a formula in terms of suitable parameters.

9. The lab session for this course module contains an example concerning a diving board. In that application, the mathematical model after discretization is a system of linear equations where the coefficient matrix has a band structure. In addition, the matrix has further properties that make pivoting unnecessary. This is a very common situation in computer simulations. In such cases,the system of equations can be solved much faster if the band structure is taken advantage of. You should now investigate this in detail for the special case of a tridiagonal matrix A, assuming that pivoting is not required. An efficient implementation of Gaussian elimination for this case should make use of the fact that most of the elements in the lower triangle of A are already zero. Sketch a psuedo code for how to LU-factorize A when the tri-diagonal structure is taken into account. You can follow the lecture note or look up for the Thomas algorithm.

10. Show that by using the algorithm from the previous exercise, you will only need ca. $3n$ floating point operations to LU-factorize the tri-diagonal matrix $A$.

11. We now consider the general case, where $A$ is a full $n\times n$ matrix. Make your own, efficient implementation of LU-factorization with partial pivoting, in such a way that no explicit swapping of rows takes place. Use the integer vector piv to keep track of the ordering of the rows. Sketch your algorithm in pseudo code.

ce258a6e56199bf95d33b8ad08bf503efbd06683
ipynb
Jupyter Notebook
Workouts/Workout1.ipynb
enigne/ScientificComputingBridging
920f3c9688ae0e7d17cffce5763289864b9cac80
MIT
2021-05-04T01:15:32.000Z
2021-11-08T15:08:27.000Z
Workouts/Workout1.ipynb
enigne/ScientificComputingBridging
920f3c9688ae0e7d17cffce5763289864b9cac80
MIT
Workouts/Workout1.ipynb
enigne/ScientificComputingBridging
920f3c9688ae0e7d17cffce5763289864b9cac80
MIT
Qwen/Qwen-72B
1. YES
2. YES