prb3.tex (9236B)
1 \include{preamble.tex} 2 3 \usepackage[final]{pdfpages} 4 5 \begin{document} 6 \maketitle 7 \tableofcontents 8 \section{Sheet 3} 9 \subsection{Problem 1} 10 Take a linear system $Ax = b$, where $A \in \mathbb{R}^{n\times n}$ and $b 11 \in \mathbb{R}^{n}$. We want to solve it using the Gradient decent method, an 12 iteration 13 \begin{align} 14 x^{k+1} = x^{k} + \alpha_k r^{k}, 15 \end{align} 16 where $r^{k} = b - Ax^{k}$ and the residual $\alpha_k= \frac{(r^{k})^T 17 r^k}{(r^k)^T Ar^k}$. 18 \subsubsection{} 19 We compute $x^1$ for 20 \begin{align} 21 A = 22 \begin{pmatrix} 23 2 & -1 \\ 24 -1 & 2 25 \end{pmatrix}, 26 \qquad 27 b = \begin{pmatrix}1 \\ 1 \end{pmatrix}, 28 \end{align} 29 with an initial guess $x^0 = 0$. 30 \begin{align} 31 r^0 = \begin{pmatrix} 1 & 1 \end{pmatrix} \qquad 32 Ar^0 = \begin{pmatrix} 1 & 1 \end{pmatrix} \quad \Rightarrow \quad 33 \alpha_0 = 1. 34 \end{align} 35 Then for $x^1$ we have 36 \begin{align} 37 x^1 = \begin{pmatrix} 0 \\ 0 \end{pmatrix} + \begin{pmatrix}1 \\ 38 1 \end{pmatrix} = b 39 \end{align} 40 \subsubsection{} 41 Suppose the $k$-th error $e^k = x - x^k$ is an eigenvector of $A$ to the 42 eigenvalue $\lambda$, then 43 \begin{align} 44 A e^{k}=\lambda e^{k} = \lambda (x^{k}-x) = \lambda x^{k} - \lambda x. 45 \end{align} 46 For the next iteration step we need $r^{k}$ which is 47 \begin{align} 48 r^{k} &= b - Ax^{k} + Ax - Ax = (b - Ax) - A(x^{k} - x) = -\lambda e^{k}\\ 49 (r^k)^{T} r^k &= \lambda^2 (e^k)^{T}e^{k}\\ 50 (r^k)^{T} A r^k &= \lambda^3 (e^k)^{T}e^{k}\\ 51 \Rightarrow \alpha_k &= \frac{1}{\lambda} 52 \end{align} 53 Then the next step $x^{k+1}$ is 54 \begin{align} 55 x^{k+1} = x^{k}+\alpha_k r^{k} = x^{k}-\frac{\lambda}{\lambda}e^{k} = 56 x^{k} - e^{k} = x^{k}-x^{k}+ x = x, 57 \end{align} 58 i.e. $x^{k+1}$ is then the solution. 59 \subsection{Exercise 2} 60 We show the norm equivalence of the vector norms $ \|\cdot\|_\infty$ and 61 $\|\cdot\|_2$ and the optimality of the constants $C, C' > 0$and the 62 optimality of the constants $C, C' > 0$ 63 \subsubsection{} 64 We show 65 \begin{align} 66 \|v\|_\infty = \max_i |v_i| \leq \sqrt{\sum_{i}^{} v_i^2} \quad 67 \Rightarrow \quad C = 1. 68 \end{align} 69 Then 70 \begin{align} 71 \|v\|_2 = \sqrt{\sum_i v_i^2} \le \sqrt{\sum_i \max_i |v_i|^2} = 72 \sqrt{\sum_i \|v\|^2_\infty} = \sqrt{n} \|v\|_\infty. 73 \end{align} 74 We get 75 \begin{align} 76 \|v\|_\infty \le \|v\|_2 \le \sqrt{n} \|v\|_\infty. 77 \end{align} 78 For $u := \frac{v}{\|v\|_\infty} \; \Rightarrow \; \|v\|_\infty = 1$ we get 79 \begin{align} 80 1 \le \|u\|_2 \le \sqrt{n} 81 \end{align} 82 which states optimality of the constants. 83 \subsection{Problem 3} 84 Now we do the same as in Problem 2 but with matrix norms induced by vector 85 norms, specifically for $\|\cdot\|_2$ and $\|\cdot\|_\infty$ matrix norms 86 induced by vector norms. 87 \subsubsection{} 88 We know that 89 \begin{align} 90 \|A\|_2 = \max_{v\neq 0} \frac{\|Ax\|_2}{\|x\|_2} \qquad \|A\|_2 &= 91 \rho(A^*A)\\ 92 \|A\|_\infty = \max_{i,j} |a_{ij}| 93 \end{align} 94 Together with the norm inequalities 95 \begin{align} 96 \|Av\|_\infty &\le \|A\|_\infty \|v\|_\infty\\ 97 \|A\|_2^2 = \rho(A^TA) \le \|A^TA\|_\infty\\ 98 \Rightarrow \|\rho(A^TA)\|_\infty = \|A^TA x\|_\infty \le \|A^T 99 A\|_\infty \|x\|_\infty, 100 \end{align} 101 thereby 102 \begin{align} 103 \|A^T A\|_\infty &= \max_{i,j} \left|(A^T A)_{ij})\right| = \max_{i,j} 104 \left| \sum_l A_{il} A_{lj} \right| \\ 105 &=\max_{i,j} \sum_l \left| A_{il} A_{lj} \right| \leq n 106 \|A\|_\infty^2\\ 107 \nonumber\\ 108 \Rightarrow \|A\|_2 &\leq \sqrt{n} \|A\|_\infty 109 \end{align} 110 \subsubsection{} 111 Let $A \in \mathbb{C}^{n\times n}$, $b \in \mathbb{C}^n$ defined as 112 \begin{align} 113 A = 114 \begin{pmatrix} 115 1 & \cdots & 1 \\ 116 0 & \cdots & 0 \\ 117 \vdots & \vdots &\vdots \\ 118 0 & \cdots & 0 119 \end{pmatrix} \qquad b = \begin{pmatrix} 1 \\ \vdots \\ 1 120 \end{pmatrix} 121 \end{align} 122 Then $Ab = \begin{pmatrix} n & 0 & \cdots & 0 \end{pmatrix}^T$ and the 123 $\|\cdot\|_2$ of $A$ is 124 \begin{align} 125 \|A\|_2 = \max_{v\neq 0} \frac{\|Av\|_2}{\|v\|} = \frac{\|Ab\|_2}{\|b\|} 126 = \frac{n}{\sqrt{n}} = \sqrt{n} 127 \end{align} 128 \subsubsection{} 129 Let $A$ be defined as above, we show that $\|A\|_\infty = \sqrt{n} \|A\|_2$, 130 where $C = \sqrt{n} $ is optimal 131 \begin{align} 132 \|A\|_\infty = \max_i \sum_j |A_{ij}| = n = \sqrt{n} \sqrt{n} = \sqrt{n} 133 \|A\|_2, 134 \end{align} 135 thereby $C$ is optimal. 136 \subsubsection{} 137 We show that $\|A\|_2 \le \sqrt{n} \|A\|_\infty$ for all $A \in 138 \mathbb{C}^{n\times n}$, and equality holds for $A$ whose columns are all 139 zero, accept the first one filled with ones. We know the norms 140 $\|\cdot\|_2$ and $\|\cdot\|_\infty$ are induced by vector norms which are 141 consistent. Then for all $v \in \mathbb{C}^{n}$ we have 142 \begin{align} 143 \|v\|_\infty &\le\sqrt{n} \|v\|_2\\ 144 \Leftrightarrow \|A\|_\infty &\le \sqrt{n} \|A\|_2 \qquad\ \forall \ A 145 \in \mathbb{C}^{n\times n}. 146 \end{align} 147 \subsection{Problem 4} 148 Let $\langle x, y \rangle$ be the standard Euclidean scalar product on 149 $\mathbb{R}^n$ and $\|\cdot\|_2$ the Euclidean norm. Let $B\in 150 \mathbb{R}^{n\times n}$ be an antisymmetric matrix, i.e. $B^T = -B$. And let 151 $A:= I - B$ 152 \subsubsection{} 153 We show that for all $x \in \mathbb{R}^{n}$ we have $\langle Bx, x\rangle =0$ 154 and $\langle Ax, x\rangle = \|x\|_2^2$. 155 \begin{align} 156 \langle Bx, x\rangle = (Bx)^T x = x^T B^T x = -x^T B x\\ 157 (-x^TBx)^T &= x^TBx\; \Rightarrow\; x^T Bx = jx^TBx\\ 158 \Rightarrow 2x^T B x &= 2 \langle Bx, x\rangle = 0. 159 \end{align} 160 And the second statement follows from the previous equation 161 \begin{align} 162 \langle Ax, x\rangle &= \rangle\left(I-B\right)x,x\rangle \\ 163 &=\langle x, x\rangle - \underbrace{\langle Bx, 164 x\rangle}_{=0} = \langle x, x\rangle = 165 \|x\|_2^2 166 \end{align} 167 \subsubsection{} 168 We show that $\|Ax\|_2^2 = \|x\|_2^2 + \|Bx\|_2^2$ and that $\|A\|_2 = 169 \sqrt{1+\|B\|_2^2}$. We start with the vector norm 170 \begin{align} 171 \|Ax\|^2_2 172 &= \|x - Bx\|_2^2 \\ 173 &= \langle x -Bx, x-Bx\rangle \\ 174 &= (x^T - x^T B^T)(x - Bx)\\ 175 &= x^T x - x^T B^T x - x^T Bx + x^T B^T Bx\\ 176 &= x^T x + x^TB^TBx = \|x\|_2^2 + \|Bx\|_2^2 177 \end{align} 178 where $i, j$ run from $1$ to $n$. Then the vector induced norm follows 179 \begin{align} 180 \|A\|_2^2 181 &= \|I-B\|_2^2 = \sup_{x\neq 0} \frac{\|Ax\|_2^2}{\|x\|^2_2}\\ 182 &= \sup_{x\neq 0} \frac{\|x\|^2_2 +\|Bx\|_2^2 }{\|x\|_2^2} = 1+ 183 \sup_{x\neq 0}\frac{\|Bx\|_2^2}{\|x\|^2_2}= 1+\|B\|_2^2, 184 \end{align} 185 pulling the square root on both sides gives us the answer. 186 \subsubsection{} 187 We show that $A$ is invertible and the inverse matrix norm is given 188 \begin{align} 189 \|A^{-1}\|^2 = \max_{x\neq}\frac{\|x\|^2}{\|Ax\|^2} 190 \end{align} 191 To show that $A$ is invertible we use the Rank-Nullity Theorem 192 \begin{align} 193 n &=\text{rg}(A) + \dim\text{Im}(A)\\ 194 \Rightarrow n - \dim\text{Im}(A) = rg(A). 195 \end{align} 196 If $A$ is invertible it has maximal rank that means $\dim \text{Im}(A) = 0$. 197 Let's look what the image of A is 198 \begin{align} 199 Ax = 0 \Rightarrow \|Ax\|_2^2 = \|x\|_2^2 + \|Bx\|_2^2 = 0 200 \end{align} 201 holds only for $x = 0$, thereby $\dim \text{Im}(A) = 0$ and the rank is 202 maximal. Now let $A^{-1}y =x$ then 203 \begin{align} 204 \frac{\|A^{-1}y\|_2}{\|y\|_2} &= \frac{\|x\|_2}{\|Ax\|_2}\\ 205 \Rightarrow \|A^{-1}\|_2 &= \max_{x\neq 0} \frac{\|x\|_2}{\|Ax\|_2}. 206 \end{align} 207 \subsubsection{} 208 Next we show that $\|A^{-1}\|_2 \le 1$. 209 \begin{align} 210 \|A^{-1}\|_2 = \max_{x\neq 0} \frac{\|x\|_2}{\|Ax\|_2} = 211 \frac{1}{\sqrt{1+\|B\|_2^2}} \le 1 212 \end{align} 213 \subsection{Problem 5} 214 We take $A$ and $B$ from last exercise. 215 \subsubsection{} 216 We show that for $k \in \{1,\ldots,m\}$ and $\mathcal{W} \subset 217 \mathbb{R}^n$ with $\dim \mathcal{W} = k$ spanned by $w_1,\ldots,w_k \in 218 \mathbb{R}^n$. We show that if $x \in \mathcal{W}$ is such that 219 \begin{align} 220 \langle Ax, w\rangle = \langle b , w \rangle \qquad \forall w\in 221 \mathcal{W}. 222 \end{align} 223 then $\|x\|_2 \le \|b\|_2$. We can choose $b = x$ then 224 \begin{align} 225 \langle Ax, x\rangle &= \|x\|_2^2 = \langle b, x\rangle \leq 226 \|b\|_2\|x\|_2.\\ 227 \Rightarrow \|x\|_2 \le \|b\|_2 228 \end{align} 229 \subsubsection{} 230 Next we show that for $x :=\sum_j c_j w_j$ and 231 \begin{align} 232 \sum_j c_j \langle Aw_j, w_i\rangle = \langle b , w_i\rangle 233 \end{align} 234 for $i = 1, \ldots , k$, we have a unique solution for $x \in \mathcal{W}$. 235 We do this by showing that every solution is the 0 solution $b=0$ 236 \begin{align} 237 \langle 0 , w\rangle = 0 = \langle Ax ,x \rangle = \|x\|_2^2. 238 \end{align} 239 \subsubsection{} 240 Lastly for $x^* := A^{-1}b$ we show and inequality relation 241 \begin{align} 242 \|x^* - x\|_2 \le \|A\|_2 \min_{x \in \mathcal{W}}\|x^* -w\|_2. 243 \end{align} 244 (We take the minimum $w = x$ and calculate) 245 \begin{align} 246 \|x^* - x\|_2^2 247 &= \langle A(x^* -x), x^* - x\rangle\\ 248 &= \langle A(x^* -x), x^* - x +w -w\rangle\\ 249 &= \langle A(x^* -x), x^* - w\rangle + \langle A(x^* -x), w - x\rangle\\ 250 &= \langle A(x^* -x), x^* - w\rangle +\underbrace{\langle A(x^* -x), w - 251 x\rangle}_{=0}\\ 252 \le \|A\|_2 \|x^* - x\|_2\|x^* - w\|. 253 \end{align} 254 When we take the minimum and divide by $\|x^* - x\|_2$ we get 255 \begin{align} 256 \|x^* - x\| \le \|A\|_2\min_{x\in\mathcal{W}} \|x^* - w\|_2. 257 \end{align} 258 259 %\printbibliography 260 \end{document}