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 $\|v_{1}\|_{2}=1\!\,$ and the inner product $(v_{1},u)\neq 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 $\langle p,q\rangle \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{aligned}\langle p,q\rangle &=(p(A)v_{1},q(A)v_{1})\\&=(q(A)v_{1},p(A)v_{1})\\&=\langle q,p\rangle \end{aligned}}\!\,$

Linearity of 1st Argument

Let $\alpha \in \mathbb {R} \!\,$

${\begin{aligned}\langle \alpha p,q\rangle &=(\alpha p(A)v_{1},q(A)v_{1})\\&=\alpha (p(A)v_{1},q(A)v_{1})\\&=\alpha \langle p,q\rangle \end{aligned}}\!\,$

${\begin{aligned}\langle p+r,q\rangle &=((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})\\&=\langle p,q\rangle +\langle r,q\rangle \end{aligned}}\!\,$

Positive Definiteness

${\begin{aligned}\langle p,p\rangle &=(\underbrace {p(A)v_{1}} _{\hat {v}},\underbrace {p(A)v_{1})} _{\hat {v}}{\mbox{ where }}{\hat {v}}\in R^{n}\\&=({\hat {v}},{\hat {v}})\\&=\sum _{i=1}^{n}({\hat {v}}_{i})^{2}\geq 0\end{aligned}}\!\,$

"Zeroness"

We also need to show that $\langle p,p\rangle =0\!\,$ if and only if $p=0\!\,$.

Forward Direction (alt)

Suppose $p\neq 0$. It suffices to show $\langle p,p\rangle \neq 0$. However, this a trivial consequence of the fact that $p(A)v_{1}\neq 0$ (which is clear from the fact that $p(A)\neq 0$ for $p\neq 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 $\langle p,p\rangle =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{aligned}\langle p,p,\rangle &=(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}){\mbox{ (since }}u_{i}{\mbox{ are eigenvectors )}}\\&=0{\mbox{ (by hypothesis) }}\end{aligned}}\!\,$

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. $Au_{i}=m_{i}u_{i}\!\,$

Since $u_{i}\neq 0\forall i\!\,$ and $\alpha _{i}\neq 0\!\,$, this implies $p=0\!\,$.

Reverse Direction

If $p=0\!\,$, then $\langle p,p\rangle =(\underbrace {p(A)} _{0}v_{1},\underbrace {p(A)} _{0}v_{1})=0\!\,$

Problem 1b

Consider the recurrence $\beta _{j+1}v_{j+1}=Av_{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{aligned}\beta _{2}v_{2}&=Av_{1}-\alpha _{1}v_{1}-\beta _{1}\underbrace {v_{0}} _{0}\\v_{2}&={\frac {1}{\beta _{2}}}[Av_{1}-\alpha _{1}v_{1}]\\v_{2}&=p_{1}(A)v_{1}\quad p_{1}(t)={\frac {1}{\beta _{2}}}[t-\alpha _{1}]\end{aligned}}\!\,$

${\begin{aligned}\beta _{3}v_{3}&=Av_{2}-\alpha _{2}v_{2}-\beta _{2}v_{1}\\v_{3}&={\frac {1}{\beta _{3}}}[\underbrace {Av_{2}} _{\in p_{2}(A)v_{1}}-\underbrace {\alpha _{2}v_{2}} _{\in p_{1}(A)v_{1}}-\underbrace {\beta _{2}v_{1}} _{\in p_{0}(A)v_{1}}]\\&\in p_{2}(A)v_{1}\end{aligned}}\!\,$

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}\neq 0$

$v_{j+1}={\frac {Ap_{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}=(Av_{j},v_{j})\!\,$ and $\beta _{j+1}\!\,$ is chosen so that $\|v_{j+1}\|_{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 $\langle p,q\rangle \equiv (p(A)v_{1},q(A)v_{1})\!\,$, it is equivalent to show that $(v_{i},v_{j})=0\!\,$ for $i\neq j\!\,$.

Since

$v_{j+1}={\frac {1}{\beta _{j+1}}}Av_{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\quad \forall j\!\,$

By induction.

Base Case

${\begin{aligned}v_{2}&={\frac {1}{\beta _{2}}}(Av_{1}-\alpha _{1}v_{1})\\(v_{2},v_{1})&={\frac {1}{\beta _{2}}}[(Av_{1},v_{1})-\underbrace {\alpha _{1}} _{(Av_{1},v_{1})}\underbrace {(v_{1},v_{1})} _{1}]\\&=0\end{aligned}}\!\,$

Induction Step

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

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

${\begin{aligned}v_{j+1}&={\frac {1}{\beta _{j+1}}}[Av_{j}-\alpha _{j}v_{j}-\beta _{j}v_{j-1}]\\(v_{j+1},v_{j})&={\frac {1}{\beta _{j+1}}}[(Av_{j},v_{j})-\underbrace {\alpha _{j}} _{(Av_{j},v_{j})}\underbrace {(v_{j},v_{j})} _{1}-\beta _{j}\underbrace {(v_{j-1},v_{j})} _{0}]\\&=0\end{aligned}}\!\,$

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

By induction.

Base Case

${\begin{aligned}v_{3}&={\frac {1}{\beta _{3}}}[Av_{2}-\alpha _{2}v_{2}-\beta _{2}v_{1}]\\(v_{3},v_{1})&={\frac {1}{\beta _{3}}}[(Av_{2},v_{1})-\alpha _{2}\underbrace {(v_{2},v_{1})} _{0}-\beta _{2}\underbrace {(v_{1},v_{1})} _{1}]\\&={\frac {1}{\beta _{3}}}[(Av_{2},v_{1})-\beta _{2}]\\&={\frac {1}{\beta _{3}}}[(v_{2},Av_{1})-\beta _{2}]{\mbox{ (because A symmetric) }}\\&={\frac {1}{\beta _{3}}}[\beta _{2}-\beta _{2}]=0{\mbox{ (see below) }}\end{aligned}}\!\,$

${\begin{aligned}\beta _{2}v_{2}&=Av_{1}-\alpha _{1}v_{1}\\\beta _{2}\underbrace {(v_{2},v_{2})} _{1}&=(Av_{1},v_{2})-\alpha _{1}\underbrace {(v_{1},v_{2})} _{0}\\\beta _{2}&=(Av_{1},v_{2})\end{aligned}}\!\,$

Induction Step

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

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

${\begin{aligned}(v_{j+1},v_{j-1})&={\frac {1}{\beta _{j+1}}}[(Av_{j},v_{j-1}-\alpha _{j}\underbrace {(v_{j},v_{j-1})} _{0}-\beta _{j}\underbrace {(v_{j-1},v_{j-1})} _{1}\\&={\frac {1}{\beta _{j+1}}}[(Av_{j},v_{j-1})-\beta _{j})]\\&={\frac {1}{\beta _{j+1}}}[(v_{j},Av_{j-1})-\beta _{j}]{\mbox{ (because A symmetric)}}\\&={\frac {1}{\beta _{j+1}}}[\beta _{j}-\beta _{j}]=0{\mbox{ (see below) }}\end{aligned}}\!\,$

${\begin{aligned}\beta _{j}v_{j}&=Av_{j-1}-\alpha _{j-1}v_{j-1}-\beta _{j-1}v_{j-2}\\\beta _{j}\underbrace {(v_{j},v_{j})} _{1}&=(Av_{j-1},v_{j})-\alpha _{j-1}\underbrace {(v_{j-1},v_{j})} _{0}-\beta _{j-1}\underbrace {(v_{j-2},v_{j})} _{0}\\\beta _{j}&=(Av_{j-1},v_{j})\end{aligned}}\!\,$

Problem 2

Consider the n-panel trapezoid rule $I_{n}(f)\!\,$ for calculating the integral $\int _{0}^{1}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)-\int _{0}^{1}f(t)dt=\int _{0}^{1}G(t)f'(t)dt\!\,$ for any continuous function $f\!\,$ such that $f'\!\,$ is integrable over [0,1]. Hint: Find $G\!\,$ by applying the fundamental theorem of calculus to $\int _{t_{k}}^{t_{k+1}}(f(t)G(t))'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}))-\int _{t_{k}}^{t_{k+1}}f(t)=\int _{t_{k}}^{t_{k+1}}G(t)f'(t)dt\!\,$.

Distributing and rearranging terms gives

$(1)\qquad ({\frac {t_{k+1}-t_{k}}{2}})f(t_{k})+({\frac {t_{k+1}-t_{k}}{2}})f(t_{k+1}))-\int _{t_{k}}^{t_{k+1}}f(t)=\int _{t_{k}}^{t_{k+1}}G(t)f'(t)\!\,$

Apply Hint

Starting with the hint and applying product rule, we get

$\int _{t_{k}}^{t_{k+1}}(f(t)G(t))'dt=\int _{t_{k}}^{t_{k+1}}f'(t)G(t)dt+\int _{t_{k}}^{t_{k+1}}f(t)G'(t)dt\!\,$.

Also, we know from the Fundamental Theorem of Calculus

$\int _{t_{k}}^{t_{k+1}}(f(t)G(t))'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 $\int _{t_{k}}^{t_{k+1}}f'(t)G(t)\!\,$ yields

$(2)\qquad -G(t_{k})f(t_{k})+G(t_{k+1})f(t_{k+1})-\int _{t_{k}}^{t_{k+1}}G'(t)f(t)dt=\int _{t_{k}}^{t_{k+1}}G(t)f'(t)\!\,$

Choose G'(t)

Let $G'(t)=1\!\,$. Therefore, since $G(t)\!\,$ is linear

$(3)\qquad 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}^{\infty }\!\,$ be a system of polynomials with $deg\,Q_{n}=n\!\,$ for each $n\!\,$, orthogonal with respect to the inner product $\langle g,h\rangle =\int _{a}^{b}\rho (x)g(x)h(x)dx,\quad \forall g,h\in C[a,b]\!\,$ For a fixed integer $n\geq 2\!\,$, let $x_{1},\ldots ,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})}},\quad k=1,2,\ldots ,n\!\,$ be polynomials of degree $n-1\!\,$. Show that $\int _{a}^{b}\rho (x)r_{j}(x)r_{k}(x)dx=0,\forall j\neq k\!\,$ and that $\sum _{k=1}^{n}\int _{a}^{b}\rho (x)(r_{k}(x))^{2}dx=\int _{a}^{b}\rho (x)dx\!\,$ Hint: Use orthogonality to simplify $\int _{a}^{b}\rho (x)(\sum _{k=1}^{n}r_{k}(x))^{2}dx\!\,$

Solution 3a

${\begin{aligned}&\quad \int _{a}^{b}\rho (x)r_{j}(x)r_{k}(x)dx\\&=\int _{a}^{b}\rho (x)\prod _{i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}\prod _{i\neq k}{\frac {x-x_{i}}{x_{k}-x_{i}}}dx\\&=\int _{a}^{b}\overbrace {\frac {\prod _{i\neq k,i\neq j}^{n}x-x_{i}}{\prod _{i\neq j}^{n}x_{j}-x_{i}}} ^{Q_{n-2}}\overbrace {\frac {\prod _{i=1}^{n}x-x_{i}}{\prod _{i\neq k}^{n}x_{k}-x_{i}}} _{n}^{Q}dx\\&=0\end{aligned}}\!\,$

Solution 3b

${\begin{aligned}&\quad \sum _{k=1}^{n}\int _{a}^{b}\rho (x)(r_{k}(x))^{2}dx\\&=\int _{a}^{b}\rho (x)\sum _{k=1}^{n}(r_{k}(x))^{2}dx\\&=\int _{a}^{b}\rho (x)(\sum _{k=1}^{n}r_{k}(x))^{2}dx{\mbox{ (from part a) }}\\&=\int _{a}^{b}\rho (x)(1)^{2}dx{\mbox{ (from claim) }}\\&=\int _{a}^{b}\rho (x)dx\end{aligned}}\!\,$

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,\ldots ,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\!\,$