Preliminary Exam, Numerical Analysis, January 2012

Full rank matrix

Given \(A\in \mathbb {C}^{m\times n}\) with \(m\geq n\), show that \(A^*A\) is nonsingular if and only if \(A\) has full rank.

\(QR\) and Cholesky Factorizations

Let \(A\) be a nonsingular square matrix and let \(A=QR\) and \(A^*A=U^*U\) be the \(QR\) factorization of \(A\) and the Cholesky factorization of \(A^*A\), respectively. Assume that the usual normalizations \(r_{jj},u_{jj}>0\) are in effect. Is it true or false that \(R=U\)? Justify your answer.

Midpoint Rule

Derive error estimate for the midpoint rule in the form: \[ |E_n^M|\leq \frac {h^2(b-a)}{24} \max _{a\leq x\leq b}|f''(x)| \] Midpoint rule: \[ M_n(f)=h(f(x_1)+f(x_2)+\cdots +f(x_n)) \] where \(h=(b-a)/n\) and \[ x_j=a+\left (j-\frac {1}{2}\right )h,\qquad j=1,\ldots ,n \]

Spectral Radius

Let \(A\in \mathbb {C}^{m\times m}\) and \(\|\cdot \|\) denote any operator norm on \(m\times m\) matrices. Show that \[ \lim _{k\to \infty }\|A^k\|^{1/k}=\rho (A). \]

Interpolating Polynomial

Define \(l_{i,n}(x)\) - Lagrange basis functions with \(x_0,x_1,\ldots ,x_n\). Prove that for any \(n\geq 1\), \[ \sum _{i=0}^n l_{i,n}(x)=1 \] for all \(x\).

Linear Multistep Methods

Construct an example of:

a) a consistent but not stable (not zero-stable) linear multistep method

b) a stable (zero-stable) but not consistent linear multistep method

What kind of behavior do you expect from the numerical solution produced by the methods in a) and in b)?

Convergence of Linear Multistep Method

Consider the method \[ y_{n+2}-2y_{n+1}+y_n = \frac {h}{2}\left (f(t_{n+2},y_{n+2})-f(t_n,y_n)\right ) \] Apply the method to the scalar IVP \(y'=y\), \(y(0)=1\) and solve exactly the resulting difference equation, considering the starting values to be \(y_0=y_1=1\). Show theoretically that the numerical solution does not converge as \(h\to 0\) and \(n\to \infty \).

Stability of the Scheme

Using the von Neumann method investigate the stability of the implicit downwind scheme: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - \frac {u_m^{n+1}-u_{m-1}^{n+1}}{h} = f_m^n, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1. \]