Questions tagged [rootfinding]

For questions about the theory and process of finding the roots of a function (values where the function returns zero).

Filter by
Sorted by
Tagged with
1 vote
2 answers
66 views

Why is the definition of convergence different for root finding algorithms as compared to sequences?

The definition of convergence for root finding algorithms is given in a few sources as: A sequence ${x^k}$ generated by a numerical method is said to converge to the root $\alpha$ with order $p\geq 1$ ...
Username_57's user avatar
1 vote
1 answer
138 views

Python libraries for larges scale optimization/rootfinding

I have been dealing with the standard libraries of scipy.optimize for rootfinding and optimization problems, but the problems i want to solve are very large, which makes the standard solvers run out ...
Klaus3's user avatar
  • 133
2 votes
0 answers
100 views

Scipy.root not converging even when provided with initial guesses very close to solution

I've made a previous question here and also in SO wondering why only the fsolve solver converges for the simple one dimensional unsteady conduction problem $$ \frac{\partial T}{\partial t} = \alpha \...
Klaus3's user avatar
  • 133
0 votes
2 answers
320 views

Why is this scipy.root code not converging?

I'm running a test problem to set up larger problems. Solving the simple unsteady heat equation via finite differences: $$ \frac{\partial T}{\partial t} = \alpha \frac{\partial^2T}{\partial x^2}$$ $\...
Klaus3's user avatar
  • 133
7 votes
1 answer
352 views

Computing powers of diagonal + rank-1 matrix?

I'm using a numeric root-finder to find $k$ satisfying $\|A^k x\|=c$ where $A$ is a symmetric $d\times d$ diagonal + rank-1 matrix. How to compute $A^k x$ efficiently? For integer $k$, I can get the ...
Yaroslav Bulatov's user avatar
3 votes
1 answer
68 views

Dynamic tolerance in a conditional loop to obtain maximum precision allowed by machine floating point numbers

I have coded a simple program for a root finding problem using Halley's method. Here is the code: ...
Hosein Javanmardi's user avatar
4 votes
1 answer
116 views

Summation of trigonometric functions results in error with finite precision

Consider the following expression: $$f(t) = B+\sum_{k=1}^{N} A_k\cos(\omega_kt)$$ where $A$ and $B$ are known. the frequencies are also known but are not multiples of a fundamental frequency. However, ...
Hosein Javanmardi's user avatar
0 votes
3 answers
254 views

finding all zeros of a continuous function

Let $f: \Bbb R \to \Bbb R$ be continuous. What are efficient algorithms to finding all the zeros in an interval $[a, b]$? I am actually only interested in the smallest zero in that interval, if there'...
Joe Shmo's user avatar
  • 121
3 votes
0 answers
124 views

Splitting system of equations into linear and nonlinear part and solving separately

I was working on a problem recently (calculating all flows in a network given input and output flows, basically what Hardy-Cross tries to achieve) which can be formulated as a well-determined system ...
nardi's user avatar
  • 131
1 vote
2 answers
127 views

Secant Method for finding $\sup f^{-1}(0)$

Let $f \in C^0[0, 1]$, and suppose $f \ge 0$. How can I compute $\sup f^{-1}(0)$ efficiently?
Joe Shmo's user avatar
  • 121
2 votes
1 answer
335 views

2nd order differential equation coupled to integro-differential equation in python

I'm trying to solve the following equations numerically in python $$\begin{align} 12\pi\int_0^\infty drf(r)\phi(r)r^4&=E\\ f(r)-\frac{1}{2\mu}\bigg(\frac{d^2\phi(r)}{dr^2}+\frac{2}{r}\frac{d\phi(r)...
mmikkelsen's user avatar
5 votes
1 answer
325 views

Complexity of recovering all roots of a polynomial

Given a polynomial of degree n and a list of putative roots $\{r_i\}_{i=1}^{n}$, we can verify that all the putative roots are indeed correct by $n$ applications of Horner's method. Hence verifying ...
user14717's user avatar
  • 2,145
0 votes
0 answers
44 views

Expected residual at double root

In a generic rootfinding problem $f(x) = 0$, we assume that the probability that the root $x$ is a floating point representable is zero. Hence, the best floating point approximation $\hat{x}$ to $x$ ...
user14717's user avatar
  • 2,145
1 vote
0 answers
41 views

Solving the non-linear Hamiltonian using Scipy's root finding method

I am a complete novice to computational physics and am finding difficulty in implementing a code to iteratively solve for a $2\times2$ nonlinear Hamiltonian using Scipy's root solver. I can't seem to ...
hello_world30's user avatar
3 votes
0 answers
75 views

Sufficient condition for real roots of a polynomial of order $n>5$ with arbitrary real coefficients

I ask for help in solving the problem. I am developing an optimization program that selects the coefficients of a polynomial of order $n> 5$ so that all its zeros are just real numbers. And I ...
dtn's user avatar
  • 131
2 votes
0 answers
105 views

Solve Rational Equation for Root Music in MATLAB

I'm trying to estimate DOA in the Hybrid architecture using root music so I need to solve the attached equation to find the roots for the Root_Music equation in Matlab. Does anyone have an idea for ...
Mona's user avatar
  • 31
1 vote
0 answers
82 views

Solving general initial value problem $\mathbf{f}(\mathbf{x}, \mathbf{x'}, t)=\mathbf{0}$

The common form of initial value problem that can be solved using ODE integrator is $$ \mathbf{x'}=\mathbf{g}(\mathbf{x}, t) $$ where $\mathbf{x'}=\partial\mathbf{x}/\partial t$. The initial ...
Firman's user avatar
  • 181
4 votes
0 answers
51 views

Pass forward intermediate results during iterative optimization

To investigate a counter-current flow heat exchanger while considering temperature dependent physical properties (such as specific heat $c_\textrm{p,i}$, heat conductivity $\lambda_\textrm{i}$, ...
albert's user avatar
  • 223
3 votes
1 answer
115 views

Calculating the Jacobian for a function containing a derivative

I have the equation $F(t) = \phi u + \frac{1}{2}\frac{d^2u}{dt^2} + u^3$ and broadly speaking, my task is to calculate the $\phi$ and $u(t)$ such that $F(t) = 0$. I am testing out a new algorithm to ...
Paddy's user avatar
  • 131
1 vote
1 answer
2k views

What is the use of arrayfun if a for loop is faster?

This may not be so much of a scientific computing question but more of a MATLAB question, if that is the case, please feel free to close or migrate the question. Root-finding problems are commonly ...
Abdullah Ali Sivas's user avatar
2 votes
0 answers
243 views

Providing Jacobian as LinearOperator in scipy.optimize.root

I asked this question a few days ago on stackoverflow, but I figure scicomp.stackexchange is probably a better place. Sorry for the double post. I want to solve a system of nonlinear equations using ...
G. Fougeron's user avatar
3 votes
1 answer
322 views

Nonlinear root solving libraries which accept a Jacobian in band-storage

I'm in search for a library for solving large systems of non-linear equations, similar to MINPACK, but unlike MINPACK, can accept a Jacobian in band-storage. My Jacobian is sometimes not invertible, ...
nicholaswogan's user avatar
0 votes
1 answer
2k views

Solve non-linear equation in R

I need to solve the following equation for $x$ in [0, 1]. Assume $0<\alpha<1$ and $0<\lambda$. $$(1 - x)^{\alpha+1} - \lambda (x+1)^{\alpha+1} = -2\lambda (\alpha + 1) x^\alpha$$ Would very ...
camibc's user avatar
  • 1
1 vote
1 answer
167 views

Help understanding Brent's root finding method

Help me understand a part of Brent's root finding algorithm. In a typical iteration we have samples (a,fa), (b,fb), (c,fc) all real with (a<b<c) or (c<b<a) . Also, in the case I am ...
Ted Ersek's user avatar
  • 111
2 votes
1 answer
223 views

Rootfinding algorithm that takes advantage of automatic differentiation

Is there any algorithm (or tricks) for rootfinding to take advantages of automatic differentiation (AD)? Rootfinding algorithms typically solve $$ \mathbf{f}(\mathbf{y}) = \mathbf{0} $$ where $\mathbf{...
Firman's user avatar
  • 181
1 vote
2 answers
140 views

Coding up a toy model for gradient-descent -- what step size to choose?

I'm coding up a simple model for gradient-descent, and using it to minimize some simple, deterministic functions. What step size could I choose that's simple enough for me to get started with? Should ...
user37083's user avatar
0 votes
1 answer
196 views

Coding up Newton's method for a mapping from R^2 to R -- the Jacobian wouldn't be invertible

I'm trying to code up in Matlab a multivariable Newton's method, for a mapping from R^2 to R, but the Jacobian would be a 2x1 matrix, not square, so it wouldn't be invertible. Does this mean that ...
user37077's user avatar
0 votes
0 answers
38 views

How to describe function convergence and function tolerance for numerical root-finding?

I'm currently doing some practice problems on root-finding and am writing up some notes / comments on my code. In my solver code, if my function value is below the tolerance that I've set, should I ...
user37069's user avatar
1 vote
0 answers
113 views

How can I practice multivariable root-finding?

Recently, I've been reading up on various root-finding / optimization algorithms such as the Levenberg-Marquardt method, Gauss-Newton, Conjugate Gradient, trust-region and trust-region-dogleg. I've ...
user37050's user avatar
0 votes
1 answer
181 views

Interpreting multivariable root-finding results from Matlab's fsolve algorithm

Edit: So I was able to get the same value of r that's given, when coding up the sum of squares of function values directly in the script file, rather than on the Command Window. So, maybe there's a ...
user36973's user avatar
1 vote
1 answer
76 views

Algorithm to determine if a polynomial has any complex roots

Is there a simple algorithm to determine if a given polynomial (with all real coefficients) has all real roots? I do not need to know what the roots are; I just what to know if a given polynomial has ...
physics_researcher's user avatar
0 votes
1 answer
61 views

Fixed-point iteration when image and domain are not the same

I have a function $f(x)$ defined on a domain $D$, but such that the image $f(D)$ may contain extra regions not included in its domain. I am interested in solving the fixed-point equation $x=f(x)$. If ...
a06e's user avatar
  • 1,729
5 votes
0 answers
355 views

Polynomial rooting - fast root finding

I need to solve a rooting problem of a polynomial (the order of which is 2(N-1), where N=48). So far I'm using Python Numpy algorithm (that relies on computing the eigenvalues of the companion matrix)...
Luca R's user avatar
  • 61
7 votes
1 answer
101 views

Fast computation of the zeros of a trigonometric polynomial

I am wondering what is the fastest way to compute the zeroes of the trigonometric polynomial $$ T(x) = \sum_{i=1}^La_i\sin\big(2\pi(a_i x) - \phi_i \big), \\ a_i \in \mathbb{N}, \\ \phi_i \in \left[-\...
Arrigo's user avatar
  • 301
3 votes
2 answers
682 views

What is an efficient way to calculate zeros of Bessel functions?

One approach is the brute force method of evaluating at all points at fixed intervals and when it nears zero write value, this can be combined with adaptive step size. Another approach is ...
Manas Dogra's user avatar
2 votes
2 answers
115 views

ODE Event detection for calculating multiple roots of continuous sinusoidal equation

I found a paper [1] that has a method for computing rise and set times of a satellite given a closed form solution. It is a complicated sinusoidal function and the paper has a method to calculate a ...
S moran's user avatar
  • 141
2 votes
1 answer
253 views

How to avoid gsl root finder evaluate function outside its domain

When I use the newton's method or hybrid solver in the GSL package to deal with 1-D or multidimensional root solving problems, the code frequently crashes when the solver requests function value ...
HD189733b's user avatar
  • 121
3 votes
1 answer
124 views

Robust ways to find zeros of the Tricomi confluent hypergeometric function as a function of its parameters

I'm solving a quantum mechanical problem, and the quantization condition requires me to solve the equation $$ U\left(\frac12(\ell+1-E), \ell+1, r^2\right) = 0, $$ where $U(a,b,z)$ is the confluent ...
Emilio Pisanty's user avatar
1 vote
1 answer
259 views

Finding curves where function goes to zero in two dimensions

Suppose $f(x,y)$ is a complex function of two real arguments with roots* that are not discrete points but lie in curves. (Is there are term for this characteristic?) An example is shown below: the ...
Fab von Bellingshausen's user avatar
6 votes
2 answers
142 views

Positive root of $x^q + bx - b$

Is there either a closed-form expression or fast/elegant algorithm for computing the positive root of the polynomial $$f(x)=x^q + \beta x - \beta,$$ where $\beta>0$ and $q\geq2$? How about the $q\...
Justin Solomon's user avatar
2 votes
0 answers
41 views

Piecewise-linear Continuations vs Marching Squares/Cubes

It seems that both piecewise-linear continuation and marching squares are methods to produce iso-contours of a scalar function given the function's values on a grid. It seems that piecwise-linear ...
Gus's user avatar
  • 251
6 votes
1 answer
888 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 ...
user14717's user avatar
  • 2,145
1 vote
1 answer
456 views

Root finding using Newton's method with quadratic interpolation - Is there a mistake in this textbook?

I've been trying to learn about root finding using Newton's method, which uses a quadratic interpolating polynomial. I found this text, Numerical methods for roots of polynomials, PART 2: McNamee &...
qwerty_uiop's user avatar
1 vote
1 answer
291 views

Muller's method is the same as Newton's method with a quadratic interpolating polynomial?

I'm new to numerical analysis, and have been learning root finding algorithms. I am a bit confused about the difference between Muller's method, and Newton's method using an n-degree interpolating ...
qwerty_uiop's user avatar
7 votes
3 answers
2k views

Finding the first N roots of transcendental equation

I need to find the first $n$ roots of the transcendental equation \begin{equation} F(k) = J_m'(kr)Y_m'(k)-J'_m(k)Y'_m(kr) \end{equation} for integer values of $m$ and any $r \in [0,1)$ where $J'$ ...
Dipole's user avatar
  • 873
1 vote
0 answers
467 views

Levenberg-Marquardt for root-finding: just square the function?

This question might be so obvious and trivial that I'm having a hard time googling it. I have a multivariate root finding problem that I'm trying to solve in C# and the library that I'm trying to use ...
lamont's user avatar
  • 133
5 votes
1 answer
157 views

Can redundant variables be beneficial for root-finding convergence

Suppose I have $n$ generally nonlinear equations for $n$ variables, like e.g. for $n=2$ the system $F(x,y)=0$ $$ \begin{aligned} x^2+2y-4&=0\\ \sqrt{8}x+y^2-5&=0 \end{aligned} $$ By ...
oliver's user avatar
  • 103
1 vote
2 answers
175 views

How does Mathematica compute real and complex solutions to single, non-polynomial equations?

This question on StackOverflow has led me to ask myself what would be involved in solving an equation like this one using tools available to the Python programmer. $$ \frac{0.125567841}{d^{2.25}} = \...
Bill Bell's user avatar
  • 185
5 votes
0 answers
301 views

Roots of transcendental equation involving bessel functions

I need an efficient way to numerically find the first $n$ positive roots $\lambda_n$ of the transcendental equation $$ \dfrac{J_0 (\lambda_n r) Y_1 (\lambda_n) - J_1 (\lambda_n) Y_0 (\lambda_n r)}{...
Luis Costa's user avatar
4 votes
3 answers
4k views

How to solve the transcendental equation: $\tan(x) = \frac{2x}{x^2-1}$

I'm interested in finding the roots of the following equation: $\tan(x) = \frac{2x}{x^2-1}$. It is easily seen that 0 is a root and the roots are symmetric w.r.t. 0. I wonder if an analytical ...
booksee's user avatar
  • 143