SICPを読む(25) 1.3.3(1) 区間二分法による方程式の解の探索

今回は区間二分法。

中高生なら喉から手が出る程欲しいプログラムだ!!

方程式の解をプログラムで求めてしまおうという素晴らしい発想。

これで宿題は楽チンに・・・。

区間二分法

f(x)=0の解を求める。

f(x)をひとつづつ解いて、半分の半分の半分の・・・として、走査する方向が右か、左かを決定し、x軸との交点を探す。

x軸との交点こそが方程式f(x)=0の解だ。

非常に地道な作戦・・・。

欠点

  • x軸の「交点」でないと解がでない。
    • つまり、x^2=0の解は出ない。「接線」なので。
  • 収束が遅い

コーディング

理論がわかったとろで、コーディング。

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

πが出てきた。

次は、x^2 - 2を求めてみる。

(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の間では解が出ない。両方プラスの値なので、交点の方向がわからない。

まとめ

方程式の解を知らないと、値が指定できない。

つまり、区間二分法で「コンピューターに宿題をやらせる」という中高生の夢は叶わなそうだ。

残念!!