牛顿法求平方根

目录

算法

y^2=x 时,已知 x 求 y。 猜测一个 y1 这样得到 y2=(y1+x/y1)/2,然后不断的迭代下去 yn 就会无限的接近 y。
y1 y2=(y1+x/y1)/2
y2 y3=(y2+x/y2)/2
yn y(n+1)=(y(n+1)+x/(y(n+1))/2

算法解释

  其实这个算法还是很好理解的,我们把 y^2=x 变形为 y=x/y,这时我们猜测一个 y1,假设 y1<y,则 y < x/y1 ,设 y2=(y1+x/y1)/2 可以推出 y1<y2<x/y1 可以看出 y2 比 y1 更接近 y.

  假设 y1>y, 则 y > x/y1, 则 x/y1<y2<y1 同样 y2 比 y1 更接近 y。这样一直迭代下去 则 y(n+1)比 yn 更接近 y。

算法程序

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


(define (abs x)
  (cond
   ((> x 0) x)
   ((= x 0) 0)
   ((< x 0) (- x))
   )
  )

(define (average x y)
  (/ (+ x y) 2)
  )

(define (sqrt x)
  (sqrt-iter 1.0 x)
  )

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)
      )
  )

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001)
  )

(define (improve guess x)
  (average guess (/ x guess))
  )

目录