定积分计算
定积分近似值的两种计算方法
1.传统计算公式
[latexpage]
$\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之间的定积分近似值是:
[latexpage]$ \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
[latexpage]$ 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 )
)
求解开平方的两种方法
平均阻尼法
[latexpage]计算某个数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$.
[latexpage]这时将$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
[latexpage]定义一个cubic,使用牛顿迭代法计算三次方程$x^3 + ax^2+c$的零点
(define (cubic a b c )
(lambda (x) ( + (cube x) ( * a ( square x ) ) ( * b x ) c ) )
)
练习1.31计算圆周率
[latexpage]按照下面公式计算$\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 )