What is a fixed point?
I am revisiting some of the previous lectures at SICP . The notion of a fixed point confuses me a little. Fixed point procedure: Should I think of it this way, "this is a way to find the fixed point of a given function." So what is given f(2) = 2
?
Also why in this lecture that the new function y
that is displayed in x / y
is a fixed point?
source to share
According to Fixed point (mathematics) on Wikipedia :
In mathematics, a fixed point (sometimes abbreviated to a fixed point, also known as an invariant point) of a function is an element of a function domain that is displayed by a function by a function.
So, as you wrote, f(2) = 2
indicates what 2
is a fixed point f
.
source to share
Only Ethier's answer indicates what a fixed point is, but that still leaves the other part of your question behind:
Also why is there a new y function that maps x / y to a fixed point?
The lecturer is quick to talk about what you mentioned, but I think he is actually saying that & radic; x is a fixed point of more than one function and that is the obvious function from which & radic; x - fixed point is
y & mapsto; x / y
So
& radic; x = x / & radic; x
However, this fixed point routine will not work for this function, since its internal routine iter
loops over the seed value and the function applied to the seed value. So the sequence of new / old values is (1,2), (2,1), (1,2), ...
source to share
This is when you get the same result as the last time you iterated over the function. To understand that, imagine a normal function for a known sequence:
Imagine a function f(x) = 2^(n+1)-1
. It is called a Mersenne sequence and you will have to supply its index from 0 and it makes a sequence 1, 3, 7, 15, 31, ...
(basically it is one less than every power of 2)
Now you can do the same sequence by changing the function to iterative. An iterative version f(x) = 2x + 1
. Now x will no longer be the index, but the previous one. You start at 0 and get1, 3, 7, 15, 31, ...
Now this function has no fixed point, because the result of its application is always greater than the argument. We can say that it explodes.
To answer your first question. In the SICP video, they talk about the square root. The square root of n is the fixed point of an iterated function f(x) = n/x
, because sqrt(x^2) = x
It does not map to other functions.
The general function of a fixed point would be similar to their definition of a fixed point, namely that you iterate through the function until the value you feed into the function is equal to (or close enough) to the next calculated number.
Now we can see that we could not find a fixed point from Mersenne and we know that we need to average the moisture n/x
in order for it to converge, but some functions actually converge on their own, for example f(x) = x/4 + 1
converge to 3/2
. Note that even if you averaged it, it will still become 3/2
, so only functions without a fixed point will loop forever.
source to share
Here are my two cents. This can really be confusing.
First, a simple definition: a point x
is a "fixed point" of a function f
if f(x) == x
.
In other words, x = f(x)
.
Could this make sense? It seems unlikely. It uses the value ultimately determined.
x
not necessarily prime. It can be a function or a lazy infinite list, and it f
can partially affect its definition. Then by re-evaluation
x = f(x) = f( f(x)) = f( f( f(x))) = f( f( f( f(x)))) = ....
the meaning is being determined more and more. Now this reminds us of a numerical example of calculating a fixed point f(y) = (y + n/y)/2
by recalculating,
n=25; f(1.0)=13.0; f(13.0)=7.4615383; f(7.4615383)=5.406027; f(5.406027)=5.0152473, f(5.0152473)=5.0152473; f(5.0152473)=5.0
The most important part is not to wait for the end of an endless chain of evaluations (it never happens), but to have a lazy list that records the progress of the evaluation steps. Then our value is gradually determined by an infinite list: at first it is undefined; then its first (head) element is determined, and the rest is not; then its first two elements are determined; etc. etc [1.0,13.0,7.4615383,5.406027,5.0152473,5.000023,5.0,5.0,5.0 ...]
. : .
And just as numerical values converge towards a certain number, closer and closer to the "final" value (which is never reached, but the distance gets smaller and smaller), so does the endless list of results converging to its final value. a fully defined infinite list with all its elements defined (a completely impossible feat, of course), getting closer and closer in definition to this final value (simply put, having its elements defined one after another, but mathematics seems to be difficult).
Similar to functions. If g(h,n) = n<2 -> 1 ; else -> n*h(h,n-1)
, then g(error)
is a (curried) function of one argument, defined for only n < 2
, since for any other argument it will diverge (throw an error). But g( g(error))
defined for everyone n < 3
; g( g( g(error)))
- for everyone n < 4
, etc. Again, we have a progression of values more and more defined ... And therefore the limit of this progression, the "final value", the fixed point of the function is g
such a function f
that f = g(f)
, which is defined for anyone n
, no matter how great it may be. Which is coincidentally a factorial function defined without using recursion.
source to share