Continuity of polynomial roots

It was recently brought up how to show that the n roots of a real or complex polynomial depend continuously on the polynomial’s coefficients. Although I have used this proposition numerous times, implicitly and explicitly, I realized that I never saw a proof of it.

Perhaps the most obvious approach would try to apply the Implicit Function Theorem but, as you may know or can easily check, such an attempt would only work for roots that are simple. Indeed, the very failure of the Implicit Function Theorem in case of non-simple roots is one of the subjects studied in local bifurcation theory. For an example, see this discussion of the Bogdanov-Takens bifurcation.

Returning to the original proposition, here is an elementary proof using only the Fundamental Theorem of Algebra and some simple estimates.


Let \mathbb{P}_n be the set of all polynomials of degree at most n \in \NN with complex coefficients. For any p \in \mathbb{P}_n let [p] be the coordinate vector of p with respect to the standard basis \{1, z, \ldots, z^n\}. If \|\cdot\|_{\infty} is the maximum norm on \CC^{n+1} then

    \[ \|p\| := \|[p]\|_{\infty} \]

turns \mathbb{P}_n into a normed space. For p, q \in \mathbb{P}_n with [p] = [a_0,\ldots,a_n] and [q] = [b_0,\ldots,b_n] their pointwise difference satisfies

(1)   \begin{equation*} \begin{aligned} |p(z) - q(z)| &= |(a_0 - b_0) + (a_1 - b_1)z + \ldots + (a_n - b_n)z^n|\\ &\le M_{z,n} \|[p] - [q]\|_{\infty}\\ &= M_{z,n} \|p - q\| \end{aligned} \end{equation*}

for all z \in \CC, where M_{z,n} := (n+1)(1 + |z|^n). Define P_n \subseteq \mathbb{P}_n as the open subset of complex polynomials of degree precisely n and let \mathcal{F} be the collection of non-empty, compact subsets of \CC^n. When endowed with the Hausdorff metric d_{\mathrm{H}} this collection becomes a metric space. Define T : P_n \to \mathcal{F} to be the map that assigns to p \in P_n its (non-empty and finite) set of roots. In these terms we have

(2)   \begin{equation*} d_{\mathrm{H}}(T(p), T(q)) = \max\left\{\max_{\lambda \in T(p)}{d(\lambda, T(q))}, \max_{\mu \in T(q)}{d(\mu, T(p))} \right\} \end{equation*}

where d(\lambda, T(q)) and d(\mu, T(p)) are the usual point-set distances in the complex plane from \lambda to T(q) and \mu to T(p), respectively.

Estimating the first term in (2)

We show that T is continuous at any point p \in P_n. Let \EPS > 0 be given. The two terms appearing inside the braces in (2) will be estimated separately. By the Fundamental Theorem of Algebra every q \in P_n with leading coefficient b_n decomposes as

    \[ q(z) = b_n(z - \mu_1)\cdot\ldots\cdot(z - \mu_n) \]

where \mu_1,\ldots,\mu_n are the roots of q, repeated according to multiplicity. So, when \lambda \in T(p) it follows that

(3)   \begin{equation*} |b_n| \prod_{k=1}^n{|\lambda - \mu_k|} = |p(\lambda) - q(\lambda)| \le M_{\lambda,n} \|p - q\| \end{equation*}

where the inequality is due to (1). Now,

    \[ \left||a_n| - |b_n|\right| \le |a_n - b_n| \le \|p - q\| \]

so |b_n| \ge |a_n| - \|p - q\| and therefore (3) implies that

(4)   \begin{equation*} \prod_{k=1}^n{|\lambda - \mu_k|} \le M_{\lambda,n} \frac{\|p - q\|}{|a_n| - \|p - q\|} \end{equation*}

Hence there exists \eta_{\lambda} > 0 such that \|p - q\| \le \eta_{\lambda} implies that the left-hand side of (4) does not exceed \EPS^n and thus |\lambda - \mu_k| \le \EPS for at least one 1 \le k \le n. Consequently,

    \[ d(\lambda, T(q)) \le |\lambda - \mu_k| \le \EPS  \]

whenever \|p - q\| \le \eta_{\lambda}. We set \eta := \min_{\lambda \in T(p)}{\eta_{\lambda}} > 0. This takes care of the first term inside the braces in (2).

Bounding the roots by the coefficients

Suppose \mu is a root of q \in P_n with coordinate vector [b_0,\ldots,b_n]. Since q(\mu) = 0 it is immediate that

    \begin{align*} |b_n| \cdot |\mu|^n &\le |b_0| + |b_1|\cdot|\mu| + \ldots + |b_{n-1}|\cdot|\mu|^{n-1}\\ &\le n \|q\| \cdot |\mu|^{n-1} \end{align*}

provided that we assume |\mu| \ge 1. This yields the bound

(5)   \begin{equation*} |\mu| \le 1 + n|b_n^{-1}|\cdot\|q\| \qquad \forall\,\mu \in T(q) \end{equation*}

of the roots of a polynomial in terms of its coefficients.

Estimating the second term in (2)

Applying the Fundamental Theorem of Algebra once more, we write

    \[ p(z) = a_n(z - \lambda_1)\cdot\ldots\cdot(z - \lambda_n) \]

where this time \lambda_1,\ldots,\lambda_n are the roots of p. Let q \in P_n and let \mu \in T(q). Then

(6)   \begin{equation*} \prod_{k=1}^n{|\mu - \lambda_k|} \le M_{\mu,n}\frac{\|p - q\|}{|a_n|} \end{equation*}

By (5) the coefficient M_{\mu,n} is bounded on every sufficiently small ball in P_n centered at p. Hence there exists \theta > 0 such that \|p - q\| \le \theta implies that the left-hand side of (6) does not exceed \EPS^n and therefore |\mu - \lambda_k| \le \EPS for at least one 1 \le k \le n. It follows that

    \[ d(\mu, T(p)) \le |\mu - \lambda_k| \le \EPS \]

provided \|p - q\| \le \theta.

We finish by puting \delta := \min\{\eta, \theta\} > 0. Then (2) shows that d_{\mathrm{H}}(p, q) \le \EPS whenever \|p - q\| \le \delta.

Update (October 2016): I thank S.A. van Gils for pointing out to me that the coefficient M_{z,n} that first appears in (1) was missing a multiplicative factor n + 1. Similarly, the second term in the right-hand side of (5) was missing a factor n. Both mistakes have been corrected. The argument remains otherwise unchanged.