Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}}$?

share|improve this question
    
Sounds like a homotopy problem... –  J. M. Dec 22 '11 at 6:13
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.