On the stability of computing polynomial roots via confederate linearizations
<p style="text-align:justify;"> A common way of computing the roots of a polynomial is to find the eigenvalues of a linearization, such as the companion (when the polynomial is expressed in the monomial basis), colleague (Chebyshev basis) or comrade matrix (general orthogonal polyn...
| Main Authors: | , |
|---|---|
| Formato: | Journal article |
| Idioma: | English |
| Publicado: |
American Mathematical Society
2015
|
| _version_ | 1826257363534872576 |
|---|---|
| author | Nakatsukasa, Y Noferini, V |
| author_facet | Nakatsukasa, Y Noferini, V |
| author_sort | Nakatsukasa, Y |
| collection | OXFORD |
| description | <p style="text-align:justify;"> A common way of computing the roots of a polynomial is to find the eigenvalues of a linearization, such as the companion (when the polynomial is expressed in the monomial basis), colleague (Chebyshev basis) or comrade matrix (general orthogonal polynomial basis). For the monomial case, many studies exist on the stability of linearization-based rootfinding algorithms. By contrast, little seems to be known for other polynomial bases. This paper studies the stability of algorithms that compute the roots via linearization in nonmonomial bases, and has three goals. First we prove normwise stability when the polynomial is properly scaled and the QZ algorithm (as opposed to the more commonly used QR algorithm) is applied to a comrade pencil associated with a Jacobi orthogonal polynomial. Second, we extend a result by Arnold that leads to a first-order expansion of the backward error when the eigenvalues are computed via QR, which shows that the method can be unstable. Based on the analysis we suggest how to choose between QR and QZ. Finally, we focus on the special case of the Chebyshev basis and finding real roots of a general function on an interval, and discuss how to compute accurate roots. The main message is that to guarantee backward stability QZ applied to a properly scaled pencil is necessary. </p> |
| first_indexed | 2024-03-06T18:17:01Z |
| format | Journal article |
| id | oxford-uuid:04f4a2f0-eef0-498f-a247-a41eb0fb55b3 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:17:01Z |
| publishDate | 2015 |
| publisher | American Mathematical Society |
| record_format | dspace |
| spelling | oxford-uuid:04f4a2f0-eef0-498f-a247-a41eb0fb55b32022-03-26T08:54:34ZOn the stability of computing polynomial roots via confederate linearizationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:04f4a2f0-eef0-498f-a247-a41eb0fb55b3EnglishSymplectic Elements at OxfordAmerican Mathematical Society2015Nakatsukasa, YNoferini, V <p style="text-align:justify;"> A common way of computing the roots of a polynomial is to find the eigenvalues of a linearization, such as the companion (when the polynomial is expressed in the monomial basis), colleague (Chebyshev basis) or comrade matrix (general orthogonal polynomial basis). For the monomial case, many studies exist on the stability of linearization-based rootfinding algorithms. By contrast, little seems to be known for other polynomial bases. This paper studies the stability of algorithms that compute the roots via linearization in nonmonomial bases, and has three goals. First we prove normwise stability when the polynomial is properly scaled and the QZ algorithm (as opposed to the more commonly used QR algorithm) is applied to a comrade pencil associated with a Jacobi orthogonal polynomial. Second, we extend a result by Arnold that leads to a first-order expansion of the backward error when the eigenvalues are computed via QR, which shows that the method can be unstable. Based on the analysis we suggest how to choose between QR and QZ. Finally, we focus on the special case of the Chebyshev basis and finding real roots of a general function on an interval, and discuss how to compute accurate roots. The main message is that to guarantee backward stability QZ applied to a properly scaled pencil is necessary. </p> |
| spellingShingle | Nakatsukasa, Y Noferini, V On the stability of computing polynomial roots via confederate linearizations |
| title | On the stability of computing polynomial roots via confederate linearizations |
| title_full | On the stability of computing polynomial roots via confederate linearizations |
| title_fullStr | On the stability of computing polynomial roots via confederate linearizations |
| title_full_unstemmed | On the stability of computing polynomial roots via confederate linearizations |
| title_short | On the stability of computing polynomial roots via confederate linearizations |
| title_sort | on the stability of computing polynomial roots via confederate linearizations |
| work_keys_str_mv | AT nakatsukasay onthestabilityofcomputingpolynomialrootsviaconfederatelinearizations AT noferiniv onthestabilityofcomputingpolynomialrootsviaconfederatelinearizations |