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

Problem 1

A set of functions $\{g_1,\dots ,g_n\}\subset C[a,b]$ is a Chebyshev system if (i) The set is linearly independent. (ii) If $g$ is a linear combination of $\{g_1,\dots ,g_n\}$ which is not identically zero, $g$ has at most $n-1$ distinct zeros in $[a,b]$.

Problem 1a

Show that $\{g_1,\dots ,g_n\}$ is a Chebyshev system if and only if for any $n$ distinct points $x_1,\dots ,x_n\in [a,b]$ the matrix $A$ with $a_{i,j}=g_j(x_i),1\le i,j\le n$ is non-singular.

Solution 1a

Forward Direction

We want to prove the following statement:

If $\{g_1,\dots ,g_n\}$ is a Chebyshev system, then for any $n$ distinct points $x_1,\dots ,x_n\in [a,b]$ the matrix $A$ with $a_{i,j}=g_j(x_i),1\le i,j\le n$ is non-singular.

Writing out the matrix $A$ yields:

$A=\left(\begin{array}{cccc}{g}_1(x_1)& g_2(x_1)& \cdots & g_n(x_1)\\ g_1(x_2)& g_2(x_2)& \cdots & g_n(x_2)\\ ⋮& ⋮& \ddots & ⋮\\ g_1(x_n)& g_2(x_n)& \cdots & g_n(x_n)\end{array}\right)$

Since the set $\{g_1,\dots ,g_n\}$ is linearly independent, there does not exist any non-zero sets of constants of ${\alpha }_i$ such that $\sum _{i=1}^n{\alpha }_i{g}_i(x)=0$ for any $x\in [a,b]$. Hence, the columns of the matrix $A$ are linearly independent which implies that $A$ is non-singular.

Reverse Direction

Proof of (i)

Assume $A$ is non-singular.

This implies the columns of

$A=\left(\begin{array}{cccc}{g}_1(x_1)& g_2(x_1)& \cdots & g_n(x_1)\\ g_1(x_2)& g_2(x_2)& \cdots & g_n(x_2)\\ ⋮& ⋮& \ddots & ⋮\\ g_1(x_n)& g_2(x_n)& \cdots & g_n(x_n)\end{array}\right)$

are linearly independent. Since $A$ is non-singular for any choice of $\{x_1,x_2,\dots ,x_n\}$, $\{g_1,g_2,\dots ,g_n\}$ is a linearly independent set and we have shown $(i)$.

Proof of (ii)

By hypothesis, $g(x)$ is a linear combination of $\{g_1,g_2,\dots ,g_n\}$ i.e.

$g(x)={\alpha }_1{g}_1(x)+{\alpha }_2{g}_2(x)+\cdots +{\alpha }_n{g}_n(x)$

for ${\alpha }_i$ not all zero.

Assume for the sake of contradiction that $g(x)$ has $n$ zeros at $\widehat{x_1},\widehat{x_2},\dots ,\widehat{x_n}$

This implies the following $n$ equations:

$\begin{array}{cc}g(\widehat{x_1})& =0={\alpha }_1{g}_1(\widehat{x_1})+{\alpha }_2{g}_2(\widehat{x_1})+\cdots +{\alpha }_n{g}_n(\widehat{x_1})\\ g(\widehat{x_2})& =0={\alpha }_1{g}_1(\widehat{x_2})+{\alpha }_2{g}_2(\widehat{x_2})+\cdots +{\alpha }_n{g}_n(\widehat{x_2})\\ & ⋮\\ g(\widehat{x_n})& =0={\alpha }_1{g}_1(\widehat{x_n})+{\alpha }_2{g}_2(\widehat{x_n})+\cdots +{\alpha }_n{g}_n(\widehat{x_n})\end{array}$

Rewriting the equations in matrix form yields

$\left(\begin{array}{cccc}{g}_1(\widehat{x_1})& g_2(\widehat{x_1})& \cdots & g_n(\widehat{x_1})\\ g_1(\widehat{x_2})& g_2(\widehat{x_2})& \cdots & g_n(\widehat{x_2})\\ ⋮& ⋮& \ddots & ⋮\\ g_1(\widehat{x_n})& g_2(\widehat{x_n})& \cdots & g_n(\widehat{x_n})\end{array}\right)\left(\begin{array}{c}{\alpha }_1\\ {\alpha }_2\\ ⋮\\ {\alpha }_n\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ ⋮\\ 0\end{array}\right)$

Since ${\alpha }_i$ are not all zero, this implies that the columns of $A$, $\{g_1,g_2,\dots ,g_n\}$, are linearly dependent, a contradiction.

Hence, $g$ has at most $n-1$ zeros, and we have shown $(ii)$.

Problem 1b

Let $f\in C^{m+1}[a,b]$ be such that $f^{(m+1)}(x)\ne 0$ for all $x\in [a,b]$. Let $g_j(x)=x^{j-1},j=1,\dots ,m+1$. Show that $\{g_1,\dots ,g_{m+1},f\}$ is a Chebyshev system. For this, you may use results from polynomial interpolation without proof.

Solution 1b

We have to prove:

(i) $\{1,x,x^2,\dots ,f\}$ is a linearly independent set

(ii)any linear combination of this set has at most $m$ zeros.

Proof of (i)

If we evaluate $g_1,g_2,\dots ,g_{m+1}$ at $m+1$ distinct points, $\{x_1,x_2,\dots ,x_{m+1}\}$, we have the following Van Der Monde matrix whose determinant is non-zero.

$\left(\begin{array}{cccc}1& 1& \cdots & 1\\ x_1& x_1^2& \cdots & x_1^m\\ ⋮& ⋮& \ddots & ⋮\\ x_{m+1}& \cdots & \cdots & x_{m+1}^m\end{array}\right)$

Hence, $g_1,g_2,\dots ,g_{m+1}$ are linearly independent.

Assume for the sake of contradiction that $f$ is a linear combination of $g_1,g_2,\dots ,g_{m+1}$, that is

$\begin{array}{cc}f(x)& ={\beta }_0{g}_1(x)+{\beta }_1{g}_2(x)+\dots +{\beta }_m{g}_{m+1}(x)\\ & ={\beta }_0\cdot 1+{\beta }_{1}x+{\beta }_2{x}^2+\dots +{\beta }_m{x}^m\end{array}$.

Hence, $f(x)$ is a polynomial of degree $m$. Taking $m+1$ derivatives of $f(x)$ yields

$f^{(m+1)}(x)=0$

which contradicts the hypothesis. Therefore $\{1,x,x^2,\dots ,f\}$ is a linearly independent set.

Proof of (ii)

Let $h(x)={\beta }_0{g}_1(x)+{\beta }_1{g}_2(x)+\dots +{\beta }_m{g}_{m+1}(x)+{\beta }_{m+1}f(x)$.

Suppose $h$ has $m+2$ (or more) zeros in $[a,b]$. By Rolle's Theorem, the (n+1)st derivative of f vanishes on the given interval, a contradiction.

(i) and (ii) show that $\{1,x,x^2,\dots ,f\}$ is a Chebyshev system.

Problem 2

Let $I_n(f)=\sum _{k=1}^n{w}_{n,k}f(x_n,k),a\le x_{n,k}\le b(0)$ be a sequence of integration rules.

Problem 2a

Suppose $\underset{n\to \mathrm{\infty }}{\lim }{I}_n(x^k)=\underset{a}{\overset{b}{\int }}{x}^{k}dx,k=0,1,\dots (1)$ and $\sum _{k=1}^n|w_{n,k}|\le M,n=1,2,\dots (2)$ for some constant $M$. Show that $\underset{n\to \mathrm{\infty }}{\lim }{I}_n(f)=\underset{a}{\overset{b}{\int }}f(x)dx$ for all $f\in C[a,b]$

Solution 2a

By the Weierstrass Approximation Theorem, given $ϵ>0$, there exists a polynomial $p(x)$ such that

$\underset{a\le x\le b}{\max }|f(x)-p(x)|\le \min \{\frac{ϵ}{2}\cdot \frac{1}{M},\frac{ϵ}{2}\cdot \frac{1}{b-a}\}(3)$

Let

$I(f)=\underset{a}{\overset{b}{\int }}f(x)dx$

Adding and subtracting $I(p)$ and $I_n(p)$, yields,

$I(f)-I_n(f)=[I(f)-I(p)]+[I(p)-I_n(p)]+[I_n(p)-I_n(f)]$

By the triangle inequality and equation (2) and (3),

$\begin{array}{cc}|I(f)-I_n(f)|& \le |I(f-p)|+|I(p)-I_n(p)|+|I_n(p-f)|\\ & \le \underset{a}{\overset{b}{\int }}|f(x)-p(x)|dx+|I(p)-I_n(p)|+\sum _{k=1}^n|w_{n,k}||f(x_n,k)-p(x_n,k)|\\ & \le \frac{ϵ}{2(b-a)}\underset{a}{\overset{b}{\int }}dx+|I(p)-I_n(p)|+\frac{ϵ}{2M}\sum _{k=1}^n|w_{n,k}|\\ & \le \frac{ϵ}{2(b-a)}(b-a)+|I(p)-I_n(p)|+\frac{ϵ}{2M}M\\ & =ϵ+|I(p)-I_n(p)|\end{array}$

By equation (1), when $n\to \mathrm{\infty }$ ,

$|I(p)-I_n(p)|=0$

Hence for arbitrary small $ϵ>0$ as $n\to \mathrm{\infty }$,

$|I(f)-I_n(f)|\le ϵ$

i.e.

$I(f)=\underset{n\to \mathrm{\infty }}{\lim }{I}_n(f)$

Problem 2b

Show that if all $w_{n,k}>0$ then (1) implies (2).

Solution 2b

For $k=0$, equation (1) yields,

$\begin{array}{cc}\underset{n\to \mathrm{\infty }}{\lim }{I}_n(x^0)& =\underset{a}{\overset{b}{\int }}{x}^{0}dx\\ \underset{n\to \mathrm{\infty }}{\lim }{I}_n(1)& =\underset{a}{\overset{b}{\int }}1\cdot dx\\ & =(b-a)\end{array}$

Letting $f(x)$ in equation (0) yields,

$I_n(1)=\sum _{k=1}^n{w}_{n,k}\cdot 1=\sum _{k=1}^n{w}_{n,k}$

Combining the two above results yields,

$\begin{array}{cc}\underset{n\to \mathrm{\infty }}{\lim }{I}_n(1)& =\underset{n\to \mathrm{\infty }}{\lim }\sum _{k=1}^n{w}_{n,k}\\ & =(b-a)\\ & \le M\end{array}$

Since $(b-a)$ is finite, there exists some number $M$ such that $(b-a)\le M$.

Since $w_{n,k}>0$,

$\underset{n\to \mathrm{\infty }}{\lim }\sum _{k=1}^n|w_{n,k}|\le M$

i.e. equation (2).

Problem 3

Consider the real system of linear equations $Ax=b(1)$ where $A$ is non singular and satisfies $(v,Av)>0$ for all real $v$, where the Euclidean inner product is used here.

Problem 3a

Show that $(v,Av)=(v,Mv)$ for all real $v$ where $M=\frac{1}{2}(A+A^T)$ is the symmetric part of $A$.

Solution 3a

Substituting for $M$ in $(v,Mv)$ and expanding the inner product we have,

$\begin{array}{cc}(v,Mv)& =(v,\frac{1}{2}(A+A^T)v)\\ & =(v,\frac{1}{2}Av+\frac{1}{2}{A}^{T}v)\\ & =(v,\frac{1}{2}Av)+(v,\frac{1}{2}{A}^{T}v)\\ & =\frac{1}{2}(v,Av)+\frac{1}{2}(v,A^{T}v)\end{array}$

From properties of inner products we have,

$(v,A^{T}v)=(Av,v)=(v,Av)$

Hence,

$\begin{array}{cc}(v,Mv)& =\frac{1}{2}(v,Av)+\frac{1}{2}(v,A^{T}v)\\ & =\frac{1}{2}(v,Av)+\frac{1}{2}(v,Av)\\ & =(v,Av)\end{array}$

Problem 3b

Prove that $\frac{(v,Av)}{(v,v)}\ge {\lambda }_{\min }(M)>0$ where ${\lambda }_{\min }(M)$ is the minimum eigenvalue of $M$.

Solution 3b

First Inequality

$\frac{(v,Av)}{(v,v)}=\frac{(v,Mv)}{(v,v)}=\frac{v^{T}Mv}{v^{T}v}$

Since $M$ is symmetric, it has a eigenvalue decomposition

$M=Q^T\mathrm{\Lambda }Q$

where $Q$ is orthogonal and $\mathrm{\Lambda }$ is a diagonal matrix containing all the eigenvalues.

Substitution yields,

$\frac{(v,Av)}{(v,v)}=\frac{v^T{Q}^T\mathrm{\Lambda }Qv}{v^{T}v}$

Let

$Qv=x$

This implies the following three relationships:

$\begin{array}{cc}v& =Q^{T}x\\ v^T{Q}^T& =x^T\\ v^T& =x^{T}Q\end{array}$

Substituting,

$\begin{array}{cc}\frac{v^T{Q}^T\mathrm{\Lambda }Qv}{v^{T}v}& =\frac{x^T\mathrm{\Lambda }x}{x^{T}Q{Q}^{T}x}\\ & =\frac{x^T\mathrm{\Lambda }x}{x^{T}x}\end{array}$

Expanding the numerator we have,

$\begin{array}{cc}{x}^T\mathrm{\Lambda }x& =\left[\begin{array}{c}{x}_1{x}_2\dots x_n\end{array}\right]\left[\begin{array}{cccc}{\lambda }_1& & & \\ & {\lambda }_2& & \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]\\ & =\left[\begin{array}{c}{x}_1{x}_2\dots x_n\end{array}\right]\left[\begin{array}{c}{\lambda }_1{x}_1\\ {\lambda }_2{x}_2\\ ⋮\\ {\lambda }_n{x}_n\end{array}\right]\\ & ={\lambda }_1{x}_1^2+{\lambda }_2{x}^2+\dots +{\lambda }_n^2{x}_n^2\\ & =\sum _{i=1}^n{\lambda }_i{x}_i^2\end{array}$

Expanding the denominator yield

$x^{T}x=\sum _{i=1}^n{x}_i^2$

Substituting,

$\begin{array}{cc}\frac{x^T\mathrm{\Lambda }x}{x^{T}x}& =\frac{\sum _{i=1}^n{\lambda }_i{x}_i^2}{\sum _{i=1}^n{x}_i^2}\\ & \ge {\lambda }_{\min }(M)\frac{\sum _{i=1}^n{x}_i^2}{\sum _{i=1}^n{x}_i^2}\\ & ={\lambda }_{\min }(M)\end{array}$

Second Inequality

From part(a)

$(v,Av)=(v,Mv)>0$

for all real $v$.

Therefore $M$ is positive definite which implies all its eigenvalues are positive. In particular,

${\lambda }_{\min }(M)>0$

Problem 3c

Now consider the iteration for computing a series of approximate solutions to (1), $x_{k+1}=x_k+\alpha r_k$ where $r_k=b-A{x}_k$ and $\alpha$ is chosen to minimize $\Vert r_{k+1}{\Vert }_2$ as a function of $\alpha$. Prove that $\frac{\Vert r_{k+1}{\Vert }_2}{\Vert r_k{\Vert }_2}\le {(1-\frac{{\lambda }_{\min }(M{)}^2}{{\lambda }_{\max }(A^{T}A)})}^{\frac{1}{2}}$

Solution 3c

First, we want to write $\Vert r_{k+1}{\Vert }^2$ as a function of $\alpha$ i.e.

$f(\alpha )=\Vert r_{k+1}{\Vert }^2$

Changing the indices of equation $r_k$ from $k$ to $k+1$,substituting for $b-A{x}_k$, and applying the definition of norm yields,

$\begin{array}{cc}\Vert r_{k+1}{\Vert }^2& =\Vert b-A{x}_{k+1}{\Vert }^2\\ & =\Vert b-A{x}_k-\alpha A{r}_k{\Vert }^2\\ & =\Vert r_k-\alpha A{r}_k{\Vert }^2\\ & =(r_k-\alpha A{r}_k,r_k-\alpha A{r}_k)\\ & =(r_k,r_k)-\alpha (A{r}_k,r_k)-\alpha (r_k,A{r}_k)+{\alpha }^2(A{r}_k,A{r}_k)\end{array}$

From a property of inner products and since $A$ is symmetric,

$(r_k,A{r}_k)=(A^T{r}_k,r_k)=(A{r}_k,r_k)$

Hence,

$f(\alpha )=\Vert r_{k+1}{\Vert }^2=(r_k,r_k)-2\alpha (A{r}_k,r_k)+{\alpha }^2(A{r}_k,A{r}_k)$

Next we want to minimize $f(\alpha )$ as a function of $\alpha$. Taking its derivative with respect to $\alpha$ yields,

$f^{\prime }(\alpha )=-2(A{r}_k,r_k)+2\alpha (A{r}_k,A{r}_k)$

Setting $f^{\prime }(\alpha )=0$ and solving for $\alpha$ gives

$\begin{array}{cc}0& =-2(A{r}_k,r_k)+2\alpha (A{r}_k,A{r}_k)\\ 0& =-(A{r}_k,r_k)+\alpha (A{r}_k,A{r}_k)\\ (A{r}_k,r_k)& =\alpha (A{r}_k,A{r}_k)\\ \alpha & =\frac{(A{r}_k,r_k)}{(A{r}_k,A{r}_k)}\end{array}$

Substituting for $\alpha$ into $\Vert r_{k+1}{\Vert }^2$ gives,

$\begin{array}{cc}\Vert r_{k+1}{\Vert }^2& =(r_k,r_k)-2\alpha (A{r}_k,r_k)+{\alpha }^2(A{r}_k,A{r}_k)\\ & =(r_k,r_k)-2\frac{(A{r}_k,r_k)}{(A{r}_k,A{r}_k)}(A{r}_k,r_k)+\frac{(A{r}_k,r_k{)}^2}{(A{r}_k,A{r}_k{)}^2}(A{r}_k,A{r}_k)\\ & =(r_k,r_k)-2\frac{(A{r}_k,r_k{)}^2}{(A{r}_k,A{r}_k)}+\frac{(A{r}_k,r_k{)}^2}{(A{r}_k,A{r}_k)}\\ & =(r_k,r_k)-\frac{(A{r}_k,r_k{)}^2}{(A{r}_k,A{r}_k)}\end{array}$

By definition of norm,

$\Vert r_k{\Vert }^2=(r_k,r_k)$

Hence

$\frac{\Vert r_{k+1}{\Vert }^2}{\Vert r_k{\Vert }^2}=1-\frac{(A{r}_k,r_k{)}^2}{(r_k,r_k)(A{r}_k,A{r}_k)}$

Multiplying and dividing the second term on the right hand side of the above equation by $(r_k,r_k)$ and applying a property of inner product yields,

$\frac{\Vert r_{k+1}{\Vert }^2}{\Vert r_k{\Vert }^2}=1-\frac{(A{r}_k,r_k{)}^2(r_k,r_k)}{(r_k,r_k{)}^2(r_k,A^{T}A{r}_k)}$

From the result of part (b), we have our desired result:

$\frac{\Vert r_{k+1}{\Vert }_2}{\Vert r_k{\Vert }_2}\le {(1-\frac{{\lambda }_{\min }(M{)}^2}{{\lambda }_{\max }(A^{T}A)})}^{\frac{1}{2}}$