1. Was ist Computer-Algebra?

Computerunterstützte Mathematik Maple, Mathematica

Symbolisches Rechnen Axiom Numerische Mathematik NAG Library

Zahlentheorie LiDIA Library Computer-Algebra CoCoA, Macaulay, Singular Diskrete Mathematik GAP

CoCoA

Computational Commutative Algebra

2. Was leistet die Computer-Algebra?

2.1. Die Voraussetzungen

(K, +, ·) sei ein berechenbarer Körper, z.B. der Körper der rationalen Zahlen ℚ oder ein endlicher Körper ℤ/(p).

Ein Polynom mit Koeffizienten aus K ist eine endliche Summe der Form

f = ∑_{α=(α_{1},...,α_{n})∈ℕ^{n}} c_{α} x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}}

mit c_{α} ∈ K. Zum Beispiel f = 3x_{1}^{2} + \frac{1}{2}x_{1}x_{2} und g = x_{1}^{3} − 4x_{2}x_{3} + 5 sind Polynome mit Koeffizienten aus ℚ.

P = K[x_{1}, …, x_{n}] sei die Menge aller Polynome in den Unbestimmten x_{1}, …, x_{n} mit Koeffizienten in K. Die Menge P ist ein Ring, d.h. man kann ihre Elemente addieren und multiplizieren und es gelten die üblichen Rechenregeln. Der Ring P heißt der Polynomring in n Unbestimmten über K.

Eine Teilmenge I ⊆ P heißt ein Ideal in P, wenn gilt:

1) f ∈ I und g ∈ I ⇒ f + g ∈ I

2) f ∈ P und g ∈ I ⇒ f · g ∈ I

Sei nun I ein Ideal in P. Eine Menge von Polynomen f_{1}, …, f_{s} in I heißt ein Erzeugendensystem von I, wenn jedes Polynom f ∈ I eine Darstellung f = g_{1}f_{1} + ⋯ + g_{s}f_{s} mit Polynomen g_{1}, …, g_{s} ∈ P besitzt.

2.2. Die Fragen

Frage 1: Sei I ein Ideal in P, das von {f_{1}, …, f_{s}} erzeugt werde, und sei f ∈ P ein Polynom. Wie kann man effektiv prüfen, ob f ∈ I gilt. Dies ist das sogenannte Ideal Membership Problem.

Frage 2: Seien I und J zwei Ideale in P. Man hat u.a. folgende idealtheoretische Operationen:

1) I + J = {f + g | f ∈ I, g ∈ J} (Idealsumme)

2) I · J = {∑_{i} f_{i}g_{i} | f_{i} ∈ I, g_{i} ∈ J} (Idealprodukt)

3) I ∩ J (Durchschnitt von Idealen)

4) I : J = {f ∈ P | f · J ⊆ I} (Colon-Ideal, Idealquotient)

5) I : J^{∞} = {f ∈ P | f ·J^{i} ⊆ I für ein i ≥ 1} (Saturierung) Alle Operationen liefern wieder Ideale in P. Wie kann

man Erzeugendensysteme für die Resultate dieser Operationen berechnen?

Frage 3: Sei d ≤ n, und sei I ein Ideal in P. Wie kann man ein Erzeugendensystem von I ∩ K[x_{1}, …, x_{d}] bestimmen, d.h. von der Menge aller Polynome in I in denen nur die Unbestimmten x_{1}, …, x_{d} vorkommen? Eine solche Aufgabe nennt man ein Eliminationsproblem.

Frage 4: Seien f_{1}, …, f_{s} ∈ P Polynome. Wie kann man das algebraische Gleichungssystem

f_{1}(x_{1}, …, x_{n}) = 0
⋮
f_{s}(x_{1}, …, x_{n}) = 0

lösen? Wie kann man die Lösungen explizit beschreiben?

Beispiel: Die Lösung des Eliminationsproblems hilft oft, algebraische Gleichungssysteme zu lösen. Z.B. sei

\begin{aligned}x^{2} + y + z − 1 & = 0 \\ x + y^{2} + z − 1 & = 0 \\ x + y + z^{2} − 1 & = 0 \end{aligned}

Sei I das Ideal, das von diesen drei Polynomen erzeugt wird. Elimination liefert I ∩ K[z] = (z^{6} − 4z^{4} + 4z^{3} − z^{2}) und somit z ∈ \{0, 1, −1 + \sqrt{2}, −1 − \sqrt{2}\}. In dem man diese Werte nacheinander in die Gleichungen einsetzt, findet man die fünf Lösungen (1, 0, 0), (0, 1, 0), (0, 0, 1), (−1+\sqrt{2}, −1+\sqrt{2}, −1+ \sqrt{2}), (−1 − \sqrt{2}, −1 − \sqrt{2}, −1 − \sqrt{2}) des Gleichungssystems.

Beispiel: Die Lösung der Eliminationsaufgabe hilft auch für das sog. Implizitisierungsproblem. Zum Beispiel sei eine Raumkurve parametrisch gegeben durch

\begin{aligned}x & = t^{4} \\ y & = t^{3} \\ z & = t^{2} \end{aligned}

wobei t den Körper ℚ durchläuft. Wir bilden das Ideal I = (x − t^{4}, y − t^{3}, z − t^{2}) in ℚ[x, y, z, t] und berechnen

I ∩ ℚ[x, y, z] = (x − z^{2}, y^{2} − z^{3}).

Dies sind die impliziten Gleichungen, die die Kurve definieren.

Frage 5: Wie groß ist die Dimension des Vektorraums aller Polynome, die gewisse Bedingungen erfüllen? Z.B. ist I ein Ideal in P und i ≥ 0, so soll die Dimension des Raumes aller Polynome vom Grad ≤ i in I bestimmt werden. Dies ist die sog. Hilbert-Funktion von I.

Frage 6: Seien Polynome f_{1}, …, f_{s} ∈ P gegeben. Ein Tupel von Polynomen (g_{1}, …, g_{s}) ∈ P^{s} heißt eine Syzygie von (f_{1}, …, f_{s}), wenn gilt

g_{1}f_{1} + ⋯ + g_{s}f_{s} = 0.

Die Menge aller Syzygien ist ein Modul in P^{s}, d.h. eine Teilmenge die bzgl. Addition und Multiplikation mit Elementen von P abgeschlossen ist. Sie heißt der Syzygienmodul von (f_{1}, …, f_{s}). Wie kann man ein Erzeugendensystem dieses Syzygienmoduls berechnen?

2.3. Die Antworten

Alle obigen Fragen können mit Hilfe der Theorie der Gröbner-Basen positiv beantwortet werden.

Ein Polynom der Form x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} heißt ein Monom oder ein Term. Eine mit der Multiplikation verträgliche Ordnung <_{σ} auf der Menge aller Terme heißt eine Termordnung, wenn für alle Terme t ≠ 1 gilt 1 <_{σ} t.

Sei nun eine Termordnung <_{σ} gegeben. In jedem Polynom f ∈ P kommen nur endlich viele Terme vor. Der bzgl. <_{σ} größte unter ihnen heißt der Leitterm von f und wird mit LT_{σ}(f) bezeichnet.

Ist I ein Ideal in P, so heißt das Ideal, das von allen Leittermen von Polynomen aus I erzeugt wird, das Leittermideal von I und wird mit LT_{σ}(I) bezeichnet. In Formeln: LT_{σ}(I) = (LT_{σ}(f) | f ∈ I).

Eine Menge von Polynomen f_{1}, …, f_{s} ∈ I heißt eine Gröbner-Basis von I bzgl. <_{σ}, wenn die Leitterme LT_{σ}(f_{1}), …, LT_{σ}(f_{s}) das Leittermideal LT_{σ}(I) erzeugen. In diesem Fall bilden die Polynome selbst automatisch ein Erzeugendensystem von I.

Satz. Jedes Ideal I in P besitzt eine Gröbner-Basis bzgl. <_{σ}. Wenn man einige Zusatzbedingungen stellt (z.B. daß die Polynome normiert sein sollen), so ist die Gröbner-Basis sogar eindeutig und heißt die reduzierte Gröbner-Basis von I bzgl. <_{σ}.

Satz. Es gibt einen Algorithmus, nämlich den Buchberger-Algorithmus, der bei gegebener Termordnung >_{σ} aus einem Erzeugendensystem {f_{1}, …, f_{s}} eines Ideals I = (f_{1}, …, f_{s}) in P eine Gröbner-Basis dieses Ideals bzgl. >_{σ} berechnet.

Satz. (Berechnung von Eliminationsidealen) Sei d ≤ n und <_{σ} eine Eliminationstermordnung für {x_{d+1}, …, x_{n}}, d.h. enthält der Leitterm eines Polynoms keine der Unbestimmten x_{d+1}, …, x_{n}, so soll das ganze Polynom sie nicht enthalten. Berechne mittels des Buchberger-Algorithmus eine Gröbner-Basis G eines gegebenen Ideals I ⊆ P. Dann ist G ∩ K[x_{1}, …, x_{d}] eine Gröbner-Basis (und insbesondere ein Erzeugendensystem) des Eliminationsideals I ∩ K[x_{1}, …, x_{d}].

3. Industrielle Anwendungen der Computeralgebra

3.1. Statistik: “Design of Experiments”

In dem Teilbereich “Design of Experiments” der Statistik geht es um folgendes Problem. Zur vollständigen Beantwortung einer Frage ist es notwendig, eine sehr große Zahl von Datenpunkten (“full factorial design”) zu kennen. Dies ist aber in der Praxis entweder unmöglich oder zu teuer. Darum soll eine Teilmenge so bestimmt werden, daß aus der Kenntnis der Teildaten die gesuchten Erkenntnisse über die Gesamtmenge erschlossen werden können.

Erstes Beispiel: (Marketing) Ein neues Handy soll am Markt eingeführt werden. Für die von den Kunden gewünschten Eigenschaften wird ein mathematisches Modell aufgestellt.

\begin{matrix}Eigenschaft & W erte & Modell \\ Farbe & blau, gelb, rot & 0, 1, 2 \\ Gewicht & 100 Gramm Schritte & 0, 1, 2, 3, 4 \\ Kanten & eckig, rund, abgeflacht & 0, 1, 2 \\ Preis & 5 P reisbereiche & 0, 1, 2, 3, 4 \end{matrix}

Die Menge aller möglichen Tupel (F, G, K, P) ∈ ℚ^{4} bildet das “full design” 𝔻. Die (gesuchten) Kundenpräferenzen entsprechen einer (unbekannten) Funktion f : 𝔻 ⟶ ℚ, die man das Modell nennt.

Bemerkung: Die Funktion f : 𝔻 ⟶ ℚ ist auf einer endlichen Menge definiert. Dann gibt es ein Polynom in ℚ[x_{1}, x_{2}, x_{3}, x_{4}], das auf 𝔻 die gleichen Werte annimmt wie f.

Problem: Wir können bei einer Kundenumfrage nicht verlangen, daß die Testpersonen eine Rangfolge für alle 225 möglichen Kombinationen der Eigenschaften aufstellen.

Lösungsansatz:

• Finde eine geeignete “kleine” Teilmenge 𝔽 ⊂ 𝔻 (“fraction”).

• Erfrage die Bewertung der Elemente von 𝔽 durch die Testpersonen.

• Versuche die Funktion f : 𝔻 ⟶ ℚ aus diesen Daten zu rekonstruieren (“identify the model”).

Mathematische Durchführung: Sie I(𝔻) die Menge aller Polynome in P = ℚ[x_{1}, x_{2}, x_{3}, x_{4}], die auf 𝔻 verschwinden. Dies ist ein Ideal in P. Es wird erzeugt von den Polynomen {x_{1}(x_{1} − 1)(x_{1} − 2), x_{2}(x_{2} − 1) ⋯ (x_{2} − 4), x_{3}(x_{3} − 1)(x_{3} − 2), x_{4}(x_{4} − 1) ⋯ (x_{4} − 4)}. Wir müssen das Ideal I(𝔽) aller Polynome, die auf 𝔽 verschwinden, berechnen und die Menge der “confounding polynomials” I(𝔽) \ I(𝔻).

Wenn wir dann etwas über die Monome wissen, die in dem gesuchten Polynom f wirklich vorkommen (z.B. “der Einfluß von Farbe und Preis auf f ist unkorrelliert”), dann können wir versuchen 𝔽 so zu wählen, dass f|_{𝔽} bereits das Polynom f ∈ P bestimmt. Allerdings können wir f stets um Elemente aus I(𝔻) abändern, ohne seine Werte auf 𝔻 zu beeinflussen.

Zweites Beispiel: (Umzug einer Chemiefabrik) Eine Chemiefabrik zog in ein neues Gebäude in einer anderen Gegend um. Plötzlich funktionierte einer der Filtrierschritte nicht mehr. Für die möglichen Ursachen gab es eine Reihe von Kandidaten:

• Die Lufttemperatur in der neuen Fabrikhalle war anders.

• Das Wasser in der neuen Gegend war anders.

• Eine der Maschinen hatte beim Transport einen Schaden erlitten.

• Die verwendeten Chemikalien hatten eine etwas andere Zusammensetzung (neue Zulieferer).

• Die Prozedur der Vorbehandlung hatte sich geändert (neue Angestellte).

Es war zu teuer, alle Kombinationen aller Werte dieser Faktoren in Testläufen durchzuspielen. Daher mußten einige wenige Testläufe so konfiguriert werden, daß sich aus ihnen der entscheidende Faktor ablesen ließ.

Wieder ist ein wichtiger Schritt in der Lösung die Berechnung des Ideals I(𝔽) ⊂ P aller Polynome in ℚ[x_{1}, …, x_{n}] die auf der (geplanten) Teilmenge 𝔽 ⊂ 𝔻 verschwinden. Sei 𝔽 = {P_{1}, …, P_{s}} mit P_{i} = (p_{i1}, …, p_{in}) ∈ ℚ^{n}. Das Ideal aller Polynome, die in P_{i} verschwinden, heiße I(P_{i}). Zu berechnen ist

I(𝔽) = ⋂_{i=1}^{s} I(P_{i}) = ⋂_{i=1}^{s}(x_{1} − p_{i1}, …, x_{n} − p_{in}).

Der effektivste Algorithmus in dieser Situation ist der Buchberger-Möller-Algorithmus.

Weitere Fragen:

1) Sei eine Teilmenge 𝔽 ⊂ 𝔻 vorgegeben. Welche Modelle f : 𝔽 ⟶ 𝔻 können mit Hilfe von f|_{𝔽} identifiziert werden?

2) Die Koeffizienten von {1, x_{1}, …, x_{n}} in f heißen die Haupteffekte, diejenigen von {x_{i}x_{j} | i, j = 1, …, n} heißen die Interaktionen. Welche Teilmengen 𝔽 von 𝔻 sind zu wählen, wenn man nur die Haupteffekte identifizieren will?

3) Welche Teilmengen 𝔽 von s Punkten aus 𝔻 identifizieren die größte Anzahl linearer polynomialer Modelle?

Literatur:

1) J. Abbott, A. Bigatti, M. Kreuzer, und L. Robbiano, Computing ideals of points, J. Symb. Comput. (erscheint)

2) L. Robbiano, Gröbner bases and statistics, in: B. Buchberger und F. Winkler (Hrsg.), Gröbner Bases and Applications, Proc. Conf. Linz 1998, London Math. Soc. Lect. Notes 251, Cambridge University Press, S. 179–204 3.2. Warteschlangentheorie

Bei der Produktion vom Microchips in der Firma “Infineon Technologies” (Regensburg) spielt das folgende Problem der Warteschlangentheorie eine große Rolle.

↓^{λ_{2}}

Schlange Q_{2}

↓
⟶^{λ_{1}}  Schlange Q_{1}  ⟶^{μ} Schlange Q_{3} ⟶

Beschreibung mit Methoden des “Operations Research”

Jede Schlange wird durch einen Poisson-Prozeß modelliert. Schlange Q_{1} ist die Produktion (mit Kapazität s_{1}), Schlange Q_{2} ist die Nachfrage (Kapazität s_{2}), und Schlange Q_{3} ist das Lager (Kapazität s_{3}). Hierbei gilt s_{1} = s_{2}+s_{3} =: s. Die Zahl p(i, j) bezeichne die Wahrscheinlichkeit dafür, daß sich i + 1 Jobs in Schlange Q_{1} und j − s_{3} Jobs in Q_{2} (oder j leere Stellen in Q_{3}) befinden.

Man erhält Rekursionsgleichungen für die Zahlen p(i, j) mit 0 ≤ i ≤ s und 0 ≤ j ≤ s. Sie lauten

p(i + 1, j + 1)χ_{i≤s−1}χ_{j≤s−1} =
p(i, j)[\frac{λ_{1}}{μ} χ_{i<s} + \frac{λ_{2}}{μ} χ_{j<s} + χ_{i>0}χ_{j>0}]
− p(i − 1, j)\frac{λ_{1}}{μ} χ_{i≥1} − p(i, j − 1)\frac{λ_{2}}{μ} χ_{j≥1}

wobei χ die charakteristische Funktion ist. Die explizite Lösung dieser Rekursionsgleichung durch Einsetzen ist sehr zeit- und rechenintensiv.

Beschreibung mit Computer-Algebra

Für jede Zahl p(i, j) führt man eine Unbestimmte x_{ij} ein. Die Koeffizienten y = \frac{λ_{1}}{μ} und z = \frac{λ_{2}}{μ} werden ebenfalls als Unbestimmte betrachtet. Die Rekursionsgleichungen liefern ein algebraisches Gleichungssystem im Polynomring ℚ[{x_{ij}}_{i,j=0,...,n}, y, z]. Dieses Gleichungssystem können wir auch als lineares Gleichungssystem in den Unbestimmten x_{ij} über dem Funktionenkörper K = ℚ(y, z) betrachten.

In beiden Fällen gibt es eine Reihe von Ansätzen wie man dieses algebraische Gleichungssystem mit Hilfe der Theorie der Gröbner-Basen lösen kann.

Beispiel: Im einfachsten Fall s = 1 ergeben sich die Gleichungen

\begin{aligned}x_{00}y + x_{00}z − x_{11} & = 0 \\ −x_{00}z + x_{01}y & = 0 \\ −x_{00}y + x_{10}z & = 0 \\ −x_{01}y − x_{10}z + x_{11} & = 0 \end{aligned}

Ihre Lösung lautet x_{00} = yz, x_{01} = z^{2}, x_{10} = y^{2}, x_{11} = y^{2}z + yz^{2} (sowie Vielfache davon).

Literatur:

1) H. Gold, A Markovian single server with upstream job and downstream demand arrival system, Queueing Systems 30 (1998), 435–455

2) A. Wills, Algebraische Probleme in der Theorie der Warteschlagenmodelle, Diplomarbeit bei M. Kreuzer (in Vorbereitung)

3.3. Robotik

Die Robotik ist eines der “klassischen” Anwendungsgebiete der Computeralgebra. Um die grundlegenden Probleme zu erklären, die hierbei auftreten, beschränken wir uns auf einen einfachen Fall, nämlich den eines ebenen einarmigen Roboters, der den folgenden Annahmen genügt:

• Der Roboter ist fest an der Unterlage fixiert.

• Der Arm besteht nur aus (eventuell ausfahrbaren) geraden Segmenten, die durch Gelenke verbunden sind.

• Am Ende des Arms befindet sich eine drehbare “Hand”.

Skizze:

Mathematisches Modell eines solchen Roboters

• Die Stellung des i-ten Gelenks wird beschrieben durch den Winkel θ_{i}, der einen Teil des Einheitskreises S^{1} durchläuft.

• Die längenveränderlichen Segmente werden durch ihre Länge ℓ_{i} beschrieben, die durch ein Intervall I ⊆ ℝ parametrisiert wird.

• Die Orientierung der Hand wird wieder durch den Einheitskreis parametrisiert, der zur Unterscheidung V genannt wird.

Die Menge der Stellungen eines Roboters mit r Gelenken und p längenveränderlichen Segmenten ist dann parametrisiert durch

J = \underbrace{S^{1} × ⋯ × S^{1}}_{r mal} ×I_{1} × ⋯ × I_{p}.

Die Menge J heißt der Joint Space des Roboters. Die resultierende Stellung der Hand ist ein Punkt (a, b) ∈ U ⊆ ℝ^{2}. Die Menge C = U ×V heißt der Konfigurationsraum. Der Roboter ist nun gegeben durch die Abbildung f : J ⟶ C, die jeder Stellung der Gelenke die resultierende Position und Orientierung der Hand zuordnet.

Probleme:

1) “Forward Kinematic Problem” Finde die expliziten Gleichungen, die die Abbildung f : J ⟶ C beschreiben.

2) “Inverse Kinematic Problem” Bestimme das Bild von f. Für alle Punkte c ∈ f(J) bestimme f^{−1}(c).

3) “Motion Planning” Zu einem vorgegebenen Pfad c(t) in C finde einen Pfad j(t) in J mit f(j(t)) = c(t) für alle t ∈ ℝ. Der Pfad j(t) soll dabei stetig differenzierbar gewählt werden, d.h. die Jacobi-Matrix von f soll an den Punkten von j(t) maximalen Rang haben.

Beispiel: (3-gliedriger Roboter)

Der Ursprung der Koordinatensystems sei der feste Endpunkt des Roboters am Ende des ersten Segments, das in der y-Achse liege. Bei drei Segmenten fester Längen und nicht drehbarer Hand errechnet sich

f(θ_{1}, θ_{2}, θ_{3}) = ( \begin{matrix}ℓ_{3} cos(θ_{1} + θ_{2}) + ℓ_{2} cos(θ_{1}) \\ ℓ_{3} sin(θ_{1} + θ_{2}) + ℓ_{2} sin(θ_{1}) \\ θ_{1} + θ_{2} + θ_{3} \end{matrix} )

Setzen wir c_{i} = cos(θ_{i}) und s_{i} = sin(θ_{i}), so liefert das inverse kinematische Problem zum Punkt (a, b) ∈ ℝ^{2} das algebraische Gleichungssystem

a = ℓ_{3}(c_{1}c_{2} − s_{1}s_{2}) + ℓ_{2}c_{1}
b = ℓ_{3}(s_{1}c_{2} + c_{1}s_{2}) + ℓ_{2}s_{1}
0 = c_{1}^{2} + s_{1}^{2} − 1  (Pythagoras)
0 = c_{2}^{2} + s_{2}^{2} − 1

Dieses kann man durch Berechnung einer geeigneten Gröbner-Basis lösen. Dann kann man die Anzahl der Lösungen für verschiedene Punkte (a, b) bestimmen. In unserem Beispiel ergibt sich die Gröbner-Basis

c_{2} − \frac{a^{2}+b^{2}−ℓ_{2}^{2}−ℓ_{3}^{2}}{2ℓ_{2}ℓ_{3}} ,

s_{2} + \frac{a^{2}+b^{2}}{aℓ_{3}} s_{1} − \frac{a^{2}b+b^{3}+b(ℓ_{2}^{2}−ℓ_{3}^{2})}{2aℓ_{2}ℓ_{3}},

c_{1} + \frac{b}{a}s_{1} − \frac{a^{2}+b^{2}+ℓ_{2}^{2}−ℓ_{3}^{2}}{2aℓ_{2}} ,

s_{1}^{2}+ \frac{a^{2}b+b^{3}+b(ℓ_{2}^{2}−ℓ_{3}^{2})}{ℓ_{2}(a^{2}+b^{2})}s_{1}+ \frac{(a^{2}+b^{2})^{2}+(ℓ_{2}^{2}−ℓ_{3}^{2})^{2}−2a^{2}(ℓ_{2}^{2}+ℓ_{3}^{2})+2b^{2}(ℓ_{2}^{2}−ℓ_{3}^{2})}{4ℓ_{2}^{2}(a^{2}+b^{2})}

mit der man leicht nach (c_{1}, c_{2}, s_{1}, s_{2}) auflösen kann.

3.4. Ganzzahlige Programmierung

Die Aufgabe: Bei der ganzzahligen Programmierung geht es darum, die Tupel natürlicher Zahlen (X_{1}, …, X_{c}) zu finden, die das Ungleichungssystem

\{ \begin{matrix}a_{11}X_{1} + a_{12}X_{2} + ⋯ + a_{1c}X_{c} & ≤ & b_{1} \\ a_{21}X_{1} + a_{22}X_{2} + ⋯ + a_{2c}X_{c} & ≤ & b_{2} \\ ⋮ & ⋮ & ⋮ \\ a_{r1}X_{1} + a_{r2}X_{2} + ⋯ + a_{rc}X_{c} & ≤ & b_{r} \end{matrix}

erfüllen, wobei a_{ij}, b_{i} ∈ ℤ gegeben sind. Unter diesen Lösungen ist diejenige zu bestimmen, für die eine gewisse Kostenfunktion C = k_{1}X_{1} + ⋯ + k_{c}X_{c} mit k_{1}, …, k_{c} ∈ ℕ minimal wird.

Anwendungen: Optimierung von Fahrplänen, Management eines Fuhrparks, Erstellung eines Investitionsplans, Planung von Bohrungen bei der Ölexploration.

Die Lösung: Man geht in mehreren Schritten vor.

1) Führe neue Unbestimmte X_{c+1}, …, X_{c+r} ein und wandle das System um in ein Gleichungssystem

\{ \begin{matrix}a_{11}X_{1} + a_{12}X_{2} + ⋯ + a_{1c}X_{c} + X_{c+1} & = & b_{1} \\ a_{21}X_{1} + a_{22}X_{2} + ⋯ + a_{2c}X_{c} + X_{c+2} & = & b_{2} \\ ⋮ & ⋮ & ⋮ \\ a_{r1}X_{1} + a_{r2}X_{2} + ⋯ + a_{rc}X_{c} + X_{c+r} & = & b_{r} \end{matrix}

Wir nehmen daher von jetzt ab an, das das ursprüngliche System bereits ein Gleichungssystem war.

2) Im Ring der Laurent-Polynome P = K[y_{1}, …, y_{r}, y_{1}^{−1}, …, y_{r}^{−1}] betrachte y_{1} hoch die erste Gleichung, etc.

\{ \begin{matrix}y_{1}^{a_{11}X_{1}+a_{12}X_{2}+···+a_{1c}X_{c}} & = & y_{1}^{b_{1}} \\ y_{2}^{a_{21}X_{1}+a_{22}X_{2}+···+a_{2c}X_{c}} & = & y_{2}^{b_{2}} \\ ⋮ & ⋮ & ⋮ \\ y_{r}^{a_{r1}X_{1}+a_{r2}X_{2}+···+a_{rc}X_{c}} & = & y_{r}^{b_{r}} \end{matrix}

3) Multipliziere diese Gleichungen zusammen und erhalte

y_{1}^{a_{11}X_{1}+a_{12}X_{2}+···+a_{1c}X_{c}} ⋯ y_{r}^{a_{r1}X_{1}+a_{r2}X_{2}+···+a_{rc}X_{c}} = y_{1}^{b_{1}} ⋯ y_{r}^{b_{r}}

was sich vereinfachen läßt zu

(y_{1}^{a_{11}}y_{2}^{a_{21}} ⋯ y_{r}^{a_{r1}})^{X_{1}} ⋯ (y_{1}^{a_{1c}}y_{2}^{a_{2c}} ⋯ y_{r}^{a_{r,c}})^{X_{c}} = y_{1}^{b_{1}} ⋯ y_{r}^{b_{r}}

4) Setzen wir t_{i} = y_{1}^{a_{1i}}y_{2}^{a_{2i}} ⋯ y_{r}^{a_{ri}} für i = 1, …, c, so ist das ursprüngliche Gleichungssystem genau dann lösbar, wenn gilt

y_{1}^{b_{1}} ⋯ y_{r}^{b_{r}} ∈ K[t_{1}, t_{2}, …, t_{c}] ⊂ K[y_{1}, …, y_{r}, y_{1}^{−1}, …, y_{r}^{−1}]

(“Subalgebra Membership Problem”)

5) Um die Lösungen einzeln zu bestimmen, setzen wir (zur Vereinfachung) voraus, daß a_{ij}, b_{i} ∈ ℕ gilt. Im Polynomring K[x_{1}, …, x_{c}, y_{1}, …, y_{r}] bilden wir das Ideal I = (x_{1} − t_{1}, …, x_{r} − t_{r}). Genau dann ist ein Tupel (λ_{1}, …, λ_{c}) aus ℕ^{c} eine Lösung des Gleichungssystems, wenn gilt: y_{1}^{b_{1}} ⋯ y_{r}^{b_{r}} − x_{1}^{λ_{1}} ⋯ x_{c}^{λ_{c}} ∈ I (“Ideal Membership Problem”).

6) Schließlich müssen wir noch die “optimale” Lösung finden. Wähle eine Termordnung <_{σ}, die mit der Kostenfunktion C “verträglich” ist. Berechne die Gröbner-Basis G des Ideals I bzgl. <_{σ}. Man kann mit Hilfe des Divisionsalgorithmus jedes Polynom f “mit Rest” durch G teilen. Der Divisionsrest heißt die Normalform NF_{σ}(f) des Polynoms. Berechnet man nun NF_{σ}(y_{1}^{b_{1}} ⋯ y_{r}^{b_{r}}) = x_{1}^{λ_{1}} ⋯ x_{c}^{λ_{c}}, so ist das Tupel (λ_{1}, …, λ_{c}) die Lösung der ganzzahligen Programmieraufgabe, also diejenige Lösung des Gleichungssystems für die die Kostenfunktion minimal ist.

Optimierung dieses Verfahrens: Die Berechnung der Gröbner-Basis in Schritt 6) ist im allgemeinen sehr aufwendig. Man kann das Verfahren wie folgt beschleunigen.

1) Anstelle des Gleichungssystems betrachten wir das zugehörige homogene System

\{ \begin{matrix}a_{11}X_{1} + a_{12}X_{2} + ⋯ + a_{1c}X_{c} & = & 0 \\ a_{21}X_{1} + a_{22}X_{2} + ⋯ + a_{2c}X_{c} & = & 0 \\ ⋮ & ⋮ & ⋮ \\ a_{r1}X_{1} + a_{r2}X_{2} + ⋯ + a_{rc}X_{c} & = & 0 \end{matrix}

Zu dem Ideal I = (x_{1} − t_{1}, …, x_{r} − t_{r}) bilden wir auch das Ideal J = I ∩ K[x_{1}, …, x_{c}]. Wissen wir eine (beliebige) Lösung (λ_{1}, …, λ_{c}) des inhomogenen Systems und eine Gröbner-Basis von J, so liefert die Berechnung der Normalform NF_{σ,J}(x_{1}^{λ_{1}} ⋯ x_{c}^{λ_{c}}) = x_{1}^{μ_{1}} ⋯ x_{c}^{μ_{c}} die kostengünstigste Lösung (μ_{1}, …, μ_{c}) des inhomogenen Systems.

2) Eine beliebige Lösung des inhomogenen Systems kann man mit Hilfe von Schritt 5) und einer vollständigen Suche finden.

3) Man braucht also noch eine Gröbner-Basis von J bzgl. <_{σ}. Die Lösungen des homogenen Systems bilden ein Gitter L vom Rang r, für das man leicht eine ℤ-Basis v_{1}, …, v_{r} bestimmen kann. Man definiert eine Funktion φ : L ⟶ J durch

φ(α_{1}, …, α_{c}) =
x_{1}^{max(α_{1},0)} ⋯ x_{c}^{max(α_{c},0)} − x_{1}^{max(−α_{1},0)} ⋯ x_{c}^{max(−α_{c},0)}

Das von den Bildvektoren φ(v_{1}), …, φ(v_{r}) in K[x_{1}, …, x_{c}] erzeugte Ideal heißt das Gitterideal I_{L} von L. Nun gilt

J = I_{L} : (x_{1} ⋯ x_{c})^{∞} (Saturierung)

Die Berechnung der Gröbner-Basis, die man für diese Saturierung sucht, kann wesentlich beschleunigt werden.

Literatur:

A. Bigatti, R. La Scala und L. Robbiano, Computing Toric Ideals, J. Symb. Comput. 27 (1999), 351–365 3.5. Triebwerksdesign

Das Problem: Während des Härtungsprozesses einer Flugzeugturbine treten verschiedene Temperaturen im Innen- und Außenbereich auf, die Kräfte auf die Verbindungen zwischen den beiden ineinander liegenden Zylindern ausüben. Werden die Kräfte zu stark, verbiegt sich die Verbindung.

Wählt man ein eindimensionales Modell, so ist dies gerade das klassische Problem der Bestimmung der Biegelast eines Balkens. Dieses könnte man in jedem konkreten Fall mit Standardmethoden der numerischen Mathematik lösen. Jedoch möchte man eigentlich den Balken schon so entwerfen, daß er unter den vorgegebenen Bedingungen einer möglichst großen Last widersteht. Die Maximallast sollte als Formel in den Designparametern gefunden werden. Dann kann man diese Formel mit Hilfe der Analysis untersuchen und einen optimalen Balken finden.

Mathematisches Modell: Ein Balken mit variablem Querschnitt liege auf seinen beiden Endpunkten. Er verlaufe entlang der x-Achse. Der linke Endpunkt sei der Ursprung. Weiter setzen wir: E Elastizitätsmodul des Materials (konstant)

J(x) axiales Trägheitsmoment der Querschnitte (Funktion) p(x) senkrecht zum Balken wirkende Kraft (Funktion) q(x) entlang der x-Achse wirkende Kraft (Funktion) y(x) Verbiegung des Balkens (Funktion) M(x) die wirkende Biegekraft (Funktion)

Dann wird die Situation beschrieben durch die beiden Differentialgleichungen

\begin{aligned}(EJ)y′′ & = −M \\ M′′ & = −p − (qy′)′ \end{aligned}

Nun nimmt man zusätzlich an, daß M(x) von der Form M(x) = λy(x) + Rx ist mit λ, R konstant. Die Zahl R heißt die Reaktionskraft. Es ergibt sich durch Ableiten und ineinander Einsetzen eine einzelne Differentialgleichung vierten Grades

−EJ(x)y′′′′(x) − 2EJ′(x)y′′′(x) + (−EJ′′(x) − λ)y′′(x) = 0.

Ist J(x) eine “einfache” gegebene Funktion, so kann man dies direkt mit Standardmethoden lösen. Jetzt aber soll J(x) in einem gegebenen Vektorraum von Funktionen so gewählt werden, daß die erlaubte Biegelast maximal wird.

Man verwendet eine symbolische Version der Raleigh-Ritz Methode. Dabei muß ein zugehöriges Energiefunktional minimiert werden. Es hat die Gestalt

Π(λ) = ∫_{o}^{ℓ} α(y′′)^{2}dx − λ ∫_{0}^{ℓ}(y′)^{2}dx.

mit α = EJ. Man geht wie folgt vor:

• Definiere Ansatzfunktionen w_{i} für die Verbiegung y(x), die der Erfahrung entsprechen und die Randbedingungen erfüllen. Setze y(x) = ∑_{i} c_{i}w_{i} und J = (∑_{i} a_{i}w_{i})^{2}. (Die Funktion J ist eine quadratische Funktion der Querschnittsfläche.)

• Betrachte den Integranden des Variationsproblems als Polynomfunktion in den c_{i}. Integriere die Koeffizienten über x von 0 bis ℓ und erhalte das Energiefunktional als homogenes Polynom vom Grad zwei in den c_{i}.

• Es gibt genau dann eine Lösung der DGL, wenn die Determinante der Matrix der partiellen Ableitungen (bzgl. der c_{i}) als quadratisches Polynome in λ verschwindet.

• Diese quadratische Gleichung für λ liefert eine implizite Darstellung von λ als Funktion der a_{i}, die wir maximieren müssen.

• Berechne die partiellen Ableitungen von λ nach den a_{i}. Löse dann das entstehende polynomiale Gleichungssystem für die a_{i} mit Hilfe der Theorie der Gröbner-Basen.

Literatur:

J. Grabmeier, An application of a symbolic version of the Raleigh-Ritz method to the design of aircraft turbines, Preprint 1995 3.6. Photogrammetrie

Bei der Photogrammetrie geht es um die Rekonstruktion einer Bildszene, von der zwei oder mehr Bilder existieren, die von verschiedenen Kamerapositionen aufgenommen wurden.

Beispiele: Auswertung von Satellitenbildern, Fernerkundung, Landvermessung

Skizze:

Mathematisches Modell: Eine Kameraposition besteht aus einem Punkt P ∈ ℝ^{3} zusammen mit einem lokalen orthogonalen Koordinatensystem {e_{1}, e_{2}, e_{3}}. Sei noch eine zweite Kameraposition (Q, {f_{1}, f_{2}, f_{3}}) gegeben. Die Kameraversetzung von P nach Q ist die lineare Isometrie φ : ℝ^{3} ⟶ ℝ^{3} mit φ(P) = Q und φ(e_{i} + P) = f_{i} + Q für i = 1, 2, 3. Sie wird durch eine orthogonale 3 × 3 -Matrix R und den Vektor a = Q − P beschrieben.

Ein Bildpunkt ist ein Punkt auf der Einheitssphäre S um die Kameraposition P (bzw. S′ um Q). Die Abbildungen φ : ℝ^{3} \ \{P \} ⟶ S mit x ↦ \frac{x−P}{|x−P |} + P sowie ψ : ℝ^{3} \ {Q} ⟶ S′ liefern die beiden gegebenen Bilder.

Ein Korrespondenzpaar ist ein Paar von Punkten q ∈ S, q′ ∈ S′ so daß es ein x ∈ ℝ^{3} gibt mit φ(x) = q und ψ(x) = q′. Mit anderen Worten, q und q′ sind die Bildpunkte des gleichen Raumpunkts.

Fragen:

1) Sind Korrespondenzpaare (q_{i}, q′_{i}) gegeben, so finde eine Matrix R sowie einen Vektor a ∈ ℝ^{3} mit βq′_{i} = R(αq_{i}−a) für alle i.

2) Wie viele solcher Korrespondenzpaare sind i.a. nötig um das Bild bis auf endlich viele Fälle rekonstruieren zu können? (Unter diesen endlich vielen Fällen kann man dann mit Hilfe von Verdeckungen etc. den richtigen bestimmen.)

3) Hat man die richtige Anzahl von Korrespondenzpaaren, wie viele Fälle muß man dann i.a. erwarten?

Es gibt auch noch weitere Mehrdeutigkeiten, die das Problem erschweren: Skalierungsmehrdeutigkeit und Spiegelung der Szene. Bringt man die Terme in den obigen Transformationsgleichungen auf eine Seite, so ergeben sich Gleichungen

(q′_{i})^{transp.} · E · q_{i} = 0

wobei E = R · T eine sogenannte essentielle Matrix ist, d.h. das Produkt einer orthonormalen mit einer antisymmetrischen 3 × 3 -Matrix.

Satz. Das Rekonstruktionsproblem ist äquivalent damit, eine 3 × 3 -Matrix E zu finden mit (q′_{i})^{tr}Eq_{i} = 0 für alle i, mit EE^{tr}E = \frac{1}{2} Spur(EE^{tr})E sowie mit Rang(E) = 2.

Betrachtet man die Einträge von E als Unbestimmte, so definieren diese Gleichungen eine projektive Varietät M im Raum ℙ^{9}, die die Varietät der essentiellen Matrizen genannt wird.

Satz. Die Varietät M ist 5-dimensional und hat den Grad 10. Sie ist irreduzibel und arithmetisch Cohen-Macaulay.

Dies kann mit Hilfe der Computer-Algebra berechnet werden und bedeutet, daß man i.a. zur Bildrekonstruktion ≥ 5 Korrespondenzpaare braucht und dann noch ≤ 10 Fälle unterscheiden muß. Jedes Korrespondenzpaar, das man gefunden hat, schränkt die Menge der möglichen essentiellen Matrizen ein. Geometrisch entspricht dies einem Hyperebenenschnitt von M.

Literatur:

S. Maybank, Theory of reconstruction from image motion, Springer, Berlin 1993 3.7. Moderne Portfoliotheorie

Gegeben seien n Anlageformen, z.B. Aktien, Anleihen, Immobilien, Bargeld, Festgeld, Gold, etc. Weiter seien die Preise dieser Anlageformen zu gewissen Zeitpunkten t_{0}, t_{1} = t_{0} + Δt, t_{2} = t_{0} + 2Δt, …, t_{N} = t_{0} + NΔt gegeben, wobei z.B. Δt ein Tag, ein Monat, oder ein Jahr sein kann.

Das Problem der Portfoliotheorie besteht darin, die Anlageformen so zu einem Portfolio zusammenzusetzen, daß

1) der langfristige Ertrag möglichst groß ist,

2) das “Risiko” des Portfolios möglichst klein ist.

Mathematisches Modell:

Sei Ω_{0} = {t_{0}, …, t_{N}} und A_{i} : Ω_{0} ⟶ ℝ der Preis der iten Anlageform. Man betrachtet A_{i} als Zufallsvariable. Ist B_{i}(t_{j}) die Ausschüttung (Dividenden, Zinsen, Aktienbonus) der i-ten Anlageform im Zeitraum (t_{j−1}, t_{j}), so heißt die Zufallsvariable

\begin{matrix}X_{i} : Ω = \{t_{1}, …, t_{N}\} & ⟶ ℝ \\ t_{j} & ⟼ (A_{i}(t_{j}) + B_{i}(t_{j}))/A_{i}(t_{j−1}) \end{matrix}

der Gesamtertrag der i-ten Anlageform.

Ein Portfolio ist ein Tupel (a_{1}, …, a_{n}) ∈ ℝ^{n} mit a_{i} ≥ 0 für i = 1, …, n und a_{1} + ⋯ + a_{n} = 1. (Die Zahl a_{i} ist der Prozentsatz der Anlagesumme, der in die i-te Anlageform investiert wird.) Die Zufallsvariable X = a_{1}X_{1} + ⋯ + a_{n}X_{n} heißt dann der Gesamtertrag des Portfolios. Dabei ist Ω ein Wahrscheinlichkeitsraum mit der Gleichverteilung. Das “Risiko” des Portfolios soll gemessen werden durch seine Varianz Var(X) = E(X^{2}) − E(X)^{2} bzw. durch seine Standardabweichung σ(X) = \sqrt{Var(X)}.

Satz. 1) Der Gesamtertrag des Portfolios beträgt

E(X) = ∑_{i=1}^{n} a_{i}E(X_{i}).

2) Die Varianz des Portfolios ist

Var(X) = ∑_{i,j=1}^{n} a_{i}a_{j}Cov(X_{i}, X_{j}),

wobei die Kovarianz zweier Anlageformen X_{i} und X_{j} definiert ist durch Cov(X_{i}, X_{j}) = E((X_{i} − E(X_{i}))(X_{j} − E(X_{j}))).

Ein Portfolio heißt effizient, wenn jedes andere Portfolio mit derselben Varianz einen kleineren Ertrag hat und jedes andere Portfolio mit demselben Ertrag hat eine größere Varianz. Die Menge der effizienten Portfolios heißt die effiziente Grenze.

Skizze:

Problem: Sind X_{1}, …, X_{n} : Ω ⟶ ℝ gegeben, so ist die effiziente Grenze zu berechnen.

Wir setzen e := E(X), v := Var(X), c_{ij} := Cov(X_{i}, X_{j}), etc. und erhalten die Portfoliogleichungen

\begin{aligned}(1)  1 & = a_{1} + ⋯ + a_{n} \\ (2)  e & = a_{1}e_{1} + ⋯ + a_{n}e_{n} \\ (3)  v & = ∑_{i,j=1}^{n} a_{i}a_{j}c_{ij} \end{aligned}

Dann denken wir uns ein Risikoniveau v vorgegeben und versuchen den Gesamtertrag e unter den Nebenbedingungen (1),(3) zu maximieren. Die Methode der Langrangeschen Multiplikatoren liefert n + 3 algebraische Gleichungen für die n+4 Unbestimmten a_{1}, …, a_{n}, e, v, λ, μ. Es sind n+2 lineare und eine quadratische Gleichung.

Diese Gleichungen definieren ein Ideal I ⊂ ℚ[a_{1}, …, a_{n}, e, v, λ, μ] der Höhe n + 3. Das Eliminationsideal I ∩ ℚ[e, v] ist ein Hauptideal, das von einem quadratischen Polynom q erzeugt wird. Die Nullstellenmenge ist eine Parabel in der (e, v)-Ebene. Der Teil der Parabel, der Portfolios mit a_{1} ≥ 0, …, a_{n} ≥ 0 entspricht, ist ein Teil der effizienten Grenze.

Die gesamte effiziente Grenze erhält man, indem man auch die entsprechenden Parabeln für Teilportfolios berechnet. Man muß ja nicht jede Anlageform verwenden. Ist e_{i} < e_{j} und v_{i} > v_{j}, so kann man auf die Anlageform X_{i} getrost verzichten.

Bemerkungen: 1) Man kann auch das Portfolio mit dem kleinsten möglichen v berechnen, also das “risikoärmste Portfolio”.

2) Es gibt auch eine Regel, die sogenannte MEL-Regel, die einen eindeutigen Punkt auf der effizienten Grenze festlegt, der auf sehr lange Frist (also wenn man das Anlageverfahren sehr oft wiederholt) den besten Gesamtertrag bringt. Auch das MEL-Portfolio kann mit Computer-Algebra berechnet werden.

Literatur:

H. Markowitz, Portfolio selection: efficient diversication of investments, Blackwell Publ. 1991