Homework 1 : Linear Algebra and Floating Point Arithmetic

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 $ϵ$ is defined as the smallest floating point number such that it holds: $fl(1+ϵ)>1$. Compute $ϵ$. 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:

$$A=\left[\begin{array}{cc}4& 2\\ 1& 3\end{array}\right]B=\left[\begin{array}{cc}4& 2\\ 2& 1\end{array}\right]$$

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.

---

Other assignments:

• Homework 2
• Homework 3
• Homework 4