Trennkreisverfahren

Approximative Faktorisierung und deren Verbesserung

In der numerischen Anwendung können die Konturintegrale nicht exakt bestimmt werden. Jedoch kann die numerische Integration mit beliebiger Genauigkeit vorgenommen werden, indem eine genügend kleine Schrittweite gewählt wird. Die mittels der Newton-Identitäten bestimmten genäherten Faktoren seien mit F₀ (x) und G₀ (x) bezeichnet. Für eine schnelle Ausführung der numerischen Integration bietet es sich an, sich auf Kreise in der komplexen Ebene zu beschränken, da dann die numerische Integration, d.h. die Bestimmung der Werte der Polynome an den Stützstellen sowie die Bestimmung der Integrale aus den Werten der Quotienten, mit Hilfe der schnellen Fourier-Transformation ausgeführt werden kann.

Bei genügend hoher Genauigkeit der numerischen Integration werden die Koeffizienten des "Fehlerpolynoms" p(x) - F₀ (x) G₀ (x) beliebig klein sein. Ist dieser Fehler von der Größenordnung , so hat der Abstand der Nullstellen von p(x) zu den entsprechenden Nullstellen der Faktoren im ungünstigsten Fall die Größenordnung . Die numerische Integration muss so ausgeführt werden, dass mit den Nullstellen von p(x) auch die entsprechenden Nullstellen von F₀ (x) innerhalb von K und die von G₀ (x) außerhalb von K liegen.

Ist die letzte Forderung erfüllt, so kann die Faktorisierung mittels einer Variante des Newton-Verfahrens verbessert werden. Es folgt aus der letztgenannten Forderung, dass sowohl f(x) und g(x) als auch F₀ (x) und G₀ (x) teilerfremd sind. Es gibt nach dem erweiterten euklidischen Algorithmus Polynome a(x) und b(x) mit 1=af+bg. Seien A₀ (x), B₀ (x) Polynome, für welche die Koeffizienten des Fehlerausdrucks 1 - (A₀ F₀ + B₀ G₀ ) ebenfalls die Größenordnung haben. Dann können verbesserte Polynome

• mit ;
• mit ;
• mit
• mit

bestimmt werden, für welche die Koeffizienten der Fehlerausdrücke p(x) - F₁ (x) G₁ (x) und 1 - (A₁ F₁ + B₁ G₁ ) die Größenordnung besitzen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Trennkreisverfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung