Scribd
Upload
16 views1 page

2019 S.-T. Yau Math Contest Problems

The document outlines the S.-T. Yau College Student Mathematics Contests for 2019, focusing on applied and computational mathematics. It presents five problems covering topics such as quadrature formulas, discrete Fourier transforms, matrix properties, convex functions, and numerical methods for solving ODEs. Each problem has specific points assigned, indicating their difficulty and importance in the contest.

Uploaded by

黃薪儒
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views1 page

2019 S.-T. Yau Math Contest Problems

The document outlines the S.-T. Yau College Student Mathematics Contests for 2019, focusing on applied and computational mathematics. It presents five problems covering topics such as quadrature formulas, discrete Fourier transforms, matrix properties, convex functions, and numerical methods for solving ODEs. Each problem has specific points assigned, indicating their difficulty and importance in the contest.

Uploaded by

黃薪儒
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

S.-T.

Yau College Student Mathematics Contests 2019

Applied and Computational Math


Team (5 problems)
1) (10 points)
Z n−1 µ ¶
1
f (x) πX 2k + 1
Show that the quadrature formula √ dx = f cosπ is exact for all polynomials
−1 1 − x2 n 2n
k=0
of degree up to and including 2n − 1.
2) (15 pointes) Let x = (x0 , . . . , xN −1 ) ∈ RN , x 6= 0 and x̂ be its discrete Fourier transform, i.e.
N −1
1 X
x̂w = √ xt exp(−2πiwt/N ), w = 0, . . . , N − 1.
N t=0
Prove that kxk0 kx̂k0 > N where kxk0 denotes the number of nonzero entries in x. (Hint: show that x̂
can not have kxk0 consecutive zeros.)
3) (20 pointes)
Let m 6 n. Consider the (n + m) × (n + m) real matrix defined by
· ¸
I X
A= ,
X> O
where I is the n × n identity matrix, X is a full-rank n × m matrix, O is the m × m zero matrix.
(i) Show that A is nonsingular.
(ii) Find the eigenvalues of A, some of which are in terms of the singular values of X.
(iii) Under what conditions on X would the iteration
xn+1 = xn − (Axn − b)
converge to the solution of Ax = b for any (n + m) × (n + m) real vector b?
4) (25 pointes)
Let f be a continuously differentiable convex function defined on Rn , i.e., f : Rn → R is continuously
differentiable and for any x, y ∈ Rn and any α ∈ (0, 1), f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y).
Suppose that the gradient of f is Lipschitz continuous, i.e., there exists a constant L > 0 such that
k∇f (x) − ∇f (y)k2 ≤ Lkx − yk2 .
Prove the following inequalities:
(i). f (y) ≤ f (x) + (∇f (x))T (y − x) + L2 ky − xk22 , ∀x, y ∈ Rn ;
1
(ii). f (y) ≥ f (x) + (∇f (x))T (y − x) + 2L k∇f (y) − ∇f (x)k22 , ∀x, y ∈ Rn ;
1
(iii). L k∇f (y) − ∇f (x)k2 ≤ (∇f (y) − ∇f (x))T (y − x), ∀x, y ∈ Rn .
2

5) (30 pointes) Consider the following problems.


(i) Determine the order of Störmer’s method,
yn+2 − 2yn+1 + yn = h2 f (tn+1 , yn+1 ), n > 0,
for solving the second order system of ODE’s
y 00 = f (t, y), t > 0,
0
with the initial conditions y(0) = y0 and y (0) = y00 .
(ii) Using the second order central differences in space and Störmer’s method in time, construct a
scheme to solve the wave equation,
utt = uxx .
(iii) Determine the condition for its stability.

Common questions

Powered by AI

One derived inequality involving Lipschitz continuous gradients of a convex function in Source 1 is: f(y) ≤ f(x) + (∇f(x))T (y −x) + L/2 ∥y −x∥^2_2. This inequality, often referred to as the upper bound inequality for convex functions with Lipschitz gradients, implies how the function values are bounded by their linearization and a quadratic term controlled by the Lipschitz constant L. It is significant as it provides an approximation scheme for evaluating function values, relevant in optimization algorithms and establishing convergence criteria.

Source 1 illustrates that the relationship between convexity and differentiability conditions for Lipschitz gradients ensures the convex function satisfies inequalities like f(y) ≤ f(x) + (∇f(x))T (y − x) + L/2 ∥y − x∥^2_2, alongside others presented. The convexity ensures the function maintains a global minimum property necessary for constructive bounds, while the Lipschitz continuity of gradients ensures that the rate of change (gradient behavior) is uniformly bounded, stabilizing the function values described in the inequalities. Thus, this relationship provides foundational stability and bounds within optimization contexts.

Störmer’s method is an explicit time-stepping procedure used primarily to solve second-order ordinary differential equations of the form y'' = f(t, y). Its key characteristic is using positions and velocities at different time steps without needing to solve a full system of equations at each step, making it computationally efficient. According to Source 1, the method is derived explicitly as yn+2 - 2yn+1 + yn = h^2 f(tn+1, yn+1), indicating a second-order accuracy. Thus, its order is determined as second-order, as it accurately approximates solutions to second-order precision.

Source 1 suggests that stability analysis for numerical schemes, like those solving differential equations, requires not only satisfying criteria such as the CFL condition but also ensuring consistency and convergence. These conditions establish that as the grid is refined (as Δx and Δt approach zero), the numerical solution approaches the true solution of the differential equations. Maintaining stability conditions ensures that small perturbations in the initial conditions or numerical errors do not magnify into large discrepancies, therefore ensuring a reliable approximation of the differential equations involved.

The convergence condition of the iteration xn+1 = xn −(Axn −b) for matrix A depends on the properties of the matrix A, particularly its eigenvalues. It requires A to be positive definite, ensuring all eigenvalues are positive, thereby making Ax = b solvable through iterative methods. The full-rank condition of the matrix X used in constructing A plays a crucial role by affecting the eigenvalue distribution. For guaranteed convergence, it's necessary to have the spectrum of A satisfy bounds that ensure iterative convergence, namely, that A must also be nonsingular and no eigenvalues should be zero.

The discrete Fourier transform (DFT) plays a pivotal role in linking the sparsity of the original sequence x with its transform ˆx. The inequality ∥x∥₀∥ˆx∥₀ ⩾ N is derived by considering the properties of the DFT which spreads the non-zero elements of x across the transform domain. If ˆx has ∥x∥₀ consecutive zeros, it would imply the transform does not capture enough frequency components, contradicting the nature of DFT which represents the entire input x in the frequency domain. Thus, proving that ˆx cannot have ∥x∥₀ consecutive zeros establishes the minimal number of non-zero entries needed for accurate representation and supports the inequality.

The quadrature formula can be shown to be exact for all polynomials of degree up to 2n-1 by demonstrating that it integrates these polynomials exactly. This involves proving that for each polynomial term up to degree 2n-1, the formula's evaluation coincides with the exact integral of that term over the interval [-1, 1]. By using orthogonal polynomial theory, specifically the properties of Chebyshev polynomials and their corresponding weights, exactness can be shown since the polynomial degree of 2n-1 matches the degree where the quadrature formula can exactly integrate.

The central difference scheme combined with Störmer’s method for solving the wave equation is conditionally stable. Stability is ensured under the Courant-Friedrichs-Lewy (CFL) condition for numerical solutions to wave equations, which involves the spatial and temporal discretization steps. Specifically, the condition requires the spatial step divided by the time step, adjusted by the wave speed, not to exceed a certain threshold. If this relation holds, oscillations in the solution are controlled, preventing unbounded growth over time.

The singular values of matrix X influence the eigenvalues of matrix A by contributing directly to the spectrum of A when it is examined through its block structure. Specifically, the singular values of X are incorporated into additional eigenvalues of A through the Schur Complement, contributing to the overall eigenvalue distribution of A. This insight reveals how the submatrix X governs not only the non-singularity but also the spectral characteristics of A, indicating the structural dependencies between the block components of A and their influence on its invertibility and diagonalization properties.

The matrix A is nonsingular because it is a block matrix composed of the identity matrix I and a zero matrix O along with a full-rank matrix X. The key property ensuring nonsingularity is the full rank of the submatrix X of dimension n × m. Since X is full-rank, the Schur complement of O in A is nonsingular as well, making A nonsingular overall. The identity matrix I contributes positively to A's determinant, which, alongside the non-zero determinant from the Schur complement, implies that A is invertible.

You might also like