MA20222 Problem Sheet 8

E8.1. Let \(U\) be a non-singular upper triangular \(d \times d\) matrix such that \(U_{i j} = 0\) for \(i>j\) and \(U_{i i} \ne 0\). Consider the work involved in solving the system of \(d\) linear equations \(U \vec{x} = \vec{b}\) by backward substitution, where \(\vec{b} \in \mathbb{R}^d\) is given and \(\vec{x} \in \mathbb{R}^d\) is to be found. That is, we evaluate \[x_{d} % = \frac{b_{d}} {U_{dd}} \quad \text{and} \quad x_{i} % = \left(b_{i}-\sum_{j=i+1}^{d}U_{ij}x_{j}\right)\frac{1}{U_{ii}}, \quad i = d-1, d-2, \dots , 1.\]

Assuming that each addition, subtraction, multiplication or division counts as one (arithmetic) operation, count how many operations are required to compute \(x_{i}\), for each \(i\).
Hence establish how many operations are required in total to find \(\vec x\) and thus establish the complexity of the backward-substitution algorithm.

\(\star\)E8.2. Consider the linear system \[\begin{aligned} 2x_1 - x_2 + x_3 = &1\\ 2x_1 +2 x_2 +2 x_3 = &4\\ -x_1 - x_2 +2 x_3 = &-5.\end{aligned}\] Formulate the Jacobi and Gauss–Seidel iterations for this system. Perform one step of each iteration with the initial guess \(\vec x_0=[0,1,0]^{\top}\).

E8.3. Write down the definitions of the norms \(\|\cdot\|_\infty\), \(\|\cdot\|_1\), and \(\|\cdot\|_2\) for a vector \(\vec x\in \mathbb{R}^n\).

Compute \(\|\vec x\|_\infty\), \(\|\vec x\|_1\), and \(\|\vec x\|_2\) for \(\vec{x}=[1,-2]^{\top}\) and \(\vec x=[-1,2,-3]^{\top}\).

\(\star\)E8.4.

Show that \(\|\vec x\|:=\max_{i=1,\dots,d} x_i\) is not a vector norm on \(\mathbb{R}^d\).
Show that \(\|\vec x\|:=(\max_{i=1,\dots,d} \sqrt{|x_i|})^2\) is not a vector norm on \(\mathbb{R}^d\).

\(\star\)E8.5. For \(d\times d\) matrices \(A\) and \(B\), show conditions (a–d) for operator matrix norms by using properties of vector norms. Thus completing the proof of Theorem 5.1.

E8.6. Let \[A= \begin{bmatrix} 1 & 2 &3\\ 4 & 5 &6\\ 7 & 8 &9 \end{bmatrix}, \qquad B=A^{\top}.\] Compute \(\|\cdot\|_1\) and \(\|\cdot\|_\infty\) for \(A\) and \(B\).

E8.7.

From the definition \[\|A\|_{1} = \max_{\|\vec x\|_1=1} \| A\vec x\|_1,\] show that \(\| A\|_1 \leq \max_{1 \le j \le d}\sum_{i=1}^{d}|a_{ij}|\).

Now choose the vector \(\vec{x} = (0, \ldots,1,0, \ldots,0)^{\top}\), with a 1 in the \(k\)th position where \[\sum_{i=1}^{d}|a_{ik}| = \max_{1 \leq j \leq n}\sum_{i=1}^{n}|a_{ij}|,\] to deduce that \(\|A\|_1 = \max_{1 \le j \le d}\sum_{i=1}^{d}|a_{ij}|\).