SICP第一章-1.3节部分内容

定积分计算

定积分近似值的两种计算方法

1.传统计算公式

$\int_{a}^{b}f=[f(a + \frac{dx}{2}) + f(a + dx + \frac{dx}{2}) + f(a + 2dx + \frac{dx}{2})+ ...]$

其中dx是一个很小的值,将这个公式描述成一个过程.

(define (cube x) ( * x x x )  )

(define (sum term a next b )
    (if ( > a b )
        0
        ( + ( term a ) 
            ( sum term ( next a ) next b ) 
        )
    )
)

(define (integral f a b dx )
    (define (add-dx x  ) ( + x dx )  )
    ( * ( sum f (+ a ( / dx 2.0 )) add-dx b ) dx )
)

(integral cube 0 1 0.01)

2.辛普森规则

练习1.29

辛普森规则是另一种比上面的传统规则更加精确的数值积分方法.(其证明方法还没找到….)函数f在范围a和b之间的定积分近似值是:

$\frac{h}{3}[ y_0 + 4y_1+2y_2+4y_3+2y_4+...+2y_{n-2} + 4y_{n-1} + y_n]$

其中 $h = \frac{b - a}{n}$ ,n是某个偶数, $y_k = f(a+kh)$ 定义一个具有参数f, a, b和n,采用辛普森规则计算并返回积分值的过程.

(define (cube x) ( * x x x )  )

(define (sum term a next b )
    (if ( > a b )
        0
        ( + ( term a ) 
            ( sum term ( next a ) next b ) 
        )
    )
)

(define (simpson f a b n)  
    (define h ( / ( - b a ) n ))

    (define k a )

    (define (next k) ( + k 1 ) )

    (define (y k) ( f (+ a ( * k h ) ) ) )

    (define (coefficient k)  
        (cond
            ((or ( = k 0 ) ( = k n )) 1)
            (( even? k ) 2)
            ( else 4 )
        )
    )

    (define (foo k) ( * ( coefficient k ) ( y k ) ) )

    ( * ( sum foo k next n ) ( / h 3.0 ) )
)

(simpson cube 0 1.5 100)

函数不动点

数x称为函数f的不动点,如果x满足方程f(x) = x.对于某些函数,通过某个初始猜测出发,反复地应用f

$f(x), f(f(x)), f(f(f(x)))...$

直到值的变化不大时,就可以找到它的一个不动点.我们可以写出fixed-point的代码.

(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 )
)

求解开平方的两种方法

平均阻尼法

计算某个数x的平方根,就是要找到一个y使得 $y^2 = x$ ,将这一等式变成另一个等价形式 $y = \frac{x}{y}$ ,这里要做的就是寻找函数 $y \mapsto \frac{x}{y}$ 的不动点.但是这个搜索不动点的过程不会收敛.从初始猜测 $y_1$ 开始,下一个猜测 $y_2= \frac{x}{y_1}$ ,而再下一个猜测是 $y_3 = \frac{x}{y_2}=\frac{x}{\frac{x}{y_1}}=y_1$ .结果就是进入了一个无限循环,没完没了地重复 $y_1$ , $y_2$ .

这时将 $y = \frac{x}{y}$ 变形为 $y = \frac{1}{2} ( y + \frac{x}{y} )$ ,那么下一个猜测的值就是 $\frac{1}{2} ( y + \frac{x}{y} )$ ,而不是 $\frac{x}{y}$ ,做出这种猜测序列的计算过程也就是搜寻 $y \mapsto \frac{1}{2} ( y + \frac{x}{y} )$ 的不动点.

使用scheme编写的平均阻尼法求平方及立方的代码

(define (average a b ) ( / ( + a b ) 2 ))

( define tolerance 0.00001 )

(define (average-damp f )
    (lambda (x) ( average x ( f x ) )  )
)

(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 )
)

(define (sqrt x )
    (fixed-point (average-damp (lambda (y) ( / x y ) ) ) 1.0 )
)

(define (cube-root x )
    (fixed-point (average-damp (lambda (y) ( / x ( square y ) ) ) ) 1.0 )
)

( cube-root 27 )

更多内容可见:平均阻尼法

牛顿迭代法

练习1.40

定义一个cubic,使用牛顿迭代法计算三次方程 $x^3 + ax^2+c$ 的零点

(define (cubic a b c )
    (lambda (x)  ( + (cube x) ( * a ( square x ) ) ( * b x ) c ) ) 
)

练习1.31计算圆周率

按照下面公式计算 $\pi$ 的近似值.

$\frac{\pi}{4} = \frac{2 * 4 * 4 * 6 * 6 *8...}{3 * 3 * 5 * 5 * 7 * 7...}$

先将这个式子进行一次变形,分子分母的每次增量就对称了.

$\frac{\pi}{8} = \frac{ 4 * 4 * 6 * 6 *8…}{3 * 3 * 5 * 5 * 7 * 7...}$

(define (product term a next b )
    (if ( > a b )
        1
        (* ( term a )
            ( product term ( next a ) next b )
        )
    )
)

(define (product2 term a next b)
    (define (iter a ans)
        (if ( > a b )
            ans
            ( iter ( + a 1 ) ( * ( term a ) ans ) )
        )
    )
    ( iter a 1 )
)

(define ( multi a b )
    (define (itself a) a)
    (define (multi-next a) ( + a 1 ))
    ( product itself a multi-next b)
)

(define ( pi n )
    (define (term-up x ) 
        (cond ( ( = x 1 ) 1 )
            ( ( even? x ) ( + x 2) )
            ( else ( + x 1 ) )
        )
    )

    (define (term-down x )
        (cond (( = x 1 ) 3)
            ( ( even? x ) ( + x 1 ) )
            (else  ( + x 2 ) )
        )
    )
    (define (next x ) ( + x 1 ) )
    (  * ( exact->inexact ( / ( product2 term-up 1 next n )
                        ( product2 term-down 1 next n ) )) 8)
)

( pi 1000 )

练习1.43

写一个过程,它的输入是一个计算f的过程和一个正整数n,返回的是能计算f的n次重复应用的那个函数.

这里的解法是基于练习1.42的,scheme能够将过程作为返回值,再一次使我见识到了这个语言神奇的地方.

(define (compose f g )
    (lambda (x)
        ( f ( g x ) )
    )
)

(define (square x ) ( * x x ))

(define (repeated f n )
    (if ( = n 1 )
        ;(lambda (x) (f x))
        f
        (lambda (x) ( 
            f ( (repeated 
                    f
                     (- n 1) 
                ) 
              x )))
    )
)

(define (repeated1 f n )
    (define (iter a g )
        (if ( = a n )
            g
            (lambda (x) ( f ( g x ) ) )
        )
    )
    ( iter 1 f )
)

(define (repeated2 f n )
    (if ( = n 1 )
        f
        (
            compose f ( repeated2 f ( - n 1 ) )
        )
    )
)

(define (repeated3 f n )
    (define (iter a g )
        (if ( = a n )
            g
            ( compose g ( iter ( + a 1 ) g ) )
        )
    )
    ( iter 1 f )
)

( (repeated3 square 2 ) 5 )