Numerical Analysis I, Fall 2009 (http://www.math.nthu.edu.tw/˜ wangwc/)

Homework Assignment for Week 13

Assigned Dec 11, 2009. Due Dec 18, 2009.

1. Section 6.2: Problems 7, 12, 15.

For problem 7, also consider C = I − ww^{T}. Give proper interpretations of the matrix A, B, C in terms of reflection and projection. For problem 12, read problem 9-11.

2. Section 6.3: Problems 1(a), 2, 5(a).

3. Section 6.4: Problems 6, 10, 11.

Skip section 6.4.1, only read the last paragraph of it.

4. There is a mistake in the following statement. Find it and correct it in your lecture note.

If A is tridiagonal nonsingular n × n matrix and A = LU, where L and U are bidiagonal lower and upper triangular matrices, respectively. Then both L^{−1} and U^{−1} are bi-diagonal matrices.

After correcting the error, find the operation count for direct multiplication of A^{−1}f. This is a contrast to solving Ax = f using LU decomposition/Gaussian elimination for tridiagonal systems.

Hint: Read Example 6.3.4 on page 274 and apply it to find L^{−1}.

Challenges of ... the week before last. As usual, you need to report preliminary progress by Dec 25.

5. Solve for the nodes and weights appearing in (5.73), page 227.

Hint: these are linear equations for the weights, therefore the linear dependency relations give rise to new equations for the locations.

6. Construct a periodic function f, such that trapezoidal rule gives I(f)−I_{n}^{T} (f) = O(n^{−6}) (exactly sixth order convergence, no more and no less). Demonstrate with numerical evidence.

7. Propose an quadrature for evaluating erf(x) = \frac{2}{\sqrt{π}} ∫_{−∞}^{x} exp(−t^{2})dt. The matlab builtin function ‘erf’ can be used to check accuracy of your algorithm. The credit for this problem is based on how many function evaluation of exp is used in your algorithm. Try to get 10 correct digits within 20 evaluations. Otherwise, do your best.

8. This problem is continuation of problem 16, section 4.2. This one requires some background in complex analysis and the programming part may be time consuming. You should talk to me first before implementing. Of course, it will carry a lot of extra credits. Do it if time permits.

In view of the dramatic difference between the cases [0, 2π] and [−π, π] (if you don’t know what that is, look at the solution posted on elearn), you may wonder what is the real reason behind the difference. An advanced theory (ask me if you are interested) states that the behavior of uniform grid interpolation is closely related to the location of the poles of the function to be interpolated. That is, if a pole of the function falls within certain region in the complex plane, then the interpolating polynomial with uniformly spaced grids will diverge.

Find this region by experimenting on f(x) = \frac{1}{a^{2}+(x−b)^{2}} on [−1, 1] and vary the parameters a and b. Then use it to predict, for what values of c ∈ R will the uniform grid interpolation for g(x) = \frac{1}{2+cos(πx+c)} on [−1, 1] converge/diverge.