prb4.tex (2751B)
1 \include{./preamble.tex} 2 3 \begin{document} 4 \maketitle 5 \tableofcontents 6 \section{Sheet 4} 7 \subsection{Problem 1} 8 Consider a linear system of equations $Ax = b$, where 9 \begin{align} 10 A = 11 \begin{pmatrix} 12 2 & -1 & 0 \\ 13 -1 & 2 & -1\\ 14 0 & -1 & 2 15 \end{pmatrix}, \qquad 16 b = 17 \begin{pmatrix} 18 4 \\ 0 \\ 0 19 \end{pmatrix}, 20 \end{align} 21 we carry out iterations of the CG method by hand until we reach the 22 solution with an initial guess $x_0 = \begin{pmatrix} 0 & 0 & 0 23 \end{pmatrix}^T$. For the sake of completeness the CG method has the following 24 iteration at the $k$-th step 25 \begin{align} 26 \alpha_k &= \frac{r_k^Tr_k}{p_k^TAp_k}\\ 27 x_{k+1} &= x_k + \alpha_k p_k\\ 28 r_{k+1} &= r_k - \alpha_k A p_k \\ 29 \beta_{k} &= \frac{r_{k+1}^Tr_{k+1}}{r_{k}^T r_k}\\ 30 p_{k+1} &= r_{k+1} + \beta_{k}p_k \\ 31 \end{align} 32 For $k=0$ we have 33 \begin{align} 34 r_0 &= b - Ax_0 = b,\\ 35 p_0 &= r_0 = b = \begin{pmatrix} 4 & 0 & 0 \end{pmatrix}^T. 36 \end{align} 37 For k=1 we have 38 \begin{align} 39 \alpha_0 &= \frac{1}{2}, \quad x_1=\begin{pmatrix} 2 \\ 0 \\0 40 \end{pmatrix}, \quad r_1 = \begin{pmatrix} 0 \\ 2 \\0 41 \end{pmatrix},\\ 42 \beta_0 &= \frac{1}{4},\quad p_1 = \begin{pmatrix} 1\\2\\0 43 \end{pmatrix}. 44 \end{align} 45 For k=2 we have 46 \begin{align} 47 \alpha_1 &= \frac{2}{3}, \quad x_2=\frac{1}{3}\begin{pmatrix} 8 \\ 4 \\0 48 \end{pmatrix}, \quad r_2 = \frac{1}{3}\begin{pmatrix} 0 \\ 0 \\4 49 \end{pmatrix},\\ 50 \beta_1 &= \frac{4}{9},\quad p_2 = \frac{1}{9}\begin{pmatrix} 4\\8\\12 51 \end{pmatrix}. 52 \end{align} 53 For k=3 we have 54 \begin{align} 55 \alpha_2 &= \frac{3}{4}, \quad x_3=\begin{pmatrix} 1 \\ 2 \\3 56 \end{pmatrix}, \quad r_3 = \begin{pmatrix} 0 \\ 0 \\0 57 \end{pmatrix},\\ 58 \beta_2 &= 0,\quad p_3 = \begin{pmatrix} 0\\0\\0 59 \end{pmatrix}. 60 \end{align} 61 Since $r_3 = \textbf{0}$ we can stop here, and $x_3 = x$ is the unique 62 solution. The Krylov space of $\mathcal{K}_k(A, b)$ is defined for $k=3$ as 63 \begin{align} 64 \mathcal{K}_3(A,b) = \text{span}\left\{b, Ab, A^2b \right\} = \text{span} \left\{ \begin{pmatrix} 0\\0\\4 \end{pmatrix}, 65 \begin{pmatrix} 8\\-4\\0 \end{pmatrix}, 66 \begin{pmatrix}26\\-16\\4\end{pmatrix}\right\} 67 \end{align} 68 the rank of the span of $\mathcal{K}_k(A,b)$ is full thereby the 69 $\dim(\mathcal{K}_k(A,b)) = 3$. Furthermore the residuals $r_0,\ldots, 70 r_{k-1}$ form an orthogonal basis for $\mathcal{K}_k(A,b)$. This can be 71 verified by checking that `key' elements in $\mathcal{K}_k(A, b)$ can be 72 expressed as a linear combination of $r_0, r_1, r_2$. 73 \begin{align} 74 b = 3\cdot r_2,\quad Ab = 2r_0-2r_1,\quad A^2b=6r_0-8r_1+3r_2. 75 \end{align} 76 \subsection{Exercise 3, 4} 77 Not important see notes is not easy 78 \end{document}