Questions tagged [roots]
The roots tag has no usage guidance.
1
vote
1answer
103 views
Find the roots of a complicated polynomial
For the polynomial
$$p(x) = (x-1)(x-2) \cdots (x-20) - 2^{-23}x^{19}\, ,$$
I tried to use fzero() in MATLAB, and I set the interval to be $[0.5,1.5]\cdots [19.5,...
2
votes
0answers
103 views
Efficient root finding algorithm for monotonic function
This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible.
I ...
7
votes
1answer
146 views
Defining a condition number and termination criteria for Newton's method
The condition number of function evaluation
$$
\mathrm{cond}(f,x) := \left| \frac{x f'(x)}{f(x)} \right|
$$
is infinite at a root of $f$. Hence it is useless for rescaling a tolerance which defines an ...
6
votes
0answers
92 views
Finding the smallest root of a function on $[0, \infty)$
I would like to find the smallest real root of a 1-D real-valued function $f(x)$ on the domain $x\in [0,\infty)$. In this problem, I can make the following guarantees on $f$:
$f$ does have a root at ...
2
votes
1answer
46 views
Test on a set of high degree polynomials whose coefficients in {-1,0,1}
I'm looking for the best way of implementing the following algorithm: consider the set of all polynomials with a high degree (say, degree 30) whose coefficients ranges from a given set of values (say, ...
1
vote
1answer
471 views
Confusion about determining the jacobian in a rootfinding algorithm
I have written some Python code to determine the numerical roots of the following non-linear equation:
$$f_m=\tan\lambda_m - \frac{\lambda_m}{1+a}$$
where $\lambda_m\gt0$ and $a\geq0$. The code is:
<...
0
votes
1answer
130 views
Obtaining extra output argument(s) from the objective function used by fsolve in MATLAB
I have a MATLAB code (see below) that employs 'fsolve' from the optimization toolbox for a root finding problem.
The bottleneck is that, within the objective function calculation, there is a ...
1
vote
0answers
75 views
vectorizing optimization or root finding [closed]
I need to find the roots of a function. I am currently using scipy.optimize.fsolve
...
1
vote
0answers
41 views
Calculating fixed point inside limit cycle
So I'm working with a rather complicated dynamical system. Instead of writing it all out. It's probably easier if you just clone my git repository.
...
1
vote
2answers
281 views
Dekker's method and fixed further border [closed]
Dekker's method and in its evolution Brent's method have as design goal to combine the certainty of a root, certified by function values of opposite sign in an increasingly smaller interval, of ...
1
vote
2answers
81 views
Iterative root finding of 2-dimensional system of non-linear equations with monotonicity properties
Let $f(x,y)$ and $g(x,y)$ be two $\mathbb{R}^2\rightarrow\mathbb{R}$ functions, both strictly increasing in both arguments. Assume that they are well-behaved functions (continuous, differentiable, etc....
2
votes
1answer
36 views
Finding common roots of two multivariate equations
I am trying to find points of a surface whose normal is parallel with the 3 dimensional axes (i.e. local maxima, minima and saddle points in x, y and z dimensions).
The function of the surface is ...
1
vote
1answer
169 views
Fastest method forfinding a solution to x*log(x)
more specifically, $C x \log_2(x)- K = 0$, where $C$ and $K$ are constants ($\log_2$ means log base 2).
I was solving a topcoder problem, SortEstimate, which requires us to solve the aforementioned ...
6
votes
1answer
128 views
Roots of a function for eigensystem
I want to find the roots for $\kappa$ for the equation
$$\sqrt{\alpha - 1} \cos{\left (\frac{\sqrt{2} \sqrt{\alpha - 1}}{2 \sqrt{\epsilon}} \right )} \cosh{\left (\frac{\sqrt{2} \sqrt{\alpha + 1}}{2 \...
1
vote
0answers
106 views
Difference between Brent's and Alefeld-Potra-Shi for root finding
I need to find the (unique) root of a nonlinear function $f(x)$, $x \in \mathbb{R}$.
For the record, $f(x)$ is the CDF of a probability density minus a constant $0 < p < 1$ (I am inverting the ...
4
votes
1answer
191 views
Efficient and stable computation of inverse CDF
What is the most efficient and numerically stable algorithm for computing the inverse CDF $F^{-1}(y)$ of a probability function, assuming that both the PDF $f(x)$ and the CDF $F(x)$ are known ...
8
votes
2answers
101 views
Bracketing a discontinuity in a step function
I have the function
$f(x) = \begin{cases}
0 \:\: (x < a) \\ 1/2 \:\: (x = a)\\ 1 \:\: (x > a)
\end{cases}$,
where $a$ is unknown. I can compute the function for any value of $x$, and seek to ...
1
vote
0answers
63 views
Finding the root of an equation
I have given $i_1$, $i_2$ and $\alpha$ which can be real or integer. How can I find the roots of:
$$
(i_1 + i_p )^{\alpha} - i_p^{\alpha} - (i_2 \cdot i_p^{\alpha-1}) = 0
$$
2
votes
1answer
144 views
solving for unknown inside an expectation
I have a an equation that need to find its root. The function is the following
$f(\theta) \equiv E[R(\theta;\eta)]=0$ for some unknown $\theta$ which is deterministic, while the expectation is taken ...
4
votes
1answer
130 views
Finding self-kissing points on a plane curve?
I have a curve in the complex plane given by
$$ f(t) = \sum_k r_k\exp(2\pi\mathrm{i}(t+\varphi_k)p_k). $$
Some of the parameters are specially chosen: $r_k>0$, $\sum_k r_k=1$, $p_k\in\mathbb{Z}$, $\...
3
votes
2answers
436 views
Bessel EVP and fzero
I am trying to solve the Eigenvalue problem
$$
x^2 y''+ x y' + x^2 y = \lambda^2 y\,,\quad x\in(0,1)\,,\quad
y(0)=0\,,\quad
y'(1)=y(1)
$$
The differential equation is the Bessel equation. The solution ...
4
votes
1answer
82 views
Evaluate sine of a polynomial root close to $\pi$
Consider the polynomial
$$ p(x) = -514-462 x+359 x^2+1129 x^3+165 x^4+490 x^5-418 x^6+497 x^7-227 x^8+60 x^9-10 x^{10}, $$
whose root $A\approx 3.14$ is very close to $\pi$:
$$|A-\pi|=2.0746\times 10^...
1
vote
0answers
39 views
Solving a nonlinear equation with a Markov process and RVs
Assume that we have the following equation and the following assumption. The scope is to solve for some particular variables expressed later.
Update
$$E_{t}\left[ b(A_{t+1})^{1-\gamma} *R_{t+1}^{-\...
2
votes
1answer
165 views
Testing 1D root-finding procedures for robustness
How can I test whether a given 1D root-finding procedure is robust? I know that there are data sets and resources online for different kinds of optimization, but I have yet to find anything with ...
4
votes
2answers
144 views
Non-linear root finding with positive definite Jacobian
I am dealing with a system of non-linear equations:
$$
f(\boldsymbol{x}) = \boldsymbol{y}, \;\;\; \boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^d.
$$
And I know that the Jacobian $J(\boldsymbol{x})$ ...
4
votes
0answers
552 views
Finding roots of systems of equations with a Jacobian that is singular everywhere
Given $a\in\mathbb{R}^{mn\times n}$, find a $C\in\mathbb{R}^{n}$, $x\in\mathbb{R}^{m\times n}$ such that
$$
0 = f_{k}(\boldsymbol{C}, \boldsymbol{x}):=\sum_{i=1}^{m} C_{i} \left(\prod_{j=1}^{n} a_{kj}^...
6
votes
2answers
185 views
Continuation procedure to solve for a 2D curve that satisfies f(x,y) = 0
I have some function of $R^2$, that must be numerically computed. For instance, I might be interested in a real-valued contour integral that begins from (x,y) = 0.
$$
f(x,y) = \Re\left[\int_0^{x + iy}...
7
votes
4answers
7k views
How to find more than one root of a polynomial?
This program finds the first root of the function f, defined in the code. There are 5 roots of this function. (x=1,2,3,4,5) I wish to find all of the roots in this program and print them to the screen....
9
votes
2answers
3k views
Find all the roots of a function in a given interval
I need to find all the roots of a scalar function in a given interval. The function may have discontinuities. The algorithm can have a precision of ε (e.g. it is ok if the algorithm doesn't find two ...
3
votes
1answer
766 views
Non-linear root finding when the Jacobian is almost singular
I'm trying to solve a system non linear-equations:
$$
\frac{\partial K(\mathbf{\lambda})}{\partial \lambda_i} - c_i = 0
$$
for $i = 1, \dots, 15$, using Newton's method:
$$
\lambda^{k + 1} = \lambda^k ...
10
votes
3answers
3k views
Solution of quartic equation
Is there a open C-implementation for the solution of quartic equations:
$$ax⁴+bx³+cx²+dx+e=0$$
I am thinking of an implementation of Ferrari's solution. On Wikipedia I read that the solution is ...
8
votes
5answers
356 views
Iterative solution to a nonlinear equation
I appologize in advance if this question is silly.
I need to compute the root of
\begin{equation}
u -f(u) =0
\end{equation}
Where $u$ is a real vector and $f(u)$ is a real-vector valued function.
...
6
votes
2answers
189 views
Is there a backward stable $\tilde{O}(n \log(1/\epsilon))$ algorithm to factor a complex polynomial?
Finding the roots of a complex polynomial is in general extremely numerically unstable, as discussed in (1). According to Pan ((2), (3)), this produces a cubic complexity lower bound, and he presents ...
