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.

Preliminaries

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

\begin{align}
|p(z) – q(z)| &= |(a_0 – b_0) + (a_1 – b_1)z + \ldots + (a_n – b_n)z^n| \nonumber\\
&\le M_{z,n} \|[p] – [q]\|_{\infty} \nonumber\\
&= M_{z,n} \|p – q\| \label{eq:pointwise}
\end{align}

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

\label{eq:dh}
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\}

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 \eqref{eq:dh}

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 \eqref{eq:dh} 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

\label{eq:prod}
|b_n| \prod_{k=1}^n{|\lambda – \mu_k|} = |p(\lambda) – q(\lambda)| \le M_{\lambda,n} \|p – q\|

where the inequality is due to \eqref{eq:pointwise}. 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 \eqref{eq:prod} implies that

\label{eq:prodest}
\prod_{k=1}^n{|\lambda – \mu_k|} \le M_{\lambda,n} \frac{\|p – q\|}{|a_n| – \|p – q\|}

Hence there exists $\eta_{\lambda} > 0$ such that $\|p – q\| \le \eta_{\lambda}$ implies that the left-hand side of \eqref{eq:prodest} 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 \eqref{eq:dh}.

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

\label{eq:rootbnd}
|\mu| \le 1 + n|b_n^{-1}|\cdot\|q\| \qquad \forall\,\mu \in T(q)

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

Estimating the second term in \eqref{eq:dh}

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

\label{eq:prodest02}
\prod_{k=1}^n{|\mu – \lambda_k|} \le M_{\mu,n}\frac{\|p – q\|}{|a_n|}

By \eqref{eq:rootbnd} 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 \eqref{eq:prodest02} 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 \eqref{eq:dh} shows that $d_{\mathrm{H}}(p, q) \le \EPS$ whenever $\|p – q\| \le \delta$.

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

Update (December 2018): I thank J.C.A. Barata (São Paulo, Brazil) for using this proof in his online course book and letting me know about it. He also pointed out a typo of mine in the process. (Indeed, the elements of $\mathcal{F}$ are subsets of $\CC$, not of $\CC^n$.)