Polynomial zerofinding iterative matrix algorithms (Q1343560): Difference between revisions

By a polynomial zerofinding algorithm, the authors mean the following: given a polynomial of degree \(n\), \(p(z)= z^ n+ a_{n-1} z^{n- 1}+\cdots+ a_ 0\), \(a_ k\in\mathbb{C}\), \(k= 0,\dots, n-1\), in the complex variable \(z\in\mathbb{C}\), one is to find simultaneously, by some matrix method (like the QR algorithm), the \(n\) eigenvalues of the \(n\times n\) matrix \(A\) such that \(\text{det}(A- \lambda I)= (-1)^ n p(\lambda)\). In the introduction polynomial zerofinding algorithms are discussed. Newbery's method is completed to a method for the construction of a (complex) symmetric or nonsymmetric matrix with a given characteristic polynomial. Polynomials found in the literature are solved iteratively by one of Fiedler's methods with initial values supplied either by Schmeisser's method, or taken on a large circle or randomly in a region of the complex plane. Two determinental equations are solved by the QR algorithm. Fiedler's method used iteratively exhibits fast convergence to simple roots, even in the presence of multiple roots. If at some iteration step, the value of the iterates, which are converging to a multiple root, are averaged according to the Hall-Mathon procedure, then fast convergence is also attained for multiple roots.