Roots of Polynomials: on twisted QR methods for companion matrices and pencils

Simple item page
dc.contributor.authorAurentz, Jared L.
dc.contributor.authorMach, Thomas
dc.contributor.authorRobol, Leonardo
dc.contributor.authorVandebril, Raf
dc.contributor.authorWatkins, David S.
dc.date.accessioned2017-01-09T05:13:22Z
dc.date.available2017-01-09T05:13:22Z
dc.date.issued2016-11-08
dc.description.abstractTwo generalizations of the companion QR algorithm by J.L. Aurentz, T. Mach, R. Vandebril, and D.S. Watkins, SIAM Journal on Matrix Analysis and Applications, 36(3): 942--973, 2015, to compute the roots of a polynomial are presented. First, we will show how the fast and backward stable QR algorithm for companion matrices can be generalized to a QZ algorithm for companion pencils. Companion pencils admit a greater flexibility in scaling the polynomial and distributing the matrix coefficients over both matrices in the pencil. This allows for an enhanced stability for polynomials with largely varying coefficients. Second, we will generalize the pencil approach further to a twisted QZ algorithm. Whereas in the classical QZ case Krylov spaces govern the convergence, the convergence of the twisted case is determined by a rational Krylov space. A backward error analysis to map the error back to the original pencil and to the polynomial coefficients shows that in both cases the error scales quadratically with the input. An extensive set of numerical experiments supports the theoretical backward error, confirms the numerical stability and shows that the computing time depends quadratically on the problem size.ru_RU
dc.identifier.citationAurentz, J. L., Mach, T., Robol, L., Vandebril, R., & Watkins, D. S. (2016). Roots of Polynomials: on twisted QR methods for companion matrices and pencils. arXiv, 1611(02435).ru_RU
dc.identifier.urihttp://nur.nu.edu.kz/handle/123456789/2214
dc.language.isoenru_RU
dc.publisherarXivru_RU
dc.rightsAttribution-NonCommercial-ShareAlike 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-sa/3.0/us/*
dc.subjectpolynomial rootfindingru_RU
dc.subjectcompanion matrixru_RU
dc.subjectcompanion pencilru_RU
dc.subjecteigenvalueru_RU
dc.subjectQR algorithmru_RU
dc.subjectQZ algorithmru_RU
dc.subjectrotatorsru_RU
dc.subjectcore transformationru_RU
dc.subjectbackward stabilityru_RU
dc.subjectRootru_RU
dc.subjectAMS subject classification: 65F15, 65H17, 15A18, 65H04ru_RU
dc.titleRoots of Polynomials: on twisted QR methods for companion matrices and pencilsru_RU
dc.typeArticleru_RU

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Jared L. Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril, David S. Watkins.pdf
Size:
81.62 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
6.22 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Articles