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