We introduced compound procedures in 1.1.4 as a mechanism for
abstracting patterns of numerical operations so as to make them independent of
the particular numbers involved. With higher-order procedures, such as the
integral procedure of 1.3.1, we began to see a more
powerful kind of abstraction: procedures used to express general methods of
computation, independent of the particular functions involved. In this section
we discuss two more elaborate examples—general methods for finding zeros and
fixed points of functions—and show how these methods can be expressed
directly as procedures.
Subheading: Finding roots of equations by the half-interval method
我们在 1.1.4 节引入了复合过程，将其作为抽象数值运算模式的机制，使这些运算独立于具体的数值。借助高阶过程（higher-order procedures）——例如 1.3.1 节的 `integral` 过程——我们开始见识到一种更强大的抽象：用过程来表达计算的通用方法，独立于具体涉及的函数。本节将讨论两个更精细的例子——求函数零点和不动点的通用方法——并展示如何将这些方法直接表达为过程。
子标题：用二分法求方程的根
The
half-interval method is a simple but powerful technique for
finding roots of an equation f
(
x
)
=
0, where f is a continuous
function. The idea is that, if we are given points a and b such that
f
(
a
)
二分法 (half-interval method) 是一种简单而有效的技术，用于求方程 f(x) = 0 的根，其中 f 是连续函数。其基本思想是：若给定点 a 和 b，使得 f(a)
0
< 0 <
f
(
b
), then f must have at least one zero between
a and b. To locate a zero, let x be the average of a and b,
and compute f
(
x
). If f
(
x
)
>
0, then f must have a zero
between a and x. If f
(
x
)
f(b)，则 f 在 a 与 b 之间至少有一个零点。为了定位该零点，取 x 为 a 与 b 的平均值，计算 f(x)。若 f(x) > 0，则 f 在 a 与 x 之间必有一个零点；若 f(x)
0, then f must have a zero
between x and b. Continuing in this way, we can identify smaller and
smaller intervals on which f must have a zero. When we reach a point where
the interval is small enough, the process stops. Since the interval of
uncertainty is reduced by half at each step of the process, the number of steps
required grows as Θ
(
log
(
L
< 0，则 f 在 x 与 b 之间必有一个零点。如此不断缩小范围，便可确定越来越小的区间，使 f 在其中必有零点。当区间小到足够精确时，计算过程停止。由于每一步不确定区间都缩减为原来的一半，所需步数随 Θ(log(L
/
T
)
), where L is the
length of the original interval and T is the error tolerance (that is, the
size of the interval we will consider “small enough”). Here is a procedure
that implements this strategy:
T)) 增长，其中 L 是初始区间的长度，T 是误差容限（即我们认为"足够小"的区间大小）。下面是实现这一策略的过程：
We assume that we are initially given the function f together with points
at which its values are negative and positive. We first compute the midpoint
of the two given points. Next we check to see if the given interval is small
enough, and if so we simply return the midpoint as our answer. Otherwise, we
compute as a test value the value of f at the midpoint. If the test value
is positive, then we continue the process with a new interval running from the
original negative point to the midpoint. If the test value is negative, we
continue with the interval from the midpoint to the positive point. Finally,
there is the possibility that the test value is 0, in which case the midpoint
is itself the root we are searching for.
我们假设初始时已知函数 f 以及使其取值分别为负数和正数的两个点。首先计算两点的中点，然后检查当前区间是否已经足够小——若是，则直接返回中点作为答案。否则，计算 f 在中点处的值作为检验值：若检验值为正，则以原来的负值点和中点为新区间继续计算过程；若检验值为负，则以中点和正值点为新区间继续。最后还有一种情况：检验值恰好为 0，此时中点本身就是我们要找的根。
To test whether the endpoints are “close enough” we can use a procedure
similar to the one used in 1.1.7 for computing square
roots:
为了检验两端点是否"足够接近"，可以使用一个类似于 1.1.7 节计算平方根时所用的过程：
Search is awkward to use directly, because we can accidentally give it
points at which f’s values do not have the required sign, in which case we
get a wrong answer. Instead we will use search via the following
procedure, which checks to see which of the endpoints has a negative function
value and which has a positive value, and calls the search procedure
accordingly. If the function has the same sign on the two given points, the
half-interval method cannot be used, in which case the procedure signals an
error.
直接使用 `search` 过程比较麻烦，因为我们可能不小心传入使 f 的值不具有所需符号的端点，从而得到错误答案。因此，我们将通过下面的过程来调用 `search`：该过程会检查哪个端点对应函数的负值、哪个对应正值，并据此调用 `search`。若函数在两个给定点处的符号相同，则二分法无法使用，此时过程发出一个错误信号。
The following example uses the half-interval method to approximate π as
the root between 2 and 4 of sin
x
=
0:
下面的例子使用二分法，将 π 近似为 sin x = 0 在 2 与 4 之间的根：
Here is another example, using the half-interval method to search for a root of
the equation x
3
再举一个例子，同样使用二分法，在 1 与 2 之间搜索方程 x³
−
2
x
−
3
=
0 between 1 and 2:
− 2x − 3 = 0 的根：
Subheading: Finding fixed points of functions
子标题：求函数的不动点
A number x is called a
fixed point of a function f if x
satisfies the equation f
(
x
)
=
x. For some functions f we can
locate a fixed point by beginning with an initial guess and applying f
repeatedly,
如果数 x 满足方程 f(x) = x，则称 x 为函数 f 的不动点 (fixed point)。对于某些函数 f，可以从一个初始猜测值出发，反复应用 f，来定位其不动点：
f
(
x
)
,
f(x)，
f
(
f
(
x
)
)
,
f(f(x))，
f
(
f
(
f
(
x
)
)
)
,
f(f(f(x)))，
…
,
……，
until the value does not change very much. Using this idea, we can devise a
procedure fixed-point that takes as inputs a function and an initial
guess and produces an approximation to a fixed point of the function. We apply
the function repeatedly until we find two successive values whose difference is
less than some prescribed tolerance:
直到值不再有明显变化为止。利用这一思想，我们可以设计一个过程 `fixed-point`，它以一个函数和一个初始猜测值为输入，产生该函数不动点的近似值。我们反复应用该函数，直到找到两个连续值之差小于某个预设容限为止：
For example, we can use this method to approximate the fixed point of the
cosine function, starting with 1 as an initial approximation:
例如，可以用这个方法来近似余弦函数的不动点，以 1 作为初始近似值：
Similarly, we can find a solution to the equation
y
=
sin
y
+
cos
y:
类似地，可以求方程 y = sin y + cos y 的一个解：
The fixed-point process is reminiscent of the process we used for finding
square roots in 1.1.7. Both are based on the idea of repeatedly
improving a guess until the result satisfies some criterion. In fact, we can
readily formulate the square-root computation as a fixed-point search.
Computing the square root of some number x requires finding a y such
that y
2
`fixed-point` 的计算过程令人联想到 1.1.7 节中求平方根时所用的计算过程。两者都基于这样一个思想：反复改进猜测值，直到结果满足某一判据。实际上，我们完全可以将平方根计算表述为一个不动点搜索问题。计算某个数 x 的平方根，需要找到一个 y，使得 y²
=
x. Putting this equation into the equivalent form
y
=
x
= x。将此方程化为等价形式 y = x
/
y, we recognize that we are looking for a fixed point of the
function y
↦
x
y，可以看出我们正在寻找函数 y ↦ x
/
y,
and we can therefore try to compute square roots as
y 的不动点，因此可以尝试用如下方式计算平方根：
Unfortunately, this fixed-point search does not converge. Consider an initial
guess y
1. The next guess is y
2
遗憾的是，这一不动点搜索并不收敛。考虑初始猜测值 y₁，下一个猜测值为 y₂
=
x
= x
/
y
1 and the next guess is
y
3
y₁，再下一个猜测值为 y₃
=
x
/
y
2
y₂
=
x
/
(
x
(x
/
y
1
)
=
y
1. This results in an
infinite loop in which the two guesses y
1 and y
2 repeat over and
over, oscillating about the answer.
y
1. 这导致了一个无限循环，其中两个猜测值 y
1 和 y
2 反复交替出现，在答案附近来回振荡。
One way to control such oscillations is to prevent the guesses from changing so
much. Since the answer is always between our guess y and x
控制这种振荡的一种方法是防止猜测值变化过大。由于答案总是介于我们的猜测值 y 与 x
/
y, we
can make a new guess that is not as far from y as x
y 之间，我们可以产生一个与 y 的距离不如 x
/
y by averaging
y with x
y 那么远的新猜测值，方法是将 y 与 x
/
y, so that the next guess after y is
1
2
y 取平均，使得 y 之后的下一个猜测值为
1
2
(
y
+
x
/
y
)
instead of x
y
) 而不是 x
/
y. The process of making such a sequence of
guesses is simply the process of looking for a fixed point of
y
↦
y。这样逐步生成猜测序列的过程，正是寻找
y
↦ 的不动点的过程，其中变换为
1
2
(
y
+
x
/
y
):
y
)：
(Note that y
=
（注意 y
=
1
2
(
y
+
x
/
y
) is a simple transformation of the
equation y
=
x
y
) 是方程
y
=
x 的一个简单变形，
/
y
; to derive it, add y to both sides of the
equation and divide by 2.)
y；只需在方程两边各加 y，再除以 2 即可推导出来。）
With this modification, the square-root procedure works. In fact, if we
unravel the definitions, we can see that the sequence of approximations to the
square root generated here is precisely the same as the one generated by our
original square-root procedure of 1.1.7. This approach of
averaging successive approximations to a solution, a technique that we call
经过这一修改，求平方根的过程得以正常工作。事实上，如果我们展开各个定义，便可以发现这里生成的平方根逼近序列，与 1.1.7 节中原始的求平方根过程所生成的序列完全相同。这种将连续逼近取平均来求解的方法——我们称之为
average damping, often aids the convergence of fixed-point searches.
平均阻尼 (average damping)，通常有助于不动点搜索的收敛。
(define (search f neg-point pos-point)
(let ((midpoint
(average neg-point pos-point)))
(if (close-enough? neg-point pos-point)
midpoint
(let ((test-value (f midpoint)))
(cond
((positive? test-value)
(search f neg-point midpoint))
((negative? test-value)
(search f midpoint pos-point))
(else midpoint))))))(define (close-enough? x y)
( (abs (- x y)) 0.001))(define (half-interval-method f a b)
(let ((a-value (f a))
(b-value (f b)))
(cond ((and (negative? a-value)
(positive? b-value))
(search f a b))
((and (negative? b-value)
(positive? a-value))
(search f b a))
(else
(error "Values are not of
opposite sign" a b)))))(half-interval-method sin 2.0 4.0)
3.14111328125(half-interval-method
(lambda (x) (- (* x x x) (* 2 x) 3))
1.0
2.0)
1.89306640625(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
( (abs (- v1 v2))
tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))(fixed-point cos 1.0)
.7390822985224023(fixed-point (lambda (y) (+ (sin y) (cos y)))
1.0)
1.2587315962971173(define (sqrt x)
(fixed-point (lambda (y) (/ x y))
1.0))(define (sqrt x)
(fixed-point
(lambda (y) (average y (/ x y)))
1.0))