PD. Dr. Martin Kreuzer WS 2001/2002 Fakultät für Mathematik Universität Regensburg

Übungen zur Vorlesung “Computeralgebra für Naturwissenschaftler”

Tutorium 3: Implementation des Divisionsalgorithmus

Nachfolgend sollen der Divisionsalgorithmus sowie zwei Varianten davon implementiert und an einigen Beispielen ausprobiert werden. Sei K ein Körper, sei P = K[x_{1}, …, x_{n}], sei σ eine Termordnung auf 𝕋^{n}, und seien g_{1}, …, g_{s} ∈ P \ {0} Polynome.

a) Schreiben Sie eine CoCoA-Funktion Division(…), die ein Polynom f ∈ P \ {0} und die Liste G = [g_{1}, …, g_{s}] nimmt und eine Liste [q_{1}, …, q_{s}, p] berechnet, so dass die Darstellung f = q_{1}g_{1} + ⋯ + q_{s}g_{s} + p die im Divisionsalgorithmus (Satz 8.3) angegebenen Eigenschaften hat.

b) Wenden Sie Ihre Funktion Division(…) in den folgenden Fällen an. Rechnen Sie dabei alles sowohl mit σ = Lex als auch mit σ = DegRevLex durch.

1) f = x^{2}y + xy^{2} + y^{2} ∈ P = ℚ[x, y], G = [xy − 1, y^{2} − 1]

2) f = xyz ∈ P = ℚ[x, y, z], G = [x − y^{2}, y − z^{3}, z^{2} − 1]

3) f = x_{1}^{4} ∈ P = ℚ[x_{1}, …, x_{4}], G = [x_{1}^{2} − x_{2}^{2}, x_{2}^{2} − x_{3}x_{4}, x_{3} − x_{4}^{2}]

c) Betrachten Sie die folgenden Instruktionen. 1) Sei i = 1 und q_{1} = ⋯ = q_{s} = 0.

2) Finde den bzgl. σ größten Term t ∈ Supp (f) der Form t = t′·LT_{σ}(g_{i}). Existiert so ein Term und ist c ∈ K \ {0} sein Koeffizient, so ersetze f durch f − \frac{c}{LC_{σ}(g_{i})} t′ g_{i} sowie q_{i} durch q_{i} + \frac{c}{LC_{σ}(g_{i})} t′.

3) Wiederhole 2) so oft wie möglich. Ist schließlich Supp (f) ∩ (LT_{σ}(g_{i})) leer, so erhöhe i um eins.

4) Gilt nun i ≤ s, so fahre mit 2) fort. Andernfalls setze p = f und gib [q_{1}, …, q_{s}, p] aus.

Zeigen Sie, dass dies ein Algorithmus ist, der eine Liste [q_{1}, …, q_{s}, p] berechnet, so dass f = q_{1}g_{1} + ⋯ + q_{s}g_{s} + p gilt.

d) Implementieren Sie den Algorithmus aus c) in einer CoCoA-Funktion Division2(…). Wenden Sie diese in den Fällen von b) an. Zeigen Sie, dass die berechneten Darstellungen i.a. nicht die Eigenschaften von Satz 8.3 haben.

e) Betrachten Sie die folgenden Instruktionen.

1) Wähle den bzgl. σ größten Term t ∈ Supp (f), der durch einen der Terme in {LT_{σ}(g_{1}), …, LT_{σ}(g_{s})} teilbar ist. Gibt es keinen solchen Term, so gib f aus und stoppe.

2) Finde das kleinste i ∈ {1, …, s} mit t = t′ · LT_{σ}(g_{i}). Sei c ∈ K \ {0} der Koeffizient von t in f. Ersetze f durch f − \frac{ct′}{LC_{σ}(g_{i})} g_{i} und fahre mit 1) fort.

Beweisen Sie, dass dies einen Algorithmus definiert, und dass das Ergebnis dieses Algorithmus gerade NR_{σ,G}(f) ist. Er heißt der Normale-Rest-Algorithmus.

f) Implementieren Sie den Algorithmus aus e) in einer CoCoA-Funktion NormRest(…) und wenden Sie diese in den Beispielen von b) an.