10
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Looks like the solution happens to be an attractive fixed point. $\endgroup$ – Brevan Ellefsen Apr 14 at 1:25
  • 10
    $\begingroup$ It's called fixed point iteration; it is one of the classical topics of numerical analysis. When the method works there is some geometric intuition in terms of a "web plot"; the geometric intuition shown there essentially captures the main idea of the proof, which is called the contraction mapping principle or the Banach fixed point theorem. You can use the statement of the fixed point theorem to answer your question 3, although resolving the dependence on the initial guess is usually intractable in practice. Your question 4 is also usually intractable to answer in practice. $\endgroup$ – Ian Apr 14 at 1:26
  • 1
    $\begingroup$ There is a proof for existence and uniqueness of fixed points for contraction mappings on certain domains using iteration. I'll find you some links to previous Questions here. $\endgroup$ – hardmath Apr 14 at 1:29
19
$\begingroup$

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:

enter image description here

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.

$\endgroup$
22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Under mild assumptions on $f$, we have that $x_n\to x^\infty$ and also $f(x_n)\to f(x^\infty)$. $\endgroup$ – Tony S.F. Apr 15 at 7:52
  • $\begingroup$ @Teepeemm Technically the statement of the theorem is one of existence of a fixed point, but the proof proceeds by constructing the fixed point using iteration. The subtlety of applying this result in practice is that you need the map to be a contraction on some compact set that is mapped to itself by the map. In practice our map is usually not a contraction on its whole domain, so rigorously invoking the theorem requires us to furnish a domain where the initial condition can be where the hypotheses of the theorem are satisfied. $\endgroup$ – Ian Apr 15 at 17:32
  • $\begingroup$ @Teepeemm A topological proof for the Banach fixed point theorem? That makes no sense to me. Can you explain? $\endgroup$ – Ian Apr 15 at 18:43
  • $\begingroup$ @Ian My mistake. I've been thinking of the Brouwer fixed point theorem this entire time. $\endgroup$ – Teepeemm Apr 15 at 19:20
9
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ That's equation (2.4.4) from Asymptotic Methods in Analysis by N. G. de Bruijn. A most excellent book. $\endgroup$ – marty cohen Apr 14 at 3:57
  • $\begingroup$ @martycohen. Thanks for the information ! Fortunately, we can find it in many places. A few years ago, one of my PhD students extended it to very high orders. Cheers :-) $\endgroup$ – Claude Leibovici Apr 14 at 4:14
  • 7
    $\begingroup$ Whilst I'm sure this is accurate, and interesting contextual information. It isn't actually an answer to the question asked. $\endgroup$ – Brondahl Apr 14 at 6:02
  • 2
    $\begingroup$ It's likely the OP wasn't even aware such a function existed. Even though it's not technically part of the question, it will still be valuable information for the OP. $\endgroup$ – Ingolifs Apr 15 at 1:22
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.