2
$\begingroup$

I'm researching a topic for solving general algebraic equations using numerical method. My numerical recipe knowledge is rather rusty with the Bisection to Newton's methods but I don't think those could be applied for equations such as:

$$ \frac{x^2}{2+x}+\cos(x+1)=x^2\times \sin\left(\frac{\sqrt x}{x^2}\right) $$

with an approximated numerical solutions: $$ x_1\approx0.531709 $$ and $$ x_2\approx3.401750 $$ I know matlab has the vpasolve function for numerical approximation of the unknown variable but I can't find any details regarding the used method or even if such a numerical method exist that can be used to approximate the unknown variable for any given equation with one unknown var. At first I tried applying Newton Raphson's method but stuck right at the beginning since:

  1. I'm not searching for a solution in the form of $f(x)=0$.
  2. I don't know the derivative for the equation and I don't want to apply symbolic algorithms.

Thank you for the tips! Cheers!

$\endgroup$
5
  • 1
    $\begingroup$ Have you considered setting $f(x) = $ LHS - RHS? $\endgroup$ – fosho Jan 6 '16 at 14:08
  • $\begingroup$ For 1, consider @Daniel's suggestion. For 2, how about trying secant method? It is a discrete version of Netwon's, but you don't need to find the derivative. $\endgroup$ – KittyL Jan 6 '16 at 14:10
  • $\begingroup$ What do you mean by "I am not searching for a solution in the form f(x)=0"? $\endgroup$ – NoChance Jan 6 '16 at 14:14
  • 2
    $\begingroup$ Your question seems to be about algebraic equations, but your example is precisely not algebraic. Check your terminology. $\endgroup$ – Yves Daoust Jan 6 '16 at 14:17
  • $\begingroup$ @NoChance OP means that he has $f(x) = g(x)$ $\endgroup$ – fosho Jan 6 '16 at 14:18
0
$\begingroup$

Set $f(x) = \frac{x^2}{2+x}+\cos(x+1)-x^2\sin\left(\frac{\sqrt x}{x^2}\right)$, now you are looking for $f(x) = 0$ and you can apply something like the bisection method if you do not know the derivative of the function.

$\endgroup$
3
$\begingroup$

As already said in answers and comments, consider that you look for the zero's of the function $$f(x)=\frac{x^2}{2+x}+\cos(x+1)-x^2\times \sin\left(\frac{\sqrt x}{x^2}\right)$$ and apply Newton method which, starting from a "reasonable" guess $x_0$, will update it according to $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ For the function, let me be very lazy and choose $x_0=5$; the successive iterates will then be $$x_1=2.63695$$ $$x_2=3.65956$$ $$x_3=3.40642$$ $$x_4=3.40175$$ which is the solution for six significant figures.

For sure, you need the derivative of the function. But, may be, you do not want to establish its analytical expression. Then, just compute it using finite differences such as $$f'(x_n)=\frac{f(x_n+\epsilon)-f(x_n)} \epsilon$$ or, better $$f'(x_n)=\frac{f(x_n+\epsilon)-f(x_n-\epsilon)} {2\epsilon}$$ using, for example, $\epsilon=\frac{x_n}{1000}$. This will work fine.

$\endgroup$
7
  • $\begingroup$ Claude, one may prefer the secant method over Newton when the derivative is estimated numerically. Indeed, the former is known to show order $\phi$ convergence rate ($1.618$), while Newton is order $2$, but when it takes $2$ or even $3$ function evaluations, this lowers the order to $\sqrt2$ ($1.41$) or $\sqrt[3]2$ ($1.26$). $\endgroup$ – Yves Daoust Jan 8 '16 at 10:24
  • $\begingroup$ @YvesDaoust. Always interesting comments ! May I disagree with your first point. There are Newton methods to 16th order which are derivative free. When you think about it, a one side derivative just requires one extra function evaluation. For complicated functions, the cost is about the same. In 1998 (if I properly remember), there was the so-called AD-CAPE-Open project and we did investigate a lot for this problem. If you wish, we can continue exchanging e-mails (my address is in my profile). Cheers :-) $\endgroup$ – Claude Leibovici Jan 8 '16 at 10:37
  • $\begingroup$ What matters is the total number of function evaluations required to reach a prescribed accuracy (assuming that the algorithm overhead is neglectible). I have an extra reason to like the secant method (more precisely Regula Falsi and variants): it can guarantee convergence in the initial interval. $\endgroup$ – Yves Daoust Jan 8 '16 at 10:48
  • $\begingroup$ @YvesDaoust. I think that (once more) I agree on this point. When the solution is bracketed, what I also enjoy and use is a combination of high and low order methods. To me, this is important when multiple roots exist. To me the problem is different when there is a single root or when we know a good estimate of the solution. Thanks for discussing with me. There are not many people here concerned by the numerical aspects. $\endgroup$ – Claude Leibovici Jan 8 '16 at 10:54
  • $\begingroup$ Converging methods is a quite interesting topic, no doubt, and there's tons of literature about it. As regards me I am more intrigued by the fact that root isolation is about nowhere addressed, though it is an essential aspect of the question: without root isolation, you just can't get started. $\endgroup$ – Yves Daoust Jan 8 '16 at 11:05
3
$\begingroup$

Contrary to common opinion, there is no established numerical method to find the roots of closed-form functions.

There are indeed several excellent methods for root refinement, among which the secant/regula falsi (without derivatives) and Newton (with derivatives), that converge super-linearly.

Anyway we are pretty deprived as regards root isolation (finding intervals where a single root is guaranteed) and even more root exhaustion (finding all the roots).

For example, it would be hard to determine the number of roots of the equation below, though this number is finite:

$$ \frac{x^2}{2+x}+\cos(x+1)=x^2\sin\left(\frac{\sqrt x}{x^2}\right)+\cos(1)-0.83x. $$

About all you can do is sampling the function densely enough, but there is no guarantee of success. You can't really spare an analytical insight into the function.

enter image description here

Update:

I found this reference which describes an interesting approach to automatic root isolation:

Root isolation using function values, Bush Jones, W. G. Waller & Arnold Feldman, BIT Numerical Mathematics, September 1978, Volume 18, Issue 3, pp 311-319.

It is base on a statistical estimation of the probability to have a zero in an interval.

$\endgroup$
12
  • $\begingroup$ Nice example! .. $\endgroup$ – KittyL Jan 6 '16 at 14:58
  • $\begingroup$ @KittyL: just inspired by the OP's equation :) $\endgroup$ – Yves Daoust Jan 6 '16 at 15:08
  • $\begingroup$ In the case of holomorphic functions, it may be worth noting that it is possible to estimate the amount of roots (and poles) lie in a region, though this requires a rather large amount of evaluations... probably not worth it compared to what you've mentioned, at least for real roots. $\endgroup$ – Simply Beautiful Art Aug 28 '20 at 20:18
  • $\begingroup$ @SimplyBeautifulArt: can you name the method ? $\endgroup$ – Yves Daoust Aug 31 '20 at 7:52
  • 1
    $\begingroup$ One such method using "complex bisection for polynomials" is the Lehmer–Schur algorithm. $\endgroup$ – Simply Beautiful Art Sep 23 '20 at 3:44

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.