Preliminary Examination, Numerical Analysis, Fall 1994

a) Derive a multistep method to approximate \(y'=f(t,y)\) of the form \[ y_{n+1}=y_n+h(b_{-1}y'_{n+1}+b_0y'_n+b_1y'_{n-1}) \] with \(y'_j=f(t_j,y_j)\), \(t_j=t_0+jh\) by interpolating \(f(s,y(s))\) at \(t_{n-1}\), \(t_n\), \(t_{n+1}\).

b) Analyze the local truncation error of this method and the consequences regarding convergence. What would be an appropriate predictor for this method?

c) Discuss the region of absolute stability of this method, and the predictor-corrector method described in part b).

a) Show that the best uniform (\(L^\infty [-1,1]\)) approximation of an even polynomial \(p_n(x)\) of (even) degree \(n\) by polynomials of degree \(\le n-2\) on \([-1,1]\), is given by \(p_n(x)-c_nT_n(x)\), where \(T_n\) is the Tchebyshev polynomial of degree \(n\), and \(c_n\) is an appropriately chosen constant. Hint: First find the best approximation by polynomials of degree \(\le n-1\).

b) What are the zeroes of \(T_n\) and what are their significance in interpolation. In particular, estimate the error of interpolation at Tchebyshev nodes.

Compare the stability of the Euler Predictor-Trapezoidal Corrector and Backwards Euler timestepping methods for solution of the heat equation \[ u_t=u_{xx}\qquad u(x,0)=u_0(x) \] using the centered second difference operator \[ u_j \to \frac {u_{j+1}-2u_j+u_{j-1}}{h^2}\qquad j=1,\ldots ,J \] where \(u_j\approx u(jh)\) on the interval \([0,2\pi ]\) with periodic boundary conditions, and mesh-size \(h=2\pi /J\). Discuss the accuracy of these methods?

a) What set of four nonlinear equations are satisfied by the nodes and weights for Gaussian quadrature with degree of precision 3, on the interval \([0,1]\).

b) Describe Newton’s method as applied to solving this system of equations.

c) Show how and why the weights and nodes for Gaussian quadrature may be modified from the standard interval to an arbitrary interval.

a) What is the best least squares approximation to \(f(x)=\cos 3x\) by functions of the form \[ a_0+a_1\cos x+a_2\cos ^2 x+b_1\sin x+b_2\sin ^2 x \] with the inner product given by \[ (v,w)_C=\frac {1}{2\pi }\int _0^{2\pi }v(x)\overline {w(x)}\,dx \]

b) What if the inner product is \[ (v,w)_D=\frac {1}{J}\sum _{j=0}^{J-1}v(x_j)\overline {w(x_j)} \] with \(x_j=jh\), \(h=2\pi /J\).

c) Briefly discuss the normal equations (do they form a well- or ill-conditioned system?), the Gram-Schmidt process, QR factorization in the context of parts a) and b). Observe the connection with problem #2.

a) Show that Jacobi’s method for solving \(Ax=b\) iteratively is convergent when \(A\) is strictly diagonally dominant. What does this imply about the spectral radius of another matrix obtained from \(A\).

b) Describe the successive over-relaxation (SOR) method with parameter \(\omega \) and it’s rate of convergence. Give a sufficient condition upon \(A\) and \(\omega \) for convergence.

c) Briefly compare the complexity of solving Poisson’s problem in three dimensions by direct and iterative methods. Assume the simplest methods, grid, differencing scheme, boundary conditions, etc.

a) Give an example to demonstrate the role of pivoting in Gaussian elimination in solving \(Ax=b\). Define and explain the significance of the condition number of \(A\). Compare the condition numbers, with respect to the norm of your choice, of \(A\) and \(PA\), where \(P\) is a permutation matrix.

b) Explain the \(LU\) decomposition of a matrix \(A\), in particular why the entries of \(L\) are multipliers used in Gaussian elimination, and how to solve \(Ax=b\) using \(L\) and \(U\). How much work does this take?

a) Give an identity that is the basis of one stage of the Fast Fourier Transform algorithm applied to a vector of length \(2^J\). Explain the approximate operation count for the complete algorithm.

b) Describe the application of the FFT to the solution of the heat equation with periodic boundary conditions, and how this may be viewed as performing a fast convolution.

a) Find the order/rate of convergence of Newton’s method to a multiple root \(r\) of multiplicity \(m>1\) of the scalar equation \(f(x)=0\).

b) What method is obtained by applying Aitken’s acceleration in this situation? Show that it is at least quadratically convergent.

c) How would you extrapolate an integration formula whose error behaved asymptotically as \[ I-I_n=c_3h^3+c_6h^6+\cdots \] where \(I\equiv \int _a^b f(x)\,dx\) is the exact value, \(I_n\) is the approximation with \(n\) subintervals, and \(h\equiv \frac {b-a}{n}\).