Das schlichte Addieren der positiven bzw. negativen Koeffizienten eines Polynoms führt zu einer recht groben Abschätzung der Ober- bzw. Untergrenze. Im folgenden wird ein verbesserter Algorithmus für die Berechnung der Obergrenze gezeigt. Die Untergrenze erhält man dann leicht mit:
Die genauere Abschätzung ergibt sich unter Verwendung der Relation
Ein negativer Term, z.B.
, kann damit ersetzt werden durch
den sicher größeren Term
, mit
für alle
.
Beispiel für ein eindimensionales Polynom:
dessen grob abgeschätzte Obergrenze sich zu
ergibt.
Durch Ersetzung aller mit negativen Koeffizienten
durch
, mit
, erhält man ein neues Polynom
. Im Beisipiel:
.
Der Ersetzungsprozeß kann mit folgendem Schema veranschaulicht werden:
Die Exponenten wachsen von links nach rechts.
Demnach ist das Verschieben eines Koeffizienten von links nach rechts
äquivalent zur oben erklärten Substitution.
Nach dem Verschieben der negativen Koeffizienten kann man sie mit den
positiven verrechnen. Die übrigbleibenden Koeffizienten bilden das
neue Polynom .
Anwendung von (4.15) auf das neue Polynom
liefert
, eine wesentlich bessere Abschätzung für die
Obergrenze des Polynoms.
Das Verfahren läßt sich leicht auf mehrere Dimensionen übertragen. Ein zweidimensionales Beispiel:
Die nach (4.15)
grob berechnete Obergrenze ergibt sich zu .
Die Koeffizienten lassen sich wieder in ein Schema eintragen, wobei diesmal die Exponenten von links nach rechts und von oben nach unten zunehmen:
Negative Koeffizienten darf man deshalb sowohl nach unten als auch nach rechts
verschieben. Optimale Anwendung dieser Möglichkeiten liefert als neues
Polynom :
Anwendung von (4.15) auf liefert
als wesentlich besseren Wert für die Obergrenze.