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

## Problem 1

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

## Problem 1a

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

## Solution 1a

Integrating ${\displaystyle \int K(x)f''(x)dx\!\,}$ by parts over arbitrary points ${\displaystyle p\!\,}$ and ${\displaystyle q\!\,}$ gives

${\displaystyle \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 ${\displaystyle K(x)\!\,}$ is defined on ${\displaystyle [x_{j-{\frac {1}{2}}},x_{j+{\frac {1}{2}}}]\!\,}$ we use

${\displaystyle [p,q]=[x_{j},x_{j+{\frac {1}{2}}}]\!\,}$

and

${\displaystyle [p,q]=[x_{j-{\frac {1}{2}}},x_{j}]\!\,}$

Using the first interval we get

${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle \mathbf {(2)} \!\,}$ with the its indecies shifted by one unit. The equation for the interval ${\displaystyle [x_{j+{\frac {1}{2}}},x_{j+1}]\!\,}$ is

${\displaystyle {\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 ${\displaystyle \mathbf {(1)} \!\,}$ and ${\displaystyle \mathbf {(2')} \!\,}$ and writing it in the same form as the integration by parts, we have

${\displaystyle \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 ${\displaystyle n\!\,}$ subintervals, noting that ${\displaystyle x_{j+1}-x_{j}=(b-a)/n\!\,}$

{\displaystyle {\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 ${\displaystyle |E_{n}(f)|\leq M_{n}\|f''\|_{\infty }\!\,}$ for every ${\displaystyle f\in C^{2}([a,b])\!\,}$. Here ${\displaystyle \|\cdot \|_{\infty }\!\,}$ denotes the maximum norm over ${\displaystyle [a,b]\!\,}$. Recall that the above bound is sharp when the inequality is an equality for some nonzero ${\displaystyle f\!\,}$.

## Solution 1b

Applying the result of part (a), the triangle inequality, and pulling out the constant ${\displaystyle \|f(x)\|_{\infty }\!\,}$, we have,

{\displaystyle {\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}}}

${\displaystyle M_{n}\!\,}$ is some constant less than infinity since ${\displaystyle [a,b]\!\,}$ is compact and ${\displaystyle |K(x)|\!\,}$ is continuous on each of the finite number of intervals for which it is defined.

The above inequality becomes an equality when

${\displaystyle f''(x)=c,}$

where ${\displaystyle c}$ is any constant.

## Problem 2

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

## Problem 2a

 Give the algorithm.

## Solution 2a

The QR algorithm produces a sequence of similar matrices ${\displaystyle \{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.

i = 0
A_1 = A
while ( error > tolerance  )
A_i=Q_i R_i  (QR decomposition/factorization)
A_{i+1}=R_i Q_i (multiply R and Q, the reverse multiplication)
i=i+1 (increment)


## Problem 2b

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

## Solution 2b

From the factor step (QR decomposition) of the algorithm, we have

${\displaystyle A_{i}=Q_{i}R_{i}\!\,}$

which implies

${\displaystyle Q_{i}^{-1}A_{i}=R_{i}\!\,}$

Substituting into the reverse multiply step, we have

{\displaystyle {\begin{aligned}A_{i+1}&=R_{i}Q_{i}\\&=Q_{i}^{-1}A_{i}Q_{i}\end{aligned}}}

## Problem 2c

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

## Solution 2c

A series of Given's Rotations matrices pre-multiplying ${\displaystyle A\!\,}$, a upper Heisenberg matrix, yield an upper triangular matrix${\displaystyle R\!\,}$ i.e.

${\displaystyle G_{(n-1,n)}\cdots G_{(2,3)}G_{(1,2)}A=R\!\,}$

Since Givens Rotations matrices are each orthogonal, we can write

${\displaystyle A=\underbrace {(G_{(n-1,n)}\cdots G_{(2,3)}G_{(1,2)})^{T}} _{Q}R\!\,}$

i.e.

${\displaystyle A=QR\!\,}$

If we let ${\displaystyle A_{0}:=A\!\,}$, we have ${\displaystyle A_{0}=Q_{0}R_{0}\!\,}$, or more generally for ${\displaystyle k=1,2,3,\ldots \!\,}$

${\displaystyle A_{k}=Q_{k}R_{k}\!\,}$.

In each case, the sequence of Given's Rotations matrices that compose ${\displaystyle Q\!\,}$ have the following structure

{\displaystyle {\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 ${\displaystyle Q\!\,}$ is upper Hessenberg.

From the algorithm, we have

{\displaystyle {\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 ${\displaystyle A_{k+1}\!\,}$ is upper Hessenberg because for ${\displaystyle j=1,2,\ldots ,n-2\!\,}$ the ${\displaystyle j\!\,}$th column of ${\displaystyle A_{k+1}\!\,}$ is a linear combination of the first ${\displaystyle j+1\!\,}$ columns of ${\displaystyle R_{k}\!\,}$ since ${\displaystyle Q_{k}\!\,}$ is also upper Hessenberg.

## Problem 2d

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

## Solution 2d

The eigenvalues of ${\displaystyle A\!\,}$ can be computed. They are ${\displaystyle 6\!\,}$ and ${\displaystyle 2\!\,}$. Furthermore, the result of matrix multiplies in the algorithm shows that the diagonal difference, ${\displaystyle (a_{1,2}-a_{2,1})\!\,}$, is constant for all ${\displaystyle i\!\,}$.

Since the limit of ${\displaystyle A\!\,}$ is an upper triangular matrix with the eigenvalues of ${\displaystyle A\!\,}$ on the diagonal, the limit is

${\displaystyle {\begin{pmatrix}6&2\\0&2\end{pmatrix}}\!\,}$

## Problem 3

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

## Problem 3a

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

## Solution 3a

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

${\displaystyle \|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 ${\displaystyle r^{(0)}\!\,}$

{\displaystyle {\begin{aligned}r^{(0)}&=Ax^{(0)}-b\\&=Ax^{(0)}-Ax\\&=A(x^{(0)}-x)\end{aligned}}}

### Rewrite Krylov space

Therefore, we can rewrite ${\displaystyle {\mathcal {K}}_{n}(r^{(0)},A)\!\,}$ as follows:

{\displaystyle {\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 ${\displaystyle y\!\,}$ explicitly as follows:

{\displaystyle {\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 ${\displaystyle y\!\,}$ into the hypothesis inequality and apply a norm inequality of matrix norms to get the desired result.

{\displaystyle {\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 ${\displaystyle T_{n}(z)\!\,}$ denote the ${\displaystyle n^{th}\!\,}$ Chebyshev polynomial. Let ${\displaystyle \lambda _{min}\!\,}$ and ${\displaystyle \lambda _{max}\!\,}$ denote respectively the smallest and largest eigenvalues of ${\displaystyle A\!\,}$. Apply the result of part (a) to ${\displaystyle 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 ${\displaystyle \|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 ${\displaystyle \|p_{n}(A)\|_{A}=\max\{|p_{n}(z)|:z\in Sp\{A\}\}\!\,}$, where ${\displaystyle Sp(A)\!\,}$ denotes the set of eigenvalues of ${\displaystyle A\!\,}$, and the facts that for every ${\displaystyle n\in \mathbb {N} \!\,}$ the polynomial ${\displaystyle T_{n}(z)\!\,}$ has degree ${\displaystyle n\!\,}$, is positive for ${\displaystyle z>1\!\,}$, and satisfies ${\displaystyle T_{n}(\cos(\theta ))=\cos(n\theta )\quad \quad {\mbox{for all}}\;\theta \in \mathbb {R} \!\,}$.

## Solution 3b

### Overview

We want to show that

${\displaystyle \|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,

${\displaystyle \|p_{n}(A)\|_{A}=\max\{|p_{n}(z)|:z\in Sp\{A\}\}\!\,}$

Since only the numerator of ${\displaystyle p_{n}(z)\!\,}$ depends on ${\displaystyle z\!\,}$, we only need to maximize the numerator in order to maximize ${\displaystyle |p_{n}(z)|\!\,}$. That is find

${\displaystyle 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 ${\displaystyle \cos(\theta )=x\!\,}$. Then

${\displaystyle \theta =\arccos(x)\!\,}$

Hence,

{\displaystyle {\begin{aligned}T_{n}(\cos \theta )&=T_{n}(x)\\&=\cos(n\theta )\\&=\cos(n\arccos(x))\end{aligned}}}

so

${\displaystyle T_{n}(x)=\cos(n\arccos(x))\!\,}$

### Max of T_n is 1

Denote the argument of ${\displaystyle T_{n}\!\,}$ as ${\displaystyle x(z)\!\,}$ since the argument depends on ${\displaystyle z\!\,}$. Hence,

${\displaystyle x(z)={\frac {\lambda _{\max }+\lambda _{\min }-2z}{\lambda _{\max }-\lambda _{\min }}}\!\,}$,

Then,

${\displaystyle x(\lambda _{\min })={\frac {\lambda _{\max }-\lambda _{\min }}{\lambda _{\max }-\lambda _{\min }}}=1\!\,}$

${\displaystyle x(\lambda _{\max })={\frac {\lambda _{\min }-\lambda _{\max }}{\lambda _{\max }-\lambda _{\min }}}=-1\!\,}$

Thus ${\displaystyle x(z)\in [-1,1]\!\,}$.

Now, since ${\displaystyle \;\arccos(x)\;}$ is real for ${\displaystyle x\in [-1,1]\!\,}$,

${\displaystyle -1\leq \underbrace {\cos(n\overbrace {\arccos(x)} ^{\in \mathbb {R} })} _{T_{n}(x)}\leq 1\!\,}$

Hence,

${\displaystyle \max _{x\in [-1,1]}T_{n}(x)=\max _{x\in [-1,1]}|\cos(n\arccos(x))|=1\!\,}$

### Show T_n(1)=1

Let ${\displaystyle z=\lambda _{\min }\!\,}$, then

${\displaystyle \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,

{\displaystyle {\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 ${\displaystyle z=\lambda _{\min }\!\,}$, ${\displaystyle T_{n}\!\,}$ achieves its maximum value of ${\displaystyle 1\!\,}$.