ENH: Add companion matrix functions.

The new companion matrices are related to the old by a
similarity transformation that makes them better conditioned
for root finding. In particular, the companion matrices for
the orthogonal polynomials are symmetric when the zeros of a
single polynomial term is wanted. This produces better zeros
for use in Gauss quadrature.

1 files changed, 45 insertions, 13 deletions

diff --git a/numpy/polynomial/hermite.py b/numpy/polynomial/hermite.py
index fadd866ee..5babfb7b1 100644
--- a/numpy/polynomial/hermite.py
+++ b/numpy/polynomial/hermite.py
@@ -1411,6 +1411,47 @@ def hermfit(x, y, deg, rcond=None, full=False, w=None):
         return c
 
 
+def hermcompanion(cs):
+    """Return the scaled companion matrix of cs.
+
+    The basis polynomials are scaled so that the companion matrix is
+    symmetric when `cs` represents a single Hermite polynomial. This
+    provides better eigenvalue estimates than the unscaled case and in the
+    single polynomial case the eigenvalues are guaranteed to be real if
+    `numpy.linalg.eigvalsh` is used to obtain them.
+
+    Parameters
+    ----------
+    cs : array_like
+        1-d array of Legendre series coefficients ordered from low to high
+        degree.
+
+    Returns
+    -------
+    mat : ndarray
+        Scaled companion matrix of dimensions (deg, deg).
+
+    """
+    accprod = np.multiply.accumulate
+    # cs is a trimmed copy
+    [cs] = pu.as_series([cs])
+    if len(cs) < 2:
+        raise ValueError('Series must have maximum degree of at least 1.')
+    if len(cs) == 2:
+        return np.array(-.5*cs[0]/cs[1])
+
+    n = len(cs) - 1
+    mat = np.zeros((n, n), dtype=cs.dtype)
+    scl = np.hstack((1., np.sqrt(2.*np.arange(1,n))))
+    scl = np.multiply.accumulate(scl)
+    top = mat.reshape(-1)[1::n+1]
+    bot = mat.reshape(-1)[n::n+1]
+    top[...] = np.sqrt(.5*np.arange(1,n))
+    bot[...] = top
+    mat[:,-1] -= (cs[:-1]/cs[-1])*(scl/scl[-1])*.5
+    return mat
+
+
 def hermroots(cs):
     """
     Compute the roots of a Hermite series.
@@ -1460,19 +1501,10 @@ def hermroots(cs):
     if len(cs) == 2 :
         return np.array([-.5*cs[0]/cs[1]])
 
-    n = len(cs) - 1
-    cs /= cs[-1]
-    cmat = np.zeros((n,n), dtype=cs.dtype)
-    cmat[1, 0] = .5
-    for i in range(1, n):
-        cmat[i - 1, i] = i
-        if i != n - 1:
-            cmat[i + 1, i] = .5
-        else:
-            cmat[:, i] -= cs[:-1]*.5
-    roots = la.eigvals(cmat)
-    roots.sort()
-    return roots
+    m = hermcompanion(cs)
+    r = la.eigvals(m)
+    r.sort()
+    return r
 
 
 #