A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

11

This is a root-finding problem for an analytic function over a single dimension. One standard technique is to approximate $F(k)$ as a polynomial $F(k) \approx c_0 + c_1 k + c_2 k^2 + \cdots$ using a Chebyshev approximation, and to compute the roots of the polynomial semi-analytically, e.g. by setting up the companion matrix and computing its eigenvalues. (...

10

According to Wolfram Alpha, $x^5+3(x-1)=0$ has no closed-form solution, so you can forget about a nice closed-form expression. :) I see nothing wrong with Newton's method; it should be quick and accurate, and with some analysis like the one you are sketching I think you can identify a safe starting point and prove global convergence. It might even be faster ...

8

I will complement @Richard Zhang 's answer (+1) with a python implementation of his suggested approach. The MATLAB package Chebfun has been partially ported in python. Actually there are two versions available: chebpy and pychebfun. Here's an implementation of the root finding procedure with pychebfun (the approach is similar with chebpy) from scipy....

5

Here is a simple (Matlab) Newton method as a first attempt to help get started. It finds 1087 roots with error below $10^{-11}$. f = @(x) ((2*x)./(x.^2-1)) - tan(x); fp = @(x)-tan(x).^2+2.0./(x.^2-1.0)-x.^2.*1.0./(x.^2-1.0).^2.*4.0-1.0; x0 = 0; for jj = 1 : 1200 %number of iterations to find some roots x0 = x0 + (jj-1)*(jj/10^4); %take previous ...

5

As the other Answer already touches on the possibility of a symbolic root-solver being applied to this particular equation (by transforming into a polynomial form, albeit of degree $\ge 5$), I'll make some remarks about numerical root-finding. When we want to find real roots of a continuous function, the Intermediate Value Theorem is a basic tool. On a ...

5

Complementing the answers, I would like to say that directly discretizing the differential equation might work really well. I used that approach in a previous question. I used Finite Differences and used an eigensolver to find the roots. That, besides a perturbation analysis followed by Newton's method. The suggestion there was to use Chebyshev ...

4

In terms of computational effort, it is useless. I mean, you are still having a nonlinear problem with a bigger Jacobian (which is the worst part to be computed quickly). For next thoughts: dense problems are always worse that sparse ones. Try to solve a sparse system and compare it with the time needed to solve a dense one. Convergence does depend on the ...

4

You can rewrite with integer exponents through a change of variable. This looks like $d=x^r$ where $r$ is the LCM of the denominator of the rationalized exponents. In your case we have $r=4$ and: $$6.72427 - 0.125568 x^4 + 2.51327 x^{13}=0$$ Which can be solved in the usual ways. In Mathematica there is a clear distinction between symbolic and numerical ...

4

This is a classical problem in numerical methods research: evaluating the zeros of special functions. Many years of research have gone into devising efficient methods. The canonical starting point for anything related to this is the classic book by Abramowicz and Stegun. Scanned versions of the book can easily be found on the internet (I'm not sure if these ...

3

You have demonstrated that the polynomial has only a single positive root (I assume here that you are only interested in positive real roots). Using Cauchy's upper bound for polynomial roots $$1+ \max\left\{\left|\frac{a_{n-1}}{a_{n}}\right|, \left|\frac{a_{n-2}}{a_{n}}\right|, \ldots, \left|\frac{a_{0}}{a_{n}}\right|\right\}$$ you can obtain an upper bound ...

3

As this is a transcendent equation, finding all roots is not an option. You cannot (in general) find an expression that gives a closed-form for the roots of the equation. So you need to do some analysis first. Plotting the function, or plotting the left-hand-side and right-hand-side of the equation (and hence, the intersections of both curves are the roots) ...

2

You can at least take a quick look at the zeros using gnuplot by plotting contours at zero of the equation $$0 = \frac{2x}{x^2-1} - \tan(x)$$ set terminal png set output "test.png" set xlabel "x" set ylabel "y" set contour set cntrparam levels discrete 0 set view map unset surface set isosamples 1000,1000 splot 2*x/(x**2-1) - tan(x) Since the equation ...

2

If you look at the full output of your script, sol has fields ipvt and qtf. Both of these fields come from MINPACK (http://www.netlib.org/minpack/lmdif.f), which is the backend here (https://github.com/scipy/scipy/blob/2526df72e5d4ca8bad6e2f4b3cbdfbc33e805865/scipy/optimize/_root.py#L246; https://docs.scipy.org/doc/scipy-0.19.0/reference/generated/scipy....

2

Any reasonable convergence criterion must be invariant to scaling of the function. A decent stopping criterion is therefore if $\|f(x_k)\|≤ \epsilon\|f(x_0)\|$ where $x_0$ is the starting point of the iteration. It's slightly annoying that the stopping criterion now depends on the starting point, but because Newton's iteration converges so quickly close to ...

2

It looks like the eigenvalues depend smoothly on your $r$ parameter. Since the problem seems to be easy to solve for small values of $r$, you can compute the eigenvalues for a set of radii $r_1,r_2,r_3$, and then extrapolate each of these eigenvalues using a quadratic function to some $r^\ast>r_3$. This extrapolation should then be an excellent starting ...

1

Assuming it is not too expensive to evaluate the function, I would recommend using the chebfun toolbox (matlab), as shown here: https://www.chebfun.org/docs/guide/guide03.html It builds an approximation of the function using Chebyshev polynomials and then finds the polynomial’s roots using a highly efficient root finder. It will find all roots in one fell ...

1

This is a technique called continuation. It typically works by using Newton's method to find one root, then you take steps along the root curve by picking a nearby point as the initial guess for the next Newton step. This is usually done to solve problems of the form $$F_\lambda(x_ \lambda)=0$$ where $\lambda$ is some parameter, but your problem can be ...

1

One of the most basic techniques in numerical analysis, when solving a complicated problem, is to construct an approximately-similar easy problem, solve that to obtain an approximate solution, and restart the process using that solution as a new starting point. This is a very general technique, and it’s not even restricted to root finding methods. Newton’s ...

Only top voted, non community-wiki answers of a minimum length are eligible