我正在重看一些早期关于SICP的讲座。定点的概念让我有点困惑。定点过程：我是否应该这样想，“这是找到给定函数的不动点的方法。” 所以给f(2) = 2？
另外，为什么在本讲座y中指出，映射到的新函数x / y是一个固定点？
问问题
927 次
4 回答
2
于 2014-08-18T14:20:46.937 回答
2
只是 Ethier 的回答解决了固定点是什么，但这仍然留下了您问题的另一部分：
还有为什么一个新函数 y 映射到 x / ya 固定点？
讲师在你提到的那一点上说得很快，但我认为他实际上是在说 √x 是多个函数的不动点，并且 √x 是不动点的一个明显函数是
y ↦ x / y
自从
√x = x / √x
然而，计算不动点的给定过程不适用于这个函数，因为它的内部过程iter在初始值上循环并且函数应用于初始值。因此新/旧值的顺序是 (1,2), (2,1), (1,2), ...</p>
于 2014-08-18T16:34:11.827 回答
1
当您在迭代函数中获得与上次相同的结果时。要掌握该想象的已知序列的正常函数：
想象一下这个功能f(x) = 2^(n+1)-1。它被称为梅森序列，你应该给它一个从 0 开始的索引，它会生成序列1, 3, 7, 15, 31, ... （基本上它比 2 的每个幂都小一）
现在，您可以通过将函数更改为迭代来制作相同的序列。迭代版本是f(x) = 2x + 1. 现在 x 不再是索引，而是以前的结果。你从 0 开始得到1, 3, 7, 15, 31, ...
现在这个函数没有固定点，因为应用它的结果总是大于它的参数。我们可以说它爆炸了。
回答你的第一个问题。在 SICP 视频中，他们谈论的是平方根。n 的平方根是迭代函数的不动点，f(x) = n/x因为sqrt(x^2) = x它不映射到其他函数。
一般的定点函数就像他们对定点的定义一样，即您迭代一个函数，直到您输入函数的值等于（或足够接近）下一个计算出的数字。
现在我们看到我们无法从 Mersenne 中找到一个固定点，并且我们知道我们需要平均阻尼n/x才能使其收敛，但有些函数实际上会自行收敛，例如f(x) = x/4 + 1收敛到3/2。请注意，即使您要对阻尼进行平均，它仍然会变成3/2这样，只有没有固定点的函数才会永远循环。
于 2014-08-18T17:20:46.263 回答
1
这是我的两分钱。它确实可能令人困惑。
首先，简单的定义：一个点x是一个函数的“不动点” f，如果f(x) == x。
反过来说，x = f(x).
以上可以有任何意义吗？似乎不太可能。毕竟，它使用正在定义的值。
x虽然不一定是一个简单的数字。它可以是一个函数，也可以是一个惰性无限列表，并且f可以产生部分定义它的效果。然后，通过反复评价
x = f(x) = f( f(x)) = f( f( f(x))) = f( f( f( f(x)))) = ....
价值的定义越来越多。现在这确实让我们想起了f(y) = (y + n/y)/2通过迭代计算计算不动点的数值示例，
n=25; f(1.0)=13.0; f(13.0)=7.4615383; f(7.4615383)=5.406027;
f(5.406027)=5.0152473, f(5.0152473)=5.0152473; f(5.0152473)=5.0
关键部分不是等到无限的评估链结束（永远不会），而是要有一个惰性列表来记录评估步骤的进展。然后，我们的无限列表的值被逐步定义：首先它是未定义的；然后它的第一个（头）元素被定义，其余的仍然没有；然后定义它的前两个元素；等等等等：[1.0,13.0,7.4615383,5.406027,5.0152473,5.000023,5.0,5.0,5.0 ...]。
就像数值收敛到某个数字，越来越接近“最终”值（永远不会完全达到，但距离越来越小），无限的结果列表也收敛到它的最终值，定义了所有元素的完全定义的无限列表（当然，这是一个不可能的壮举），在定义上越来越接近最终值（简单地说，它的元素一个一个定义，但数学家喜欢它复杂）。
函数也是如此。如果g(h,n) = n<2 -> 1 ; else -> n*h(h,n-1)theng(error)是一个只为 定义的参数的（柯里化）函数n < 2，那么对于任何其他参数，它将发散（导致错误）。但是g( g(error))是为所有人定义的n < 3；g( g( g(error)))- 对于所有n < 4，等等。再次，我们有一个越来越定义的值的级数......所以这个级数的极限，“最终值”，函数的不动点g就是这样一个函数f，f = g(f)它被定义为任何 n，无论多大。巧合的是，它是一个阶乘函数，在没有使用递归的情况下定义。
于 2014-08-27T19:59:42.040 回答