SICP第一章-1.3节 部分内容

Posted by

定积分计算

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

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 )

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注