1. Let $A\in {\mathbb{R}}^{n\times n}$ be a non-singular matrix. Let $u,v\in {\mathbb{R}}^n$ be col umn vectors. Define the rank 1 perturbation $\hat{A}=A+u{v}^T$.
(a) Derive a necessary and sufficient condition for $\hat{A}$ to be inv ertible.
(b) Let $x,z$ and $b$ be column vectors in ${\mathbb{R}}^n$. Suppose one can solve $Az=b$ with $\mathcal{O}(n)$ floating-point operations (flops). Un der conditions derived in (a), design an algorithm to solve $\hat{A}x=b$ with $\mathcal{O}(n)$ flops, and provide justification for your an swer.

2. Consider the integral
$${\int }_0^{\mathrm{\infty }}f(x)\mathrm{d}x$$
where $f$ is continuous, $f^{\prime }(0)\ne 0$, and $f(x)$ decays like $x^{-1-\alpha }$ with $\alpha >0$ in the limit $x\to \mathrm{\infty }$.
(a) Suppose you apply the equispaced composite trapezoid $\mathrm{r}$ ule with $n$ subintervals to approximate
$${\int }_0^{L}f(x)\mathrm{d}x$$

What is the asymptotic error formula for the error in the limit $n\to \mathrm{\infty }$ with $L$ fixed?
(b) Suppose you consider the quadrature from (a) to be an ap proximation to the full integral from 0 to $\mathrm{\infty }$. How should $L$ in crease with $n$ to optimize the asymptotic rate of total error $d$ ecay? What is the rate of error decrease with this choice of $L$ ?
(c) Make the following change of variable $x=\frac{L(1+y)}{1-y}$, $y=\frac{x-L}{x+L}$ in the original integral to obtain
$${\int }_{-1}^1{F}_L(y)\mathrm{d}y$$

Suppose you apply the equispaced composite trapezoid rule; what is the asymptotic error formula for fixed $L$ ?
(d) Depending on $\alpha$, which method - domain truncation of ch ange-of-variable - is preferable?

3. Consider the Chebyshev polynomial of the first kind
$$T_n(x)=\cos (n\theta ),x=\cos (\theta ),x\in [-1,1].$$

The Chebyshev polynomials of the second kind are defined a $\mathrm{s}$
$$U_n(x)=\frac{1}{n+1}{T}^{\prime }(x),n\ge 0.$$
(a) Derive a recursive formula for computing $U_n(x)$ for all $n\ge 0$.
(b) Show that the Chebyshev polynomials of the second kind are orthogonal with respect to the inner product
$$⟨f,g⟩={\int }_{-1}^{1}f(x)g(x)\sqrt{1-x^2}\mathrm{d}x.$$
(c) Derive the 2-point Gaussian Quadrature rule for the integr al
$${\int }_{-1}^{1}f(x)\sqrt{1-x^2}\mathrm{d}x=\sum _{j=1}^3{w}_{j}f\left(x_j\right).$$

4. Consider the boundary value problem
$$-\frac{d}{dx}(a(x)\frac{du}{dx})=f(x),u(0)=u(1)=0$$
where $a(x)>\delta \ge 0$ is a bounded differentiable function in $[0,1]$. We assume that, although $a(x)$ is available, an expressi on for its derivative, $\frac{da}{dx}$, is not available.
(a) Using finite differences and an equally spaced gird in $[0,1],x_l=hl,l=0,\cdots ,n$ and $h=1/n$, we discretize the ODE to obtain a linear system of equations, yielding an $O\left(h^2\right)$ approximation of the ODE. After the application of the boundary conditions, the resulting coefficient matrix of the li near system is an $(n-1)\times (n-1)$ tridiagonal matrix.

Provide a derivation and write down the resulting linear syste $\mathrm{m}$ (by giving the expressions of the elements).
(b) Utilizing all the information provided, find a disc in $\mathbb{C}$, the smaller the better, that is guaranteed to contain all the eigenv alues of the linear system constructed in part (a).

5. (a) Verify that the PDE
$$u_t=u_{xxx}$$
is well posed as an initial value problem.
(b) Consider solving it numerically using the scheme
$$\frac{u(t+k,x)-u(t-k,x)}{2k}=\frac{-\frac{1}{2}u(x-2h,t)+u(x-h,t)-u(x+h,t)+\frac{1}{2}u(x+2h,t)}{h}.$$

Determine this scheme's stability condition.

6. Consider the diffusion equation
$$\frac{\partial v}{\partial t}=\mu \frac{{\partial }^{2}v}{\partial x^2},v(x,0)=\varphi (x),{\int }_a^{b}v(x,t)\mathrm{d}x=0$$
with $x\in [a,b]$ and periodic boundary conditions. The solutio $\mathrm{n}$ is to be approximated using the central difference operator $L$ for the 1D Laplacian.
$$L{v}_m=\frac{v_{m+1}-2v_m+v_{m-1}}{h^2}$$
and the following two finite different approximations, (i) Forw ard-Euler
$$v_{n+1}=v_n+\mu kL{v}_n,(1)$$
and (ii) Crank-Nicolson
$$v_{n+1}=v_n+\mu k(L{v}_n+L{v}_{n+1})$$

Throughout, consider $[a,b]=[0,2\pi ]$ and the finite differenc e stencil to have periodic boundary conditions on the spatial lattice $[0,h,2h,\cdots ,(N-1)h]$ where $h=\frac{2\pi }{N}$ and $N$ is ev en.
(a) Determine the order of accuracy of the central difference operator $Lv$ is approximating the second derivative $v_{xx}$.
(b) Using $v_m^n=\sum _{l=0}^{N-1}{\hat{v}}_l^n\exp (-i\frac{2\pi lm}{N})$ give the updates ${\hat{v}}_l^{n+1}$ in terms of ${\hat{v}}_l^n$ for each of the methods, including the ca se $l=0$.
(c) Give the solution for $v_m^n$ for each method when the initial condition is $\varphi (m\mathrm{\Delta }x)=(-1{)}^m$.
(d) What are the stability constraints on the time step $k$ for ea ch of the methods, if any, in equation (1) and (2)? Show there are either no constraints or express them in the form $k\le F(h,\mu )$