ISSN:
1436-5057
Keywords:
Primary 65G05
;
secondary 65F
;
Horner's scheme
;
rounding error analysis
;
linear error equations
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung In dieser Arbeit entwickeln wir eine Vorwärts-Fehleranalyse für das vollständige verallgemeinerte Hornerschema eines Polynoms $$p = \sum {a_j X^{n - j} } $$ an den Stellenz 1, ...,z n . Dieser Fehleranalyse liegt die Linearisierungsmethode zugrunde, deren wesentliche Hilfsmittel Systeme linearer Fehlergleichungen und zugehöriger Konditionszahlen sind, welche optimale Schranken für die Fehler liefern, die bei Datenstörungen und dem Rechnen in Gleitkommaarithmetik entstehen können. Für das Hornerschema lassen sich diese Konditionszahlen auf einfache Weise rekursiv berechnen. Das gewöhnliche vollständige Hornerschema ist gekennzeichnet durchz=z 1=...=z n . Im Gegensatz zu den für diesen Fall bisher bekannten Fehlerabschätzungen für das Polynomp and der Stellez unterscheiden sich unsere optimalen Schranken von denen für das Polynom $$p_a = \sum {\left| {a_j } \right|X^{n - j} } $$ an der Stelle |z| und berücksichtigen so das sich teilweise Aufheben von Termen. Eine Reihe von numerischen Beispielen veranschaulicht die erhaltenen Fehlerschranken.
Notes:
Abstract In this paper we establish a forward error analysis of the generalized complete Horner scheme for a polynomial $$p = \sum {a_j X^{n - j} } $$ with pivotal pointsz 1, ...,z n . The error analysis is based on the linearization method whose fundamental tools are systems of linear error equations and associated condition numbers which yield optimal bounds of the possible errors under data perturbations and rounding errors in floating point arithmetic. For Horner's scheme the bounds may be calculated by simple recurrences. The ordinary complete Horner scheme is characterized byz=z 1=...=z n . In contrast to the hitherto known error estimates for this special case our new optimal bounds for the polynomialp atz differ from those for the polynomial $$p_a = \sum {\left| {a_j } \right|X^{n - j} } $$ at |z| and thus take into account the possible partial cancellation of terms. The error estimates are illustrated by a series of numerical examples.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02242136
Permalink
