The Concept of a Limit | 极限的概念

📚 The Concept of a Limit | 极限的概念

A limit describes the value that a function, sequence, or process approaches as the input or index tends toward some point. In computer science, limits appear in algorithm analysis, numerical computation, and even in the foundations of computation itself.

极限描述了函数、数列或过程在输入或指标趋近某一点时所接近的值。在计算机科学中，极限出现在算法分析、数值计算乃至计算理论的基础之中。

1. Definition of a Limit | 极限的定义

For a function f(x), we say that the limit of f(x) as x approaches a is L if, for every small positive tolerance ε, there exists a positive δ such that whenever 0 < |x − a| < δ, we have |f(x) − L| < ε. This is the ε-δ definition.

对于函数 f(x)，我们说当 x 趋近 a 时 f(x) 的极限是 L，如果对于任意小的正容差 ε，都存在一个正数 δ，使得只要 0 < |x − a| < δ，就有 |f(x) − L| < ε。这就是 ε-δ 定义。

In computing, this definition underpins rigorous proofs of numerical algorithms. Without a formal definition, terms like “eventually close” would remain vague.

在计算中，这一定义构成了数值算法严格证明的基础。没有形式化定义，“最终接近”之类的说法就会显得含糊不清。

limₓ→ₐ f(x) = L

2. Limits of Sequences | 数列的极限

A sequence aₙ has a limit L if the terms become arbitrarily close to L as n grows without bound. We write aₙ → L as n → ∞.

数列 aₙ 的极限是 L，意味着当 n 无限增大时，项 aₙ 任意地接近 L。我们记作 n → ∞ 时 aₙ → L。

This concept is essential in iterative algorithms. For example, the sequence produced by repeatedly applying x ← (x + a/x) / 2 converges to √a for any positive starting value.

这一概念在迭代算法中至关重要。例如，反复执行 x ← (x + a/x) / 2 所生成的数列，对于任何正初始值都会收敛到 √a。

Without limits, we could not guarantee that a loop or recurrence terminates at a meaningful answer.

没有极限，我们便无法保证循环或递归能够在有意义的答案处终止。

3. Limits in Computing: Floating-Point Representation | 计算机中的极限：浮点数表示

Computers store real numbers using a finite number of bits. A double-precision floating-point number has a finite set of representable values, so irrational numbers like π are represented by nearest approximations.

计算机使用有限位来存储实数。双精度浮点数只有有限个可表示的值，因此 π 这类无理数只能以最接近的近似值表示。

This introduces a practical limit: the error between the mathematical value and its stored approximation. Mathematically, we can define this error as a limit of better approximations, but in hardware the limit is fixed by the chosen precision.

这引入了实际极限：数学值与存储近似值之间的误差。从数学上，我们可以将误差视为更佳近似的极限，但在硬件中，极限由所选精度固定。

Thus, algorithms must account for rounding errors, especially in iterative methods where small errors accumulate.

因此，算法必须考虑舍入误差，尤其是在迭代方法中，小误差会不断累积。

4. Convergence of Algorithms | 算法的收敛性

An iterative algorithm converges if successive approximations approach a fixed answer. The rate of convergence describes how quickly the error tends to zero.

如果迭代算法的连续近似值逼近一个固定答案，则该算法收敛。收敛速度描述了误差趋近零的快慢。

Linear convergence means the error is roughly halved each step, while quadratic convergence squares the error. In formula form, for a sequence of errors eₖ, quadratic convergence means eₖ₊₁ ≈ c·eₖ².

线性收敛意味着误差每一步大致减半，而二次收敛则使误差平方。用公式表示，对于误差序列 eₖ，二次收敛意味着 eₖ₊₁ ≈ c·eₖ²。

limₖ→∞ |eₖ₊₁| / |eₖ|² = c

Machine learning training often relies on stochastic gradient descent, which converges in probability to a minimum under certain assumptions.

机器学习训练常依赖随机梯度下降，它在一定条件下依概率收敛到一个最小值。

5. Limits in Asymptotic Analysis | 渐近分析中的极限

Big-O notation describes the limiting behaviour of an algorithm’s time or space usage as the input size n tends to infinity. For example, a loop that runs n times has O(n) complexity.

大 O 表示法描述了算法时间或空间使用量在输入规模 n 趋近无穷大时的极限行为。例如，运行 n 次的循环具有 O(n) 复杂度。

Formally, f(n) = O(g(n)) if there exist constants c and n₀ such that for all n ≥ n₀, |f(n)| ≤ c·|g(n)|. The limit comparison is often used:

形式上，如果存在常数 c 和 n₀，使得对所有 n ≥ n₀ 都有 |f(n)| ≤ c·|g(n)|，则 f(n) = O(g(n))。极限比较常被使用：

limₙ→∞ f(n) / g(n) < ∞ ⇒ f = O(g)

This lets us classify algorithms by their growth rates, ignoring constants and lower-order terms.

这使得我们可以根据算法的增长率分类，忽略常数项和低阶项。

6. Infinite Series and Recursion | 无穷级数与递归

An infinite series is the limit of its partial sums. For example, the geometric series Σ (1/2)ⁿ converges to 2 as n tends to infinity.

无穷级数是其部分和的极限。例如，几何级数 Σ (1/2)ⁿ 在 n 趋向无穷时收敛到 2。

In recursive algorithms, the total work can often be expressed as a series. Merge sort’s running time T(n) = 2T(n/2) + O(n) solves to O(n log n); the sum of work at each level approaches a constant multiple of n.

在递归算法中，总工作量通常可以表示为一个级数。归并排序的运行时间 T(n) = 2T(n/2) + O(n) 可解为 O(n log n)；每一层工作量之和趋近于 n 的常数倍。

Thus, understanding series limits helps analyse the total cost of divide-and-conquer algorithms.

因此，理解级数极限有助于分析分治算法的总代价。

7. Limits in Numerical Methods | 数值方法中的极限

Numerical integration, such as Simpson’s rule, approximates a definite integral by taking limits of Riemann sums. The error tends to zero as the step size h decreases.

数值积分（如辛普森法则）通过黎曼和的极限来近似定积分。随着步长 h 减小，误差趋近于零。

Similarly, the derivative f'(x) is defined as the limit of difference quotients. In practice, computers use finite differences, which are approximations because h cannot be zero.

类似地，导数 f'(x) 被定义为差商的极限。实际中，计算机使用有限差分，这是一种近似，因为 h 不能为零。

f'(x) = limₕ→₀ (f(x+h) − f(x)) / h

Choosing h too small causes floating-point errors, so there is a “sweet spot” that balances truncation and rounding errors.

选择过小的 h 会引入浮点误差，因此存在一个平衡截断误差和舍入误差的“最佳点”。

8. Limits and Computability | 极限与可计算性

In computability theory, a function is computable if there exists an algorithm that computes it exactly in finite time. Some real numbers, however, are not computable; no algorithm can output their decimal expansion up to arbitrary precision.

在可计算性理论中，如果存在一个算法能在有限时间内精确计算某个函数，则该函数是可计算的。然而，有些实数不是可计算的；没有任何算法可以输出它们任意精度的十进制展开。

Yet limits can produce non-computable objects. For instance, the limit of a sequence of rational numbers may be a non-computable real number, such as Chaitin’s constant Ω.

然而，极限可以产生不可计算的对象。例如，有理数数列的极限可能是不可计算的实数，如柴廷常数 Ω。

This reveals a deep connection between limits and the boundaries of algorithmic solvability.

这揭示了极限与算法可解性边界之间的深层联系。

9. Practical Limits in Computer Systems | 计算机系统的实际极限

Real systems have physical and logical limits: memory size, instruction cycle time, and energy dissipation. These limits can be modelling using limits in the mathematical sense, such as signal to noise ratios and clock frequency scaling.

真实系统具有物理和逻辑极限：内存大小、指令周期时间和能量耗散。这些极限可以用数学意义上的极限来建模，例如信噪比和时钟频率缩放。

The von Neumann bottleneck is a practical limit: the maximum rate of data transfer between CPU and memory restricts performance regardless of processor speed.

冯·诺依曼瓶颈是一个实际极限：CPU 与内存之间的最大数据传输速率限制了性能，无论处理器速度如何。

In algorithm design, understanding these limits helps engineers choose between time and space trade-offs.

在算法设计中，理解这些极限有助于工程师在时间与空间之间做出权衡。

10. Conclusion | 结论

The concept of a limit is not merely a mathematical curiosity; it is a cornerstone of computer science. From proving correctness of iterative algorithms to analysing asymptotic complexity and understanding hardware constraints, limits provide a precise language for describing behaviour “in the limit”.

极限的概念不仅是数学上的好奇之物，更是计算机科学的基石。从证明迭代算法的正确性，到分析渐近复杂度，再到理解硬件约束，极限为描述“极限情况下”的行为提供了一种精确的语言。

Mastering this concept prepares computing students to reason rigorously about algorithms and systems that must work reliably in the presence of finite resources and infinite possibilities.

掌握这个概念，能帮助计算机专业的学生在有限资源和无限可能并存的环境中，严谨地思考必须可靠运行的算法与系统。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

The Concept of a Limit | 极限的概念