How does this approximation of the intersection point of two functions work?

Question

When I have two functions $f(n)=n^3$ and $g(n)=2^n$ and I want to find the intersection point I can do it by numerical approximation. So I put the functions in an equation $f(n)=g(n)$, transform the equation so there is just $n$ on one side and then I start my approximation.

$$n^3=2^n$$ $$n=\log_2(n^3)$$

So I start e.g. with $n_0=5$ and put it into $\log_2(n^3)$ that gives me $6.69$. I take this result and put it into $\log_2(n^3)$ and get $8.39$. When I repeat that I'll find the solution for $n$ because it is approximated.

When I transform the equation like so

$$n^3=2^n$$ $$n=\sqrt[3]{2^n}$$

and try the same thing, the approximation doesn't work.

Could someone explain to me why the first but the second doesn't work? What is this numerical method called? What are the rules I have to follow to make each iteration approximate $n$?

Answer 1

Fixed Point Iteration

This method is called Fixed Point Iteration.

Suppose we are trying to solve $f(x)=x$. We set up the sequence $$ x_{n+1}=f(x_n)\tag1 $$ starting with some $x_0$ reasonably close to a fixed point $a$ where $f(a)=a$.

The Mean Value Theorem says that $$ \begin{align} \frac{x_{n+1}-a}{x_n-a} &=\frac{f(x_n)-f(a)}{x_n-a}\\ &=f'(\xi)\tag2 \end{align} $$ for some $\xi$ between $x_n$ and $a$.

If $|f'(x)|\le b\lt1$ for $x$ in a neighborhood of $a$, then $(2)$ says $f$ is a Contraction Map and the sequence $\{x_n\}$ will converge to $a$

---

Inverse Function

Let $g(y)=f^{-1}(y)$ in a neighborhood of $a$. Note that $g(a)=a$. Suppose we set up the sequence $$ y_{n+1}=g(y_n)\tag3 $$ starting with some $y_0$ reasonably close to $a$.

Again, the Mean Value Theorem says that $$ \frac{y_{n+1}-a}{y_n-a}=g'(\xi)\tag4 $$ for some $\xi$ between $y_n$ and $a$.

Since $|g'(a)|=\left|\frac1{f'(a)}\right|\ge\frac1b\gt1$, the terms of the sequence are moving away from $a$.

---

One Converges, The Other Doesn't

Therefore, if $x_{n+1}=f(x_n)$ converges to a root for $f(x)=x$, most likely, using $g=f^{-1}$ and $y_{n+1}=g(y_n)$ will not converge to the root for $g(a)=a$.

In your question, $f(x)=\log_2\left(x^3\right)$ where the fixed point is $a=9.9395351414269045380$, and $f'(a)=0.4354414025488879061\lt1$ (which is an attractive fixed point).

The inverse function, $g(x)=2^{x/3}$ has the same fixed point, $a=9.9395351414269045380$, but $g'(a)=2.2965202531188520456\gt1$ (which is a repulsive fixed point).

Answer 2

It is called a fixed-point iteration and largely you want to shrink the range of the function values. The logarithm in $3\log_2(n)$ has such a shrinking behavior for larger arguments, the power function in $(\sqrt[3]2)^n$ has an expanding behavior. The first iteration will shrink towards the fixed point, while the second will expand away from it.

Or in other words, if you reverse a contracting iteration, you get naturally an expanding iteration.