Если корни сильно разной величины, x₁≫x₂≫x₃≫…, то k-й элементарный симметрический многчлен неотличим от произведения k самых больших иксов, так что любой корень — это примерно отношение соседних коэффициентов многочлена.
Если числа изначально разные по модулю, то чтобы их «раздвинуть» достаточно возвести все их в большую степень. Если P(x) многочлен, то P(√x) конечно не многочлен… зато P(√x)P(-√x) — вполне себе многочлен, а его корни суть квадраты корней исходного. После нескольких таких итераций корни становятся достаточно различными, чтобы работала идея из предыдущего абзаца.
Такой способ предлагал Лобачевский (впрочем до него видимо Данделен), а мне про это рассказал коллега Бахарев.
На коленке реализовал это так:
def absroots(poly,N=5):
poly, d = np.array(poly,dtype=np.float64), len(poly)-1
signs = np.ones(d+1)
signs[1::2] *= -1
for _ in range(N):
poly *= 1/poly[-1]
poly = np.convolve(poly,poly*signs)[::2]
return np.array([(-poly[k]/poly[k+1])**(1/(2**N))
for k in range(d)])
— и действительно работает… но близко к корням (модулям корней) так не подойдешь (точность растет медлено, а потом вообще происходит катастрофа). Вроде есть какие-то модификации, которые улучшают ситуацию.
Впрочем, уже грубая оценка для всех корней видимо полезна — метод Ньютона, наоборот, сходится очень быстро, но если начинать итерации рядом с корнем (и действительно, пара итераций Лобачевского + пара итераций Ньютона для каких-то многочленов у меня работает прекрасно).
// Ранее здесь про метод Ньютона: https://t.me/compmathweekly/27 (и далее по ссылкам)