HW 1: Linear Algebra and Floating Point Arithmetic

HW 1: Linear Algebra and Floating Point Arithmetic#

Warning

The submission of the homeworks has NO deadline. You can submit them whenever you want, on Virtuale. You are only required to upload it on Virtuale BEFORE your exam session, since the Homeworks will be a central part of the oral exam.

You are asked to submit the homework as one of the two, following modalities:

  • A PDF (or Word) document, containing screenshoots of code snippets, screeshots of the results generated by your code, and a brief comment on the obtained results.

  • A Python Notebook (i.e. a .ipynb file), with cells containing the code required to solve the indicated exercises, alternated with a brief comment on the obtained results in the form of a markdown cell. We remark that the code SHOULD NOT be runned during the exam, but the student is asked to enter the exam with all the programs already executed, with the results clearly visible on the screen.

Joining the oral exam with a non-executed code OR without a PDF file with the obtained results visible on that, will cause the student to be rejected.

Direct Methods for the solution of Linear Systems#

  1. Given a matrix \(A \in \mathbb{R}^{n \times n}\), the vector \(x_{true} = (1,1,...,1)^T \in \mathbb{R}^n\), and a value for \(n\), write a script that:

    • Computes the right-hand side of the linear system \(y = A x_{true}\) (test problem).

    • Computes the condition number in 2-norm of the matrix \(A\). It is ill-conditioned? What if we use the \(\infty\)-norm instead of the 2-norm?

    • Solves the linear system \(Ax = y\) with the function np.linalg.solve().

    • Computes the relative error between the computed solution and the true solution \(x_{true}\).

    • Plot a graph (using matplotlib.pyplot) with the relative errors as a function of \(n\) and (in a different window) the condition number in 2-norm and in \(\infty\)-norm, as a function of \(n\).

  2. Test the program above with the following choices of \(A \in \mathbb{R}^{n \times n}\):

    • A random matrix (created with the function np.random.rand()) with size varying in \(n = \{10, 20, 30, ..., 100\}\).

    • The Vandermonde matrix (np.vander) with dimension \(n= \{5,10,15,20,25,30\}\) with respect to the vector \(v = {1,2,3,...,n}\).

    • The Hilbert matrix (scipy.linalg.hilbert) with dimension \(n= \{4, 5, 6, ..., 12\}\).

Floating point arithmetic#

  1. The Machine epsilon \(\epsilon\) is defined as the smallest floating point number such that it holds: \(fl(1 + \epsilon) > 1\). Compute \(\epsilon\). Tips: use a while structure.

  2. Let’s consider the sequence \(a_n = (1 + \frac{1}{n})^n\). It is well known that: \(\lim_{n \to \infty} a_n = e\), where \(e\) is the Nepero number. Choose different values for \(n\), compute \(a_n\) and compare it to the real value of the Nepero number. What happens if you choose a large value of \(n\)?

  3. Let’s consider the matrices:

\[\begin{split} A = \begin{bmatrix} 4 & 2 \\ 1 & 3 \end{bmatrix} \quad B = \begin{bmatrix} 4 & 2 \\ 2 & 1 \end{bmatrix} \end{split}\]

Compute the rank of \(A\) and \(B\) and their eigenvalues. Are \(A\) and \(B\) full-rank matrices? Can you infer some relationship between the values of the eigenvalues and the full-rank condition? Please, corroborate your deduction with other examples. Tips: Please, have a look at np.linalg.

Contents