数学代写|MAT361 Numerical Analysis

Exercise 14 (Convergence of the $\mathrm{cg}$ method)
Assume that $A \in \mathbf{R}^{n \times n}$ is symmetric positive definite with $p<n$ different eigenvalues. Consider the linear system $A x=b \in \mathbf{R}^n$ and show that in case of exact computations, for any initial iterate $x^0 \in \mathbf{R}^n$ the cg method terminates after at most $p$ steps with the solution $A^{-1} b$.
[Hint: Apply the the Cayley-Hamilton theorem together with estimates for the iteration error.]

Exercise 15 (Preconditioned $\mathrm{cg}$ method)
The numerical solution of two-point boundary value problems often gives rise to a symmetric matrix $A=\left(a_{i j}\right){i, j=1}^n \in \mathbf{R}^{n \times n}$, where $$ a{i j}=\left{\begin{array}{cll}
2 & \text { für } & i=j \
-1 & \text { für } & |i-j|=1 \
0 & \text { für } & |i-j| \geq 2
\end{array} \quad, \quad 1 \leq i, j \leq n .\right.
$$
(i) Show that $A$ is positive definite.
(ii) Let $D:=\operatorname{diag}(A)$ be the diagonal of $A$ and denote by $L$ the lower triangular part so that $A=L+D+L^T$.
Consider the linear system $A x=b, b \in \mathbf{R}^n$ and show that the preconditioned cg method with preconditioner $C:=E E^T$, where $E:=\frac{1}{2} D+L$, converges after at most two steps.
Hint: Observe that the convergence properties of the preconditioned cg method correspond to the original $\mathrm{cg}$ method applied to the transformed matrix $\tilde{A}:=$ $E^{-1} A E^{-T}$ and apply the result of Exercise 14.

Exercise 16 (cg method for the discrete Laplacian)
The discretization of the 2D Laplacian by finite differences with respect to a uniform grid results in a linear algebraic system with the symmetric coefficient $\operatorname{matrix} A=\left(a_{\ell j}\right)_{\ell, j=0}^{n-1} \in \mathbf{R}^{n \times n}, n=k^2, k \in \mathbf{N}$, where

Here, $\ell$ DIV $k$ stands for the integer part of $\ell / k$, whereas $\ell \operatorname{MOD} k \in{0, \ldots, k-1}$ denotes the rest of the division.
(i) Represent $A$ as a $k \times k$ block matrix and specify the individual blocks.
(ii) A vector $x=\left(x_0, \ldots, x_{n-1}\right)^T \in \mathbf{R}^n$ can be stored in a $k \times k$ array $\hat{x}$ as follows:
$$
x_{\ell}=\hat{x}[\ell \mathrm{DIV} k, \ell \mathrm{MOD} k] \quad, \quad 0 \leq \ell \leq n-1
$$
Using this ‘two-dimensional’ ordering of the components of the vector, the action of the matrix $A$ can be easily explained. Describe by means of a two-dimensional drawing how the components of $\hat{x}$ change under the mapping represented by the $\operatorname{matrix} A$.
Hint: $\hat{x}$ is a $k \times k$ array of certain values. In case of multiplication by $A$, a new value is assigned to each grid point which can be written as a weighted sum of other values. The weights in this sum correspond to the entries of $A$.

(iii) Assume that for $1 \leq \mu, \nu \leq k$ the vectors $e_{\mu, \nu} \in \mathbf{R}^n$ are stored in the $k \times k$ arrays $\hat{e}{\mu, \nu}$ of complex numbers. In this form, they can be represented according to $$ \hat{e}{\mu, \nu}[i, j]:=\sin \left(\pi \mu \frac{i+1}{k+1}\right) \sin \left(\pi \nu \frac{j+1}{k+1}\right) \quad, \quad 0 \leq i, j \leq k-1 .
$$
Show that $e_{\mu, \nu}$ is an eigenvector of $A$ corresponding to the eigenvalue
$$
\lambda_{\mu, \nu}=4\left(\sin ^2\left(\frac{\pi}{2} \frac{\mu}{k+1}\right)+\sin ^2\left(\frac{\pi}{2} \frac{\nu}{k+1}\right)\right) \text {. }
$$
(iv) Compute $\lambda_{\max }(A):=\max {|\lambda| ; \lambda \in \sigma(A)}, \lambda_{\min }(A):=\min {|\lambda| ; \lambda \in$ $\sigma(A)}$ and the spectral condition number
$$
\kappa(A):=\frac{\lambda_{\max }(A)}{\lambda_{\min }(A)}
$$
(v) Show that $A$ is positive definite.
(vi) Derive an estimate for the convergence rate of the cg method in the $A$ energy norm. How does the convergence behave in terms of $k$ ?

Consider the function $f(x)=\sin x$ near $x=0$.
(a) Write the Taylor polynomials $P_1(x), P_3(x)$ and $P_5(x)$.
(b) Graph $P_1(x), P_3(x)$ and $P_5(x)$ as well as $f(x)$ over $[0,2 \pi]$.
(c) Compute $P_1(0.1), P_3(0.1)$ and $P_5(0.1)$ and find the absolute and relative error.
(d) Compute $P_1(0.5), P_3(0.5)$ and $P_5(0.5)$ and find the absolute and rela tive error.
(e) Compute $P_1(1), P_3(1)$ and $P_5(1)$ and find the absolute and relative error.