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

Problem 1

Let $A$ be a real symmetric matrix of order $n$ with $n$ distinct eigenvalues, and let $v_1\in R^n$ be such that $\Vert v_1{\Vert }_2=1$ and the inner product $(v_1,u)\ne 0$ for every eigenvector $u$ of $A$.

Problem 1a

Let $P_n$ denote the space of polynomials of degree at most $n-1$. Show that $⟨p,q⟩\equiv (p(A)v_1,q(A)v_1)$ defines an inner product on $P_n$, where the expression on the right above is the Euclidean inner product in $R^n$

Solution 1a

Symmetry

$\begin{array}{cc}⟨p,q⟩& =(p(A)v_1,q(A)v_1)\\ & =(q(A)v_1,p(A)v_1)\\ & =⟨q,p⟩\end{array}$

Linearity of 1st Argument

Let $\alpha \in ℝ$

$\begin{array}{cc}⟨\alpha p,q⟩& =(\alpha p(A)v_1,q(A)v_1)\\ & =\alpha (p(A)v_1,q(A)v_1)\\ & =\alpha ⟨p,q⟩\end{array}$

$\begin{array}{cc}⟨p+r,q⟩& =((p(A)+r(A))v_1,q(A)v_1)\\ & =(p(A)v_1,q(A)v_1)+(r(A)v_1,q(A)v_1)\\ & =⟨p,q⟩+⟨r,q⟩\end{array}$

Positive Definiteness

$\begin{array}{cc}⟨p,p⟩& =(\underset{\hat{v}}{\underbrace{p(A)v_1}},\underset{\hat{v}}{\underbrace{p(A)v_1)}}\text{ where }\hat{v}\in R^n\\ & =(\hat{v},\hat{v})\\ & =\sum _{i=1}^n({\hat{v}}_i{)}^2\ge 0\end{array}$

"Zeroness"

We also need to show that $⟨p,p⟩=0$ if and only if $p=0$.

Forward Direction (alt)

Suppose $p\ne 0$. It suffices to show $⟨p,p⟩\ne 0$. However, this a trivial consequence of the fact that $p(A)v_1\ne 0$ (which is clear from the fact that $p(A)\ne 0$ for $p\ne 0$ with degree less than $n$ and that $v_i$ does not lie in the orthogonal compliment of any of the $n$ distinct eigen vectors of $A$).

Forward Direction

Claim: If $⟨p,p⟩=0$, then $p=0$.

From hypothesis

$v_1=\sum _{i=1}^n{\alpha }_i{u}_i$

where $u_i$ are the orthogonal eigenvectors of $A$ and all ${\alpha }_i$ are non-zero

$\begin{array}{cc}⟨p,p,⟩& =(p(A)v_1,p(A)v_1)\\ & =(p(A)\sum _{i=1}^n{\alpha }_i{u}_i,p(A)\sum _{i=1}^n{\alpha }_i{u}_i)\\ & =(\sum _{i=1}^n{\beta }_i{u}_i,\sum _{i=1}^n\beta u_i)\text{ (since }{u}_i\text{ are eigenvectors )}\\ & =0\text{ (by hypothesis) }\end{array}$

Notice that ${\beta }_i$ is a linear combination of ${\alpha }_i$, the coefficients of the polynomial $A$, and the scaling coefficient $m_i$ of the eigenvector e.g. $A{u}_i=m_i{u}_i$

Since $u_i\ne 0\mathrm{\forall }i$ and ${\alpha }_i\ne 0$, this implies $p=0$.

Reverse Direction

If $p=0$, then $⟨p,p⟩=(\underset{0}{\underbrace{p(A)}}{v}_1,\underset{0}{\underbrace{p(A)}}{v}_1)=0$

Problem 1b

Consider the recurrence ${\beta }_{j+1}{v}_{j+1}=A{v}_j-{\alpha }_j{v}_j-{\beta }_j{v}_{j-1}$ where the ${\alpha }_j$ and ${\beta }_j$ are scalars and $v_0\equiv 0$. Show that $v_j=p_{j-1}(A)v_1$, where $p_{j-1}(t)$ is a polynomial of degree $j-1$

Solution 1b

By induction.

Base Case

$\begin{array}{cc}{\beta }_2{v}_2& =A{v}_1-{\alpha }_1{v}_1-{\beta }_1\underset{0}{\underbrace{v_0}}\\ v_2& =\frac{1}{{\beta }_2}[A{v}_1-{\alpha }_1{v}_1]\\ v_2& =p_1(A)v_1{p}_1(t)=\frac{1}{{\beta }_2}[t-{\alpha }_1]\end{array}$

$\begin{array}{cc}{\beta }_3{v}_3& =A{v}_2-{\alpha }_2{v}_2-{\beta }_2{v}_1\\ v_3& =\frac{1}{{\beta }_3}[\underset{\in p_2(A)v_1}{\underbrace{A{v}_2}}-\underset{\in p_1(A)v_1}{\underbrace{{\alpha }_2{v}_2}}-\underset{\in p_0(A)v_1}{\underbrace{{\beta }_2{v}_1}}]\\ & \in p_2(A)v_1\end{array}$

Induction Step

Claim: $v_j=p_{j-1}(A)v_1$

Hypothesis:

Suppose

$v_j=p_{j-1}(A)v_1$

$v_{j-1}=p_{j-2}(A)v_1$

where $p_{j-1}$ (respectively $p_{j-2}$) has degree $j-1$ (respectively $j-2$). Then for ${\beta }_{j+1}\ne 0$

$v_{j+1}=\frac{A{p}_{j-1}(A)-{\alpha }_j{p}_{j-1}(A)-{\beta }_j{p}_{j-2}(A)}{{\beta }_{j+1}}{v}_1$

which is as desired.

Problem 1c

Suppose the scalars above are such that ${\alpha }_j=(A{v}_j,v_j)$ and ${\beta }_{j+1}$ is chosen so that $\Vert v_{j+1}{\Vert }_2=1$. Use this to show that that the polynomials in part (b) are othogonal with respect to the inner product from part (a.

Solution 1c

Since $v_j=p_{j-1}(A)v_1$ and $⟨p,q⟩\equiv (p(A)v_1,q(A)v_1)$, it is equivalent to show that $(v_i,v_j)=0$ for $i\ne j$.

Since

$v_{j+1}=\frac{1}{{\beta }_{j+1}}A{v}_j-\frac{{\alpha }_j}{{\beta }_j}{v}_j-\frac{{\beta }_{j+1}}{{\beta }_j}{v}_{j-1}$,

it is then sufficient to show that

$(v_{j+1},v_j)=(v_{j+1},v_{j-1})=0$

Claim $(v_{j+1},v_j)=0\mathrm{\forall }j$

By induction.

Base Case

$\begin{array}{cc}{v}_2& =\frac{1}{{\beta }_2}(A{v}_1-{\alpha }_1{v}_1)\\ (v_2,v_1)& =\frac{1}{{\beta }_2}[(A{v}_1,v_1)-\underset{(A{v}_1,v_1)}{\underbrace{{\alpha }_1}}\underset{1}{\underbrace{(v_1,v_1)}}]\\ & =0\end{array}$

Induction Step

Assume: $(v_j,v_{j-1})=0$

Claim: $(v_{j+1},v_j)=0$

$\begin{array}{cc}{v}_{j+1}& =\frac{1}{{\beta }_{j+1}}[A{v}_j-{\alpha }_j{v}_j-{\beta }_j{v}_{j-1}]\\ (v_{j+1},v_j)& =\frac{1}{{\beta }_{j+1}}[(A{v}_j,v_j)-\underset{(A{v}_j,v_j)}{\underbrace{{\alpha }_j}}\underset{1}{\underbrace{(v_j,v_j)}}-{\beta }_j\underset{0}{\underbrace{(v_{j-1},v_j)}}]\\ & =0\end{array}$

Claim $(v_{j+1},v_{j-1})=0$

By induction.

Base Case

$\begin{array}{cc}{v}_3& =\frac{1}{{\beta }_3}[A{v}_2-{\alpha }_2{v}_2-{\beta }_2{v}_1]\\ (v_3,v_1)& =\frac{1}{{\beta }_3}[(A{v}_2,v_1)-{\alpha }_2\underset{0}{\underbrace{(v_2,v_1)}}-{\beta }_2\underset{1}{\underbrace{(v_1,v_1)}}]\\ & =\frac{1}{{\beta }_3}[(A{v}_2,v_1)-{\beta }_2]\\ & =\frac{1}{{\beta }_3}[(v_2,A{v}_1)-{\beta }_2]\text{ (because A symmetric) }\\ & =\frac{1}{{\beta }_3}[{\beta }_2-{\beta }_2]=0\text{ (see below) }\end{array}$

$\begin{array}{cc}{\beta }_2{v}_2& =A{v}_1-{\alpha }_1{v}_1\\ {\beta }_2\underset{1}{\underbrace{(v_2,v_2)}}& =(A{v}_1,v_2)-{\alpha }_1\underset{0}{\underbrace{(v_1,v_2)}}\\ {\beta }_2& =(A{v}_1,v_2)\end{array}$

Induction Step

Assume: $(v_j,v_{j-2})=0$

Claim: $(v_{j+1},v_{j-1})=0$

$\begin{array}{cc}(v_{j+1},v_{j-1})& =\frac{1}{{\beta }_{j+1}}[(A{v}_j,v_{j-1}-{\alpha }_j\underset{0}{\underbrace{(v_j,v_{j-1})}}-{\beta }_j\underset{1}{\underbrace{(v_{j-1},v_{j-1})}}\\ & =\frac{1}{{\beta }_{j+1}}[(A{v}_j,v_{j-1})-{\beta }_j)]\\ & =\frac{1}{{\beta }_{j+1}}[(v_j,A{v}_{j-1})-{\beta }_j]\text{ (because A symmetric)}\\ & =\frac{1}{{\beta }_{j+1}}[{\beta }_j-{\beta }_j]=0\text{ (see below) }\end{array}$

$\begin{array}{cc}{\beta }_j{v}_j& =A{v}_{j-1}-{\alpha }_{j-1}{v}_{j-1}-{\beta }_{j-1}{v}_{j-2}\\ {\beta }_j\underset{1}{\underbrace{(v_j,v_j)}}& =(A{v}_{j-1},v_j)-{\alpha }_{j-1}\underset{0}{\underbrace{(v_{j-1},v_j)}}-{\beta }_{j-1}\underset{0}{\underbrace{(v_{j-2},v_j)}}\\ {\beta }_j& =(A{v}_{j-1},v_j)\end{array}$

Problem 2

Consider the n-panel trapezoid rule $I_n(f)$ for calculating the integral $\underset{0}{\overset{1}{\int }}f(x)dx$ of a continuous function $f\in C[0,1]$, $I_n(f)=\sum _{k=0}^{n-1}\left(\frac{t_{k+1}-t_k}{2}\right)(f(t_k)+f(t_{k+1}))$ where $0=t_0<t_1<...<t_n=1$

Problem 2a

Find a piecewise linear function $G$ such that $I_n(f)-\underset{0}{\overset{1}{\int }}f(t)dt=\underset{0}{\overset{1}{\int }}G(t)f^{\prime }(t)dt$ for any continuous function $f$ such that $f^{\prime }$ is integrable over [0,1]. Hint: Find $G$ by applying the fundamental theorem of calculus to $\underset{t_k}{\overset{t_{k+1}}{\int }}(f(t)G(t){)}^{\prime }dt$.

Solution 2a

Rewrite given equation on specific interval

For a specific interval $[t_k,t_{k+1}]$, we have from hypothesis

$(\frac{t_{k+1}-t_k}{2})(f(t_k)+f(t_{k+1}))-\underset{t_k}{\overset{t_{k+1}}{\int }}f(t)=\underset{t_k}{\overset{t_{k+1}}{\int }}G(t)f^{\prime }(t)dt$.

Distributing and rearranging terms gives

$(1)(\frac{t_{k+1}-t_k}{2})f(t_k)+(\frac{t_{k+1}-t_k}{2})f(t_{k+1}))-\underset{t_k}{\overset{t_{k+1}}{\int }}f(t)=\underset{t_k}{\overset{t_{k+1}}{\int }}G(t)f^{\prime }(t)$

Apply Hint

Starting with the hint and applying product rule, we get

$\underset{t_k}{\overset{t_{k+1}}{\int }}(f(t)G(t){)}^{\prime }dt=\underset{t_k}{\overset{t_{k+1}}{\int }}{f}^{\prime }(t)G(t)dt+\underset{t_k}{\overset{t_{k+1}}{\int }}f(t)G^{\prime }(t)dt$.

Also, we know from the Fundamental Theorem of Calculus

$\underset{t_k}{\overset{t_{k+1}}{\int }}(f(t)G(t){)}^{\prime }dt=f(t_{k+1})G(t_{k+1})-f(t_k)G(t_k)$.

Setting the above two equations equal to each other and solving for $\underset{t_k}{\overset{t_{k+1}}{\int }}{f}^{\prime }(t)G(t)$ yields

$(2)-G(t_k)f(t_k)+G(t_{k+1})f(t_{k+1})-\underset{t_k}{\overset{t_{k+1}}{\int }}{G}^{\prime }(t)f(t)dt=\underset{t_k}{\overset{t_{k+1}}{\int }}G(t)f^{\prime }(t)$

Choose G'(t)

Let $G^{\prime }(t)=1$. Therefore, since $G(t)$ is linear

$(3)G(t)=t+b$

By comparing equations (1) and (2) we see that

$G(t_{k+1})=\frac{t_{k+1}-t_k}{2}$ and

$G(t_k)=-\frac{t_{k+1}-t_k}{2}$.

Plugging in either $G(t_k)$ or $G(t_{k+1})$ into equation (3), we get that

$b=-\frac{t_{k+1}+t_k}{2}$

Hence

$G(t)=t-\frac{t_{k+1}+t_k}{2}$

Problem 2b

Apply the previous result to $f(x)=x^{\alpha }$, $0<\alpha <1$, to obtain a rate of convergence.

Problem 3

Let $C[a,b]$ denote the set of all real-valued continuous functions defined on the closed interval $[a,b]$ be positive everywhere in $[a,b]$. Let $\{Q_n{\}}_{n=0}^{\mathrm{\infty }}$ be a system of polynomials with $deg{Q}_n=n$ for each $n$, orthogonal with respect to the inner product $⟨g,h⟩=\underset{a}{\overset{b}{\int }}\rho (x)g(x)h(x)dx,\mathrm{\forall }g,h\in C[a,b]$ For a fixed integer $n\ge 2$, let $x_1,\dots ,x_n$ be the $n$ distinct roots of $Q_n$ in $(a,b)$. Let $r_k(x)=\frac{(x-x_1)\cdots (x-x_{k-1})(x-x_{k+1})\cdots (x-x_n)}{(x_k-x_1)\cdots (x_k-x_{k-1})(x_k-x_{k+1})\cdots (x_k-x_n)},k=1,2,\dots ,n$ be polynomials of degree $n-1$. Show that $\underset{a}{\overset{b}{\int }}\rho (x)r_j(x)r_k(x)dx=0,\mathrm{\forall }j\ne k$ and that $\sum _{k=1}^n\underset{a}{\overset{b}{\int }}\rho (x)(r_k(x){)}^{2}dx=\underset{a}{\overset{b}{\int }}\rho (x)dx$ Hint: Use orthogonality to simplify $\underset{a}{\overset{b}{\int }}\rho (x)(\sum _{k=1}^n{r}_k(x){)}^{2}dx$

Solution 3a

$\begin{array}{cc}& \underset{a}{\overset{b}{\int }}\rho (x)r_j(x)r_k(x)dx\\ & =\underset{a}{\overset{b}{\int }}\rho (x)\prod _{i\ne j}\frac{x-x_i}{x_j-x_i}\prod _{i\ne k}\frac{x-x_i}{x_k-x_i}dx\\ & =\underset{a}{\overset{b}{\int }}\stackrel{Q_{n-2}}{\overbrace{\frac{\prod _{i\ne k,i\ne j}^{n}x-x_i}{\prod _{i\ne j}^n{x}_j-x_i}}}{\overbrace{\frac{\prod _{i=1}^{n}x-x_i}{\prod _{i\ne k}^n{x}_k-x_i}}}_n^{Q}dx\\ & =0\end{array}$

Solution 3b

$\begin{array}{cc}& \sum _{k=1}^n\underset{a}{\overset{b}{\int }}\rho (x)(r_k(x){)}^{2}dx\\ & =\underset{a}{\overset{b}{\int }}\rho (x)\sum _{k=1}^n(r_k(x){)}^{2}dx\\ & =\underset{a}{\overset{b}{\int }}\rho (x)(\sum _{k=1}^n{r}_k(x){)}^{2}dx\text{ (from part a) }\\ & =\underset{a}{\overset{b}{\int }}\rho (x)(1{)}^{2}dx\text{ (from claim) }\\ & =\underset{a}{\overset{b}{\int }}\rho (x)dx\end{array}$

Claim

$\sum _{k=1}^n{r}_k(x)=1$

Proof

Since $r_k$ is a polynomial of degree $n-1$ for all $k$, $\sum _{k=1}^n{r}_k(x)$ is a polynomial of degree $n-1$.

Notice that $\sum _{k=1}^n{r}_k(x_i)=1$ for $i=1,2,\dots ,n$ where $x_i$ are the $n$ distinct roots of $Q_n$. Since $\sum _{k=1}^n{r}_k(x)$ is a polynomial of degree $n-1$ and takes on the value 1, $n$ distinct times

$\sum _{k=1}^n{r}_k(x)=1$