Fixed Point And Newton Method

Feb 22nd, 2019 - written by Kimserey with .

Last week, we briefly looked into the Y Combinator also known as fixed-point combinator. Today we will explore more on the territory of fixed-points by looking at what a fixed-point is, and how it can be utilized with the Newton’s Method to define an implementation of a square root procedure.

• Fixed-point
• Square Root
• Newton’s Method

Fixed-point

A fixed-point $x$ of a function $f$ is a value satisfying $x=f(x)$, which in turns, implies $x=f(x)=f(f(x))$ and $f(f(x))=f(f(f(x)))$, and etc…

From this definition, we can devise a plan to find the fixed-point of a function by defining an epsilone tolerance $\varepsilon$, and recursively applying the function to itself until the delta between two successive results becomes smaller than $\varepsilon$.

This method can be seen on calculator with cosinus which given an initial guess, and iteratively calling $\cos$ with its result, will converge to its fixed-point 0.737390822985224024.

We start first by defining an $\varepsilon$.

1
(define epsilon 0.00001)

We can then use $\varepsilon$ to create a function checking for almost equality.

1
(define (almost-equal? v1 v2) (< (abs (- v1 v2)) epsilon))

Then we can define a fixed-point procedure which recursively applies the function to its antecedent result, and returns the latest result when consecutive results are almost equal.

1
2
3
4
5
6
7
(define (fixed-point f initial-guess)
  (define (apply x) 
    (let ([result (f x)])
      (if (almost-equal? x result)
        result
        (apply result))))
  (apply initial-guess))

Giving cos as function and an initial guess of 1.0, we get its fixed-point.

1
2
(fixed-point cos 1.0)
; 0.7390822985224024

Square Root

To compute $\sqrt{x}$, we would need to solve $y=\sqrt{x}$:

For a given $x$, we can compute $\sqrt{x}$ by finding $fix$ the fixed-point satisfying $fix=g(fix)$ where $g(fix)=\frac{x}{fix}$. Using our current fixed-point function, we could try (don’t try it) to find it:

1
2
(define (sqrt x)
  (fixed-point (λ (y) (/ x y)) 1.0))

But this execution will result in an infinite loop as $y_{1}=\frac{x}{y_{0}}$ then $y_{2}=\frac{x}{y{1}}=\frac{x}{\frac{x}{y_{0}}}=x*\frac{y_{0}}{x}=y_{0}$, we are back to $y_{0}$. One way to avoid going into an infinite loop is to reduce the step toward $fix$ by taking the average between the current approximation of $fix_{current}=y$ and the next approximation of $fix_{next}=\frac{x}{y}$.

We define a utility procedure to compute the average.

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

Then we can use average in our fixed-point function.

1
2
3
4
5
6
7
(define (fixed-point f initial-guess)
  (define (apply x) 
    (let ([result (f x)])
      (if (almost-equal? x result)
        result
        (apply (average x result)))))
  (apply initial-guess))

We will now be converging to the proper fixed-point. And our sqrt function will work as expected.

1
2
> (sqrt 25)
5.000000000000005

Newton’s Method

We used the average to calculate the next approximation. It turns out that averaging is a special case of the Newton’s Method, a method used to find the roots (the zeros) of a function. Each result represents an approximation of the root where each iteration provides a better aproximation.

Where $g’$ is the derivative of $g$. Each iteration of the Newton’s Method provides a better approximation to the root of $g$ where $g(x)=0$. With our example of $\sqrt{x}$, we can define the following.

Which then turns into finding the root of $g$, $g(y)=0$, which we can achieve using Newton’s Method.

As we can see, we manage to derive the average method from the square root resolution with the Newton’s Method. Taking a general approach, we can then implement a procedure computing the Newton’s Method itself.

We start first by a procedure computing derivatives at particular points, which can be calculated with $f’(x)=\frac{f(x+\delta{x})-f(x)}{\delta{x}}$.

1
2
3
4
5
(define dx 0.000001) 

(define (derivative f)
  (λ (x)
    (/ (- (f (+ x dx)) (f x)) dx)))

We can then use derivative to compute derivates at $x$, for example $x^2$ derivative at $x=10$ would be $2x=2*10=20$.

1
2
> ((derivative (λ (x) (* x x))) 10)
20.00000098689725

We can then express the Newton’s Method entirely.

1
2
(define (newton-method g y)
  (- y (/ (g y) ((derivative g) y))))

To calculate $\sqrt{10}$, we can apply newton-method iteratively, and with an initial guess close enough, we can quickly converge to the fixed-point.

1
2
3
4
5
6
7
8
> (newton-method (λ (y) (- 10 (* y y))) 5.0)
3.500000150222987
> (newton-method (λ (y) (- 10 (* y y))) 3.5)
3.1785714744980167
> (newton-method (λ (y) (- 10 (* y y))) 3.1785)
3.1623190602776896
> (newton-method (λ (y) (- 10 (* y y))) 3.1623)
3.1622776602508247

Lastly we can reuse our previous version of fixed-point procedure by replacing our average call with a parameterized procedure.

1
2
3
4
5
6
7
(define (fixed-point f transform initial-guess)
  (define (apply x) 
    (let ([result (f x)])
      (if (almost-equal? x result)
        result
        (apply (transform x result)))))
  (apply initial-guess))

And then use it to construct a new sqrt function using fixed-point:

1
2
3
4
5
(define (sqrt x)
  (fixed-point
   (λ (g) (newton-method (λ (y) (- x (* y y))) g))
   (λ (x y) y)
   1.0))

By finding the fixed-point of the Newton’s Method applied to $g(y)=x-y^2=0$, we found the result of $\sqrt{x}$. We now have a working square root procedure, and a general method to compute roots of function.

1
2
3
4
> (sqrt 25)
5.0
> (sqrt 100)
10.0

And that concludes today’s exploration of fixed-points!

Conclusion

Today we saw what the definition of a fixed-point was. We started by looking at what it represented, then moved to look at how fixed-point could be used with iterations to approximate the value of a square root. We then moved to demonstrate that what we tried earlier was a special case of the Newton’s Method which allows us to generalize the approach, and we then ended the post by implementing a complete Newton’s Method procedure. I hope you liked this post and I see you on the next one!

External Sources

• SICP Chapter 1.3.4
• Fixed-point - Wikipedia
• Newton’s Method - Wikipedia