# Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/August 2006
## Problem 1

* Consider the definite integral
* $I(f)=\int _{a}^{b}f(x)dx\!\,$
* Let $Q_{n}(f)\!\,$ denote the approximation of$I(f)\!\,$ by the composite midpoint rule with $n\!\,$ uniform subintervals. For every $j\in \mathbb {Z} \!\,$ set
* $x_{j}=a+j{\frac {b-a}{n}},\quad \quad x_{j+{\frac {1}{2}}}={\frac {x_{j}+x_{j+1}}{2}}\!\,$.
* Let $K(x)\!\,$ be defined by
* $K(x)=-{\frac {1}{2}}(x-x_{j})^{2},\quad x_{j-{\frac {1}{2}}}<x<x_{j+{\frac {1}{2}}}\!\,$.
* Assume that $f\in C^{2}([a,b])\!\,$.

## Problem 1a

* Show that the quadrature error $E_{n}(f)\!\,$ satisfies
* $E_{n}\equiv Q_{n}(f)-I(f)=\int _{a}^{b}K(x)f''(x)dx\!\,$
* Hint: Use integration by parts over each subinterval $[x_{j-1},x_{j}]\!\,$.

## Solution 1a

Integrating $\int K(x)f''(x)dx\!\,$ by parts over arbitrary points $p\!\,$ and $q\!\,$ gives
    $\int _{p}^{q}K(x)f''(x)dx=\left[(x-x_{j})f(x)-{\frac {1}{2}}(x-x_{j})^{2}f'(x)\right]_{x=p}^{x=q}-\int _{p}^{q}f(x)dx\!\,$
Since $K(x)\!\,$ is defined on $[x_{j-{\frac {1}{2}}},x_{j+{\frac {1}{2}}}]\!\,$ we use
    $[p,q]=[x_{j},x_{j+{\frac {1}{2}}}]\!\,$
and
    $[p,q]=[x_{j-{\frac {1}{2}}},x_{j}]\!\,$
Using the first interval we get
    ${\frac {1}{2}}\left[-{\frac {1}{4}}(x_{j+1}-x_{j})^{2}f'(x_{j+{\frac {1}{2}}})+(x_{j+1}-x_{j})f(x_{j+{\frac {1}{2}}})\right]\qquad \mathbf {(1)} \!\,$
And for the second we get
    ${\frac {1}{2}}\left[{\frac {1}{4}}(x_{j-1}-x_{j})^{2}f'(x_{j-{\frac {1}{2}}})+(x_{j}-x_{j-1})f(x_{j-{\frac {1}{2}}})\right]\qquad \mathbf {(2)} \!\,$
Since these apply to arbitrary half-subintervals, we can rewrite equation $\mathbf {(2)} \!\,$ with the its indecies shifted by one unit. The equation for the interval $[x_{j+{\frac {1}{2}}},x_{j+1}]\!\,$ is
    ${\frac {1}{2}}\left[{\frac {1}{4}}(x_{j}-x_{j+1})^{2}f'(x_{j+{\frac {1}{2}}})+(x_{j+1}-x_{j})f(x_{j+{\frac {1}{2}}})\right]\qquad \mathbf {(2')} \!\,$
Combining $\mathbf {(1)} \!\,$ and $\mathbf {(2')} \!\,$ and writing it in the same form as the integration by parts, we have
    $\int _{x_{j}}^{x_{j+1}}K(x)f''(x)dx=(x_{j+1}-x_{j})f(x_{j+{\frac {1}{2}}})-\int _{x_{j}}^{x_{j+1}}f(x)dx\!\,$
Then our last step is to sum this over all of our $n\!\,$ subintervals, noting that $x_{j+1}-x_{j}=(b-a)/n\!\,$
    ${\begin{aligned}\sum _{j=0}^{n-1}\int _{x_{j}}^{x_{j+1}}K(x)f''(x)dx&=\sum _{j=0}^{n-1}(x_{j+1}-x_{j})f(x_{j+{\frac {1}{2}}})-\sum _{j=0}^{n-1}\int _{x_{j}}^{x_{j+1}}f(x)dx\\\int _{a}^{b}K(x)f''(x)dx&={\frac {b-a}{n}}\sum _{j=0}^{n-1}f((x_{j}+x_{x+1})/2)-\int _{a}^{b}f(x)dx\\\int _{a}^{b}K(x)f''(x)dx&=Q_{n}(f)-I(f)\end{aligned}}$

## Problem 1b

* Derive a sharp bound on the error of the form
* $|E_{n}(f)|\leq M_{n}\|f''\|_{\infty }\!\,$ for every $f\in C^{2}([a,b])\!\,$.
* Here $\|\cdot \|_{\infty }\!\,$ denotes the maximum norm over $[a,b]\!\,$. Recall that the above bound is sharp when the inequality is an equality for some nonzero $f\!\,$.

## Solution 1b

Applying the result of part (a), the triangle inequality, and pulling out the constant $\|f(x)\|_{\infty }\!\,$, we have,
${\begin{aligned}|E_{n}(f)|&=|\int _{a}^{b}K(x)f^{\prime \prime }(x)dx|\\&\leq \int _{a}^{b}|K(x)||f^{\prime \prime }(x)|dx\\&\leq \|f^{\prime \prime }(x)\|_{\infty }\underbrace {\int _{a}^{b}|K(x)|dx} _{M_{n}}\end{aligned}}$
$M_{n}\!\,$ is some constant less than infinity since $[a,b]\!\,$ is compact and $|K(x)|\!\,$ is continuous on each of the finite number of intervals for which it is defined.
The above inequality becomes an equality when
    $f''(x)=c,$
where $c$ is any constant.

## Problem 2

* Consider the (unshifted) $QR-\!\,$ method for finding the eigenvalues of an invertible matrix $A\in \mathbb {R} ^{n\times n}\!\,$

## Problem 2a

* Give the algorithm.

## Solution 2a

The QR algorithm produces a sequence of similar matrices $\{A_{i}\}\!\,$ whose limit tends towards being upper triangular or nearly upper triangular. This is advantageous since the eigenvalues of an upper triangular matrix lie on its diagonal.

## Problem 2b

* Show that each of the matrices $A_{n}\!\,$ generated by this algorithm are orthogonally similar to $A\!\,$.

## Solution 2b

From the factor step (QR decomposition) of the algorithm, we have
    $A_{i}=Q_{i}R_{i}\!\,$
which implies
    $Q_{i}^{-1}A_{i}=R_{i}\!\,$
Substituting into the reverse multiply step, we have
${\begin{aligned}A_{i+1}&=R_{i}Q_{i}\\&=Q_{i}^{-1}A_{i}Q_{i}\end{aligned}}$

## Problem 2c

* Show that if $A\!\,$ is upper Hessenberg then so are each of the matrices $A_{n}\!\,$ generated by this algorithm.

## Solution 2c

A series of Given's Rotations matrices pre-multiplying $A\!\,$, a upper Heisenberg matrix, yield an upper triangular matrix$R\!\,$ i.e.
$G_{(n-1,n)}\cdots G_{(2,3)}G_{(1,2)}A=R\!\,$
Since Givens Rotations matrices are each orthogonal, we can write
    $A=\underbrace {(G_{(n-1,n)}\cdots G_{(2,3)}G_{(1,2)})^{T}} _{Q}R\!\,$
i.e.
    $A=QR\!\,$
If we let $A_{0}:=A\!\,$, we have $A_{0}=Q_{0}R_{0}\!\,$, or more generally for $k=1,2,3,\ldots \!\,$
    $A_{k}=Q_{k}R_{k}\!\,$.
In each case, the sequence of Given's Rotations matrices that compose $Q\!\,$ have the following structure
${\begin{aligned}Q&=G_{(1,2)}^{T}G_{2,3}^{T}\cdots G_{(n-1,n)}^{T}\\&={\begin{pmatrix}*&*&0&0&\cdots &0\\\!\,*&*&0&0&\cdots &0\\0&0&1&0&\cdots &0\\0&0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\0&0&\cdots &\cdots &0&1\\\end{pmatrix}}{\begin{pmatrix}1&0&0&0&\cdots &0\\0&*&*&0&\cdots &0\\0&*&*&0&\cdots &0\\0&0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\0&0&\cdots &\cdots &0&1\\\end{pmatrix}}\cdots {\begin{pmatrix}1&0&0&0&\cdots &0\\0&1&0&0&\cdots &0\\\vdots &\ddots &\ddots &\ddots &\ddots &0\\0&0&0&1&0&0\\0&0&0&0&*&*\\0&0&0&0&*&*\\\end{pmatrix}}\\&={\begin{pmatrix}*&*&*&\cdots &*\\\!\,*&*&*&\cdots &*\\0&*&*&\cdots &*\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&0&0&*&*\\\end{pmatrix}}\end{aligned}}$
So $Q\!\,$ is upper Hessenberg.
From the algorithm, we have
${\begin{aligned}A_{k+1}&=R_{k}Q_{k}\\&={\begin{pmatrix}*&*&*&\cdots &*\\0&*&*&\cdots &*\\0&0&*&\cdots &*\\\vdots &\vdots &\ddots &\ddots &\vdots \\0&0&0&0&*\\\end{pmatrix}}{\begin{pmatrix}*&*&*&\cdots &*\\\!\,*&*&*&\cdots &*\\0&*&*&\cdots &*\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&0&0&*&*\\\end{pmatrix}}\end{aligned}}$
We conclude $A_{k+1}\!\,$ is upper Hessenberg because for $j=1,2,\ldots ,n-2\!\,$ the $j\!\,$th column of $A_{k+1}\!\,$ is a linear combination of the first $j+1\!\,$ columns of $R_{k}\!\,$ since $Q_{k}\!\,$ is also upper Hessenberg.

## Problem 2d

* Let
* ${\begin{pmatrix}3&3\\1&5\end{pmatrix}}$
* For this $A\!\,$ the sequence $\{A_{n}\}\!\,$ has a limit. Find this limit. Give your reasoning.

## Solution 2d

The eigenvalues of $A\!\,$ can be computed. They are $6\!\,$ and $2\!\,$. Furthermore, the result of matrix multiplies in the algorithm shows that the diagonal difference, $(a_{1,2}-a_{2,1})\!\,$, is constant for all $i\!\,$.
Since the limit of $A\!\,$ is an upper triangular matrix with the eigenvalues of $A\!\,$ on the diagonal, the limit is
    ${\begin{pmatrix}6&2\\0&2\end{pmatrix}}\!\,$

## Problem 3

* Let $A\in \mathbb {R} ^{N\times N}\!\,$ be symmetric and positive definite. Let $b\in \mathbb {R} ^{N}\!\,$. Consider solving $Ax=b\!\,$ using the conjugate gradient method. The $n^{th}\!\,$ iterate $x^{(n)}\!\,$ then satisfies
* $\|x^{(n)}-x\|_{A}\leq \|y-x\|_{A}\!\,$ for every $y\in x^{(0)}+{\mathcal {K}}_{n}(r^{(0)},A)\!\,$,
* where $\|\cdot \|_{A}\!\,$ denotes the vector A-norm, $r^{(0)}\!\,$ is the initial residual, and
* ${\mathcal {K}}_{n}(r^{(0)},A)={\mbox{span}}\{r^{(0)},Ar^{(0)},\dots ,A^{n-1}r^{(0)}\}\!\,$.

## Problem 3a

* Prove that the error $x^{(n)}-x\!\,$ is bounded by
* $\|x^{(n)}-x\|_{A}\leq \|p_{n}(A)\|_{A}\|x^{(0)}-x\|_{A}\!\,$,
* where $p_{n}(z)\!\,$ is any real polynomial of degree $n\!\,$ or less that satisfies $p_{n}(0)=1\!\,$. Here $\|p_{n}(A)\|_{A}\!\,$ denotes the matrix norm of $p_{n}(A)\!\,$ that is induced by the vector A-norm.

## Solution 3a

We know that $\|x^{(n)}-x\|_{A}\leq \|y-x\|_{A}\!\,$ for every $y\in x^{(0)}+{\mathcal {K}}_{n}(r^{(0)},A)\!\,$, so if we can choose a $y\in x^{(0)}+{\mathcal {K}}_{n}(r^{(0)},A)\!\,$ such that
    $\|x^{(n)}-x\|_{A}\leq \|y-x\|_{A}\leq \|p_{n}(A)\|_{A}\|x^{(0)}-x\|_{A}\!\,$,
then we can solve part a.

### Rewrite r^(0)

First note from definition of $r^{(0)}\!\,$
${\begin{aligned}r^{(0)}&=Ax^{(0)}-b\\&=Ax^{(0)}-Ax\\&=A(x^{(0)}-x)\end{aligned}}$

### Rewrite Krylov space

Therefore, we can rewrite ${\mathcal {K}}_{n}(r^{(0)},A)\!\,$ as follows:
${\begin{aligned}{\mathcal {K}}_{n}(r^{(0)},A)&={\mathcal {K}}_{n}(A(x^{(0)}-x),A)\\&={\mbox{span}}\{A(x^{(0)}-x),A^{2}(x^{(0)}-x),\ldots ,A^{n}(x^{(0)}-x)\}\end{aligned}}$

### Write y explicitly

We can then write $y\!\,$ explicitly as follows:
${\begin{aligned}y&\in x_{0}+{\mathcal {K}}_{n}(r^{(0)},A)\\&\in x_{0}+{\mathcal {K}}_{n}(A(x^{(0)}-x),A)\\&=x_{0}+\alpha _{1}A(x^{(0)}-x)+\alpha _{2}A^{2}(x^{(0)}-x)+\ldots +\alpha _{n}A^{n}(x^{(0)}-x)\\&{\mbox{for arbitrary real numbers }}\alpha _{i}\quad i=1,2,\ldots ,n\end{aligned}}$

### Substitute and Apply Inequality

We substitute $y\!\,$ into the hypothesis inequality and apply a norm inequality of matrix norms to get the desired result.
${\begin{aligned}\|x^{(n)}-x\|_{A}&\leq \|y-x\|_{A}\\&=\|(x_{0}-x)+\alpha _{1}A(x^{(0)}-x)+\alpha _{2}A^{2}(x^{(0)}-x)+\ldots +\alpha _{n}A^{n}(x^{(0)}-x)\|_{A}\\&=\|\alpha _{n}A^{n}(x^{(0)}-x)+\alpha _{n-1}A^{n-1}(x^{(0)}-x)+\ldots +\alpha _{2}A^{2}(x^{(0)}-x)+\alpha _{1}A(x^{(0)}-x)+(x_{0}-x)\|_{A}\\&=\|P(A)(x^{(0)}-x)\|_{A}\\&\leq \|P(A)\|_{A}\|x^{(0)}-x\|_{A}\end{aligned}}$

## Problem 3b

* Let $T_{n}(z)\!\,$ denote the $n^{th}\!\,$ Chebyshev polynomial. Let $\lambda _{min}\!\,$ and $\lambda _{max}\!\,$ denote respectively the smallest and largest eigenvalues of $A\!\,$. Apply the result of part (a) to
* $p_{n}(z)={\frac {T_{n}({\frac {\lambda _{max}+\lambda _{min}-2z}{\lambda _{max}-\lambda _{min}}})}{T_{n}({\frac {\lambda _{max}+\lambda _{min}}{\lambda _{max}-\lambda _{min}}})}}$
* to show that
* $\|x^{(n)}-x\|_{A}\leq {\frac {1}{T_{n}({\frac {\lambda _{max}+\lambda _{min}}{\lambda _{max}-\lambda _{min}}})}}\|x^{(0)}-x\|_{A}$.
* You can use without proof the fact that
* $\|p_{n}(A)\|_{A}=\max\{|p_{n}(z)|:z\in Sp\{A\}\}\!\,$,
* where $Sp(A)\!\,$ denotes the set of eigenvalues of $A\!\,$, and the facts that for every $n\in \mathbb {N} \!\,$ the polynomial $T_{n}(z)\!\,$ has degree $n\!\,$, is positive for $z>1\!\,$, and satisfies
* $T_{n}(\cos(\theta ))=\cos(n\theta )\quad \quad {\mbox{for all}}\;\theta \in \mathbb {R} \!\,$.

## Solution 3b
### Overview

We want to show that
$\|p_{n}(A)\|_{A}={\frac {1}{T_{n}({\frac {\lambda _{\max }+\lambda _{\min }}{\lambda _{\max }-\lambda _{\min }}})}}\!\,$

### Maximize Numerator of p_n(z)

By hypothesis,
    $\|p_{n}(A)\|_{A}=\max\{|p_{n}(z)|:z\in Sp\{A\}\}\!\,$
Since only the numerator of $p_{n}(z)\!\,$ depends on $z\!\,$, we only need to maximize the numerator in order to maximize $|p_{n}(z)|\!\,$. That is find
    $z:\max _{z\in [\lambda _{\min },\lambda _{\max }]}\left|T_{n}\left({\frac {\lambda _{\max }+\lambda _{\min }-2z}{\lambda _{\max }-\lambda _{\min }}}\right)\right|\!\,$

### Rewrite T_n

Let $\cos(\theta )=x\!\,$. Then
    $\theta =\arccos(x)\!\,$
Hence,
${\begin{aligned}T_{n}(\cos \theta )&=T_{n}(x)\\&=\cos(n\theta )\\&=\cos(n\arccos(x))\end{aligned}}$
so
    $T_{n}(x)=\cos(n\arccos(x))\!\,$

### Max of T_n is 1

Denote the argument of $T_{n}\!\,$ as $x(z)\!\,$ since the argument depends on $z\!\,$. Hence,
    $x(z)={\frac {\lambda _{\max }+\lambda _{\min }-2z}{\lambda _{\max }-\lambda _{\min }}}\!\,$,
Then,
    $x(\lambda _{\min })={\frac {\lambda _{\max }-\lambda _{\min }}{\lambda _{\max }-\lambda _{\min }}}=1\!\,$
    $x(\lambda _{\max })={\frac {\lambda _{\min }-\lambda _{\max }}{\lambda _{\max }-\lambda _{\min }}}=-1\!\,$
Thus $x(z)\in [-1,1]\!\,$.
Now, since $\;\arccos(x)\;$ is real for $x\in [-1,1]\!\,$,
    $-1\leq \underbrace {\cos(n\overbrace {\arccos(x)} ^{\in \mathbb {R} })} _{T_{n}(x)}\leq 1\!\,$
Hence,
    $\max _{x\in [-1,1]}T_{n}(x)=\max _{x\in [-1,1]}|\cos(n\arccos(x))|=1\!\,$

### Show T_n(1)=1

Let $z=\lambda _{\min }\!\,$, then
$\left|T_{n}\left({\frac {\lambda _{\max }+\lambda _{\min }-2(\lambda _{\min })}{\lambda _{\max }-\lambda _{\min }}}\right)\right|=|T_{n}(1)|\!\,$
Using our formula we have,
${\begin{aligned}|T_{n}(1)|&=|\cos(n\cdot \arccos(1))|\\&=|\cos(n\cdot 2\pi k)|\quad k\in \mathbf {Z} \\&=1\end{aligned}}$
In other words, if $z=\lambda _{\min }\!\,$, $T_{n}\!\,$ achieves its maximum value of $1\!\,$.