跳到主要内容

東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年8月実施 専門科目II 問題5

Author

zephyr

Description

Suppose that is a real function defined on a closed interval from to . Suppose that is an integer that is no less than 2, and define . Then, for each integer , define and , respectively. Namely, are the points that divide the interval from to into equal parts, and is the value of the function at .

Next, define , and define as the approximate value calculated by the composite trapezoid rule applied on using the points which divide the interval from to into equal parts.

Answer the following questions.

(1) Assume that is a four times continuously differentiable function. Let be an integer such that and define as the second order differential of at . Express an approximate value of whose error is , as a linear combination of , and .

(2) The approximation obtained by question (1) seems to become accurate when approaches zero. Answer, with a reason, whether this is correct or not in the calculation with the IEEE 754 double precision floating point operations.

(3) Express using , and .

(4) Assume that can be expressed by a quadratic function in each interval formed by the division into equal parts. Then, define similarly using the division into equal parts composed of the division of each original part into two halves. Express using and .


假设 是一个定义在从 的闭区间上的实函数。假设 是不小于 2 的整数,并定义 。然后,对于每个整数 ,分别定义 。即, 是将从 的区间分成 等分的点, 是函数 处的值。

接下来,定义 ,并定义 为使用复合梯形规则计算的近似值,该规则适用于使用将区间 分成 等分的点上的

回答以下问题。

(1) 假设 是四次连续可微函数。设 是整数,使得 ,并定义 处的二阶导数。表示 的一个近似值,其误差为 ,作为 的线性组合。

(2) 问题 (1) 中获得的近似值在 趋近于零时似乎变得准确。回答,在使用 IEEE 754 双精度浮点运算进行计算时,这是否正确,并给出理由。

(3) 使用 表示

(4) 假设 可以在每个由分成 等分形成的区间中用二次函数表示。然后,类似地定义 ,使用将每个原始部分分成两半的 等分的划分。使用 表示

Kai

(1)

To approximate the second derivative at using the values , , and , we can use the central difference formula:

The error in this approximation is . This formula is derived from the Taylor series expansion of around .

(2)

The approximation for becomes more accurate as approaches zero theoretically. However, in the context of IEEE 754 double precision floating point operations, as decreases, the difference between and also becomes very small. This can lead to a significant loss of precision due to rounding errors, which is known as catastrophic cancellation. Therefore, in practice, there is a limit to the accuracy of this approximation when becomes too small.

(3)

The composite trapezoidal rule for approximating the integral is given by:

where and .

(4)

When is approximated by a quadratic function on each subinterval, the error can be related to the integral approximations and as follows:

This formula arises from the fact that the error in the trapezoidal rule is proportional to , and doubling the number of intervals reduces the error by a factor of 4. By subtracting the two approximations, we can eliminate the leading order error term, leaving a smaller error proportional to .

Knowledge

数值分析 数值积分 复合梯形法 数值微分 误差分析 浮点运算

难点思路

在第二问中,理解浮点数运算中的精度问题是关键。尤其是当差值变小时,浮点运算的误差可能会导致结果不准确。

解题技巧和信息

  1. 数值微分:当计算导数时,中央差分法通常比前向或后向差分法具有更高的精度,但需要注意数值稳定性。
  2. 数值积分:复合梯形法的误差分析依赖于对被积函数的光滑性假设,常见的误差公式与分割数 的关系密切。
  3. 误差消除:使用不同分割方式计算积分时,考虑两次计算的结果,可以有效减少误差,这种方法类似于龙贝格积分法。

重点词汇

  • Trapezoidal rule: 梯形法
  • Central difference: 中央差分
  • IEEE 754 double precision: IEEE 754 双精度浮点数
  • Catastrophic cancellation: 灾难性消减

参考资料

  1. Burden, R. L., & Faires, J. D. (2011). Numerical Analysis (9th ed.). Brooks Cole. Chapter 4: Numerical Differentiation and Integration.
  2. Heath, M. T. (2002). Scientific Computing: An Introductory Survey (2nd ed.). McGraw-Hill. Chapter 8: Numerical Integration.