3
$\begingroup$

Let $N(s)$ and $D(s)$ be two polynomials in $s \in \mathbb C$ of degrees $m$ and $n$, respectively, with $m. 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}}$?

  • 0
    Sounds like a homotopy problem...2011-12-22

2 Answers 2

3

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.

  • 0
    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.2011-12-23
3

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$.