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 ∫_{−1}^{1} w(x)f(x)dx, where w(x) = 1 + x^{4}. Leave any irrationals in simplified radical form (i.e. \frac{\sqrt{5}}{3}. etc.).

2. Let < f, g >= ∑_{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 F_{k} denote the discrete Fourier transform from C^{k} to C^{k}.

(a) Give formulas which allow you to compute F_{N} in terms of F_{n} (one step of the FFT).

(b) Let

y = [\begin{matrix}−1 \\ 0 \\ 1 \\ 2 \end{matrix}] .

Compute F_{4}(y).

(c) Let the components of the vector y of part (b) be denoted by y_{0}, y_{1}, y_{2}, y_{3}. Find the interpolating function of the form p(x) = ∑_{k=0}^{3} a_{k} exp(ikx), such that p(\frac{jπ}{2} ) = y_{j}.

4. We use the same notation as in problem 5.

(a) Express the matrix F_{4} in terms of ω = exp(\frac{−πi}{2}). (This is not exactly the same notation that I used in class.)

(b) Let

[\begin{matrix}c_{0} \\ c_{1} \\ c_{2} \\ c_{3} \end{matrix}] = F_{4}(y),

where y is any vector in C^{n}. Derive the following factorization:

[\begin{matrix}c_{0} \\ c_{2} \\ c_{1} \\ c_{3} \end{matrix}] = \frac{1}{4} [\begin{matrix}1 & 1 & 0 & 0 \\ 1 & ω^{2} & 0 & 0 \\ 0 & 0 & 1 & ω \\ 0 & 0 & 1 & ω^{3} \end{matrix}] [\begin{matrix}1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & ω^{2} & 0 \\ 0 & 1 & 0 & ω^{2} \end{matrix}] y

5. Do one step of Newton’s method for solving the system

x^{2} + 4y^{2} = 4, x + y = 0,

starting at the point (x_{0}, y_{0}) = (1, 0).

6. Using Householder transformations, find a symmetric tridiagonal matrix which is orthogonally similar to

[\begin{matrix}1 & 4 & −3 \\ 4 & 0 & 25 \\ −3 & 25 & 0 \end{matrix}]

7. Let V be a real vector space with inner product < u, v >. Let {ϕ_{1}, ϕ_{2}, ⋯, ϕ_{n}} be an orthonormal set in V. Let v ∈ V and let c_{j} =< v, ϕ_{j} >. Prove Bessel’s inequality:

∑_{j=1}^{n} c_{j}^{2} ≤ ∥v∥^{2}

8. Let A be a real symmetric matrix with eigenvalues −5, 1, 3. Let x^{0} be a fixed vector in R^{3} which is not orthogonal to any of the eigenvectors of A.

a) Let the vectors x^{k} and the values μ_{k} be generated by the following scheme:

y^{k} = Ax^{k−1},
μ_{k} = (y^{k})^{T} x^{k−1},
x^{k} = \frac{y^{k}}{∥y^{k}∥_{2}}

What is lim_{k→∞} μ_{k}? Explain your answer.

Sample Problems 3

b) If we generate x^{k} and the values ν_{k} by the following scheme what

is lim_{k→∞} ν_{k}? Explain your answer.

(A − 2I)y^{k} = x^{k−1},
ν_{k} = (y^{k})^{T} x^{k−1},
x^{k} = \frac{y^{k}}{∥y^{k}∥_{2}}