使用不动点显示平方根

Question

在进行SICP练习时，它将定点定义为满足方程F(x(=x的函数。并迭代以找到函数停止更改的位置，例如F(F(F(x)))。

我不明白的是，9的平方根与此有什么关系。

例如，如果我有F(x) = sqrt(9)，显然x=3。然而，这与做什么有关：

F(F(F(x))) --> sqrt(sqrt(sqrt(9)))

我相信它收敛为零：

>>> math.sqrt(math.sqrt(math.sqrt(math.sqrt(math.sqrt(math.sqrt(9))))))
1.0349277670798647

由于当x＝1时F(x(＝sqrt(x(。换句话说，求常数的平方根与求函数的不动点有什么关系？

Answer 1

当计算一个数字的平方根时，比如a，实际上有一个形式为x^2 - a = 0的方程。也就是说，要找到a的平方根，你必须找到一个x，使得x^2 = a或x^2 - a = 0-将后一个方程称为(1(。(1(中给出的形式是形式为g(x) = 0的方程，其中g(x) := x^2 - a。

要使用定点方法计算该方程的根，必须对现有方程进行一些细微的修改，并将其形成为f(x) = x。一种方法是将(1(重写为x=a/x——称之为(2(。现在在(2(中，您已经获得了通过定点方法求解方程所需的形式：f(x(是a/x。

注意，这种方法要求方程的两边都有一个"x"项；形式为CCD_ 12的方程不符合规范，因此不能使用定点方法(迭代地(求解。

我不明白的是，9的平方根与此有什么关系。

例如，如果我有F(x(=sqrt(9(，显然x=3。然而，这与做：F(F(F(x((-->sqrt(sqrt(9((

这些是非线性方程根的数值计算的标准方法，这本身就是一个相当复杂的主题，通常在工程课程中涉及。所以，如果你没有得到"；挂起它"；，作者可能觉得这是一个很好的迭代问题解决的例子。

Answer 2

您需要将问题f(x) = 0转换为可能收敛到f(x)的根的不动点问题g(x) = x。一般来说，g(x)的选择是非常棘手的。

如果是f(x) = x² - a = 0，则应按如下方式选择g(x)：

g(x) = 1/2*(x + a/x)

(这个选择是基于牛顿方法，这是定点迭代的一个特殊情况(。

要找到平方根，sqrt(a):

1. 猜测x₀的初始值
2. 给定公差ε，计算n = 0, 1, ...的x_n+1=1/2*(x_n+a/x_n(，直到收敛