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}}$?
 A: 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$.
A: 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. 
