Fast and backward stable computation of roots of polynomials

Simple item page
dc.contributor.authorAurentz, Jared L.
dc.contributor.authorMach, Thomas
dc.contributor.authorVandebril, Raf
dc.contributor.authorWatkins, David S.
dc.date.accessioned2017-01-09T07:33:23Z
dc.date.available2017-01-09T07:33:23Z
dc.date.issued2015
dc.description.abstractA stable algorithm to compute the roots of polynomials is presented. The roots are found by computing the eigenvalues of the associated companion matrix by Francis's implicitly shifted QR algorithm. A companion matrix is an upper Hessenberg matrix that is unitary-plus-rankone, that is, it is the sum of a unitary matrix and a rank-one matrix. These properties are preserved by iterations of Francis's algorithm, and it is these properties that are exploited here. The matrix is represented as a product of 3n - 1 Givens rotators plus the rank-one part, so only O(n) storage space is required. In fact, the information about the rank-one part is also encoded in the rotators, so it is not necessary to store the rank-one part explicitly. Francis's algorithm implemented on this representation requires only O(n) flops per iteration and thus O(n2) flops overall. The algorithm is described, normwise backward stability is proved, and an extensive set of numerical experiments is presented. The algorithm is shown to be about as accurate as the (slow) Francis QR algorithm applied to the companion matrix without exploiting the structure. It is faster than other fast methods that have been proposed, and its accuracy is comparable or better.ru_RU
dc.identifier.citationAurentz, J. L., Mach, T., Vandebril, R., & Watkins, D. S. (2015). Fast and backward stable computation of roots of polynomials. SIAM Journal on Matrix Analysis and Applications, 36(3), 942-973. DOI: 10.1137/140983434ru_RU
dc.identifier.urihttp://nur.nu.edu.kz/handle/123456789/2225
dc.language.isoenru_RU
dc.publisherSIAM Journal on Matrix Analysis and Applicationsru_RU
dc.rightsAttribution-NonCommercial-ShareAlike 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-sa/3.0/us/*
dc.subjectcompanion matrixru_RU
dc.subjecteigenvalueru_RU
dc.subjectpolynomialru_RU
dc.subjectQR algorithmru_RU
dc.subjectrootru_RU
dc.subjectrootfindingru_RU
dc.subjectrotatorsru_RU
dc.titleFast and backward stable computation of roots of polynomialsru_RU
dc.typeArticleru_RU

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Jared L. Aurentz, Thomas Mach, Raf Vandebril, David S. Watkins1.pdf
Size:
16.66 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