Methods used inside "roots" and "solve" functions to solve polynomial equations.

I am wondering to know which mathematical methods is used inside the Matlab "roots" and "solve" functions to solve for polynomial equations. I read their descriptions and there are no references to methods or papers used to build these functions.

Answer 1

[Torsten]

For numerial computation of polynomial roots, see

https://math.mit.edu/~edelman/publications/polynomial_roots.pdf

https://de.mathworks.com/content/dam/mathworks/tag-team/Objects/r/72931_92035v00Cleve_Roots_Polynomials_Spr_1991.pdf

For symbolic computation of polynomial roots, see the analytical formula for polynomials up to degree 4.

In short: numerically, the roots of a polynomial are computed as the eigenvalues of the companion matrix.

[Mahrad Sharifvaghefi]

Many thanks for your response. Just to clarify, you mean both roots and solve functions using the eigenvalues of the companion matrix to compute the roots of a polynomial or only the root function use this.

[Torsten]

I don't see that "solve" gives a solution for polynomials of degree >= 5. You will have to use "root" or "vpasolve" instead (which most probably use the same method as "roots", namely the eigenvalue solution).

For degree <= 4, there exist analytical solutions, and specifying "MaxDegree" in the "solve" command will activate these formulae, I guess.

syms x
r = solve(x^5 + 6*x^4 + 7*x^3 -15*x^2-6*x+20==0,x)

r = 

r = solve(6*x^4 + 7*x^3 -15*x^2-6*x+20==0,x)

r = 

r = solve(6*x^4 + 7*x^3 -15*x^2-6*x+20==0,x,"MaxDegree",4)

r = 

[Mahrad Sharifvaghefi]

I see. Many thanks. So the difference between the solutions given by "solve" vs "roots" in the example below should be related to numerical accuracy rather than difference in methods.

syms f(x)

f(x) = (x-20)*(x-19)*(x-18)*(x-17)*(x-16)*(x-15)*(x-14)*(x-13)*(x-12)*(x-11)*...
    (x-10)*(x-9)*(x-8)*(x-7)*(x-6)*(x-5)*(x-4)*(x-3)*(x-2)*(x-1);
fs = collect(f);
c = double(coeffs(fs,'All'));

tic
roots(c)

ans = 20×1

19.9998 19.0019 17.9909 17.0254 15.9463 15.0755 13.9148 13.0743 11.9533 11.0250

toc

Elapsed time is 0.242319 seconds.

tic
double(solve(fs,x))

ans = 20×1

1 2 3 4 5 6 7 8 9 10

toc

Elapsed time is 0.309659 seconds.

[Torsten]

Yes, by the choice of symbolic arithmetic, I guess.