An (Asymptotic) Error Bound for the Evaluation of Polynomials at Roots

Manfred Göbel ()
Additional contact information
Manfred Göbel: University of Essex, Department of Electronic Systems Engineering

A chapter in Computer Algebra in Scientific Computing, 2000, pp 183-190 from Springer

Abstract: Abstract Given is a univariate polynomial $$F(X) = {X^n} - {\sigma _1}{X^{n - 1}} + \ldots + {( - 1)^{n - 1}}{\sigma _{n - 1}}X + {( - 1)^n}{\sigma _n} \in \left[ X \right]$$ and a “poor” numerical solution α1, ‖ , αn ∈ ℂ of F(X) = 0 such that 1 ≤ ∣αi - x i∣ ≤ δ ∈ ℝ and F(x i) = 0 for 1 ≤ i ≤ n. We show that $$O\left( {{2^{n - 1}}n! \cdot {\delta ^{{\textstyle{{n(n - 1)} \over 2}}}}} \right)$$ is an (asymptotic) error bound for the evaluation of an arbitrary but fixed multivariate polynomial f ∈ ℂ[x 1,...,x n ] at the n-tuple (α1,...,αn) instead of the n-tuple of the roots (x 1,...,x n ),and that for some polynomials the (asymptotic) error bound is Ω Keywords. Analysis of algorithms, data structures, rewriting techniques, evaluation of polynomials, roots, error bounds $$\Omega \left( {n! \cdot {\delta ^{{\textstyle{{n(n - 1)} \over 2}}}}} \right)$$ .

Date: 2000
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-57201-2_15

Ordering information: This item can be ordered from
http://www.springer.com/9783642572012

DOI: 10.1007/978-3-642-57201-2_15

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().