Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25990
Titel: Real root isolation for exact and approximate polynomials using descartes' rule of signs
Verfasser: Eigenwillig, Arno
Sprache: Englisch
Erscheinungsjahr: 2008
SWD-Schlagwörter: Rechenzeit
Genauigkeit
Freie Schlagwörter: Descartes
Nullstellen
Bitstream
Bitstream-Descartes- Verfahren
real roots
Descartes method
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: Collins und Akritas (1976) have described the Descartes method for isolating the real roots of an integer polynomial in one variable. This method recursively subdivides an initial interval until Descartes' Rule of Signs indicates that all roots have been isolated. The partial converse of Descartes' Rule by Obreshkoff (1952) in conjunction with the bound of Mahler (1964) and Davenport (1985) leads us to an asymptotically almost tight bound for the resulting subdivision tree. It implies directly the best known complexity bounds for the equivalent forms of the Descartes method in the power basis (Collins/Akritas, 1976), the Bernstein basis (Lane/Riesenfeld, 1981) and the scaled Bernstein basis (Johnson, 1991), which are presented here in a unified fashion. Without losing correctness of the output, we modify the Descartes method such that it can handle bitstream coefficients, which can be approximated arbitrarily well but cannot be determined exactly. We analyze the computing time and precision requirements. The method described elsewhere by the author together with Kerber/Wolpert (2007) and Kerber (2008) to determine the arrangement of plane algebraic curves rests in an essential way on variants of the bitstream Descartes algorithm; we analyze a central part of it.
Collins und Akritas (1976) haben das Descartes-Verfahren zur Einschließung der reellen Nullstellen eines ganzzahligen Polynoms in einer Veränderlichen angegeben. Das Verfahren unterteilt rekursiv ein Ausgangsintervall, bis die Descartes'sche Vorzeichenregel anzeigt, dass alle Nullstellen getrennt worden sind. Die partielle Umkehrung der Descartes'schen Regel nach Obreschkoff (1952) in Verbindung mit der Schranke von Mahler (1964) und Davenport (1985) führt uns auf eine asymptotisch fast scharfe Schranke für den sich ergebenden Unterteilungsbaum. Daraus folgen direkt die besten bekannten Komplexitätsschranken für die äquivalenten Formen des Descartes-Verfahrens in der Monom-Basis (Collins/Akritas, 1976), der Bernstein-Basis (Lane/Riesenfeld, 1981) und der skalierten Bernstein-Basis (Johnson, 1991), die hier vereinheitlicht dargestellt werden. Ohne dass die Korrektheit der Ausgabe verloren geht, modifizieren wir das Descartes-Verfahren so, dass es mit "Bitstream"-Koeffizienten umgehen kann, die beliebig genau angenähert, aber nicht exakt bestimmt werden können. Wir analysieren die erforderliche Rechenzeit und Präzision. Das vom Verfasser mit Kerber/Wolpert (2007) und Kerber (2008) an anderer Stelle beschriebene Verfahren zur Bestimmung des Arrangements (der Schnittfigur) ebener algebraischer Kurven fußt wesentlich auf Varianten des Bitstream-Descartes-Verfahrens; wir analysieren einen zentralen Teil davon.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-32445
hdl:20.500.11880/26046
http://dx.doi.org/10.22028/D291-25990
Erstgutachter: Mehlhorn, Kurt
Tag der mündlichen Prüfung: 15-Mai-2008
SciDok-Publikation: 2-Aug-2010
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_8200_Eige_Arno_2008.pdf1,07 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.