Fixed-point of a function and an inverse problem

Question

This is perhaps a theoretical computer science question. Please help redirect appropriately. The question is about mental processes involved in discovering a solution.

Consider an iterative higher-order function fixed_point that is applied to two parameters: a function f whose fixed-point exists and a real number guess which is the initial guess. It results in the fixed-point of f:

function fixed_point(f, guess) {
    // implements the fixed-point iteration
}

(program omitted for brevity).

Given f, one can apply fixed_point to it starting with an appropriate guess. This we may term the direct problem.

But how does one start to think about finding a function $f$ such that applying fixed_point to $f$ results in the square-root of a real number? This may be termed an inverse problem.

I played with it in GeoGebra and found $f(x)=\frac{1}{2}(\frac{a}{x}+x)$, but it was by chance, I believe.

How would you have gone to reason about finding this function (solving the inverse problem)? Coming up with this $f$ seems magical to me.

Answer 1

To recap your question:

How to construct a function $f(x,a)$ such that the fixed point solution $x^*=f(x^*,a)$ is $x^* = \sqrt a$.

First, notice that the answer is not unique. For example $f(x ,a)={a\over x}$, in addition to your own solution $f(x, a)={1\over2}({a \over x} + x)$ Here is a naive recipe for generating such functions:

1. Find a function $P(x)$ such that $P(\sqrt a)=0$
2. Define f(x)=x-P(x)

By construction $f(\sqrt a)=\sqrt a -P(\sqrt a)=\sqrt a$

For example, $P(x) = {1\over2 }(x-{a\over x})$ will generate your function.

However These functions may not converge under iterations, so a better way to create such functions is to use the Newton-Raphson root finding method on $P$. As an example, take $P=x^2-a$. Instead of using the direct fixed point function $y=x^2-x-a$ we construct the N-R iteration $$x_{n+1} = x_n - {P(x_n) \over P'(x_n)}=x_n-{x_n^2-a \over 2 x_n}$$ That is a fixed point of the function $$y(x)={1\over 2}{(x+{a\over x})}.$$ This iteration will converge.

So generally, If you want to solve iteratively $g(x)=a$, Instead of using $y= x - (g(x)-a)$, Newton-Raphson will have you consider it as a "Fixed Point" of the iteration $$x_{n+1}=x_n- {g(x_n)-a \over g'(x_n)}$$