I am considering the problem of finding the root of equation $$f(x)=-x+\sum_{i=m}^{i=n} \sqrt{x+i}=0$$ where $m,n$ can both be from very small to very large integers. Since, in a single calculation, the equation has to be solved billions of times (high accuracy is required for the solution) , I tried to find a good approximation of the solution from which Newton's method and/or high order iteration schemes could start and solve in a minimum number of iterations.
The solution is easily bounded by $x_m$ and $x_n$ corresponding to the solutions of $$x_k=(n-m+1)\sqrt{x+k}$$ which are simple to solve but the range is quite large ($\approx (n-m-1)$ for large values of $n$) while the solution is rather close to $n^2$. For large values of $n$, using series to $ O\left(\left(\frac{1}{n}\right)^2\right)$, the solution is more or less such that $$n^2+(2-2 m) n+\left(m^2-m+1\right)< x
To improve the guess of the solution, I wondered if I could find $\alpha(m,n)$ such that the solution of $$x=(n-m+1)\sqrt{x+\alpha(m,n)}$$ would be as close as possible to the solution. To my surprise, $\alpha(m,n)=\frac {m+n}{2}$ has been revealed to provide very good results (in spite of their cost, I also tried geometric and harmonic means of the $i$'s from $m$ to $n$ but they revealed to be much less efficient). So, the current approximation of the solution is $$x\approx \frac{1}{2} \left((n-m+1)^2+\sqrt{(n-m+1)^2 \left((n-m)^2+4 n+1\right)}\right)$$ For illustration purposes, using $m=10,n=30$, the approximation gives $460.167$ while the solution is $460.149$.
The problem is that I am unable to justify this approximation which uses the arithmetic mean.
Is there any way to justify the above approximation and (why not ?) to improve it ?
No comments:
Post a Comment