Why does this iterative way of solving an equation work?

Question

I was solving some semiconductor physics problem and in order to get the temperature I got this nasty equation:

$$ T = \dfrac{7020}{\dfrac{3}{2}\ln(T)+12}.$$

It seems that I can solve this kind of equation by simply guessing a solution for $T$ and then substituting that answer back into the equation and then again substituting the new answer back into equation and so on until I am satisfied by the precision of result. Somehow this method works.

Concretely for my example, my first guess was $T=1$ and I got this sequence of numbers $(585.0, 325.6419704169386, 339.4797907885183, 338.4580701961562, 338.53186591337385,338.52652733834424, ...)$ and they really seem to solve equation better and better.

Questions.

1) What is an intuitive way to see why this method works?

2) How can I show rigorously that this method actually converges to a solution of the equation?

3) An obvious generalization for which the method might work seems to be: $$ x = \dfrac{a}{b\ln(x)+c}. $$ For which $a,b,c$ will this method work? Is this equation a special case of some natural generalization of this equation? What are some similar equations which I can solve by the method described?

4) When will the sequence of numbers in the iteration process converge in finitely many steps to an exact solution to the equation? Does that case exist? Is a solution to: $$ x = \dfrac{a}{b\ln(x)+c} $$ irrational for every $a,b,c$? Is it transcendental? If not, for which $a,b,c$ will that be the case?

Thank you for any help.

Answer 1

In general, a fixed point $p$ of a function $f(x)$ is an attractor for the iteration $x_{n+1} = f(x_n)$ if $|f'(p)| < 1$. Then, if your initial guess is close enough to the fixed point, the iterations will eventually converge to it. If $|f'(p)| > 1$, the fixed point is a repeller, and the only way to converge to the fixed point is to start exactly there (or happen to land there after a finite number of iterations).

You have three parameters $a,b,c$, but there are really just two because you can multiply numerator and denominator by the same constant. So let's suppose $b=1$. As Claude remarked, the fixed point is $$ p = \frac{a}{W(a e^c)}$$ and this is the only real fixed point if $a,c>0$ (this is easy to see because $f(x)$ is decreasing where it is positive). The curve $f'(p) = -1$ in the $a,c$ plane looks like this:

Above the curve, the fixed point is an attractor. In particular that is always true for $a > e$. However, $a=c=1$ is right on the curve, and it's not clear whether the fixed point would be an attractor in that case (it turns out that it isn't, by taking higher derivatives into account). If $(a,c)$ is below the curve, the fixed point is a repeller.

Answer 2

This method works because you are looking at a discrete dynamical of the form

$$x_{n+1} = f(x_n)$$

where $f$ is a contraction. The rigorous proof is the Banach fixed point theorem.

Answer 3

The equation $$T=\frac{a}{b \log (T)+c}$$ has explicit solution(s) in terms of Lambert function.

The result is given by $$T=\frac{a}{b\, W\left(\frac{a }{b}e^{\frac{c}{b}}\right)}$$

In the linked page, you will see the different steps.

Applied to your case, this will immeditely give $$T=\frac{4680}{W\left(4680 e^8\right)}=338.526887451390053458527935852$$ If you do not access this function, for large values of the argument, use the expansion given in the linked page $$W(x)=L_1-L_2+\frac{L_2}{L_1}+\frac{(L_2-2) L_2}{2 L_1^2}+\frac{(2 L_2^2-9L_2+6) L_2}{6 L_1^3}+ ...$$ with $L_1=\log (x)$ and $L_2=\log (L_1)$

Answer 4

This isn't a solution, but maybe it'll still be useful.

Assume the solution is $t^* = f(t^*) \approx 338.53$. Our sequence of iterates is $t$, $f(t)$, $f(f(t))$, $\ldots$, so analyze the error of the sequence (the distance to the optimal solution) using Taylor series to figure out when the distance starts decreasing:

\begin{align} \left\lVert f(t) - t^*\right\rVert &< \left\lVert t - t^*\right\rVert \\ \left\lVert f(t^*) + f'(t^*)(t - t^*) + f''(t^*)\frac{(t - t^*)^2}{2} + \ldots - t^* \right\rVert &< \left\lVert t - t^*\right\rVert \\ \left\lVert (f(t^*) - t^*) + f'(t^*)(t - t^*) + f''(t^*)\frac{(t - t^*)^2}{2} + \ldots \right\rVert &< \left\lVert t - t^*\right\rVert \\ \left\lVert \frac{f'(t^*)(t - t^*) + f''(t^*)\frac{(t - t^*)^2}{2} + \ldots}{t - t^*} \right\rVert &< 1 \\ \implies \left\lVert f'(t^*) + f''(t^*)\frac{(t - t^*)}{2} + \ldots \right\rVert &< 1 \end{align}

To have convergence to the solution we must have this inequality hold (though the reverse isn't true until you show more regularity in the problem), so you could try to see when this is the case. Unfortunately I don't immediately see a nice way to solve it. You could try something like the triangle inequality to bound the left side to obtain an approximation, but it might not be useful.

Answer 5

Simplified explanation:

By the Taylor development to the first order around the root $T_0$, we have

$$f(T)\approx f(T_0)+f'(T_0)(T-T_0)=T_0+f'(T_0)(T-T_0).$$

Then

$$f(f(T))\approx T_0+(f'(T_0))^2(T-T_0)$$ $$f(f(f(T)))\approx T_0+(f'(T_0))^3(T-T_0)$$ $$\cdots$$

So you understand that if $|f'(T_0)|<1$, the second term goes decreasing and the iterations tend to $T_0$ with the error decreasing in a geometric progression.

---

Addendum:

The following fixed-point iterations can be used as well:

$$T\leftarrow T-\frac{f(T)}{f'(T)}.$$

This is the famous Newton's method. It yields a much more favorable geometric ratio and faster convergence.