課程名稱︰數值線性代數
課程性質︰數學系選修
課程教師︰薛克民
開課學院：理學院
開課系所︰數學系
考試日期（年月日）︰2017/01/10
考試時限（分鐘）：110
試題 :
Instructions:
● Total points 100
● Open books, notes, and laptop
● Answer the questions thoroughly and justify all your answers
1. (35 points) Given an arbitrary 2×2 real symmetric matrix written in the form
\[A = \begin{bmatrix}
w+z & \varepsilon\\
\varepsilon & z
\end{bmatrix}.\]
(a) (25 points) Perform the following shifted QR step:
\[A-zI = QR, \bar A = RQ+zI.\]
Show that
\[\bar A = \begin{bmatrix}
\bar x+\bar z & \bar\varepsilon\\
\bar\varepsilon & \bar z
\end{bmatrix},\]
where
\[
\bar z = z - \frac{\varepsilon^2w}{w^2+\varepsilon^2},
\bar w = w + 2\frac{\varepsilon^2w}{w^2+\varepsilon^2},
\bar\varepsilon = \frac{\varepsilon^3}{w^2+\varepsilon^3}.
\]
(b) (10 points) What does the result shown in (a) tell you about the conver-
gence of the QR-iteration for this type of matrix?
2. (20 points) Let $A \in \mathbf C^{m\times m}$, $x \in \mathbf C^m$, and $X =
\begin{bmatrix}x, Ax, \ldots, A^{m-1}x\end{bmatrix}$. If X is nonsingular,
show that $X^{-1}AX$ is an upper Hessenberg matrix.
3. (45 points) Let $A \in \mathbf R^{m\times m}$ be symmetric, $T_n = Q_n^TAQ_n
\in \mathbf R^{n\times n}$ be the projection of A onto the Krylov subspace
$\mathcal K_n$ (computed via Lanczos algorithm), and $r_n = b - Ax_n \in
\mathbf R^m$ be the residual where $x_n \in \mathcal K_n$ gives an approxi-
mate solution of Ax = b at the iteration step n. Assume that A is positive
definite also, i.e., $\langle v, Av\rangle = v^TAv > 0$, for any vector v and
$T_n$ is nonsingular.
(a) (15 points) Show that $x_n = Q_nT_n^{-1}e_1\|b\|_2$ minimizes
$\|r_n\|^2_{A^{-1}} = r_n^TA^{-1}r_n$, where $e_1 = \begin{bmatrix}1, 0,
\ldots, 0\end{bmatrix}$ is an n×1 vector.
(b) (15 points) Show that the minimization of $\|r_n\|_{A^{-1}}$ in (a) is
equivalent to minimizing the error in A-norm, i.e., $\|x-x_n\|_A$.
(c) (15 points) Show that $Q_n^Tr_n = 0$.