2024

Computational and Applied Mathematics

---

1.

Let \(A \in \mathbb{R}^{n\times n}\) be a non-singular matrix. Let \(u, v \in \mathbb{R}^n\) be column vectors. Define the rank 1 perturbation \(\tilde{A} = A + uv^T\).

(a)

Derive a necessary and sufficient condition for \(\tilde{A}\) to be invertible.

(b)

Let \(x, z, b\) be column vectors in \(\mathbb{R}^n\). Suppose one can solve \(Az = b\) with \(O(n)\) flops. Under the conditions derived in (a), design an algorithm to solve \(\tilde{A}x = b\) with \(O(n)\) flops, and provide justification for your answer.

---

2.

Consider the integral $$ \int_0^\infty f(x),dx $$ where \(f\) is continuous, \(f'(0)\neq 0\), and \(f(x)\) decays like \(x^{-1-\alpha}\) with \(\alpha>0\) as \(x\to\infty\).

(a)

Suppose you apply the equispaced composite trapezoid rule with \(n\) subintervals to approximate $$ \int_0^L f(x),dx. $$ What is the asymptotic error formula as \(n\to\infty\) with \(L\) fixed?

(b)

Regard the quadrature in (a) as an approximation to the full integral on \((0,\infty)\). How should \(L\) increase with \(n\) to optimize the asymptotic rate of total error decay? What is the resulting error decay rate?

(c)

Make the change of variable $$ x = L\frac{1+y}{1-y},\qquad y = \frac{x-L}{x+L}, $$ to obtain $$ \int_{-1}^1 F_L(y),dy. $$ Apply the equispaced composite trapezoid rule; what is the asymptotic error formula for fixed \(L\)?

(d)

Depending on \(\alpha\), which method—domain truncation or change-of-variable—is preferable?

---

3.

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

The Chebyshev polynomials of the second kind are defined as $$ U_n(x) = \frac{1}{n+1}T_n'(x),\qquad n\ge 0. $$

(a)

Derive a recursive formula for computing \(U_n(x)\) for all \(n\ge 0\).

(b)

Show that the Chebyshev polynomials \(U_n(x)\) are orthogonal with respect to the inner product $$ \langle f, g\rangle = \int_{-1}^1 f(x)g(x)\sqrt{1-x^2},dx. $$

(c)

Derive the 2-point Gaussian Quadrature rule for the integral $$ \int_{-1}^1 f(x)\sqrt{1-x^2},dx = \sum_{j=1}^2 w_j f(x_j). $$

---

4.

Consider the boundary value problem $$ -\frac{d}{dx}\left(a(x)\frac{du}{dx}\right) = f(x),\qquad u(0)=u(1)=0 $$ where \(a(x)>\delta\ge 0\) is a bounded differentiable function in \([0,1]\), and although \(a(x)\) is available, an expression for its derivative \(a'(x)\) is not available.

(a)

Using finite differences and an equally spaced grid in \([0,1]\), \(x_l = hl,; l=0,\dots,n\), \(h=1/n\), discretize the ODE to obtain a linear system giving an \(O(h^2)\) approximation. After applying boundary conditions, the resulting coefficient matrix is an \((n-1)\times(n-1)\) tridiagonal matrix. Provide a derivation and give the expressions of its entries.

(b)

Using all provided information, find a disk in \(\mathbb{C}\)—the smaller the better—that is guaranteed to contain all eigenvalues of the linear system 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{-\tfrac12 u(x-2h,t) + u(x-h,t) - u(x+h,t) + \tfrac12 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},\qquad v(x,0)=\varphi(x), $$ with periodic boundary conditions and $$ \int_a^b v(x,t),dx = 0. $$

Let \([a,b]=[0,2\pi]\), lattice points \(0,h,2h,\dots,(N-1)h\), \(h=\frac{2\pi}{N}\) with even \(N\).

The central difference operator for the Laplacian: $$ L v_m = \frac{v_{m+1}-2v_m+v_{m-1}}{h^2}. $$

Two finite difference approximations:

1. Forward–Euler $$ v^{n+1} = v^n + \mu k L v^n. $$

2. Crank–Nicolson $$ v^{n+1} = v^n + \mu k (L v^n + L v^{n+1}). $$

(a)

Determine the order of accuracy of \(L v\) in approximating \(v_{xx}\).

(b)

Using $$ v_m^n = \sum_{l=0}^{N-1} \hat{v}_l^n \exp\left(-i\frac{2\pi lm}{N}\right), $$ give the updates \(\hat{v}_l^{n+1}\) in terms of \(\hat{v}_l^n\) for each method, including \(l=0\).

(c)

Give the solution \(v_m^n\) for each method when the initial condition is $$ \varphi(m\Delta x) = (-1)^m. $$

(d)

What are the stability constraints on the time step \(k\) for each method, if any? Express them in the form \(k \le F(h,\mu)\).