11
votes
Finding the first N roots of transcendental equation
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 ...
- 2,505
10
votes
Positive root of $x^q + bx - b$
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 ...
- 12.6k
8
votes
Accepted
Finding the first N roots of transcendental equation
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 <...
- 741
8
votes
Fast computation of the zeros of a trigonometric polynomial
It all boils down to building a certain matrix from the polynomial coefficients and computing its eigenvalues. John Boyd did a lot of work in this area, these are some relevant papers:
Boyd, John P. "...
- 301
8
votes
Accepted
Computing powers of diagonal + rank-1 matrix?
This paper shows an algorithm to compute the eigendecomposition of symmetric diagonal-plus-rank-1 matrices in $O(d^2)$.
- 12.6k
6
votes
Accepted
Algorithm to find local minima of function which is unbounded from below
If the "basin of attraction" for the best local minimum occupies 1% of the volume of the bounding box, then the following strategy suffices:
Repeat a few hundred times: Pick a random ...
- 477
5
votes
What is an efficient way to calculate zeros of Bessel functions?
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 ...
- 56.8k
5
votes
Finding the first N roots of transcendental equation
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 ...
- 8,622
5
votes
Accepted
How to solve the transcendental equation: $\tan(x) = \frac{2x}{x^2-1}$
Here is a simple (Matlab) Newton method as a first attempt to help get started. It finds 1087 roots with error below $10^{-11}$.
...
- 607
5
votes
Accepted
Can redundant variables be beneficial for root-finding convergence
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 ...
- 1,668
5
votes
How does Mathematica compute real and complex solutions to single, non-polynomial equations?
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 ...
- 3,459
5
votes
Secant Method for finding $\sup f^{-1}(0)$
If you need a certified result, you can try interval methods such as the ones in https://github.com/JuliaIntervals/IntervalRootFinding.jl/ . They are at their best for (at least) piecewise ...
- 12.6k
5
votes
Why is the definition of convergence different for root finding algorithms as compared to sequences?
This is not the definition of convergence. It is the definition of the convergence rate -- that is, how fast the sequence converges to a limit.
In other words, the definition you quote can only be ...
- 56.8k
4
votes
Accepted
Complexity of recovering all roots of a polynomial
Evaluating a polynomial of degree $<n$ in $n$ points can be done in time $O(n\log n)$. This is called fast multipoint evaluation; see for instance von zur Gathen, Modern Computer Algebra, ch. 10.
- 12.6k
4
votes
Accepted
2nd order differential equation coupled to integro-differential equation in python
The next transformation step would see the system reformulated as a boundary value problem with the additional equations and conditions replacing the integral
$$
I'(r)=12πf(r)ϕ(r)r^4,~~I(0)=0,~~ I(\...
- 6,159
3
votes
Accepted
Coding up a toy model for gradient-descent -- what step size to choose?
Suppose you want to minimize
$$\Phi(x)=\frac{1}{2}||Ax-b||^2$$
The gradient is
$$\frac{\partial \Phi}{\partial x} = A^T(Ax-b)$$
The step size to guarantee convergence is
$$\alpha=||A^TA||^{-1}$$
Why? ...
- 725
3
votes
Positive root of $x^q + bx - b$
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\...
- 6,199
3
votes
ODE Event detection for calculating multiple roots of continuous sinusoidal equation
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 ...
- 1,091
3
votes
How to solve the transcendental equation: $\tan(x) = \frac{2x}{x^2-1}$
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 ...
- 6,199
3
votes
Calculating the Jacobian for a function containing a derivative
There are some unknowns in what you are doing but for simplicity, suppose we want to find $u(t)$ as discrete times $t_1, t_2, \cdots, t_n$. Let $\textbf{F} = [F(t_1), F(t_2), \cdots, F(t_n)]^T$ and $\...
- 4,338
3
votes
finding all zeros of a continuous function
The question is ill-formulated, in the sense that you will never be able to find the smallest zero for all continuous functions in $[a,b]$, unless you now something more, like for example some ...
- 436
3
votes
Accepted
finding all zeros of a continuous function
As others have pointed out, you cannot solve this problem in general for all continuous functions. But there are methods that work quite well in practice. One such method is to sample the function at ...
- 1,091
3
votes
Accepted
Dynamic tolerance in a conditional loop to obtain maximum precision allowed by machine floating point numbers
You are using the wrong measure for the achievable accuracy. $|x|\mu$ is in some way a lower bound for the error, the smallest increment that would give a different value, so that any smaller ...
- 6,159
3
votes
Why is this scipy.root code not converging?
My suggestion would be to use an ODE solver combined with the method of lines instead of trying to use a non-linear system solver.
Here's an example of what this might look like:
...
- 645
3
votes
Python libraries for larges scale optimization/rootfinding
PETSc is widely-used and highly performant library that has a wrapper in Python (https://petsc.org/release/), but I suspect that with the problems you are encountering in SciPy, simply swapping the ...
- 3,101
3
votes
Why is the definition of convergence different for root finding algorithms as compared to sequences?
I can't give a very informed answer on this topic, but I can help sort out whether such a sequence converges.
Let's denote $\epsilon_k = |x^k - \alpha|$ the error for simplicity. If $p=1$, we have
$\...
- 376
2
votes
How to solve the transcendental equation: $\tan(x) = \frac{2x}{x^2-1}$
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)$$
...
- 465
2
votes
Accepted
Confusion about determining the jacobian in a rootfinding algorithm
If you look at the full output of your script, sol has fields ipvt and qtf. Both of these ...
- 11.5k
Only top scored, non community-wiki answers of a minimum length are eligible