Symbolisches Rechnen
Vorlesung
Wintersemester 2006, 2014, 2026
Sommersemester 2021, 2025

Johannes Waldmann, HTWK Leipzig

<all>

Einleitung

Symbolisches Rechnen: Beispiele: Zahlen

Symbolisches Rechnen: Beisp.: Funktionen

Symbolisches Rechnen: Motivation

hat weitreichende Anwendungen:

ist nützlich im Studium, verwendet und vertieft:

Überblick

Literatur

Software

Beispiel: S.R. und Term-Ersetzung

Regeln für symbolisches Differenzieren (nach t):

 D(t) -> 1         D(constant) -> 0
 D(+(x,y)) -> +(D(x),D(y))
 D(*(x,y)) -> +(*(y,D(x)),*(x,D(y)))
 D(-(x,y)) -> -(D(x),D(y))

Robert Floyd 1967, zitiert in: Nachum Dershowitz: 33 Examples of Termination,

https://doi.org/10.1007/3-540-59340-3_2

Beispiel: Termersetzung (cont.)

data E = Zero | One | T 
       | Plus E E | Times E E  deriving Show

e :: E
e = let b = Plus T One in Times b b

d :: E ->  E
d e = case e of
    Zero -> Zero ; One -> Zero ; T -> One
    Plus x y -> Plus (d x) (d y)
    Times x y -> 
        Plus (Times y (d x)) (Times x (d y))

Beispiel: Inverse Symbolic Calculator

Hausaufgaben KW 15, Organisatorisches

  1. zum Haskell-Programm zum Symb. Differenzieren:

    • füge Syntax und Regel für Quotienten hinzu

    • schlage Regeln zur Vereinfachung vor

  2. ISC Simple Lookup and Browser sagt für 2+3\sqrt{2+\sqrt{3}}:

    Mixed constants with 5 operations
1931851652578136 = 1/2/sin(Pi/12)

    begründen Sie das (geometrisch oder schriftlich)

  3. ein Polynom mit Nullstelle 22+33\sqrt[2]{2} +\sqrt[3]{3} bestimmen, nachrechnen.

  4. Geonext: Satz von Napoleon illustrieren (gleichseitige Dreiecke über den Seiten eines beliebigen Dreiecks)

  5. eigener Rechner: rlwrap maxima installieren,

    Rechner im Pool: ssh und tmux ausprobieren, auch Management von Sessions, Windows, Panes (split horizontal, vertikal), vgl. https://news.ycombinator.com/item?id=26670708

Organisatorisches:

Zahlen

Überblick

Darstellung natürlicher Zahlen

Natürliche Zahlen, Addition

Rekursive Multiplikation

Karatsuba-Multiplikation

Asymptotisch schnellere Multiplikation

Ganze Zahlen

Rationale Zahlen

Explosion der Stellenanzahl (Beispiel)

Endliche und unendliche „Dezimal“brüche

Berechenbare reelle Zahlen

Potenzreihen, Exponentialfunktion

Potenzreihe für Wurzelfunktion

Logarithmen

Taylor-Entwicklung log⁡(1+x)=x−x2/2+x3/3−…\log(1+x)=x-x^2/2+x^3/3- \ldots

konvergiert sehr langsam für x=1x=1, gar nicht für größere xx.

J.R. Young, 1835, siehe v. Mangoldt/Knopp, Bd. 2, S. 127 a=log⁡(16/15)=4log⁡2−1log⁡3−log⁡5,b=log⁡(25/24)=…c=log⁡(81/80)=…\begin{eqnarray*} a = \log (16/15) &=& 4\log 2-1 \log 3-\log 5, \\ b = \log (25/24) &=& \dots \\ c = \log (81/80) &=& \dots \end{eqnarray*} Umstellung ergibt log⁡2=7a+5b+3c,…\log 2 = 7a + 5b + 3c , \dots Aufgaben:

Pi

darüber gibt es ganze Bücher (Aufgabe: finde Beispiele)

Ansatz: Taylor-Entwicklung von arctan⁡x\arctan x

arctan⁡x=x−x3/3+x5/5−…\arctan x = x - x^3/3 + x^5/5 - \dots

(J. Machin, 1706, 100 Stellen; W. Shanks, 1873, 707 St.)

Approximiertes Rechnen

Hausaufgaben

WS26 empfohlen: 2, 4, 6 (andere sind nicht verboten)

  1. Multiplikation in GMP (GNU Multiprecision Library) https://gmplib.org/manual/Multiplication-Algorithms

    1. Karatsuba-Rechnung ist dort etwas anders als hier auf der Folie, warum?

    2. GHC verwendet GMP für den Typ Integer.

      Bestimmen Sie experimentell den Anstieg der Rechenzeit bei Verdopplung der Stellenzahl, z.B.

      :set +s
x = 10^10^8 :: Integer
odd x -- damit x ausgewertet wird
odd ((x-1)*(x+1)) -- die eigentliche Messung
  True
  (3.73 secs, 166,159,792 bytes)
y = x*x -- hat doppelte Stellenzahl

      Ist die Anzahl der Bytes plausibel?

      Diskutieren Sie mögliche verkürzte Auswertungen für odd .... Kann GMP/GHC das?

    3. Zusatz: warum ist (oder erscheint) (x+1)^2 schneller als (x+1)*(x+1)?

  2. zu Multiplikation nach Toom (3 Blöcke): ergänzen Sie den Ausdruck CC sowie die fehlenden Linearkombinationen

  3. diskutieren (Zusatz: implementieren) Sie die Darstellung von ganzen Zahlen mit negativer Basis B≤−2B\le -2

    (und nichtnegativen Ziffern ∈{0,…,|B|−1}\in\{0,\dots,|B|-1\} wie bisher)

    Bsp: B=−2B=-2,

    −3=1⋅B0+0⋅B1+1⋅B2+1⋅B3=1+0+4−8-3 = 1\cdot B^0 + 0\cdot B^1 + 1\cdot B^2+1\cdot B^3 =1+0+4-8

    1. Eindeutigkeit, Konstruktion

    2. Arithmetik (Nachfolger, Addition, Multiplikation)

  4. Bestimmen Sie die Taylor-Reihe für den Arcustangens an der Stelle 0

    wie auf Folie Potenzreihe für Wurzelfunktion

    Bestimmen Sie damit x=arctan⁡(1/2),y=arctan⁡(1/3)x=\arctan(1/2), y=\arctan(1/3) auf (z.B.) 20 Stellen.

    Begründen Sie x+y=π/4x+y=\pi/4. Rechnen Sie den Wert für π\pi aus und vergleichen Sie mit einer verläßlichen Quelle.

    Kann man π\pi nach diesem Verfahren, aber mit anderen Parametern, besser bestimmen? (mehr Stellen bei gleichem Aufwand)

  5. Bestimmen Sie die Taylor-Reihe für den (natürlichen) Logarithmus an der Stelle 1. Bestimmen Sie damit a=log⁡(6/5),b=log⁡(9/8),c=log⁡(10/9)a=\log(6/5), b=\log(9/8), c=\log(10/9) auf (z.B.) 100 Stellen und daraus log⁡2\log 2 als eine Linearkombination.

  6. wie bestimmt man 3\sqrt{3}, 5\sqrt{5}, 23\sqrt[3]{2}

    Hinweis: 23\sqrt[3]{2} als Fixpunkt von x↦(2x+2/x2)/3x \mapsto (2x + 2/x^2)/3,

    diese Gewichte ergeben quadratische Konvergenz,

    ist äquivalent zu Bestimmung der Nullstelle von f(x)=x3−2f(x)=x^3-2 nach Newton-Verfahren:

    f′(x)=3x2,x↦x−f(x)/f′(x)=…f'(x)=3x^2, x\mapsto x - f(x)/f'(x) = \dots

  7. Was macht dieses Programm?

    int n = 1000;
int [] d = new int [n];
for (int i=2; i<n; i++) { d[i]=1; }
for (int j=2; j<n; j++) {
    int c = 0;
    for (int i=n-1; i>=1; i--) {
        int h = 10 * d[i] + c;
        d[i] = h % i; c = h / i;
    }
    System.out.print(c); System.out.flush();
}

    Ist die Ausgabe korrekt? Wie weit darf man n erhöhen?

  8. Jerzy Karczmarczuk: The Most Unreliable Technique in the World to compute pi, 2003? https://web.archive.org/web/20051017081559/http://users.info.unicaen.fr/~karczma/arpap/lazypi.ps.gz

Polynome

Motivation (I): Polynom-Interpretationen

Motivation (II): Algebraische Zahlen

Bsp: gesucht ist Minimalpolynom für y=2+33y = \sqrt{2} + \sqrt[3]{3}

13322333232323y0100000y1011000y2200210y3362003y443128120y56020415320y61790120246018\begin{array}{c|cccccc} & 1 & \sqrt[3]{3} & \sqrt{2} & \sqrt{2} \sqrt[3]{3} & \sqrt[3]{3^2} & \sqrt{2} \sqrt[3]{3^2} \\ \hline y^0 & 1 & 0 & 0 & 0 & 0 & 0 \\ y^1 & 0 & 1 & 1 & 0 & 0 & 0 \\ y^2 & 2 & 0 & 0 & 2 & 1 & 0 \\ y^3 & 3 & 6 & 2 & 0 & 0 & 3 \\ y^4 & 4 & 3 & 12& 8 & 12& 0 \\ y^5 & 60& 20& 4 & 15& 3 & 20 \\ \hline y^6 & 17& 90&120& 24& 60& 18 \end{array} die letzte Zeile ist linear abhängig von den vorigen (Dimension des Vektorraumes ist ≤6\le 6), ergibt Darstellung von y6y^6 als rationale Linearkombination von y0,…,y5y^0,\dots, y^5.

Motivation (III): Geometrische Örter

Semantik und Syntax von Polynomen

Gruppen, Ringe, Körper

Polynome in einer Variablen

Polynom-Division (über ℚ\mathbb{Q})

Polynome in mehreren Variablen

Polynom-Darstellung als geordnete Liste

Listen-Darstellung f. mehr Var.

Ideale

Hausaufgaben

  1. Bezeichnungen:

    arithmetisches Mittel A(x1,…,xn)=(∑xi)/nA(x_1,\dots,x_n)=(\sum x_i)/n, geometrisches Mittel G(x1,…,xn)=∏xi)nG(x_1,\dots,x_n)=\sqrt[n]{\prod x_i)}.

    Aufgabe: Stelle A(x1,…,x4)4−G(x1,…,x4)4A(x_1,\ldots,x_4)^4-G(x_1,\ldots,x_4)^4 als Summe von Quadraten (SOS) von Polynomen dar.

    Hinweis: A(x1,x2)2−G(x1,x2)2=(x1−x2)2/4A(x_1,x_2)^2-G(x_1,x_2)^2 = (x_1-x_2)^2/4 und

    A(x1,x2,x3,x4)=A(A(x1,x2),A(x3,x4))≥A(G(x1,x2),G(x3,x4))≥G(G(x1,x2),G(x3,x4))=G(x1,x2,x3,x4)A(x_1,x_2,x_3,x_4)=A(A(x_1,x_2),A(x_3,x_4)) \ge A(G(x_1,x_2),G(x_3,x_4)) \ge G(G(x_1,x_2),G(x_3,x_4)) = G(x_1,x_2,x_3,x_4).

    Zusatz: A(x1,x2,x3)3−G(x1,x2,x3)3A(x_1,x_2,x_3)^3-G(x_1,x_2,x_3)^3 ist kein SOS, kann aber als Bruch mit SOS im Zähler und (x+y+z)(x+y+z) im Nenner geschrieben werden. Dazu die SOS-Darstellung der A-G-Ungleichung für die 4 Werte x1,x2,x3,t=A(x1,x2,x3)x_1,x_2,x_3,t=A(x_1,x_2,x_3) benutzen, denn A(x1,x2,x3,t)=tA(x_1,x_2,x_3,t)=t und G(x1,x2,x3,t)4=G(x1,x2,x3)3⋅tG(x_1,x_2,x_3,t)^4=G(x_1,x_2,x_3)^3\cdot t.

    Hintergrund: Bruce Reznick: Some Concrete Aspects of Hilbert’s 17th Problem, 2000, https://faculty.math.illinois.edu/~reznick/.

  2. das Minimalpolynom für 2+33\sqrt{2}+\sqrt[3]{3} nach angegebenem Verfahren ausrechnen und überprüfen.

    Ähnlich für 3+5\sqrt{3}+\sqrt{5} oder (z.B.) 35+55\sqrt[5]{3}+\sqrt[5]{5}

  3. Das Polynom PP für „liegt auf Umkreis der Seitenmitten“ angeben (oder ähnlicher geometrischer Ort im Dreieck).

    o.B.d.A A1=A2=B1=0A_1=A_2=B_1=0 annehmen.

    Warum wäre zusätzlich C2=0C_2=0 doch eine B.d.A.?

  4. für die in VL angegebene Implementierung von Polynomen:

    eine anderen Koeffizientenbereich (als Rational) benutzen, z.B. Complex Rational

    nichttriviale Rechnungen durchführen (z.B. Division von Xpq−1X^{pq}-1 durch Xp−1X^p-1), Ergebnis prüfen,

    Laufzeit messen, Ausführung profilieren, teure Funktionen feststellen, ggf. verbessern

    Vergleichen mit derselben Rechnung in einem richtigen Computer-Algebra-System (maxima, fricas). (Nicht irgendwo online, sondern lokal, damit man messen und vergleichen kann.)

  5. für P=X2Y+XY2+Y2,Q=XY−1,R=Y2−1P=X^2Y + XY^2 + Y^2, Q=XY-1, R=Y^2-1:

    ist P∈Ideal⁡(Q,R)P\in\operatorname{Ideal}(Q,R)?

    Hinweis: nein. Hinweis: Betrachten Sie Werte von PP für die gemeinsamen Nullstellen von Q,RQ,R.

  6. gilt X5−Y2∈Ideal⁡(X2Y−1,XY2−1)X^5-Y^2 \in\operatorname{Ideal}(X^2Y-1,XY^2-1)?

    Welches Resultat liefert der Nullstellentest?

  7. Zeigen Sie Ideal⁡(X+XY,Y+XY,X2,Y2)=Ideal⁡(X,Y)\operatorname{Ideal}(X+XY,Y+XY,X^2,Y^2)=\operatorname{Ideal}(X,Y).

  8. Entscheiden Sie X2+1∈Ideal⁡(X+1)X^2+1 \in \operatorname{Ideal}(X+1), X2−y2∈Ideal⁡(X+Y)X^2-y^2\in\operatorname{Ideal}(X+Y), geben Sie Algorithmus für P∈Ideal⁡(Q)P\in\operatorname{Ideal}(Q) an.

  9. der arktische Halbring 𝔸=({−∞}∪ℕ,max⁡,−∞,+,0)\mathbb{A}=(\{-\infty\}\cup\mathbb{N},\max,-\infty,+,0).

    Ist deg\deg homomorph (strukturerhaltend) von (ℤ[X],+,0,⋅,1)(\mathbb{Z}[X],+,0,\cdot,1) nach 𝔸\mathbb{A}?

  10. Def: Monom-Ordnung: total, monoton bzgl. Multiplikation, terminierend.

    Implementieren und Eigenschaften überprüfen/beweisen für graded reverse lexicographic: Ordnen nach absteigender Exponentensumme, bei Gleichheit nach aufsteigender Exponentenfolge

    Bsp. (für X>YX > Y) X3Y2>X1Y3X^3Y^2 > X^1Y^3, X3Y2>X4Y1X^3Y^2 > X^4Y^1.

    Welche Eigenschaft(en) gehen dabei ohne Gradierung verloren?

  11. Für Monom-Ordnung >> bezeichnet 𝗆𝖽𝖾𝗀⁡(M)\operatorname{\textsf{mdeg}}(M) für Monome: den Exponentenvektor (in der Reihenfolge der Variablen).

    und für Polynome (≠0\neq 0): den größten solchen Vektor (ist eindeutig, weil die Ordnung total ist).

    Bsp.: für X>YX>Y ist 𝗆𝖽𝖾𝗀⁡(X2Y5)=[2,5]\operatorname{\textsf{mdeg}}(X^2Y^5)=[2,5],

    für lex-Ordnung ist 𝗆𝖽𝖾𝗀⁡(X2Y5−X8)=[8,0]\operatorname{\textsf{mdeg}}(X^2Y^5-X^8)=[8,0].

    Ausprobieren, beweisen, ergänzen: für Polynome f,g≠0f,g\neq 0 ist 𝗆𝖽𝖾𝗀⁡(f⋅g)=𝗆𝖽𝖾𝗀⁡(f)+𝗆𝖽𝖾𝗀⁡(g)\operatorname{\textsf{mdeg}}(f\cdot g)=\operatorname{\textsf{mdeg}}(f)+\operatorname{\textsf{mdeg}}(g) (komponentenweise Addition)

    Welche Beziehung zw. 𝗆𝖽𝖾𝗀⁡(f+g)\operatorname{\textsf{mdeg}}(f+g) und 𝗆𝖽𝖾𝗀⁡(f),𝗆𝖽𝖾𝗀⁡(g)\operatorname{\textsf{mdeg}}(f),\operatorname{\textsf{mdeg}}(g)? Ggf. unter welchen Randbedingungen?

Gröbnerbasen

Begriff, Motivation

Literatur

Reduktion von Polynomen

Eigenschaften der Redukton: Termination

Eigenschaften d. Reduktion: Konfluenz?

S-Polynome

Der Buchberger-Algorithmus

Buchberger-Alg., Beispiel

Buchberger-Alg., Eigenschaften

Hausaufgaben

  1. zur Ordnung auf Monomen:

    1. unterschiedliche Ordnungen ((graded) (reverse) lexikografisch) selbst implementieren.

      instance Ord (Mono v) where ...

    2. stimmt die abgeleitete Ordnung newtype Mono v = M [(v, Natural)] deriving (Eq, Ord) mit einer dieser Ordnungen überein?

  2. zur Ordnung auf Polynomen:

    für Polynome in Variablen X>Y>ZX>Y>Z: geben Sie möglichst lange ≫\gg-Ketten an, die bei X3+Y2ZX^3+Y^2Z beginnen

    • bzgl. der lexikografische Ordnung auf Monomen

    • bzgl. der grad-lexikografische Ordnung auf Monomen

  3. Kann S(f1,f2)S(f_1,f_2) Monome mit höherem Grad enthalten als f1f_1 und f2f_2?

  4. bestimmen Sie nach dem Buchberger-Algorithmus eine Gröbner-Basis BB für I=Ideal⁡(X2Y−1,XY2−1)I=\operatorname{Ideal}(X^2Y-1,XY^2-1).

    (auf Papier, mit maxima, mit eigener Impl.)

  5. Benutzen Sie dieses BB, um X5−Y2∈IX^5 - Y^2\in I zu entscheiden.

    (Papier, maxima (poly_grobner_member), eigen)

  6. Geben Sie Polynome c1,c2c_1,c_2 mit X5−Y2=c1(X2Y−1)+c2(XY2−1)X^5-Y^2= c_1(X^2Y-1)+c_2 (XY^2-1) an.

    Erweitern Sie dazu den Buchberger-Alg. und das Reduktionsverfahren →B\to_B.

    (zum Vergleich: Euklid bestimmt gcd⁡(a,b)\gcd(a,b), erweiterter Euklid bestimmt c,dc,d mit ac+bd=gcd⁡(a,b)ac+bd=\gcd(a,b).)

  7. Eine Gröbner-Basis BB heißt reduziert, wenn ∀b∈B:¬∃c:b→B\{b}c\forall b\in B: \neg\exists c: b\to_{B\setminus\{b\}}c.

    (bb kann nicht durch die jeweils anderen Basis-Elemente reduziert werden)

    Ist die Basis auf Folie Buchberger-Bsp. reduziert? Wenn nein, bestimmen sie eine reduzierte B′B'.

    Ergänzen Sie die Eigenbau-Implementierung.

    Probieren Sie verschiedene Monom-Ordnungen.

    Die reduzierte Gröbner-Basis eines Polynom-Ideals ist im wesentlichen eindeutig.

  8. Arjen Cohen: Gröbner Bases, an Introduction (in: Some Tapas of Computer Algebra, Springer, 1999):

    it is very hard to provide a good explicit upper bound on [die Laufzeit des Buchberger-Algorithmus], bad examples are known.

    Finden Sie solche bad examples

    1. selbst ausdenken

    2. mit Suchmaschine (welche Testfälle werden in Publikationen verwendet, die verbesserte Algorithmen beschreiben)

    3. brute force

    und messen Sie den Ressourcenverbrauch (maxima, Eigenbau)

Gröberbasen in der Geometrie

Beispiel

Aufgaben und Anschauung Geometrie

  1. Coxeter und Greitzer: Geometry Revisited, 1967

    Bsp. 9-Punkte-Kreis (Feuerbachkreis) Kap. 1.8

  2. Intl. Math. Olympiade, Bsp: Aufgabe 2024/4 https://www.imo-official.org/problems.aspx

  3. dynamische Geometrie-Software Geonext (Univ. Bayreuth, Mathematikdidaktik)

    https://web.archive.org/web/20130605045826/http://geonext.uni-bayreuth.de/

    /opt/jdk/jdk8u442-b06/bin/java -cp /opt/geonext/geonext-1.74/geonext.jar geonext.Geonext

    Export der Zeichenvorschrift im Format i2g

Methode

Methode (Variante)

Anwendungen

Hausaufgaben

  1. Beispiele für geometrische Theoreme aus Skript Gräbe 2018 (Simsonsche Gerade, Miquelscher Punkt, …)

    • mit Geogebra zeichnen, Theorem überprüfen (durch Betrachtung der Lage bei Verschieben von Punkten)

    • algebraisieren (automatisieren!)

    • nach beschriebenen Verfahren lösen (Gröberbasis mit verschiedenen CAS ausrechnen)

  2. ein falsches Theorem beweisen (um zu sehen, wie die Methode die Falsch-Aussage erkennt)

  3. noch offene Aufgaben aus vorigen Wochen, insbesondere zur Eigenimplementierung von Polynomen (Division!) und Buchberger-Algorithmus

  4. bad examples (für Buchberger-Algorithmus) in verschiedenen CAS (viele naive Algebraisierungen von geometrischen Sätzen ergeben aufwendige Rechnungen, aber es gibt auch kleinere schwere Testfälle)

    Beispiel (Verallgemeinerung? Quelle?)

    cyclic4 =
  let [a,b,c,d] = map (var . V) [1 .. 4]
  in  [ a*b*c*d-1
      , a*b*c+b*c*d+c*d*a+d*a*b
      , a*b+b*c+c*d+d*a
      , a+b+c+d
      ]

  5. den Rabinovitch-Trick anwenden für den Satz über die Simson-Gerade in allgemeiner Lage (nur ein Punkt ist fixiert)

    fsimson = prove $ do
  ...
  return $ colinear a' b' c'

    die letzte Zeile ersetzen durch

      z0 <- number
  assert $ ...
  return $ ...

    und Laufzeiten (der naiven Implementierung sowie anderer CAS) vergleichen

  6. die Behandlung von Degenerations-Bedingungen,

    Beispiel: der Satz von Pappus

    pappus = prove $ do
  a  <- point ; b  <- point; c  <- point_on a  b
  a' <- point ; b' <- point; c' <- point_on a' b'
  p <- intersection b c' b' c
  q <- intersection a c' a' c
  r <- intersection a b' a' b
  return $ -- degenerate cases:
           parallel (b-c') (b'-c)
         * parallel (a-c') (a'-c)
         * parallel (a-b') (a'-b)
           -- actual conclusion:
         * colinear p q r

  7. bessere Implementierungen des Buchberger-Verfahrens: nicht jedesmal alle S-Polynome bestimmen und bezüglich aller bisherigen reduzieren.

    Zum Code in poly/Grobner.hs:

    • die Invarianten beweisen

    • die Termination begründen

      • für jede einzelne Reduktion eines (S-)Polynoms

      • für das gesamte Buchberger-Verfahren

Plan (vorläufig)