数值积分练习题

数值积分

Spring, 2025

Assume that \(f\) is a periodic function with period \(2\pi\). Considering the integration \(I(f)=\int_{0}^{2\pi}f(x)dx\), prove the following statements on the order of convergence of composite trapezoidal rule: \(I_{h}^{Tr}(f)=h\sum_{i=1}^{n}f(i\cdot h)\), where \(h=2\pi/n\).

(i) Assume further that \(f\in C^{m}([0,2\pi])\), prove that the above rule achieves \(m\)-th order convergence, i.e. \(\exists C>0\) s.t.

\[ |I(f)-I_{h}^{Tr}(f)|\le C\cdot h^{m}. \]

(ii) Assume further that \(f\) is analytic, prove that the above rule achieves exponential convergence.

证明

\((i)\)：由EM公式：

\[ I_h^{Tr}(f) - I(f) = \sum_{k=1}^{m-1} \frac{B_{2k}}{(2k)!} h^{2k} \left( f^{(2k-1)}(2\pi) - f^{(2k-1)}(0) \right) + R_m \]

其中 \(B_{2k}\) 是伯努利数，\(R_m\) 是余项，且 \(R_m = O(h^m)\)。由周期性可知 \(f^{(2k-1)}(2\pi) = f^{(2k-1)}(0)\)，因此 \(I_h^{Tr}(f) - I(f) = O(h^m)\)。

\((ii)\)：由 \(f\) 解析，考虑 \(f\) 的傅里叶级数展开 \(f(x) = \sum_{k=-\infty}^{\infty} c_k e^{ikx}\)，其中 \(c_k = \frac{1}{2\pi} \int_0^{2\pi} f(x) e^{-ikx} dx\)。

.

Consider a quadrature formula of the form

\[ \int_0^1 f(x)dx \approx a_0 f(0) + a_1 f'(0) + \sum_{k=1}^n w_k f(x_k) + b_0 f(1). \]

Call the formula "Hermite-interpolatory" if the right-hand side is obtained by integrating on the left instead of \(f\) the (Hermite) interpolation polynomial \(p\) satisfying

\[ p(0)=f(0), \quad p'(0)=f'(0), \quad p(1)=f(1); \quad p(x_k)=f(x_k), \quad k=1,2,\ldots,n. \]

(i) What degree of precision does the formula have in this case (regardless of how the nodes \(x_k\) are chosen, as long as they are mutually distinct and strictly inside the interval \([0, 1]\))? What is the maximum degree of precision expected to be if all coefficients and nodes \(x_k\) are allowed to be freely chosen?

(ii) Show that for the maximum degree of precision to be achieved, it is necessary that \(\{x_k\}\) are the zeros of the polynomial \(\pi_n\) of degree \(n\) which is orthogonal on \([0, 1]\) with respect to the weight function \(w(x) = x^2(1-x)\).

(iii) Show that the choice of the \(x_k\) in (ii) together with the requirement of the quadrature formula to be Hermite-interpolatory is sufficient for the maximum degree of precision to be attained.

证明

\((i)\)：\(n+3\) 个条件故对任意次数不超过 \(n+2\) 的多项式 \(f\)，公式都能精确计算出积分值，因此精度至少为 \(n+2\)。再算上 \(x_k\) 的 \(n\) 个自由度，最高精度为 \(2n+2\)。

\((ii)\)：设 \(\pi_n=\prod_{k=1}^n (x-x_k)\)，任取不超过 \(n-1\) 次的多项式 \(q(x)\)，构造测试多项式 \(f(x)=x^2(1-x)q(x)\pi_n(x)\)，则 \(\deg(f)=n+3+\deg(q)\le 2n+2\)。我们需要 \(\int_0^1 f(x)dx=Q[f]=a_0f(0)+a_1f'(0)+\sum_{k=1}^n w_k f(x_k)+b_0f(1)=0\)，即 \(\int_0^1 x^2(1-x)q(x)\pi_n(x)dx=0\) 对任意的次数不超过 \(n-1\) 的多项式 \(q\) 都成立，因此 \(\pi_n\) 是 \(w(x)=x^2(1-x)\) 的正交多项式。

\((iii)\) 将 \(f\) 对 \(\pi_n(x)x^2(1-x)\) 作带余除法即可。

2012 Individual

Problem 1. An numerical integration formula is given by

\[ \int_{-1}^{1} f(x) \, dx \approx a f(-1) + b f(c), \]

where \(a\), \(b\), and \(c\) are constants to be chosen arbitrarily.

(a) What is the highest degree \(k\) such that the formula is exact for all polynomials of degree up to \(k\)?
(b) Find the constants \(a\), \(b\), and \(c\) for which the formula is exact for all polynomials of degree up to this \(k\).

证明

设 \(f(x)=x^n\)，则 \(a(-1)^n + b c^n = \int_{-1}^1 x^n dx\)。当 \(n=0\) 时，\(a+b=2\)；当 \(n=1\) 时，\(-a+bc=0\)；当 \(n=2\) 时，\(a+bc^2=\frac{2}{3}\)，解得 \(a=\frac{1}{2}\)，\(b=\frac{3}{2}\)，\(c=\frac{1}{3}\)。当 \(n=3\) 时，\(-a+bc^3\neq 0\) 不成立，因此最高精度为 \(2\)。

2013 Team

Problem 2. Let \(f(x)\) defined on \([0,1]\) be a smooth function with sufficiently many derivatives. Let \(x_i = i h\), where \(h = \frac{1}{N}\) and \(i = 0,1,\cdots,N\) are uniformly distributed points in \([0,1]\). Consider the numerical integration formula

\[ I_N = \frac{1}{N} \left( a_0 \left( f(x_0) + f(x_N) \right) + a_1 \left( f(x_1) + f(x_{N-1}) \right) + \sum_{i=2}^{N-2} f(x_i) \right). \]

(a) What is the highest integer \(k\) such that the formula is \(k\)-th order accurate, i.e.,

\[ |I_N - \int_0^1 f(x) \, dx| \leq C h^k \]

for a constant \(C\) independent of \(h\)?
(b) Describe the procedure to obtain the two constants \(a_0\) and \(a_1\) for this \(k\).

2019 Team

Problem 3. (Chebyshev Quadrature)

(a) (10 points) Show that the quadrature formula

\[ \int_{-1}^1 \frac{f(x)}{\sqrt{1-x^2}} \, dx = \frac{\pi}{n} \sum_{k=0}^{n-1} f \left( \cos \frac{2k+1}{2n} \pi \right) \]

is exact for all polynomials of degree up to and including \(2n-1\).
(b) (15 points) Let \(x = (x_0, \ldots, x_{N-1}) \in \mathbb{R}^N\), \(x \neq 0\) and \(\hat{x}\) be its discrete Fourier transform, i.e.,

\[ \hat{x}_\omega = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} x_i \exp(-2\pi i \omega i / N), \quad \omega = 0, \ldots, N-1. \]

Prove that \(\|x\|_0 \cdot \|\hat{x}\|_0 \geq N\), where \(\|x\|_0\) denotes the number of nonzero entries in \(x\).

Hint: Show that \(\hat{x}\) cannot have \(\|x\|_0\) consecutive zeros.

证明

2018 Individual

Problem 4. Consider the definite integral

\[ I = \int_{a}^{b} f(x) \, dx. \]

(a) Construct an approximation to \(I\) by using the composite trapezoidal rule with a uniform partition of the interval \([a, b]\).
(b) Suppose \(f \in C^2[a, b]\), show that the above approximation is second-order accurate.
(c) Suppose \(f\) is periodic and smooth on the interval \([a, b]\), show that the above approximation is spectral order accurate.

Unknown Year

Problem 5. (Error Estimate for Simpson's Rule) Prove the following error estimate for Simpson's rule:

\[ \int_{a}^{b} f(x) \, dx - \frac{b-a}{6} \left( f(a) + 4f \left( \frac{a+b}{2} \right) + f(b) \right) = -\left( \frac{b-a}{2} \right)^5 \frac{f^{(4)}(\xi)}{90}, \]

where \(a < \xi < b\).

证明

设 \(p\) 是满足 \(p(a)=f(a)\)，\(p\left( \frac{a+b}{2} \right)=f\left( \frac{a+b}{2} \right)\)，\(p(b)=f(b)\) 的二次插值多项式，则 \(p(x)=f(a) \frac{(x-\frac{a+b}{2})(x-b)}{(a-\frac{a+b}{2})(a-b)} + f\left( \frac{a+b}{2} \right) \frac{(x-a)(x-b)}{\left( \frac{a+b}{2}-a \right)\left( \frac{a+b}{2}-b \right)} + f(b) \frac{(x-a)(x-\frac{a+b}{2})}{(b-a)(b-\frac{a+b}{2})}\)。因此 \(f(x)-p(x)=\frac{f^{(4)}(\xi)}{4!}(x-a)^2\left( x-\frac{a+b}{2} \right)^2 (x-b)^2\)，积分两边即可。