0
$\begingroup$

I have a function in the following form:

$a^k+b^k+c^k=1$,

where $0<a,b,c<1$, and k is the unknown. I need to solve this equation for $k$ a ~million times for different $a$, $b$ and $c$ values. Although it works appropriately with an iterative approximation, it would take ages to finish.

I wonder if this function could be approximated with an infinite series. Can you give me any suggestions I can follow to find such an approximation?

$\endgroup$
3
  • 1
    $\begingroup$ there is this post math.stackexchange.com/q/2778053/399263, but no definitive answer I fear. $\endgroup$ – zwim Oct 4 '20 at 22:27
  • 1
    $\begingroup$ Because you're region of a, b, and c is very restricted, it seems newtons method maybe converge from a simple guess pretty well in maybe 10 or 20 iterations. You might just try newtons method with some rather hardcore iteration limiting, at least as a baseline. Especially, since your input is a cube, you could precompute with Newtons method at regular intervals and then save that and try some sort of interpolation $\endgroup$ – Cade Reinberger Oct 5 '20 at 0:26
  • $\begingroup$ @CadeReinberger This would be an efficient method for most of the points inside the cube. However, k tends to infinity close to the faces of the cube making the interpolation very inaccurate in those regions. $\endgroup$ – BalazsToth Oct 5 '20 at 0:42
1
$\begingroup$

You are looking for the zero of function $$f(k)=a^k+b^k+c^k-1$$ For sure, a numerical method should be used.

Making the function more linear, consider instead you look for the zero of the more linear function $$g(k)=\log(a^k+b^k+c^k)$$ for which $$g'(k)=\frac{a^k \log (a)+b^k \log (b)+c^k \log (c)}{a^k+b^k+c^k}\quad < 0 \quad \forall k$$ $$g''(k)=\frac{a^k b^k (\log (a)-\log (b))^2+a^kc^k \left( \log (a)-\log (c))^2+b^kc^k (\log (b)-\log (c))^2\right)}{\left(a^k+b^k+c^k\right)^2}$$ wich is positive $\forall k$.

Since $g(0)=\log(3) >0$, by Darboux theorem, the first iterate of Newton method is an underestimate of the solution. So, using $k_0=0$ $$k_1=-\frac {3\log(3)}{\log(abc)}$$ could be "reasonable".

Trying for $a=\frac 12$, $b=\frac 13$, $c=\frac 14$, this would give $$k_1=\frac{\log (27)}{\log (24)}\approx 1.03706$$ while the exact solution is $1.08213$.

Performing the next iterations according to $$k_{n+1}=k_n-\frac{g(k_n)}{g'(k_n)}=k_n -\frac{\left(a^{k_n}+b^{k_n}+c^{k_n}\right) \log \left(a^{k_n}+b^{k_n}+c^{k_n}\right)}{a^{k_n} \log (a)+b^{k_n} \log (b)+c^{k_n} \log (c)}$$ For the worked example, the would give $k_2=1.08205$ and a second iteration leads to the solution.

Edit

You could have a better estimate of the solution computing the first iterate of the original Halley method and get

$$k_1=\frac{3 \log (3) \log (abc)} {(\log (3)-1) A-(2+\log (3))B }$$ where $$A=\log ^2(a)+\log ^2(b)+\log ^2(c)$$ $$B=\log (a) \log (b)+\log (a) \log (c)+\log (b) \log (c)$$

For the worked example, this would give $k_1=1.07979$ which is much better.

$\endgroup$
2
  • $\begingroup$ This is a valuable answer. What I do not understand is how the second equation is equivalent to the first one. $\endgroup$ – BalazsToth Oct 5 '20 at 18:49
  • 1
    $\begingroup$ The roots of $f(k)=1$ are the same as the roots of $g(k)=\log(f(k))=0$ $\endgroup$ – Claude Leibovici Oct 6 '20 at 4:31

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.