# Efficient computation of the trajectory of roots of a parameterized polynomial

Let $N(s)$ and $D(s)$ be two polynomials in $s \in \mathbb C$ of degrees $m$ and $n$, respectively, with $m<n$. Consider the polynomial equation $$P(s) = N(s) + kD(s) = 0,$$ where $k > 0$.

For a given $k$, let $R_k$ be the set of roots of $P(s)$: $$R_k = \{ r_i \in \mathbb C | P(r_i)=0, i = 1,\ldots,n \}$$

Assume for some $k^\prime$, I have already computed $R_{k^\prime}$.

Is there a numerically efficient method to compute the set of roots $R_{k^{\prime\prime}}$ for an adjacent value $k^{\prime\prime}$ of $k^\prime$?

Or, less specifically, given a perturbation $\delta = |k^{\prime\prime} - k^{\prime}|$, is there a way to compute the maximum change in the location of the roots if it is possible to pair the roots in $R_{k^{\prime\prime}}$ with those in $R_{k^{\prime}}$?

-
Sounds like a homotopy problem... – J. M. Dec 22 '11 at 6:13

The roots satisfy a differential equation. If $r = r(k)$ is a root, differentiate $N(r(k)) + k D(r(k)) = 0$ wrt $k$ to get $$\frac{dr}{dk} = - \frac{D(r)}{N'(r) + k D'(r)}$$ when the denominator is nonzero. Note that the denominator is $0$ if and only if $r(k)$ is a multiple root of $N(s) + k D(s)$. Numerical differential equation solvers can be used. As long as you don't run into a multiple root (which happens when two or more roots collide) this should work very well.

-
Wouldn't this only work for real roots. Are there numerical differential equation solvers for complex variables? – Kavka Dec 23 '11 at 16:06
Maple's dsolve(..., numeric), for example, works for complex variables. If you needed to use a solver that didn't handle complex variables, you could separate the real and imaginary parts, giving a system of two real DE's. – Robert Israel Dec 23 '11 at 20:45

You can get a Taylor expansion for $s(k)$ by differentiating the equation with respect to $k$:

$$N+kD=0$$

$$\left(N'+kD'\right)\dot s+D=0$$

$$\left(N'+kD'\right)\ddot s+\left(N''+kD''\right)\dot s^2+2D'\dot s=0$$

and so on, where dots and primes denote differentiation with respect to $k$ and $s$, respectively. Each equation only contains one new unknown derivative, so you can solve for them one after the other. You can use this to get approximations to the roots for nearby $k$, and perhaps also to bound the change in $s$.

-