函数的重复应用

对于这些函数,证明 ceil(f(x))<x x > 2 就够了。你可以做一次迭代——得到一个整数,然后进行简单的归纳。

well-founded induction 来证明这一点。然而,正如白痴在评论中指出的,这在一般情况下是不可能的,而且在许多情况下,很难找到正确的顺序。

编辑,回应阿姆农的评论:

x << y 当且仅当 ceil(x) < ceil(y) << 是这个新秩序的象征。这个顺序当然是建立在大于2的数字上的,而且两者都是 sqrt 和 log

当然,一般情况下,这样的顺序要难得多。在某种程度上,这也与 Hoare logic ,您需要在每个循环构造上保证类似的义务。

有一个普遍的定理,当迭代序列 汇聚

序列x,f(x),f(f(x))。。。如果f是a,则收敛 也就是说,存在一个正常数k<对于所有x和y,| f(x)-f(y)|<=k | x-y |。

(f(x)<x代表x>2似乎没有帮助,因为系列可能会收敛)。

x > n f(x) 严格小于 x ,它将到达 n 在某个点上(因为任意两个数字之间只有有限的浮点值)。

f(x) 十 f(x) = x

根本没有 判断函数 f x 会不会在那个循环中结束。停顿问题可以归结为那个问题。

为了 sqrt 和 log 接近1, 日志 x < 2

希望有帮助。

在一般情况下,可以说循环将在遇到x时终止 ≤2.这并不意味着序列会收敛,甚至也不意味着它的界在2以下,它只意味着序列包含一个不大于2的值。

_我+1 =平方米(x _我 ),因为x收敛到1 _{我+1 我} R C级* ,但我认为它一般不会收敛,除非在任何可能存在的稳定点(即z=log(z))。最终,这意味着您需要对序列执行一些预先分析,以便更好地了解其行为。

序列x收敛性的标准检验 _我 到了z点,这是给吗ε &燃气轮机;0,存在一个n,使得对于所有i>n、 | x个 _我

作为旁白,考虑一下 Mandelbrot Set , M 对于中的元素 M _{我+1 我} ² _我 M 可能会收敛(如0),但许多不会收敛(如-1)。

当然。对于所有正数 x ,以下不等式成立:

 log(x) <= x - 1

log 对所有积极的人都是消极的 十 x-1 x = 1 ). 从这一点来看,你的 while 循环必须在第一个 ceil(x) - 2 步骤——尽管实际上它终止的速度要快得多。

一个类似的论点将证明你的结论 f(x) = sqrt(x) ; 具体来说,您可以使用以下事实:

sqrt(x) <= x/(2 sqrt(2)) + 1/sqrt(2)

十

日志 真的,真的很可怕 日志 .

我建议你读书 this wikipedia entry 它提供了有用的指针。没有关于f的额外知识,什么也说不出来。