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 $A z=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.

Consider the integral
$$
\int_0^{\infty} f(x) \mathrm{d} x
$$
where $f$ is continuous, $f^{\prime}(0) \neq 0$, and $f(x)$ decays like $x^{-1-\alpha}$ with $\alpha>0$ in the limit $x \rightarrow \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 \rightarrow \infty$ with $L$ fixed?
(b) Suppose you consider the quadrature from (a) to be an ap proximation to the full integral from 0 to $\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?

Consider the Chebyshev polynomial of the first kind
$$
T_n(x)=\cos (n \theta), \quad x=\cos (\theta), \quad 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), \quad n \geq 0 .
$$
(a) Derive a recursive formula for computing $U_n(x)$ for all $n \geq 0$.
(b) Show that the Chebyshev polynomials of the second kind are orthogonal with respect to the inner product
$$
\langle f, g\rangle=\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) .
$$

Consider the boundary value problem
$$
-\frac{d}{d x}\left(a(x) \frac{d u}{d x}\right)=f(x), \quad u(0)=u(1)=0
$$
where $a(x)>\delta \geq 0$ is a bounded differentiable function in $[0,1]$. We assume that, although $a(x)$ is available, an expressi on for its derivative, $\frac{d a}{d x}$, is not available.
(a) Using finite differences and an equally spaced gird in $[0,1], x_l=h l, 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).

(a) Verify that the PDE
$$
u_t=u_{x x x}
$$
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)}{2 k}=\frac{-\frac{1}{2} u(x-2 h, t)+u(x-h, t)-u(x+h, t)+\frac{1}{2} u(x+2 h, t)}{h} .
$$

Determine this scheme's stability condition.

Consider the diffusion equation
$$
\frac{\partial v}{\partial t}=\mu \frac{\partial^2 v}{\partial x^2}, \quad v(x, 0)=\phi(x), \quad \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}-2 v_m+v_{m-1}}{h^2}
$$
and the following two finite different approximations, (i) Forw ard-Euler
$$
v_{n+1}=v_n+\mu k L v_n,(1)
$$
and (ii) Crank-Nicolson
$$
v_{n+1}=v_n+\mu k\left(L v_n+L v_{n+1}\right)
$$

Throughout, consider $[a, b]=[0,2 \pi]$ and the finite differenc e stencil to have periodic boundary conditions on the spatial lattice $[0, h, 2 h, \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 $L v$ is approximating the second derivative $v_{x x}$.
(b) Using $v_m^n=\sum_{l=0}^{N-1} \hat{v}_l^n \exp \left(-i \frac{2 \pi l m}{N}\right)$ 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 $\phi(m \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 \leq F(h, \mu)$