Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/January 2004

Problem 1

Let $a=x_0<x_1<\cdots <x_n=b$ be an arbitrary fixed partition of the interval $[a,b]$. A function $q(x)$ is a quadratic spline function if (i) $q\in C^1[a,b]$ (ii) On each subinterval $[x_i,x_{i+1}]$, $q$ is a quadratic polynomial The problem is to construct a quadratic spline $q(x)$ interpolating data points $(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)$. The construction is similar to the construction of the cubic spline but much easier.

Problem 1a

Show that if we know $z_i\equiv q^{\prime }(x_i),i=0,\dots ,n$, we can construct $q$.

Solution 1a

Consider interval $[x_i,x_{i+1}]$. Since $q{\text{'}}_i(x)$ is linear on this interval, using the point slope form we have

${q_i}^{\prime }(x)=\frac{z_{i+1}-z_i}{x_{i+1}-x_i}(x-x_i)+z_i$

Integrating, we have

$q_i(x)=z_{i}x+\frac{z_{i+1}-z_i}{x_{i+1}-x_i}\frac{(x-x_i{)}^2}{2}+K_i$

or, in a more convenient form,

$q_i(x)=z_i(x-x_i)+\frac{z_{i+1}-z_i}{x_{i+1}-x_i}\frac{(x-x_i{)}^2}{2}+y_i$

Problem 1b

Find equations which enable us to determine the $z_i$. You should find that one of the $z_i$ can be prescribed arbitrarily, for instance $z_0=0$

Solution 1

Since $q$ is continuous on $[a,b]$,

$q_{i-1}(x_i)=q_i(x_i)=y_i$

i.e.

$z_{i-1}(x_i-x_{i-1})+\frac{z_i-z_{i-1}}{x_i-x_{i-1}}\frac{(x_i-x_{i-1}{)}^2}{2}+y_{i-1}=y_i$

Simplifying and rearranging terms yields the reoccurrence formula

$z_i=-z_{i-1}+\frac{2(y_i-y_{i-1})}{x_i-x_{i-1}}i=1,\dots n$

Problem 2a

Give the definition of the $QR$ algorithm for finding the eigenvalues of a matrix $A$. Define both the unshifted version and the version with shifts ${\chi }_0,{\chi }_1,{\chi }_2,\dots$

Solution 2a

Unshifted Version

$Q_k{R}_k=A_k$

$A_{k+1}=R_k{Q}_k$

Shifted Version

$Q_k{R}_k=A_k-{\chi }_{k}I$

$A_{k+1}=R_k{Q}_k+{\chi }_{k}I$

Problem 2b

Show that in each case the matrices $A_1,A_2$ generated by the $QR$ algorithm are unitarily equivalent to $A$ (i.e. $A_i=U_{i}A{U}_i^H,U_i$ unitary).

Solution 2b

Suppose $A_m=U^{T}AU$ for some unitary $U$. Since $R_m=Q_m^T{A}_m$ we have

$A_{m+1}=R_m{Q}_m=Q_m^T{A}_m{Q}_m=Q_m^T{U}^{T}AU{Q}_m$

which is as desired as $Q_{m}U$ is unitary.

For the shifted case, the same argument holds using the fact that $R_m=Q_m^T(A_m-{\chi }_{m}I)$.

Problem 2c

Let $A=\left(\begin{array}{cc}3& 1\\ 1& 2\end{array}\right)$ Use plane rotations (Givens rotations) to carry out one step of the $QR$ algorithm on $A$, first without shifting and then using the shift ${\chi }_0=1$. Which seems to do better? The eigenvalues of $A$ are ${\lambda }_1=1.382,{\lambda }_2=3.618$. (Recall that a plane rotation is a matrix of the form $Q=\left(\begin{array}{cc}c& -s\\ s& c\end{array}\right)$ with $c^2+s^2=1$

Solution 2c

The shifted iteration appears to work better because its diagonal entries are closer to the actual eigenvalues than the diagonal entries of the unshifted iteration.

Unshifted Iteration

$A_1=\left(\begin{array}{cc}3.5& .5\\ .5& 1.5\end{array}\right)$

Shifted Iteration

$A_1=\left(\begin{array}{cc}3.6& .2\\ .2& 1.4\end{array}\right)$

Problem 3

Let $A$ be an $N\times N$ symmetric, positive definite matrix. Then we know that solving $Ax=b$ is equivalent to minimizing the functional $F(x)=\frac{1}{2}⟨x,Ax⟩-⟨b,x⟩$ where $⟨\cdot ,\cdot ⟩$ denotes the standard inner product in $R^N$. To solve the problem by minimization of $F$ we consider the general iterative method $x_{v+1}=x_v+{\alpha }_v{d}_v$

Problem 3a

When $x_v$ and $d_v$ are given, show that the value of ${\alpha }_v$ which minimizes $F(x_v+\alpha d_v)$ as a function of $\alpha$ is given in terms of the residual $r_v$ ${\alpha }_v=\frac{⟨r_v,d_v⟩}{⟨d_v,A{d}_v⟩},r_v=b-A{x}_v$

Solution 3a

Useful Relationship

Since $A$ is symmetric

$(Ax,y)=(x,A^{T}y)=(x,Ay)$

This relationship will used throughout the solutions.

Substitute into Functional

$\begin{array}{cc}F(x_v+\alpha d_v)& =\frac{1}{2}⟨x_v+\alpha d_v,A{x}_v+\alpha A{d}_v⟩-⟨b,x_v+\alpha d_v⟩\\ & =\frac{⟨d_v,A{d}_v⟩}{2}{\alpha }^2+\alpha ⟨d_v,A{x}_v⟩-\alpha ⟨b,d_v⟩+\frac{1}{2}⟨x_v,A{x}_v⟩-⟨b,x_v⟩\end{array}$

Take Derivative With Respect to Alpha

$F^{\prime }(x_v+\alpha d_v)=⟨d_v,A{d}_v⟩\alpha +⟨d_v,A{x}_v⟩-⟨b,d_v⟩$

Set Derivative Equal To Zero

$0=⟨d_v,A{d}_v⟩\alpha +⟨d_v,A{x}_v-b⟩$

which implies

$\alpha =\frac{⟨d_v,r_v⟩}{⟨d_v,A{d}_v⟩}$

Problem 3b

Let $\{d_j{\}}_{j=1}^N$ be an $A$-orthogonal basis of $R^N$, $⟨d_j,A{d}_k⟩=0,j\ne k$. Consider the expansion of the solution $x$ in this basis: $x=\sum _{j=1}^N\widehat{x_j}{d}_j$ Use that $A-$orthogonality of the $d_j$ to compute the ${\hat{x}}_j$ in terms of the solution $x$ and the $d_j$'s

Solution 3b

$\begin{array}{cc}⟨x,A{d}_k⟩& =⟨\sum _{j=1}^n{\hat{x}}_j{d}_j,A{d}_k⟩\\ & =\sum _{j=1}^N{\hat{x}}_j⟨d_j,A{d}_k⟩\\ & ={\hat{x}}_k⟨d_k,A{d}_k⟩\end{array}$

which implies

${\hat{x}}_k=\frac{⟨x,A{d}_k⟩}{⟨d_k,A{d}_k⟩}$

Problem 3c

Let $x_v$ denote the partial sum $x_v=\sum _{j=1}^{v-1}{\hat{x}}_j{d}_j,v=2,3,\dots$ so that $x_{v+1}=x_v+{\hat{x}}_v{d}_v$ where the ${\hat{x}}_v$'s are the coefficients found in (b). Use the fact that $x_v\in \text{span}\{d_1,d_2,\dots ,d_{v-1}\}$ and the $A$-orthogonality of the $d_j$'s to conclude that the coefficient ${\hat{x}}_v$ is given by the optimal ${\alpha }_v$ i.e. ${\hat{x}}_v=\frac{⟨r_v,d_v⟩}{⟨d_v,A{d}_v⟩}={\alpha }_v$

Solution 3c

$\begin{array}{cc}⟨r_v,d_v⟩& =⟨b-A{x}_v,d_v⟩\\ & =⟨Ax-A{x}_v,dv⟩\\ & =⟨Ax,d_v⟩-⟨A{x}_v,d_v⟩\\ & =⟨x,A{d}_v⟩-\underset{0}{\underbrace{⟨x_v,A{d}_v⟩}}\\ & ={\hat{x}}_v⟨d_v,A{d}_v⟩\end{array}$

which implies

${\hat{x}}_v=\frac{⟨r_v,d_v⟩}{⟨d_v,A{d}_v⟩}$