Preliminary Exam, Numerical Analysis, Winter 2020

Rank-One Perturbation of the Identity

If \(x\) and \(y\) are \(m\)-vectors, the matrix \(A=I+xy^*\) is known as a rank-one perturbation of the identity. Show that if \(A\) is nonsingular, then its inverse has the form \(A^{-1}=I+\beta xy^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(x\) and \(y\) is \(A\) singular? If it is singular, what is \(\operatorname {null}(A)\)?

Properties via SVD 

Prove that any matrix in \(\mathbb {C}^{m\times n}\) is the limit of a sequence of matrices of full rank. Use the 2-norm for your proof.

Numerical Integration

Determine a formula \[ \int _{-\pi }^{\pi } f(x)\cos (x)\,dx \approx A_0 f\left (-\frac {3}{4}\pi \right ) +A_1 f\left (-\frac {1}{4}\pi \right ) +A_2 f\left (\frac {1}{4}\pi \right ) +A_3 f\left (\frac {3}{4}\pi \right ) \] that is exact when \(f\) is a polynomial of degree 3.

Numerical Algorithm to Find Eigenvalues/Eigenvectors

State the Rayleigh Quotient Iteration Algorithm to find eigenvalues/eigenvectors for general real symmetric matrix \(A\in \mathbb {R}^{m\times m}\).

Interpolation

Let \(x_0,\ldots ,x_n\) be distinct real points, and consider the following interpolation problem. Choose a function \[ F_n(x)=\sum _{j=0}^{n}a_j e^{jx} \] such that \[ F_n(x_i)=y_i,\qquad i=0,1,\ldots ,n \] with the \(\{y_i\}\) given data. Show there is a unique choice of \(a_0,\ldots ,a_n\).

Unstable Multistep Method

Consider the numerical method \[ y_{k+1}=3y_k-2y_{k-1} +\frac {h}{2}\left (f(x_k,y_k)-3f(x_{k-1},y_{k-1})\right ), \qquad k\ge 1 \] Illustrate with an example of a simple initial value problem that the above scheme is unstable.

 Heat Equation and Stability of the Scheme

Consider the implicit in time, Backward Euler method for the solution of the heat equation: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - 4\frac {u_{m+1}^{n+1}-2u_m^{n+1}+u_{m-1}^{n+1}}{h^2} = f_m^{n+1}, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1, \] and investigate the stability of the scheme using the von Neumann analysis.