SICPを読む(25) 1.3.3(1) 区間二分法による方程式の解の探索
今回は区間二分法。
中高生なら喉から手が出る程欲しいプログラムだ!!
方程式の解をプログラムで求めてしまおうという素晴らしい発想。
これで宿題は楽チンに・・・。
区間二分法
f(x)=0の解を求める。
f(x)をひとつづつ解いて、半分の半分の半分の・・・として、走査する方向が右か、左かを決定し、x軸との交点を探す。
x軸との交点こそが方程式f(x)=0の解だ。
非常に地道な作戦・・・。
- 二分法 - Wikipedia
- はんぶんの、はんぶんの、はんぶんの・・・。バイナリサーチと同じ考え方。
欠点
- x軸の「交点」でないと解がでない。
- つまり、
の解は出ない。「接線」なので。
- つまり、
- 収束が遅い
コーディング
理論がわかったとろで、コーディング。
(define (average a b) (/ (+ a b) 2.0)) (define (search f neg-point pos-point) (let ((mid-point (average neg-point pos-point))) (if (close-enough? neg-point pos-point) mid-point (let ((test-value (f mid-point))) (cond ((positive? test-value) (search f neg-point mid-point)) ((negative? test-value) (search f mid-point pos-point)) (else mid-point)))))) (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")))))
長い。
どうもletに慣れない。
お試し
僕の一番好きな関数。sinの2〜4の間の解。
(half-interval-method sin 2 4) ;3.1411...
πが出てきた。
次は、を求めてみる。
(half-interval-method (lambda (x) (- (* x x) 2)) 0 2) ; √2 (half-interval-method (lambda (x) (- (* x x) 2)) -2 0) ; -√2 (half-interval-method (lambda (x) (- (* x x) 2)) -2 2) ; エラー
答えは,√2,-√2。
-2,2の間では解が出ない。両方プラスの値なので、交点の方向がわからない。
