Day 12: Roots of polynomial

Let’s say we want to find roots of the polynomial, e.g. x⁵+x⁴+x³+x²+x+1.

While there’s no analytical solution for higher order polynomials, numerical solution is just an application of linear algebra. All we need is to construct a matrix whose characteristic polynomial is the one we are solving.

To get the roots we then find eigenvalues of the matrix.

algorithm

https://github.com/coells/100days

def roots(*coeffs):
matrix = np.eye(len(coeffs) - 1, k=-1)
matrix[:,-1] = np.array(coeffs[:0:-1]) / -coeffs[0]
return np.linalg.eigvals(matrix)

test

> roots(1, 1, 1, 1, 1, 1) # x^5 + x^4 + x^3 + x^2 + x + 1 = 0
array([0.5+0.8660254j,
0.5-0.8660254j,
-1.0+0.j,
-0.5+0.8660254j,
-0.5-0.8660254j])
Show your support

Clapping shows how much you appreciated Tomáš Bouda’s story.