Numerical Solution of an Equation with Multiple Roots

583 Views Asked by At

Let me consider an equation $f(x)=0$ which I know to have a solution $x=x_0$, but I need to find its another solution. So I might consider finding root for the equation $$\frac{f(x)}{x-x_0}=0$$ but I do not have any idea where it's root can be. So it is difficult to apply Newton-Raphson method to get the other solution. But is there an efficient method that does the job? Thank you.

EDIT: A sample function is the following: $$f(x)=\sum_{ij}p_{ij}\left(1-e^{-\alpha_{ij}x}\right)$$ where $p_{ij},\alpha_{ij}\ge 0,\ 1\le i,j\le N,\ \sum_{ij}p_{ij}=1,\ $ Note that $x=0$ is a solution to $f(x)=0$ and I need to find another solution of this function if it exists (Though this is a bad example).

1

There are 1 best solutions below

0
On BEST ANSWER

If you have to compute a root for changing parameters, you could use a homotopy continuation method, assume that the function is $f(p,x)=0$ and for $p_0$ the solution $x_0$ is known, then to go to a different parameter set $p_1$ you consider the family of equations $f((1-t)p_0+tp_1,x(t))=0$. If the step from $t$ to $t+\Delta t$ is small enough, the solution $x(t)$ will be a good initial point for $x(t+Δt)$. From two or more previous solutions you might get better starting points via polynomial extrapolation.

However, the solution curve you follow could have fold points or other singularities before reaching the end point at $t=1$. For this case and for the solution of an initial problem you still need a global search strategy. There it depends on the structure of the function, there might be a sensible homotopy to an easily solvable problem.

Making a table of function values over some region might provide an interval with a sign change (apply bisection or better to refine, Newton for the highest accuracy). Or you could perform 3 to 5 Newton steps at each sample point to test if there is a solution close-by. Or do the same with random points in that region. Use the function values obtained this way also to look for sign changes.

Even for polynomials where you can reliably estimate how large and small the roots can be, one still needs about $2d^2$ test point for degree $d$ to reliably find all of the roots via Newtons method, see http://link.springer.com/article/10.1007/s002220100149 or the homepage of the last author.