M465 -- Final Examination

Collaborative work on this examination is not permitted. Be sure to show all of your work. Turn in all relevant computer files either via email or on a 3.5-inch diskette. All work must be turned in by Thursday, 13 May 1999 at 3 p.m. GOOD LUCK!

1) Recall the Fixed Point Theorem, p. 61.

a) If we replace the hypothesis

$$\left\vert g^{\prime }\left( x\right) \right\vert \leq k$$

with

$$-k\leq g^{\prime }\left( x\right) <0,$$

prove that the convergence is oscillatory (like in Figure 2.6a, p. 59). ( Hint: Use the Mean Value Theorem.)

b) If we replace the hypothesis

$$\left\vert g^{\prime }\left( x\right) \right\vert \leq k$$

with

$$0<g^{\prime }\left( x\right) \leq k,$$

prove that the convergence is monotone (like in Figure 2.6b, p. 59). ( Hint: Again, use the Mean Value Theorem.)

2) Find the unique polynomial of degree two that interpolates the data $\left( 0,1\right)$, $\left( \frac{\pi }{4},\frac{\sqrt{2}}{2}% \right)$, $\left( \frac{\pi }{2},0\right)$, all of which lie on $y=\cos x$.

3) Exercise 14, p. 198, Section 4.3.

4) Consider the matrix equation Ax=b, where the $n\times n$ matrix A is

$$A=\left[ \begin{array}{ccccc} n & -1 & -1 & \cdots & -1 \\ ... ...ots & \vdots \\ -1 & -1 & -1 & \cdots & n \end{array}\right]$$

and the $n\times 1$ vector b is

$$\mathbf{b}=\left[ \begin{array}{c} 1 \\ 1 \\ 1 \\ \vdots \\ 1 \end{array}\right] .$$

a) Prove x=b, irrespective of n.

b) Prove A is strictly diagonally dominant.

c) Explain why Gaussian Elimination for solving Ax=bfor xcan be preformed without performed without pivoting for this problem.

d) Compare using Gaussian Elimination (without pivoting) and SOR (with $% \omega =1.25$) to solve Ax=b for various values of n. Your comparison should focus on operation counts; count the number of additions/subtractions separately from the number of multiplications/divisions. We expect that for small values of n, Gaussian Elimination will be more efficient than SOR but for large values of n, SOR will be more efficient than Gaussian Elimination. Find the value of n at which SOR becomes more efficient than Gaussian Elimination. For SOR, use the stopping criterion $\left\Vert \mathbf{r}_{k}\right\Vert _{\infty }<10^{-5}$, where the residual vector r_k=b-Ax _k.

Note: the amount of coding you have to do for this problem is minimal, since you possess code for both Gaussian Elimination and SOR. The SOR code will have to be altered to account for stopping criterion based on the residual.

5) Consider the Shooting Method for nonlinear differential equations (Algorithm 11.2, p. 635), which is implemented using the fourth-order Runge-Kutta method. Rewrite this program using the predictor-corrector method 3-Step Adams-Bashforth (predictor) / 2-Step Adams-Moulton (corrector) instead of Runge-Kutta. Use copious quantities of comments in your code: if I need to struggle to follow your logic, points will be deducted. Make sure also that I can easily compile your code; if I've had trouble with compiling your code in the past, turn this in early so the kinks can be ironed out before the due date.