prb1.tex (11523B)
1 \include{preamble.tex} 2 3 \usepackage{scratch} 4 5 \begin{document} 6 \maketitle 7 \tableofcontents 8 \section{Sheet 1} 9 \subsection{Problem 1} 10 Consider the following two matrices $A, L_1 \in \mathbb{R}^{4 \times 4}$ 11 defined in as 12 \begin{align} 13 A := 14 \begin{pmatrix} 15 2 & 1 & 1 & 0 \\ 16 4 & 3 & 3 & 1 \\ 17 8 & 7 & 9 & 5 \\ 18 6 & 7 & 9 & 8 19 \end{pmatrix}, 20 \qquad 21 L_1 := 22 \begin{pmatrix} 23 1 & 0 & 0 & 0\\ 24 x & 1 & 0 & 0\\ 25 y & 0 & 1 & 0\\ 26 z & 0 & 0 & 1 27 \end{pmatrix} 28 ,\end{align} 29 for $x, y, z \mathbb{R}$. 30 31 To show that $A$ is invertible, we need to show it has maximal rank, that 32 is $\text{rank}(A) = 4$. We can do this by doing Gaussian elimination 33 steps until $A$ is of the form of a upper triangular matrix 34 \begin{gather} 35 \begin{bmatrix} 36 2 & 1 & 1 & 0 \\ 37 4 & 3 & 3 & 1 \\ 38 8 & 7 & 9 & 5 \\ 39 6 & 7 & 9 & 8 40 \end{bmatrix} 41 \begin{matrix} 42 \\ 43 -2 \cdot I\\ 44 -4 \cdot I\\ 45 -3 \cdot I 46 \end{matrix} \quad 47 \longrightarrow 48 \begin{bmatrix} 49 2 & 1 & 1 & 0 \\ 50 0 & 1 & 1 & 1 \\ 51 0 & 3 & 5 & 5 \\ 52 0 & 4 & 6 & 8 53 \end{bmatrix} 54 \begin{matrix} 55 \\ 56 \\ 57 -3 \cdot II\\ 58 -4 \cdot II 59 \end{matrix} \quad 60 \longrightarrow 61 \begin{bmatrix} 62 2 & 1 & 1 & 0 \\ 63 0 & 1 & 1 & 1 \\ 64 0 & 0 & 2 & 2 \\ 65 0 & 0 & 2 & 4 66 \end{bmatrix} 67 \begin{matrix} 68 \\ 69 \\ 70 \\ 71 -1 \cdot III 72 \end{matrix} \quad 73 \label{eq: gelim1} 74 \\ 75 \longrightarrow 76 \begin{bmatrix} 77 2 & 1 & 1 & 0 \\ 78 0 & 1 & 1 & 1 \\ 79 0 & 0 & 2 & 2 \\ 80 0 & 0 & 0 & 2 81 \end{bmatrix} \quad 82 \underset{\text{det}}{\longrightarrow} \quad 8 83 \label{eq: gelim2} 84 .\end{gather} 85 86 Next we will determine $x, y$ and $z$, s.t. $(L_1A)_{\cdot, 1} = 87 \begin{pmatrix} 2 & 0 & 0 & 0 \end{pmatrix} $ by solving the linear 88 system 89 \begin{align} 90 L_1 A = 91 \begin{pmatrix} 92 2 & 1 & 1 & 0 \\ 93 2x+4 & x+3 & x+3 & 1\\ 94 2y+8 & y+7 & y+9 & 5\\ 95 2z+6 & z+7 & z+9 & 8\\ 96 \end{pmatrix} 97 ,\end{align} 98 we get $x = -2$, $y = -4$ and $z=-3$ and thereby 99 \begin{align} 100 L_1 A = 101 \begin{pmatrix} 102 1 & 0 & 0 & 0\\ 103 -2 & 1 & 0 & 0\\ 104 -4 & 0 & 1 & 0\\ 105 -3 & 0 & 0 & 1 106 \end{pmatrix} 107 \begin{pmatrix} 108 2 & 1 & 1 & 0 \\ 109 4 & 3 & 3 & 1 \\ 110 8 & 7 & 9 & 5 \\ 111 6 & 7 & 9 & 8 112 \end{pmatrix}= 113 \begin{pmatrix} 114 2 & 1 & 1 & 0 \\ 115 0 & 1 & 1 & 1\\ 116 0 & 3 & 5 & 5\\ 117 0 & 3 & 5 & 8\\ 118 \end{pmatrix} 119 .\end{align} 120 In an analogous structure we may define $L_2, L_3 \in \mathbb{R}^{4\times4}$, 121 s.t. 122 \begin{align} 123 L_3L_2L_1A=U, 124 \end{align} 125 where $U$ is an upper triangular matrix. We may notice that this is an LU 126 decompositions of a matrix and can be determined by the inversion of a 127 single step of Gaussian elimination. By that the three steps needed to 128 achieve the upper triangular by Gaussian elimination are introduced 129 in \ref{eq: gelim1} and \ref{eq: gelim2}, that is also why $-2, -4, -3$ aligns up with $L_1$. 130 To summarize, by looking at \ref{eq: gelim1} and \ref{eq: gelim2} the matrices $L_2, L_3$ are 131 the following 132 \begin{align} 133 L_2 = 134 \begin{pmatrix} 135 1 & 0 & 0 & 0\\ 136 0 & 1 & 0 & 0\\ 137 0 & -3 & 1 & 0\\ 138 0 & -4 & 0 & 1 139 \end{pmatrix}, \qquad 140 L_3 = 141 \begin{pmatrix} 142 1 & 0 & 0 & 0\\ 143 0 & 1 & 0 & 0\\ 144 0 & 0 & 1 & 0\\ 145 0 & 0 & -1 & 1 146 \end{pmatrix}. 147 \end{align} 148 And by no calculation we know that $U$ needs to be the upper triangular 149 found in \ref{eq: gelim2}, i.e. 150 \begin{align} 151 L_3L_2L_1A = U = 152 \begin{pmatrix} 153 2 & 1 & 1 & 0 \\ 154 0 & 1 & 1 & 1 \\ 155 0 & 0 & 2 & 2 \\ 156 0 & 0 & 0 & 2 157 \end{pmatrix}. 158 \end{align} 159 We have indeed preformed an LU decomposition of $A$, which is indeed 160 useful for solving a linear system of the form 161 \begin{align} 162 A x &= b \qquad \text{and} \quad L_3L_2L_1A = U,\\ 163 (L_3L_2L_1A)x = Ux &= L_3L_2L_1b = y\\ 164 \Rightarrow Ux &= y, 165 \end{align} 166 where the system is recursively solvable as $U$ is the upper triangular 167 and no additional transformation steps are required only ''plug and 168 play``. 169 \subsection{Problem 2} 170 Next we consider $A_\varepsilon \in \mathbb{R}^{2 \times 2}$ defined as 171 \begin{align} 172 A_\varepsilon := 173 \begin{pmatrix} 174 \varepsilon & 1\\ 175 1 & 1 176 \end{pmatrix}, 177 \end{align} 178 for $\varepsilon > 0$. The inverse of $A_\varepsilon$ is 179 \begin{align} 180 A_\varepsilon^{-1} = \frac{1}{\text{det}(A_\varepsilon)} 181 \text{adj}(A_\varepsilon) = 182 \frac{1}{\varepsilon - 1} \begin{pmatrix} 1 & -1 \\ -1 & \varepsilon \end{pmatrix} 183 \end{align} 184 Now let $\|x\|_\infty = \max\{|x_1|, |x_2|\}$ be the maximum norm of $x \in 185 \mathbb{R}^{2}$, and $\|A_\varepsilon\|_\infty$ the induced matrix norm of 186 $A_\varepsilon$. We can show that 187 \begin{align} 188 \lim_{\varepsilon \to 0} K(A_\varepsilon) = 4, 189 \end{align} 190 where $K(A_\varepsilon) = \|A_\varepsilon\|_\infty 191 \|A_\varepsilon^{-1}\|_\infty$ is the condition number of $A_\varepsilon$. 192 \begin{align} 193 \|A_\varepsilon\|_\infty &= \|\begin{pmatrix} \varepsilon + 1 & 1 + 1 194 \end{pmatrix} \|_\infty = 2\\ 195 \|A_\varepsilon^{-1}\|_\infty &= 196 \|\begin{pmatrix} \mid -\frac{2}{\varepsilon-1} \mid & 1 \end{pmatrix} \|_\infty 197 = \frac{2}{1-\varepsilon}, 198 \end{align} 199 and thereby 200 \begin{align} 201 \lim_{\varepsilon \to 0} K(A_\varepsilon)=\lim_{\varepsilon \to 0} 2\cdot 202 \frac{2}{1-\varepsilon} = 4 203 \end{align} 204 If we preformed an LU decomposition of $A_\varepsilon$ like in the first 205 problem to get an upper diagonal the decompostion would be 206 \begin{align} 207 LA_\varepsilon &= 208 \begin{pmatrix} 1 & 0 \\ -\frac{1}{\varepsilon} & 1 \end{pmatrix} 209 \begin{pmatrix} \varepsilon & 1 \\ 1 & 1 \end{pmatrix} \\ 210 &= 211 \begin{pmatrix} \varepsilon & 1 \\ 0 & 1 - \frac{1}{\varepsilon} 212 \end{pmatrix} = U_\varepsilon, 213 \end{align} 214 with the inverse 215 \begin{align} 216 U_\varepsilon^{-1}= \frac{1}{\varepsilon -1} 217 \begin{pmatrix}1-\frac{1}{\varepsilon} & -1 \\ 0 & \varepsilon 218 \end{pmatrix} . 219 \end{align} 220 The condition number of the resulting upper triangular matrix 221 $U_\varepsilon$, $K(U_\varepsilon)$ as $\varepsilon \rightarrow 0$ is 222 \begin{align} 223 \|U_\varepsilon\|_\infty &= \|\begin{pmatrix} \varepsilon + 1 & 224 \mid 1-\frac{1}{\varepsilon} \mid \end{pmatrix} \|_\infty = \frac{1}{\varepsilon} - 225 1\\ 226 \|U_\varepsilon^{-1}\|_\infty &= 227 \|\begin{pmatrix} \mid \frac{1- \frac{1}{\varepsilon}}{\varepsilon 228 -1} \mid & \mid\frac{\varepsilon}{\varepsilon-1} \mid \end{pmatrix} 229 \|_\infty = \frac{1}{\varepsilon(\varepsilon - 1)}\\ 230 \Longrightarrow 231 \lim_{\varepsilon \to 0}K(U_\varepsilon) &= \lim_{\varepsilon \to 0} 232 \frac{1-\varepsilon}{\varepsilon}\frac{1}{\varepsilon(1 - 233 \varepsilon)} = \infty. 234 \end{align} 235 But if we on the other hand considered a pivoting step in which we exchange 236 the rows of $A_\varepsilon$ 237 \begin{align} 238 PA_\varepsilon = A_\varepsilon' = 239 \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix} 240 \begin{pmatrix} \varepsilon & 1 \\ 1 & 1 \end{pmatrix} 241 = 242 \begin{pmatrix}1 & 1 \\ \varepsilon & 1 \end{pmatrix} 243 \end{align} 244 Then the P-LU decomposition is 245 \begin{align} 246 L'A_\varepsilon' = 247 \begin{pmatrix} 1 & 0 \\ -\varepsilon & 1 \end{pmatrix} 248 \begin{pmatrix}1 & 1 \\ \varepsilon & 1 \end{pmatrix} 249 = 250 \begin{pmatrix}1 & 1 \\ 0 & 1 - \varepsilon \end{pmatrix} = 251 U_\varepsilon', 252 \end{align} 253 with the inverse 254 \begin{align} 255 (U_\varepsilon')^{-1} = \frac{1}{1-\varepsilon} 256 \begin{pmatrix} 1-\varepsilon & - 1\\ 0 & 1 \end{pmatrix}. 257 \end{align} 258 Then the condition number as $\varepsilon \rightarrow 0$ 259 \begin{align} 260 \|U_\varepsilon'\|_\infty 261 &= \|\begin{pmatrix} 2 & 1-\varepsilon \end{pmatrix} \|_\infty = 2\\ 262 \|\left(U_\varepsilon'\right)^{-1} \|_\infty 263 &= \|\begin{pmatrix} 264 \frac{1-\varepsilon + 1}{1 - \varepsilon} & \frac{1}{1-\varepsilon} 265 \end{pmatrix} \| = \frac{2-\varepsilon}{1-\varepsilon}\\ 266 \Longrightarrow 267 \lim_{\varepsilon \to 0}K(U_\varepsilon') &= \lim_{\varepsilon \to 0} 268 2\cdot \frac{2-\varepsilon}{1-\varepsilon} = 2\cdot2 = 4 269 \end{align} 270 \subsection{Problem 3} 271 Let $v \in \mathbb{R}^n$, $n \in \mathbb{N}$ and $v \neq 0$. We define the Housholder 272 matrix 273 \begin{align} 274 H = \text{Id} - \frac{2}{\langle v, v \rangle}v v^T. 275 \end{align} 276 Indeed $H$ is an orthogonal matrix, it satisfies $H H^T = H^T H = \text{Id}$. 277 \begin{align} 278 H H^T 279 &= 280 \left( \text{Id} - \frac{2}{\langle v, v \rangle}vv^T\right) 281 \left( \text{Id} - \frac{2}{\langle v, v \rangle}vv^T\right)^T\\ 282 &= 283 \left( \text{Id} - \frac{2}{\langle v, v \rangle}vv^T\right) 284 \left( \text{Id} - \frac{2}{\langle v, v \rangle}(vv^T)^T\right)\\ 285 &= 286 \left( \text{Id} - \frac{2}{\langle v, v \rangle}vv^T\right) 287 \left( \text{Id} - \frac{2}{\langle v, v \rangle}vv^T\right)\\ 288 &= \text{Id} - \frac{4}{\langle v, v \rangle} vv^T + \frac{4}{\langle v, 289 v \rangle^2} (v v^T)(v v^T)\\ 290 &= \text{Id} - \frac{4}{\langle v, v \rangle} vv^T + \frac{4}{\langle v, 291 v \rangle} (v v^T) = \text{Id} 292 \\ 293 \nonumber\\ 294 H^T H &= 295 \left( \text{Id} - \frac{2}{\langle v, v \rangle}vv^T\right) 296 \left( \text{Id} - \frac{2}{\langle v, v \rangle}vv^T\right)\\ 297 &= \text{Id} 298 \end{align} 299 Let us look at the projection of some $x \in \mathbb{R}^n$ in the $v$ 300 direction is given by 301 \begin{align} 302 \frac{\langle v, x \rangle}{\langle v, v \rangle} v, 303 \end{align} 304 The projection of $x$ in the orthogonal direction is 305 \begin{align} 306 x - \frac{\langle v, x \rangle}{\langle v, v \rangle} v, 307 \end{align} 308 A reflection of $x$ in $v$ has $-1$ times the projection onto $v$, that $x$ 309 has onto $v$, so the orthogonal projection of the reflection onto $v$ is the 310 orthogonal projection of $x$ onto $v$, therefor the reflection in $v$ of $x$ 311 is 312 \begin{align} 313 x - 2\frac{\langle v, x \rangle}{\langle v, v \rangle} v, 314 \end{align} 315 if we wanted to reflect $x$ on the line spanned by $v$ we would have to 316 subtract the vector $\frac{\langle v, x \rangle}{\langle v, v \rangle} v$ 317 twice, graphically it would look like this 318 \begin{figure}[H] 319 \centering 320 \begin{tikzpicture}[ 321 xscale = 1.5, 322 yscale = 1.5, 323 rotate = 30 324 ] 325 \draw[->] (0, 0) -- (1, 1) node[right] {$x$}; 326 \draw[->] (0, 0) -- (2, 0) node[right] {$v$}; 327 \draw[dotted, very thick] (1, 1) -- (1, 0); 328 \draw[dotted, very thick] (1, 0) -- (1, -1); 329 \draw[->] (0, 0) -- (1, 0) node[midway, below] {$x_v$}; 330 \draw[->] (0, 0) -- (1, -1) node[below] {$Hx$}; 331 \end{tikzpicture} 332 \end{figure} 333 The Household matrix acting on a vector $x$, $Hx$ is exactly the above case 334 since vector multiplication is associative we have 335 \begin{align} 336 Hx &= x - \frac{2}{\langle v, v \rangle} vv^T x\\ 337 &= x - 2\frac{\langle v, x\rangle}{\langle v, v \rangle} v 338 \end{align} 339 The condition number of an orthogonal matrix $A$ in the $\|\cdot\|_2$ induced 340 norm is 341 \begin{align} 342 K(A) = \|A\|_2 \|A^{-1}\|_2 = 1, 343 \end{align} 344 because the orthogonal matrix preserves distance, i.e. $\|Ax\|_2 = \|x\|_2$ 345 for all $x$. Also $A^{-1} =A^T$ is orthogonal as well 346 \begin{align} 347 \|A\|_2 = \sup_{x\neq 0} \frac{\|Ax\|_2}{\|x\|_2} = \sup_{x \neq 0} \frac{\|x\|_2}{\|x\|_2} = 348 1 349 \end{align} 350 %\printbibliography 351 \end{document} 352