Sample Problems

Math 465

One notebook sized page of notes (both sides) allowed. Bring calculators to the exam. There are three pages of problems.

1.

Find the Gaussian quadrature rule of precision 3 for $\int_{-1}^{1}w(x)f(x)dx$, where w(x)=1+x⁴. Leave any irrationals in simplified radical form (i.e. $\frac {\sqrt 5} {3}$. etc.).

2.

Let $<f,g\gt=\sum_{j=0}^2 (j+1)f(j)g(j)$. Find the monic orthogonal polynomials of degree 0,1,2 for this inner product. What happens if you try to find the polynomial of degree 3?

3.

Let N=2n and let ${\mathcal F}_k$ denote the discrete Fourier transform from ${\bf C} ^k$ to ${\bf C} ^k$.

(a)

Give formulas which allow you to compute ${\mathcal F}_N$ in terms of ${\mathcal F}_n$ (one step of the FFT).

(b)

Let $$y= \begin{bmatrix} -1\\ 0\\ 1\\ 2\end{bmatrix}.$$ Compute ${\mathcal F}_4(y)$.

(c)

Let the components of the vector y of part (b) be denoted by y₀,y₁,y₂,y₃. Find the interpolating function of the form $p(x)=\sum_{k=0}^3a_k\exp(ikx)$, such that $p(\frac {j\pi} 2 ) = y_j$.

4.

We use the same notation as in problem 3.

(a)

Express the matrix ${\mathcal F}_4$ in terms of $\omega=\exp({\frac{-\pi i}{2} })$. (This may not be exactly the same notation in class.)

(b)

Let $$\begin{bmatrix} c_0\\ c_1\\ c_2\\ c_3\end{bmatrix}={\mathcal F}_4(y),$$where y is any vector in ${\bf C} ^n$. Derive the following factorization: $$\begin{bmatrix} c_0\\ c_2\\ c_1\\ c_3\end{bmatrix} = {\frac{1}... ...1&0&1&0\\ 0&1&0&1\\ 1&0&\omega^2&0\\ 0&1&0&\omega^2\end{bmatrix}y$$

5.

Do one step of Newton's method for solving the system $$x^2+4y^2=4,\hskip .1in x+y=0,$$
starting at the point (x₀,y₀)=(1,0).

6.

Using Householder transformations, find a symmetric tridiagonal matrix which is orthogonally similar to $$\begin{bmatrix} 1&4&-3\\ 4&0&25\\ -3&25&0\end{bmatrix}$$

7.

Let V be a real vector space with inner product <u,v>. Let $\{\phi_1, \phi_2, \cdots, \phi_n\}$ be an orthonormal set in V. Let $v\in V$ and let $c_j=<v,\phi_j\gt$. Prove Bessel's inequality: $$\sum_{j=1}^n c_j^2 \le \Vert v\Vert ^2$$

8.

Let A be a real symmetric matrix with eigenvalues -5, 1, 3. Let x⁰ be a fixed vector in ${\bf R} ^3$ which is not orthogonal to any of the eigenvectors of A.

a)

Let the vectors x^k and the values $\mu_k$ be generated by the following scheme:
$$\begin{align*} y^k&=Ax^{k-1},\\ \mu_k&=(y^k)^Tx^{k-1},\\ x^k&={\frac{y^k}{{\Vert y^k\Vert}_2} }\end{align*}$$
What is $\lim_{k\to \infty} \mu_k$? Explain your answer.

b)

If we generate x^k and the values $\nu_k$ by the following scheme what is $\lim_{k\to \infty} \nu_k$? Explain your answer.
$$\begin{align*} (A-2I)y^k&=x^{k-1},\\ \nu_k&=(y^k)^Tx^{k-1},\\ x^k&={\frac{y^k}{{\Vert y^k\Vert}_2} }\end{align*}$$