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}$:

\[\begin{split} y & = \sqrt{x}\\ y^2 & = x\\ y & = \frac{x}{y}\\ y & = g(y) \end{split}\]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.

\[\begin{split} y&=\sqrt{x}\\ y^2&=x\\ 0&=x-y^2\\ g(y)&=x-y^2\\ \end{split}\]Which then turns into finding the root of $g$, $g(y)=0$, which we can achieve using Newton’s Method.

\[\begin{split} f(y)&=y-\frac{g(y)}{g'(y)}\\ f(y)&=y+\frac{x-y^2}{2y}\\ f(y)&=\frac{2y^2+x-y^2}{2y}\\ f(y)&=\frac{y^2+x}{2y}\\ f(y)&=\frac{y+\frac{x}{y}}{2}\\ f(y)&=average(y,\,\frac{x}{y}) \end{split}\]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!