Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a computer application, I need to solve trillions of times an equation which can be reduced to $$f(x)=\sin(x)-a x=0$$ Newton methods (quadratic and higher orders) are used for the solution. Parameter $a$ is random and the solution $x$ looked for is the one between $0$ and $\pi$ if it exists. The retained solution is immediate ($x=0$) if $a \geq 1$ or $a \leq 0$.

For the other cases ($0 \lt a \lt 1$), since I need to save as many iterations as I can, I focused on how to establish a good and unexpensive approximation of the solution. After some empirical experiments, what I found is that writing $$\sin(x) \simeq \frac{4}{\pi^2} x(\pi-x)$$ is a quite good approximation if $0 \leq a \leq 0.7$ leading to $$x \simeq \pi -\frac{\pi ^2 a}{4}$$

For the remaining interval, using Pade approximation $$\sin(x) \simeq \frac{x-\frac{7 x^3}{60}}{1+\frac{x^2}{20}}$$ which leads to $$x \simeq \frac{2 \sqrt{15} \sqrt{1-a}}{\sqrt{3 a+7}}$$ seems interesting.

I wonder if this could be improved, the goal being a simple explicit expression for the estimate of the solution.

Any idea and/or suggestion would really be welcome.

Added later

In comments and answers, Bhoot suggested me to look at the approximation $$\sin(x) \simeq \frac{16 (\pi -x) x}{5 \pi ^2-4 (\pi -x) x}$$ proposed by Mahabhaskariya of Bhaskara I, a seventh-century Indian mathematician. This spendid approximation leads to $$x \simeq \frac{2 \sqrt{-\pi ^2 a^2+2 \pi a+4}+\pi a-4}{2 a}$$ which is effectively very good except very close to $a=1$. This already makes a significant improvement.

Temporary improvement

Extremely impressed by the quality of the approximation proposed by Mahabhaskariya of Bhaskara I (more than 1400 years ago), I tried to undertand why it was very good except in the vicinity of $a=1$. I suspected that the derivative could be in error at the end points. Effectively, this formula gives a slope equal to $\frac{16}{5\pi} \simeq 1.01859$ instead of $1$. On the other side, the area under the curve is given by $$A=\pi \left(-4+\pi +\tan ^{-1}\left(\frac{3116}{237}\right)\right) \simeq 1.99955$$ So, modestly, I built an approximation which is $$\sin(x) \simeq \frac{\pi x(\pi-x)}{\pi^2+(\pi-4)x(\pi-x)}$$ which allows to match exactly the function and derivative values at $x=0,\frac{\pi}{2},\pi$; with respect to accuracy, it is not as good as the original showing a maximum error of $0.0052$ instead of $0.0016$. The area under the curve is then given by $$A=\frac{\pi \left(-4 \pi +\pi ^2+4 \sqrt{(4-\pi ) \pi } \tan ^{-1}\left(\sqrt{\frac{4}{\pi }-1}\right)\right)}{(\pi -4)^2} \simeq 1.99161$$ quite significantly worse than the original.

The estimate of the solution is given by $$x \simeq \frac{\pi \left((\pi -4) a-\sqrt{(\pi -4) a (\pi a-2)+1}+1\right)}{2 (\pi -4) a}$$ which makes Newton scheme converging in less than two iterations for the whole range.

Added after Christian Blatter's answer

I used what has been kindly proposed by Christian Blatter in his answer and set

$$\tilde f^2(a):={p(a)\over q(a)},\qquad p(a):=c_0+c_1 a+ c_2 a^2,\quad q(a):=1+d_1a +d_2 a^2\ $$ Using nonlinear regression, I adjusted the five involved parameters in order to minimize $$SSQ=\sum_{i=1}^n \Big(\sin(\tilde f(a_i))-a_i \tilde f(a_i)\Big)^2$$ The values of the $a_i$ were generated using $1000$ equally spaced values of the $x_i$ between $0$ and $\pi$. I have not been able to compute formally $$\int_0^1 \Big(\sin(\tilde f(a_i))-a_i \tilde f(a_i)\Big)^2 da$$

Starting with the coefficients given in Christian Blatter's answer, the initial $SSQ=5.968\times 10^{-5}$ which is already very good. I arrived to $SSQ= 3.800\times 10^{-6}$. The corresponding parameters are $$c_0=9.86774920$$ $$c_1=4.91765690$$ $$c_2=-14.77935381$$ $$d_1=2.48744104$$ $$d_2=0.63396306$$ For these values, the largest error is $0.000295$ and the average error is $0.000052$ which is incredibly good. As a result, a single Newton iteration is basically required for the desired accuracy. In the following plot the function $\tilde f$ is denoted $g$:

enter image description here

I would like to thank all people who contribute to this work. You have been extremely helpful.

Added later

Continuing working the problem, I set $$\tilde f^2(a):={p(a)\over q(a)},\qquad p(a):=\sum_{i=0}^n c_i a^i,\quad q(a):=1+\sum_{i=1}^n d_i a^i\ $$ and played with $n$. The first result is that moving to cubic polynomials changes a lot the result : $SSQ=4.9609379\times 10^{-10}$, maximum error $= 0.000004$, average error $< 0.000001$. This means that one single Newton iteration is required for a high accuracy. Mowing to fourth oder gives the solution without any Newton iteration.

share|improve this question
4  
Maybe of interest: en.wikipedia.org/wiki/… –  user105475 Jul 19 at 7:03
    
@Bhoot. This is a superb approximation (I did not know it). Please, put it as an answer to my post. I shall edit and refer to you. –  Claude Leibovici Jul 19 at 7:20
    
@ClaudeLeibovici: You are right! It is a nice approximation formula. –  Mhenni Benghorbal Jul 19 at 9:22
1  
@MhenniBenghorbal. When you think that is was done almost $1400$ years ago ! Cheers :) –  Claude Leibovici Jul 19 at 9:24
    
@ClaudeLeibovici: He is a seventh-century Indian mathematician. –  Mhenni Benghorbal Jul 19 at 9:25

3 Answers 3

up vote 2 down vote accepted

Here is a way to solve this equation quickly that I think is more efficient that the methods proposed so far. The reason I think this is more efficient is that allows you to get about 15 digits with some multiplications (which are cheap), one square root, and at most one sin-cos evaluation (which are expensive).

Your equation reminds me of the Kepler equation, that I once tried to analyse, and used a similar approach.

Instead of approximating $\sin x$ by some algebraic function, and then solving the approximate equation, let's approximate the true solution instead. Denote the solution $y(a)$, $0<y(a)<\pi$, $0<a<1$, of the equation $$ \sin y(a)-a y(a) = 0, $$ then $y(a)$ has a root, $y(1)=0$, and it behaves at $a\approx1$ as $$ y(a) \sim \sqrt{6}(1-a)^{1/2}. $$ Here is the graph of $y(a)/\sqrt{1-a}$:

enter image description here

Now the red function $y(a)/\sqrt{1-a}$ is smooth, non-singular, has no roots, so we can approximate it with a Chebyshev series $\sum_{k\geq0}c_k T_k(x)-\frac12 c_0$, with these coefficients:

[5.468893253088218, -0.3315308418632746, 0.05711908619285262, -0.0133386391330606, 0.003604590132654065, -0.001061080932244192, 0.0003303619584939474, -0.0001070040549514469, 3.56907424708586e-5, -1.217702854008323e-5, 4.22996639149332e-6, -1.491025149248465e-6, 5.319859653014493e-7, -1.917577069128536e-7, 6.972596591016018e-8, -2.554518680989035e-8, 9.420605435988877e-9, -3.494307402618534e-9, 1.302781037141137e-9, -4.879450499229215e-10, 1.835088955571608e-10, -6.927187870873964e-11, 2.62374324329517e-11, -9.968294055829801e-12, 3.797891128370018e-12, -1.450731732722623e-12, 5.554781896411238e-13, -2.131593799567149e-13, 8.196531167958859e-14, -3.15778010597506e-14, 1.218720260971691e-14, -4.711359031839824e-15, 1.824159314975387e-15, -7.073133344264407e-16, 2.746327946190114e-16, -1.067647609986269e-16, 4.153961510615797e-17, -1.613912600904692e-17, 6.171147771603768e-18, -2.090308692683401e-18]

Depending on how much accuracy you need, it might be enough to sum the first 34 terms using the Clenshaw recurrence (this takes 33 multiplications, and uses no expensive operations, like divisions). Here is the plot of relative error for successive Chebyshev approximations to $y(a)/\sqrt{1-a}$:

enter image description here

Depending on the relative cost of trigonometric operations on your machine (this should be established experimentally), it may be faster to take just enough Chebyshev terms that one Newton iteration suffices to get accuracy to machine precision. Here is 8 terms followed by one Newton iteration (blue) or one Halley iteration (red). The only expensive operation here would the simultaneous evaluation of sin and cos for the function and its derivative:

enter image description here

The cost of this is 7 multiplications for the Chebyshev series, and 4 multiplications, 2 divisions and one sin-cos for the Halley iteration, and one square root and a multiplication to get back $y(a)$.

share|improve this answer
    
This is an very intersting answer and I thank you very much. I shall start working on this basis right now. Moreover, from a purely esthetical point of view, it is beautiful ! Thanks again. Cheers :-) –  Claude Leibovici Sep 27 at 5:30

Bhaskara's sine approximation looks a bit like a Padé approximant and is eerily accurate.

Another option---since you need to do this trillions of times---is to save the solutions for many values of $a$, and then look up/interpolate solutions as you need them.

share|improve this answer
    
Table lookup and interpolation are quite expensive. Again, thank you very much for this superb reference. Cheers :) –  Claude Leibovici Jul 19 at 7:33
    
You're welcome. I think the lookup can be made to be quite cheap, since you know the structure of the table. But yes, for trillions of calls, even a small cost per call can mean a lot. An interesting problem! –  user105475 Jul 19 at 7:45
    
If you are interested, have a look to what I added. Thanks to you, I have been able to make just incredible improvements in few hours. Thanks again. Cheers :) –  Claude Leibovici Jul 19 at 15:33

We have to solve the equation ${\rm sinc}(x)=a$ for $x\in[0,\pi]$ in terms of the parameter $a\in[0,1]$. As Kirill has remarked, for $a\to1\!-\ $ we obtain $x\doteq\sqrt{6(1-a)}$. Therefore, if we want a single simple expression giving accurate values over the whole $a$-interval $[0,1]$ we have to take a square root at the end.

For this reason we put $x:=\sqrt{u}$ and solve the equation $$\bigl(s(u):=\bigr)\quad {\rm sinc}\bigl(\sqrt{u}\bigr)=a\tag{1}$$ for $u$ in terms of $a$. Let $$a\mapsto u:=f(a)\qquad(0\leq a\leq1)$$ be the solution of $(1)$, i.e. the inverse function of $s$. From known values of $s$ and $s'$ we can, e.g., deduce the values $$f(0)=\pi^2,\quad f\left({2\over\pi}\right)={\pi^2\over4},\quad f\left({\sqrt{27}\over 4\pi}\right)={4\pi^2\over9},\quad f(1)=0\ ,\tag{2}$$ and $$f'(0)=-2\pi^2\tag{3}$$ (one could take more such values into account and determine more coefficients $c_k$, $d_k$ in the following).

We now make the "Ansatz" $$\tilde f(a):={p(a)\over q(a)},\qquad p(a):=\pi^2+c_1 a+ c_2 a^2,\quad q(a):=1+d_1a +d_2 a^2\ ,$$ and determine the coefficients $c_1$, $c_2$, $d_1$, $d_2$ such that $(2)$ and $(3)$ are satisfied. This leads to the approximation $$x=g(a):=\sqrt{\tilde f(a)}=\sqrt{{\pi^2+5.95839 a - 15.828 a^2\over 1 + 2.60371 a + 0.690687 a^2}}\ .$$ The following figure shows a plot of $a\mapsto \sin\bigl(g(a)\bigr)-a\> g(a)$:

enter image description here

share|improve this answer
    
I thank you very much for this very interesting answer. I shall start working on this basis right now. Thanks again. Cheers :-) –  Claude Leibovici Sep 27 at 5:34
    
I worked based on your ideas and I made a quite good approximation. I added that to my question and let it for your review (if you wish). I would have liked to add a plot similar to your; the problem is that I am blind and producing graphics is very very hard to me. May be, if you wish, could you add one ? Thanks again. –  Claude Leibovici Sep 29 at 4:59
    
My wife just tells me that the plot is very nice and illustrative. Thanks again. Cheers :) –  Claude Leibovici Sep 29 at 10:22
    
May be you should be amazed by the following :increasing the degree of the polynomials makes the solution better and better, not to say almost exact. The most funny is that this can be done without requiring initial estimates ! Thanks again. –  Claude Leibovici Oct 1 at 9:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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