Preliminary Exam, Numerical Analysis, January 2009

Polynomial Interpolation Let \(I=[a,b]\), let \(x_i\), \(i=0,\ldots ,n\), be \(n+1\) distinct points in \(I\), and let \(y_i\), \(i=0,\ldots ,n\), be \(n+1\) given real numbers. Show that there exists a unique polynomial \[ p(x)=\sum _{i=0}^n \alpha _i x^i \] such that \[ p(x_i)=y_i,\qquad i=0,\ldots ,n. \]

Error Analysis Consider the linear system \[ Ax=b \tag {1} \] where \(A\) is an invertible matrix. Let \(\hat {x}\) be an approximation of the solution of (1) and let \[ e=x-\hat {x}\qquad \text {and}\qquad r=b-A\hat {x}. \] Let \(\|\cdot \|\) denote any vector norm or the corresponding induced matrix norm. Show that \[ \frac {\|e\|}{\|x\|} \leq \|A\|\|A^{-1}\|\frac {\|r\|}{\|b\|}. \] Comment on the significance of the condition number \(\|A\|\|A^{-1}\|\) and give a lower bound for it in terms of the eigenvalues of \(A\).

Linear Programming Define the phrase “Linear Programming Problem”. Let \(A\) be a given \(m\times n\) matrix with \(m>n\), and let \(b\in \mathbb {R}^m\) be a given vector. Write the problem \[ \text {Find }x\in \mathbb {R}^n\quad \text {such that }\|Ax-b\|_\infty =\min \] as a linear programming problem.

The Gershgorin Theorem Let \(\lambda \) be an eigenvalue of \(A\in A^{n\times n}\). Show that there exists an \[ i\in \{1,2,\cdots ,n\} \tag {2} \] such that \[ |a_{ii}-\lambda |\leq \sum _{\substack {j=1\\ i\neq j}}^n |a_{ij}| \tag {3} \]

For every eigenvalue \(\lambda \), the inequality (3) describes a circle in the complex plane called a Gershgorin circle. Let \(S\) be a set that is the union of \(k\leq n\) Gershgorin circles such that the intersection of \(S\) with all other Gershgorin circles is empty. Show that \(S\) contains precisely \(k\) eigenvalues of \(A\) (counting multiplicities). Without proof or counterproof state whether it is possible for a Gershgorin Circle not to contain any eigenvalue at all.

Adaptive Quadrature Describe the basic idea of adaptive quadrature, and give a simple example, including formulas.

Linear Multistep Methods Consider the initial value problem \[ y'=f(x,y),\qquad y(a)=y_0 \] Let \(h\) be some stepsize, \(x_n=a+nh\), \(y_n\approx y(x_n)\), and \(f_n=f(x_n,y_n)\), for \(n=0,1,2,3,\ldots \). Let \(k\) be some step number, and ignore the question of obtaining starting values \(y_1,y_2,\ldots ,y_{k-1}\). Suppose the approximations \(y_n\), \(n=k,k+1,\ldots \) are obtained by the Linear Multistep Method \[ \sum _{j=0}^k \alpha _j y_{n+j} =h\sum _{j=0}^k \beta _j f_{n+j}. \tag {4} \] Define what is meant by the local truncation error and the order of the linear multistep method (4). Compute the order and the local truncation error of Euler’s Method \[ y_{n+1}-y_n=hf_n. \tag {5} \]

Numerical PDEs Consider the one-dimensional heat equation: Find \(u(x,t)\) such that \[ u_t=u_{xx},\qquad t\geq 0,\qquad x\in [0,1],\qquad u(x,0)=f(x),\qquad u(0,t)=u(1,t)=0. \] Describe how this problem might be solved by applying the Method of Lines and Euler’s Method. Give formulas that could be used to write a suitable computer code.