S.-T.
Yau College Student Mathematics Contests 2023
Computational and Applied Mathematics
Solve every problem.
1. Consider the forward and the centered finite difference formulas
f (x0 + h) − f (x0 )
Dh+ f (x0 ) = , (1)
h
f (x0 + h) − f (x0 − h)
Dh0 f (x0 ) = , (2)
2h
to approximate the derivative of f at a point x0 . Assume f is a smooth function in a
neighborhood of x0 containing the points x0 + h and x0 − h.
(a) Prove that Dh+ f (x0 ) and Dh0 f (x0 ) approximate f 0 (x0 ) to O(h) and O(h2 ), respec-
tively.
(b) Derive an O(h2 ) approximation to f 0 (x0 ) from Dh+ f (x0 ) by doing Richardson
extrapolation.
(c) Take f (x) = sin x and x0 = 0. Prove that both Dh+ f (x0 ) and Dh0 f (x0 ) con-
verge quadratically to f 0 (x0 ) as h → 0 and that in fact they produce the same
approximation to f 0 (x0 ) in this particular case.
2. For functions defined on a closed interval [0, 1], we want to compute the following
definite integral, Z 1
I[f ] = f (x) log(1/x)dx.
0
Here we consider the weight function log(1/x), and denote Pn (x) as the monic orthog-
onal polynomials for the corresponding weighted inner product.
(a) Let P0 = 1. Find P1 (x), and the corresponding node x11 and weight ω11 for the
1-point Gaussian quadrature rule.
(b) Derive a recursive formula for Pn+1 (x) using Pn (x) and Pn−1 (x).
(c) Consider the normalized orthogonal polynomials Qn (x) = Pn (x)/||Pn ||, where
p
||Pn || = Pn (x)2 log(1/x)dx.
Derive a recursive formula for Qn+1 (x) using Qn (x) and Qn−1 (x).
1
(d) Use the above recursive formula to show that x = λ is a node of the 4-point
Gaussian quadrature if and only if it is an eigenvalue of a symmetric, tridiagonal
matrix. Write out the form of the symmetric and tridiagonal matrix explicitly.
3. Let A be a real n × n matrix with distinct eigenvalues such that
|λ1 | > |λ2 | ≥ |λ3 | ≥ · · · ≥ |λn | ≥ 0,
with corresponding eigenvectors {vj }nj=1 .
(a) Show that the power iteration
Am z0 v1
zm = m
−→ ± , ∀z0 ∈ Rn .
||A z0 ||∞ ||v1 || ∞
(b) Consider the following iteration with initial guess x0 = y0 = 1,
xn+1 = xn + yn , yn+1 = xn+1 + xn .
√
Show that yn /xn → 2 as n → ∞.
4. Consider the initial value problem
y 0 = f (t, y), 0 < t ≤ T. (3)
y(0) = y0 . (4)
Assume f is continuous and Lipschitz in y in [0, T ] × (−∞, ∞). Denote yn ≈ y(tn ),
tn = nh, and h = T /N , with N a positive integer, and consider the one-step method
yn+1 = yn + αhf (tn , yn ) + βhf (tn + γh, yn + γhf (tn , yn )),
where α, β and γ are real parameters.
(a) Prove that the method is consistent if and only if α + β = 1, and the order of the
method can not exceed 2.
(b) Suppose that a second-order method of the above form is applied to f (t, y) = −λy
with λ > 0, and the initial condition y0 = 1. Show that the sequence (yn )n≥0 is
bounded if and only if h ≤ λ2 . Show further that for such h,
1
|y(tn ) − yn | ≤ λ3 h2 tn , n ≥ 0.
6
2
5. Let u(t, x) be the solution of the initial-boundary value problem
ut = Duxx , 0 < x < L, 0 < t ≤ T, (5)
u(0, x) = f (x) (6)
u(t, 0) = u(t, L) = 0, (7)
where L > 0 and D > 0. Consider the finite difference scheme
un+1
j − unj unj+1 − 2unj + unj−1
=D , j = 1, . . . , M − 1, n = 0, 1, . . . , N − 1 (8)
∆t (∆x)2
with un0 = unM = 0 for all n and u0j = f (j∆x), j = 0, . . . , M . Here ∆t = T /N and
∆x = L/M and unj ≈ u(n∆t, j∆x).
(a) Prove that (8) is consistent with (5).
1
(b) Prove that if ∆t ≤ 2D
(∆x)2 the finite difference scheme (8) is stable under the
l∞ norm.
1
(c) Prove that if ∆t ≤ 2D (∆x)2 the finite difference scheme (8) converges in the l∞
norm to the exact solution of (5)-(7).
6. Let ψ ε (t, x) be the solution to the following Schrödinger equation:
∂ψ ε ε2
iε = − ∇2x ψ ε + V (x)ψ ε , x = (x1 , · · · , xn )T ∈ Rn ,
∂t 2
√
where i = −1, ε 1 is a small positive real number (rescaled Planck constant),
X n
2
∇x = ∂x2j , and V (x) ∈ C ∞ (Rn ) is the potential function.
j=1
Consider the WKB expansion
S(t,x)
ψ ε (t, x) = A(t, x)ei ε ,
(a) Derive equations for A(t, x) and S(t, x) by asymptotic expansion. (Here both
A(t, x) and S(t, x) are real-valued functions, and do not depend on ε.)
(b) Define u(t, x) = ∇x S(t, x) ∈ Rn . Derive an equation for u(t, x). Suppose u(0, x) ∈
C ∞ (Rn ), will u(t, x) always be in C ∞ (Rn ) for all t > 0? Explain why.
