Questions tagged [rootfinding]
Algorithms to approximate numerically a root of a nonlinear equation or system: for instance, Newton's method, secant method, bisection, etc.
36 questions
15 votes
1 answer
686 views
The most efficient algorithm for finding a root of a polynomial over finite field
I have a polynomial of degree around $2^{35}$ over a finite field $\mathbb{F}_p$, where $p$ is a 64-bit prime number. What is the most efficient algorithm for finding a root of such a polynomial? (...
- 151
2 votes
1 answer
159 views
Finding closed form roots for pseudo-trinomial
I have the below function: $$\pi(x) = \frac{s_0\cdot \left(1-\left(\frac{s_1}{s_1+x \cdot \lambda}\right)^{k}\right) \cdot r_1}{s_0\cdot \left(1-\left(\frac{s_1}{s_1+x \cdot \lambda}\right)^{k}\right) ...
- 21
3 votes
1 answer
363 views
Root finding algorithm for an analytic function
Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of ...
- 81
1 vote
0 answers
174 views
Complexity of calculating the expectation of $\operatorname{Tr} h(A)$, $A$ is a random matrix
$A$ is a $d_1\times d_1$ random matrix. Given $\{g_i\}~(1\leq i\leq n)$ iid Gaussian variables, $f_{ij}(g_1,g_2,...,g_n)~(1\leq i,j\leq d_1)$ are degree-$d_2$ polynomials. And $f_{ij}\equiv f_{ji}~(\...
- 91
3 votes
0 answers
219 views
Number of positive roots for an exponential sum
Given $n\geq 3$ distinct constants $c_1, c_2, ..., c_n \in\mathbb{C}$, I want to bound/estimate the number of positive real roots for the equation $$f(x):=\sum_{i=1}^{n}\dfrac{c_i^n}{\prod_{j\neq i}(...
- 1,538
0 votes
0 answers
75 views
Educated guess for algebraic approximation
I found a very neat ancient hindi formula for approximating square roots using rational numbers. After doing some algebra on the formula, i came across with this recursive relation: Given any number $...
2 votes
1 answer
105 views
Uniqueness of a solution to an equation
Let $t \in [0,1]$ or $t \in (0,1)$ be distributed according to $F(t)$. Now consider the following equation: \begin{equation} \frac{\int_{\underline{t}}^{\overline{t}}(\gamma-t(2\gamma-1))dF(t)}{\int_{...
- 23
0 votes
1 answer
313 views
Roots of linear combination of $x \sin x$
Let $\theta=(\theta_1,\theta_2,\cdots \theta_n)$, and $a_{ij}$ are constants. There is no condition on the positiveness of $a_{ij}$. Under which condition on $\theta$, such that the following function ...
- 405
7 votes
3 answers
597 views
Rigorous estimates on roots of function
We consider the function $$f(x) = 1- \frac{1}{N} \sum_{i=1}^N \frac{\sin\left(\tfrac{\pi i}{N}\right)^2}{1+\sin\left(\tfrac{\pi i}{2N}\right)^2-x}.$$ The arguments of the two sines differ by a factor ...
3 votes
0 answers
96 views
how to efficiently find level sets (using a modification of a root-finding algorithm)?
I'm trying to find a set of points $\{ a_i | f(a_i) = c_i \}_{i=1}^k$ where $f$ and $\{ c_i \}_{i=1}^k$ are given in sorted order. All $c_i > 0$, $f$ is continuous and monotonically increasing, $f(...
- 131
1 vote
1 answer
298 views
Closed form roots for polynomial $x^9 + ax^6 + bx^5 + cx^3 + d = 0$
I know about Abel–Ruffini theorem, but I have a polynomial of special form. From "Beyond the Quartic Equation" by R.B. King (a very interesting book, btw) I've learned about Tschirnhaus ...
- 365
2 votes
1 answer
225 views
How to solve for $a$ in $\sum_{j=i}^n (a -j) \binom{n}{j} y^j (1-y)^{n-j} = 0$
The Problem Given $i, n, y$, I am trying to find a closed form solution for $a$ in the equation $$ \sum_{j=i}^n (a -j) \binom{n}{j} y^j (1-y)^{n-j} = 0 $$ Do you have any recommendations on how to ...
- 23
1 vote
0 answers
111 views
Newton-Raphson and bisection for solving for a system of nonlinear equations?
We know that for a single equation root-finding, we can use the Newton's method, or a combination of Newton with bisection to guarantee convergence. Can we use Newton+bisection for a system of ...
- 11
2 votes
1 answer
507 views
Square root of prime numbers
I found that the square root of any prime number S can be approximated, at the n-th order, as a rational number represented by the polynomials shown below. $x_0$ is an initial seed, which is a ...
0 votes
1 answer
222 views
Calculating derivatives of arbitrary-order at an operator's root
Consider roots $f = 0$ of a nicely-behaved real function $f(x, t)$ of two (real) variables. Namely, points $(x, t)$ on which $f$ vanishes, $f(x, t) = 0$. Suppose that $x$ can be written as function of ...
- 623
0 votes
1 answer
230 views
Are root finding algorithms stable for bounded polynomials? [closed]
Suppose that we have a bounded polynomial defined on $[0,1]$. I think because it is just polynomial, root finding algorithms would easily and without any instability find all its roots. Am I right? ...
- 113
6 votes
1 answer
1k views
Solution to sixth order equation
I'm dealing with the expression $x = \frac{1}{3}y(y+1)(2y+1)^2(2y^2+2y+1)$. What is this approximately, if one is explicitly writing y in terms of x? There's no general formula for sixth powers ...
- 1,205
1 vote
0 answers
223 views
Is it possible in principle (but not in practice) to recursively factor away the Riemann zeta zeros as they are computed?
Let: $$f_0(x)=\frac{\zeta (x)}{\sin \left(\frac{\pi x}{2}\right)}$$ and let the seed point be: $$s=\sqrt{-1}$$ which is the input into the limit: $$\rho_1=s+\lim\limits_{n \rightarrow \infty}\left(1-\...
- 1,203
-2 votes
1 answer
174 views
How many positive roots can $\sum_{i}\frac{a_i}{x+b_i}$ have where $b_i$'s are all positive? [closed]
What is the maximum number of positive roots $\sum_{i}^N\frac{a_i}{x+b_i}$ can have where $b_i$'s are all positive? (everything here is a real number. To provide context, I encountered this problem ...
- 451
-1 votes
1 answer
191 views
Searching the roots of a self-consistent transcendental equation
I have the equation $$M = c_1 + c_2M - c_3T\ln\left(\left|\frac{e^{(c_4M + c_5)/T}-1}{e^{(c_6M + c_5)/T}-1}\right|\right)$$ where $c_1, \dots, c_6$ are constants. I am interested in the roots of $$M\...
1 vote
0 answers
39 views
Using Regula-Falsi to determine the solution to a non-linear system [closed]
Apologies, for this isn't a field or subject I know much about. Regula Falsi (I believe some may know this as "double false position" or something like this) can be used trivially, of course,...
- 111
0 votes
0 answers
59 views
Solving nonlinear equations involving expectations
Let $X$ be a random variable and $g(x,y)$ be a function of two variables. Consider the equation $$ \mathbb{E}_Xg(X,y) = 0 $$ Are there any specialized techniques for solving such equations (...
- 11
2 votes
0 answers
252 views
Could analytically deriving the next non-trivial zero of $\zeta(s)$ be made rigorous up to a fixed accuracy?
In this question., a very inefficient, yet rigorous analytic approach for finding the next prime was established. I wondered whether a similar approach could exist to find the next non-trivial zero ($\...
- 4,189
2 votes
0 answers
256 views
A question in regards to finding the roots of numbers
A simple algorithm for finding the square root of any integer goes as the following: example $√25$: $25 - 1 -3 - 5 - 7 - 9 = 0$ We have deducted 5 numbers (-1, -3, -5, -7, -9) without resulting in a ...
- 55
5 votes
0 answers
255 views
Are the ordinates of the non-trivial zeros of $\zeta(s)$ uniformly distributed around the mid points of Gram point intervals they can be mapped to?
Let $\rho_n$ be the $n$-th non-trivial zero of $\zeta(s)$ and $z_n = \Im(\rho_n)$ with $z_n > 0$ and $z_{n+1} \ge z_n$. A well known method to establish that all $\rho$s reside on the critical line ...
- 4,189
1 vote
0 answers
415 views
How to solve a system of quadratic equations?
Suppose we have a system of $p$ quadratic equations about $\mathbf{x} \in \mathbb{R}^3$ and $\mathbf{x} > 0$ $$ \left\{ \begin{array}{lr} \mathbf{x}^\top \mathbf{C}_1 \mathbf{x} = 1, ...
- 19
1 vote
1 answer
488 views
When does this limiting ratio give a real root $x$ to the equation of the form $\sum\limits_{k=0}^d \frac{x^k a_{k+1}}{k!}=0$?
By searching the Inverse Symbolic Calculator, we appear to be able to make the following conjecture about a real root to the equation: $$\sum\limits_{k=0}^d \frac{x^k a_{k+1}}{k!}=0 \tag{1}$$ Let the ...
- 1,203
1 vote
0 answers
71 views
On a structural decomposition of polynomials based on integral roots
Given an irreducible polynomial of structure $$f(x,y)=\sum_{\substack{i,j\in\{0,1,2\}\\i+j\leq3}}a_{i, j}x^iy^j\in\mathbb Z[x,y]$$ with $a_{2,1}a_{1,2}a_{1,1}a_{1,0}a_{0,1}a_{0,0}\neq0$ if $f(m,n)=0$ ...
- 1,846
4 votes
0 answers
182 views
Finding roots of this polynomial
I have a polynomial, given for parameters $x$ in $\mathbb{R}_+$ and $\alpha$ and $\beta$ in $\mathbb{R}_+^{n}$ by : $$P(t) = \sum\limits_{i=1}^n \left\{\left(\beta_i - \frac{\alpha_i}{x} - t\right) ...
- 696
0 votes
1 answer
307 views
Zeros of partial sums of the Ramanujan's zeta function
In this post we consider the Ramanujan tau function $\tau(n)$, see the Wikipedia Ramanujan tau function, and we consider partial sums of its corresponding Dirichlet series (see for example the article ...
3 votes
0 answers
88 views
Sign of an integer polynomial at a real algebraic number
Given $p\in\mathbb{Z}[x]$, assumed to have a real root, let $r$ be the largest real root of $p$. Now, given $f\in\mathbb{Z}[x]$ (without loss, of lesser degree than $p$), I would like to find out ...
- 481
2 votes
0 answers
38 views
Isolating Real Roots of Polynomial–Exponential Function over Algebraic Numbers
Let $\mathbb{A}$ be the set of algebraic numbers and $\mathbb{A}[t]$ the set of polynomials in $t$ with coefficients in $\mathbb{A}$. Given a finite sum of $F(t)=\sum_{k}f_k(t) e^{\eta_k t}$ for ...
- 21
1 vote
4 answers
547 views
how to solve $\sum_{i=0}^n (x-\mu_i)e^{-(x-\mu_i)^2} = 0$ [closed]
I’d like to solve following equation for $x.$ If it is not possible, why I can’t? $$\sum_{i=0}^n (x-\mu_i)e^{-(x-\mu_i)^2} = 0$$
- 19
3 votes
1 answer
579 views
root solving without analytic derivative
I have two related questions about numerical methods for root solving: 1) $f: R \to R$ is continuous and piece-wise smooth, with $f(a)f(b) < 0$. $f$ has very high number of knot-points and ...
- 33
2 votes
3 answers
4k views
Fast root finding for strictly decreasing function
What is a fast algorithm to find the root of a strictly decreasing function? If the root is not exact I want to find a root such that the function value is positive to an error.
- 121
3 votes
0 answers
2k views
Multi-variate secant method for solving $F(x)=0$
The secant method for solving an equation $F(x)=0$ in one variable is much older than Newton's one. Recall that given two iterates $x_{k-1}$ and $x_k$, it provides an update $x_k$ by taking the ...
- 53.1k