S.-T.
Yau College Student Mathematics Contests 2024
Computational and Applied Mathematics
1. Let A ∈ Rn×n be a non-singular matrix. Let u, v ∈ Rn be column vectors. Define the
b = A + uv T .
rank 1 perturbation A
(a) Derive a necessary and sufficient condition for A
b to be invertible.
(b) Let x, z and b be column vectors in Rn . Suppose one can solve Az = b with
O(n) floating-point operations (flops). Under the conditions derived in(a), design
b = b with O(n) flops, and provide justification for your
an algorithm to solve Ax
answer.
2. Consider the integral Z ∞
f (x) dx
0
where f is continuous, f 0 (0) 6= 0, and f (x) decays like x−1−α with α > 0 in the limit
x → ∞.
(a) Suppose you apply the equispaced composite trapezoid rule with n subintervals
to approximate Z L
f (x) dx.
0
What is the asymptotic error formula for the error in the limit n → ∞ with L
fixed?
(b) Suppose you consider the quadrature from (a) to be an approximation to the full
integral from 0 to ∞. How should L increase with n to optimize the asymptotic
rate of total error decay? What is the rate of error decrease with this choice of
L? 5
L(1 + y) x−L
(c) Make the following change of variable x = ,y = in the original
1−y x+L
integral to obtain Z 1
FL (y) dy.
−1
Suppose you apply the equispaced composite trapezoid rule; what is the asymp-
totic error formula for fixed L?
(d) Depending on α, which method - domain truncation or change-of-variable - is
preferable?
1
3. Consider the Chebyshev polynomial of the first kind
Tn (x) = cos(nθ), x = cos(θ), x ∈ [−1, 1].
The Chebyshev polynomials of the second kind are defined as
1
Un (x) = T 0 (x), n ≥ 0.
n+1
(a) Derive a recursive formula for computing Un (x) for all n ≥ 0.
(b) Show that the Chebyshev polynomials of the second kind are orthogonal with
respect to the inner product
Z 1 √
hf, gi = f (x)g(x) 1 − x2 dx
−1
(c) Derive the 2-point Gaussian Quadrature rule for the integral
2
Z 1 √ X
f (x) 1 − x2 dx = wj f (xj )
−1 j=1
4. Consider the boundary value problem
d du
− a(x) = f (x), u(0) = u(1) = 0
dx dx
where a(x) > δ ≥ 0 is a bounded differentiable function in [0, 1]. We assume that,
da
although a(x) is available, an expression for its derivative, , is not available.
dx
(a) Using finite differences and an equally spaced grid in [0, 1], xl = hl, l = 0, . . . , n
and h = 1/n, we discretize the ODE to obtain a linear system of equations, yield-
ing an O(h2 ) approximation of the ODE. After the application of the boundary
conditions, the resulting coefficient matrix of the linear system is an (n−1)×(n−1)
tridiagonal matrix.
Provide a derivation and write down the resulting linear system (by giving the
expressions of the elements).
(b) Utilizing all the information provided, find a disc in C, the smaller the better,
that is guaranteed to contain all the eigenvalues of the linear system constructed
in part (a).
2
5. (a) Verify that the PDE
ut = uxxx
is well posed as an initial value problem.
(b) Consider solving it numerically using the scheme
u(t + k, x) − u(t − k, x) − 1 u(x − 2h, t) + u(x − h, t) − u(x + h, t) + 12 u(x + 2h, t)
= 2 .
2k h
Determine this scheme’s stability condition.
6. Consider the diffusion equation
b
∂ 2v
Z
∂v
= µ 2, v(x, 0) = φ(x), v(x, t) dx = 0
∂t ∂x a
with x ∈ [a, b] and periodic boundary conditions. The solution is to be approximated
using the central difference operator L for the 1D Laplacian.
vm+1 − 2vm + vm−1
Lvm = ,
h2
and the following two finite different approximations, (i) Forward-Euler
vn+1 = vn + µkLvn , (1)
and (ii) Crank-Nicolson
vn+1 = vn + µk(Lvn + Lvn+1 ). (2)
Throughout, consider [a, b] = [0, 2π] and the finite difference stencil to have periodic
2π
boundary conditions on the spatial lattice [0, h, 2h, . . . , (N − 1)h] where h = and
N
N is even.
(a) Determine the order of accuracy of the central difference operator Lv in approxi-
mating the second derivative vxx .
N −1
X 2πlm
n
(b) Using vm = n
v̂l exp −i give the updates v̂ln+1 in terms of v̂ln for each
l=0
N
of the methods, including the case l = 0.
n
(c) Give the solution for vm for each method when the initial condition is φ(m∆x) =
m
(−1) .
(d) What are the stability constraints on the time step k for each of the methods,
if any, in equations (1) and (2)? Show there are either no constraints or express
them in the form k ≤ F (h, µ).
