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

## Problem 1

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

## Problem 1a

 Show that ${\displaystyle \{g_{1},\ldots ,g_{n}\}\!\,}$  is a Chebyshev system if and only if for any ${\displaystyle n\!\,}$  distinct points ${\displaystyle x_{1},\ldots ,x_{n}\in [a,b]\!\,}$  the matrix ${\displaystyle A\!\,}$  with ${\displaystyle a_{i,j}=g_{j}(x_{i}),1\leq i,j\leq n\!\,}$  is non-singular.

## Solution 1a

### Forward Direction

We want to prove the following statement:

If ${\displaystyle \{g_{1},\ldots ,g_{n}\}\!\,}$  is a Chebyshev system, then for any ${\displaystyle n\!\,}$  distinct points ${\displaystyle x_{1},\ldots ,x_{n}\in [a,b]\!\,}$  the matrix ${\displaystyle A\!\,}$  with ${\displaystyle a_{i,j}=g_{j}(x_{i}),1\leq i,j\leq n\!\,}$  is non-singular.

Writing out the matrix ${\displaystyle A\!\,}$  yields:

${\displaystyle A={\begin{pmatrix}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})\\\vdots &\vdots &\ddots &\vdots \\g_{1}(x_{n})&g_{2}(x_{n})&\cdots &g_{n}(x_{n})\end{pmatrix}}}$

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

### Reverse Direction

#### Proof of (i)

Assume ${\displaystyle A\!\,}$  is non-singular.

This implies the columns of

${\displaystyle A={\begin{pmatrix}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})\\\vdots &\vdots &\ddots &\vdots \\g_{1}(x_{n})&g_{2}(x_{n})&\cdots &g_{n}(x_{n})\end{pmatrix}}}$

are linearly independent. Since ${\displaystyle A\!\,}$  is non-singular for any choice of ${\displaystyle \{x_{1},x_{2},\ldots ,x_{n}\}\!\,}$ , ${\displaystyle \{g_{1},g_{2},\dots ,g_{n}\}\!\,}$  is a linearly independent set and we have shown ${\displaystyle (i)\!\,}$ .

#### Proof of (ii)

By hypothesis, ${\displaystyle g(x)\!\,}$  is a linear combination of ${\displaystyle \{g_{1},g_{2},\dots ,g_{n}\}\!\,}$  i.e.

${\displaystyle g(x)=\alpha _{1}g_{1}(x)+\alpha _{2}g_{2}(x)+\cdots +\alpha _{n}g_{n}(x)\!\,}$

for ${\displaystyle \alpha _{i}\!\,}$  not all zero.

Assume for the sake of contradiction that ${\displaystyle g(x)\!\,}$  has ${\displaystyle n\!\,}$  zeros at ${\displaystyle {\hat {x_{1}}},{\hat {x_{2}}},\ldots ,{\hat {x_{n}}}\!\,}$

This implies the following ${\displaystyle n\!\,}$  equations:

{\displaystyle {\begin{aligned}g({\hat {x_{1}}})&=0=\alpha _{1}g_{1}({\hat {x_{1}}})+\alpha _{2}g_{2}({\hat {x_{1}}})+\cdots +\alpha _{n}g_{n}({\hat {x_{1}}})\\g({\hat {x_{2}}})&=0=\alpha _{1}g_{1}({\hat {x_{2}}})+\alpha _{2}g_{2}({\hat {x_{2}}})+\cdots +\alpha _{n}g_{n}({\hat {x_{2}}})\\&\vdots \\g({\hat {x_{n}}})&=0=\alpha _{1}g_{1}({\hat {x_{n}}})+\alpha _{2}g_{2}({\hat {x_{n}}})+\cdots +\alpha _{n}g_{n}({\hat {x_{n}}})\end{aligned}}}

Rewriting the equations in matrix form yields

${\displaystyle {\begin{pmatrix}g_{1}({\hat {x_{1}}})&g_{2}({\hat {x_{1}}})&\cdots &g_{n}({\hat {x_{1}}})\\g_{1}({\hat {x_{2}}})&g_{2}({\hat {x_{2}}})&\cdots &g_{n}({\hat {x_{2}}})\\\vdots &\vdots &\ddots &\vdots \\g_{1}({\hat {x_{n}}})&g_{2}({\hat {x_{n}}})&\cdots &g_{n}({\hat {x_{n}}})\end{pmatrix}}{\begin{pmatrix}\alpha _{1}\\\alpha _{2}\\\vdots \\\alpha _{n}\end{pmatrix}}={\begin{pmatrix}0\\0\\\vdots \\0\end{pmatrix}}}$

Since ${\displaystyle \alpha _{i}\!\,}$  are not all zero, this implies that the columns of ${\displaystyle A\!\,}$ , ${\displaystyle \{g_{1},g_{2},\ldots ,g_{n}\}}$ , are linearly dependent, a contradiction.

Hence, ${\displaystyle g\!\,}$  has at most ${\displaystyle n-1\!\,}$  zeros, and we have shown ${\displaystyle (ii)\!\,}$ .

## Problem 1b

 Let ${\displaystyle f\in C^{m+1}[a,b]\!\,}$  be such that ${\displaystyle f^{(m+1)}(x)\neq 0\!\,}$  for all ${\displaystyle x\in [a,b]\!\,}$ . Let ${\displaystyle g_{j}(x)=x^{j-1},j=1,\ldots ,m+1\!\,}$ . Show that ${\displaystyle \{g_{1},\ldots ,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) ${\displaystyle \{1,x,x^{2},\dots ,f\}\!\,}$  is a linearly independent set

(ii)any linear combination of this set has at most ${\displaystyle m\!\,}$  zeros.

### Proof of (i)

If we evaluate ${\displaystyle g_{1},g_{2},\dots ,g_{m+1}\!\,}$  at ${\displaystyle m+1\!\,}$  distinct points, ${\displaystyle \{x_{1},x_{2},\ldots ,x_{m+1}\}}$ , we have the following Van Der Monde matrix whose determinant is non-zero.

${\displaystyle {\begin{pmatrix}1&1&\cdots &1\\x_{1}&x_{1}^{2}&\cdots &x_{1}^{m}\\\vdots &\vdots &\ddots &\vdots \\x_{m+1}&\cdots &\cdots &x_{m+1}^{m}\end{pmatrix}}}$

Hence, ${\displaystyle g_{1},g_{2},\dots ,g_{m+1}\!\,}$  are linearly independent.

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

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

Hence, ${\displaystyle f(x)\!\,}$  is a polynomial of degree ${\displaystyle m\!\,}$ . Taking ${\displaystyle m+1\!\,}$  derivatives of ${\displaystyle f(x)\!\,}$  yields

${\displaystyle f^{(m+1)}(x)=0\!\,}$

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

### Proof of (ii)

Let ${\displaystyle 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 ${\displaystyle h\!\,}$  has ${\displaystyle m+2\!\,}$  (or more) zeros in ${\displaystyle [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 ${\displaystyle \{1,x,x^{2},\dots ,f\}\!\,}$  is a Chebyshev system.

## Problem 2

 Let ${\displaystyle I_{n}(f)=\sum _{k=1}^{n}w_{n,k}f(x_{n},k),\quad \quad a\leq x_{n,k}\leq b\quad \quad (0)}$ be a sequence of integration rules.

## Problem 2a

 Suppose ${\displaystyle \lim _{n\rightarrow \infty }I_{n}(x^{k})=\int _{a}^{b}x^{k}dx,\quad \quad k=0,1,\ldots \quad \quad (1)}$ and ${\displaystyle \sum _{k=1}^{n}|w_{n,k}|\leq M,\quad \quad n=1,2,\ldots \quad \quad (2)}$ for some constant ${\displaystyle M\!\,}$ . Show that ${\displaystyle \lim _{n\rightarrow \infty }I_{n}(f)=\int _{a}^{b}f(x)dx}$ for all ${\displaystyle f\in C[a,b]\!\,}$

## Solution 2a

By the Weierstrass Approximation Theorem, given ${\displaystyle \epsilon >0\!\,}$ , there exists a polynomial ${\displaystyle p(x)\!\,}$  such that

${\displaystyle \max _{a\leq x\leq b}|f(x)-p(x)|\leq \min\{{\frac {\epsilon }{2}}\cdot {\frac {1}{M}},{\frac {\epsilon }{2}}\cdot {\frac {1}{b-a}}\}\quad \quad (3)}$

Let

${\displaystyle I(f)=\int _{a}^{b}f(x)dx}$

Adding and subtracting ${\displaystyle I(p)\!\,}$  and ${\displaystyle I_{n}(p)\!\,}$ , yields,

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

{\displaystyle {\begin{aligned}|I(f)-I_{n}(f)|&\leq |I(f-p)|+|I(p)-I_{n}(p)|+|I_{n}(p-f)|\\&\leq \int _{a}^{b}|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)|\\&\leq {\frac {\epsilon }{2(b-a)}}\int _{a}^{b}dx+|I(p)-I_{n}(p)|+{\frac {\epsilon }{2M}}\sum _{k=1}^{n}|w_{n,k}|\\&\leq {\frac {\epsilon }{2(b-a)}}(b-a)+|I(p)-I_{n}(p)|+{\frac {\epsilon }{2M}}M\\&=\epsilon +|I(p)-I_{n}(p)|\end{aligned}}}

By equation (1), when ${\displaystyle n\rightarrow \infty \!\,}$  ,

${\displaystyle |I(p)-I_{n}(p)|=0\!\,}$

Hence for arbitrary small ${\displaystyle \epsilon >0\!\,}$  as ${\displaystyle n\rightarrow \infty \!\,}$ ,

${\displaystyle |I(f)-I_{n}(f)|\leq \epsilon }$

i.e.

${\displaystyle I(f)=\lim _{n\rightarrow \infty }I_{n}(f)\!\,}$

## Problem 2b

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

## Solution 2b

For ${\displaystyle k=0\!\,}$ , equation (1) yields,

{\displaystyle {\begin{aligned}\lim _{n\rightarrow \infty }I_{n}(x^{0})&=\int _{a}^{b}x^{0}dx\\\lim _{n\rightarrow \infty }I_{n}(1)&=\int _{a}^{b}1\cdot dx\\&=(b-a)\end{aligned}}}

Letting ${\displaystyle f(x)\!\,}$  in equation (0) yields,

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

{\displaystyle {\begin{aligned}\lim _{n\rightarrow \infty }I_{n}(1)&=\lim _{n\rightarrow \infty }\sum _{k=1}^{n}w_{n,k}\\&=(b-a)\\&\leq M\end{aligned}}}

Since ${\displaystyle (b-a)\!\,}$  is finite, there exists some number ${\displaystyle M\!\,}$  such that ${\displaystyle (b-a)\leq M}$ .

Since ${\displaystyle w_{n,k}>0\!\,}$ ,

${\displaystyle \lim _{n\rightarrow \infty }\sum _{k=1}^{n}|w_{n,k}|\leq M}$

i.e. equation (2).

## Problem 3

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

## Problem 3a

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

## Solution 3a

Substituting for ${\displaystyle M\!\,}$  in ${\displaystyle (v,Mv)\!\,}$  and expanding the inner product we have,

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

From properties of inner products we have,

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

Hence,

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

## Problem 3b

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

## Solution 3b

### First Inequality

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

Since ${\displaystyle M\,\!}$  is symmetric, it has a eigenvalue decomposition

${\displaystyle M=Q^{T}\Lambda Q\!\,}$

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

Substitution yields,

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

Let

${\displaystyle Qv=x\!\,}$

This implies the following three relationships:

{\displaystyle {\begin{aligned}v&=Q^{T}x\\v^{T}Q^{T}&=x^{T}\\v^{T}&=x^{T}Q\end{aligned}}}

Substituting,

{\displaystyle {\begin{aligned}{\frac {v^{T}Q^{T}\Lambda Qv}{v^{T}v}}&={\frac {x^{T}\Lambda x}{x^{T}QQ^{T}x}}\\&={\frac {x^{T}\Lambda x}{x^{T}x}}\end{aligned}}}

Expanding the numerator we have,

{\displaystyle {\begin{aligned}x^{T}\Lambda x&={\begin{bmatrix}x_{1}x_{2}\ldots x_{n}\end{bmatrix}}{\begin{bmatrix}\lambda _{1}&&&\\&\lambda _{2}&&\\&&\ddots &\\&&&\lambda _{n}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}}\\&={\begin{bmatrix}x_{1}x_{2}\ldots x_{n}\end{bmatrix}}{\begin{bmatrix}\lambda _{1}x_{1}\\\lambda _{2}x_{2}\\\vdots \\\lambda _{n}x_{n}\\\end{bmatrix}}\\&=\lambda _{1}x_{1}^{2}+\lambda _{2}x^{2}+\ldots +\lambda _{n}^{2}x_{n}^{2}\\&=\sum _{i=1}^{n}\lambda _{i}x_{i}^{2}\end{aligned}}}

Expanding the denominator yield

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

Substituting,

{\displaystyle {\begin{aligned}{\frac {x^{T}\Lambda x}{x^{T}x}}&={\frac {\sum _{i=1}^{n}\lambda _{i}x_{i}^{2}}{\sum _{i=1}^{n}x_{i}^{2}}}\\&\geq \lambda _{\min }(M){\frac {\sum _{i=1}^{n}x_{i}^{2}}{\sum _{i=1}^{n}x_{i}^{2}}}\\&=\lambda _{\min }(M)\end{aligned}}}

### Second Inequality

From part(a)

${\displaystyle (v,Av)=(v,Mv)>0\!\,}$

for all real ${\displaystyle v\!\,}$ .

Therefore ${\displaystyle M\!\,}$  is positive definite which implies all its eigenvalues are positive. In particular,

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

## Problem 3c

 Now consider the iteration for computing a series of approximate solutions to (1), ${\displaystyle x_{k+1}=x_{k}+\alpha r_{k}\!\,}$  where ${\displaystyle r_{k}=b-Ax_{k}\!\,}$  and ${\displaystyle \alpha \!\,}$  is chosen to minimize ${\displaystyle \|r_{k+1}\|_{2}\!\,}$  as a function of ${\displaystyle \alpha \!\,}$ . Prove that ${\displaystyle {\frac {\|r_{k+1}\|_{2}}{\|r_{k}\|_{2}}}\leq \left(1-{\frac {\lambda _{\min }(M)^{2}}{\lambda _{\max }(A^{T}A)}}\right)^{\frac {1}{2}}\!\,}$

## Solution 3c

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

${\displaystyle f(\alpha )=\|r_{k+1}\|^{2}\!\,}$

Changing the indices of equation ${\displaystyle r_{k}\!\,}$  from ${\displaystyle k\!\,}$  to ${\displaystyle k+1\!\,}$ ,substituting for ${\displaystyle b-Ax_{k}\!\,}$ , and applying the definition of norm yields,

{\displaystyle {\begin{aligned}\|r_{k+1}\|^{2}&=\|b-Ax_{k+1}\|^{2}\\&=\|b-Ax_{k}-\alpha Ar_{k}\|^{2}\\&=\|r_{k}-\alpha Ar_{k}\|^{2}\\&=(r_{k}-\alpha Ar_{k},r_{k}-\alpha Ar_{k})\\&=(r_{k},r_{k})-\alpha (Ar_{k},r_{k})-\alpha (r_{k},Ar_{k})+\alpha ^{2}(Ar_{k},Ar_{k})\end{aligned}}}

From a property of inner products and since ${\displaystyle A\!\,}$  is symmetric,

${\displaystyle (r_{k},Ar_{k})=(A^{T}r_{k},r_{k})=(Ar_{k},r_{k})\!\,}$

Hence,

${\displaystyle f(\alpha )=\|r_{k+1}\|^{2}=(r_{k},r_{k})-2\alpha (Ar_{k},r_{k})+\alpha ^{2}(Ar_{k},Ar_{k})\!\,}$

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

${\displaystyle f^{\prime }(\alpha )=-2(Ar_{k},r_{k})+2\alpha (Ar_{k},Ar_{k})\!\,}$

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

{\displaystyle {\begin{aligned}0&=-2(Ar_{k},r_{k})+2\alpha (Ar_{k},Ar_{k})\\0&=-(Ar_{k},r_{k})+\alpha (Ar_{k},Ar_{k})\\(Ar_{k},r_{k})&=\alpha (Ar_{k},Ar_{k})\\\alpha &={\frac {(Ar_{k},r_{k})}{(Ar_{k},Ar_{k})}}\end{aligned}}}

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

{\displaystyle {\begin{aligned}\|r_{k+1}\|^{2}&=(r_{k},r_{k})-2\alpha (Ar_{k},r_{k})+\alpha ^{2}(Ar_{k},Ar_{k})\\&=(r_{k},r_{k})-2{\frac {(Ar_{k},r_{k})}{(Ar_{k},Ar_{k})}}(Ar_{k},r_{k})+{\frac {(Ar_{k},r_{k})^{2}}{(Ar_{k},Ar_{k})^{2}}}(Ar_{k},Ar_{k})\\&=(r_{k},r_{k})-2{\frac {(Ar_{k},r_{k})^{2}}{(Ar_{k},Ar_{k})}}+{\frac {(Ar_{k},r_{k})^{2}}{(Ar_{k},Ar_{k})}}\\&=(r_{k},r_{k})-{\frac {(Ar_{k},r_{k})^{2}}{(Ar_{k},Ar_{k})}}\end{aligned}}}

By definition of norm,

${\displaystyle \|r_{k}\|^{2}=(r_{k},r_{k})\!\,}$

Hence

${\displaystyle {\frac {\|r_{k+1}\|^{2}}{\|r_{k}\|^{2}}}=1-{\frac {(Ar_{k},r_{k})^{2}}{(r_{k},r_{k})(Ar_{k},Ar_{k})}}\!\,}$

Multiplying and dividing the second term on the right hand side of the above equation by ${\displaystyle (r_{k},r_{k})\!\,}$  and applying a property of inner product yields,

${\displaystyle {\frac {\|r_{k+1}\|^{2}}{\|r_{k}\|^{2}}}=1-{\frac {(Ar_{k},r_{k})^{2}(r_{k},r_{k})}{(r_{k},r_{k})^{2}(r_{k},A^{T}Ar_{k})}}\!\,}$

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

${\displaystyle {\frac {\|r_{k+1}\|_{2}}{\|r_{k}\|_{2}}}\leq \left(1-{\frac {\lambda _{\min }(M)^{2}}{\lambda _{\max }(A^{T}A)}}\right)^{\frac {1}{2}}\!\,}$