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 \(\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 \(\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

Ganze Zahlen

Rationale Zahlen

Explosion der Stellenanzahl (Beispiel)

Endliche und unendliche Dezimalbrüche

Berechenbare reelle Zahlen

Potenzreihen, Exponentialfunktion

Potenzreihe für Wurzelfunktion

Logarithmen

Taylor-Entwicklung \(\log(1+x)=x-x^2/2+x^3/3- \ldots\)

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

J.R. Young, 1835, siehe v. Mangoldt/Knopp, Bd. 2, S. 127 \[\begin{aligned} a = \log (16/15) &=& 4\log 2-1 \log 3-\log 5, \\ b = \log (25/24) &=& \dots \\ c = \log (81/80) &=& \dots \end{aligned}\] Umstellung ergibt \(\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 = x - x^3/3 + x^5/5 - \dots\]

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

Hausaufgaben

  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. diskutieren (Zusatz: implementieren) Sie die Darstellung von ganzen Zahlen mit negativer Basis \(B\le -2\)

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

    Bsp: \(B=-2\),

    \(-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)

  3. 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)\) auf (z.B.) 20 Stellen.

    Begründen Sie \(x+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)

  4. 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)\) auf (z.B.) 100 Stellen und daraus \(\log 2\) als eine Linearkombination.

  5. wie bestimmt man \(\sqrt{3}\), \(\sqrt{5}\), \(\sqrt[3]{2}\)

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

    diese Gewichte ergeben quadratische Konvergenz,

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

    \(f'(x)=3x^2, x\mapsto x - f(x)/f'(x) = \dots\)

  6. 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

Automatische Differentiation

Motivation, Anwendung

Verfahren zur Gradientenbestimmung

Automatische Differentiation (AD)

Stochastischer Gradientenabstieg

Anwendung: Matrix-Interpretationen

Constraint-Lösen durch Optimieren

Literatur und Software (funktionaler) AD

Aufgaben

  1. (H. Rosenbrock 1960) ein Test für Abstiegsverfahren ist \(f(x,y)=(x^2-y)^2 + y^2/100\),

    Veranschaulichen Sie den Werteverlauf mit rlwrap maxima

    f : (x^2-y)^2 + y^2/100;
plot3d(f,[x,-50,50],[y,-1000,3000]);

    wo ist das globale Minimum?

    in welche Richtung geht der (entgegengesetze) Gradient im Punkt \((20,100)\),

    wo verläuft die Folge der Näherungswerte, wird das globale Minimum erreicht? (1. diskutieren, 2. ausprobieren)

  2. für den Typ N v z: weitere Funktionen implementieren (Division, recip, sqrt, exp, log),

    den so bestimmten Wert des Gradienten mit numerischer Differentiation vergleichen

    diese Fkt. in einer Minimum-Bestimmung verwenden

  3. in neuronalen Netzen wird oft die Funktion \(S : x\mapsto 1/(1+\exp(-x))\) verwendet (sie bildet \(\RR\) monoton steigend auf \([0,1]\) ab)

    bestimmen Sie deren Ableitung symbolisch (zu Fuß oder Maxima), vergleichen mit AD-Implementierung (vorige Aufgabe)

  4. (Fortsetzung) ein \(k\)-stelliges Neuron mit Gewichten \(w_0,w_1,\dots,w_k\in\RR\) ist die Funktion \(x \mapsto S(w_0+\sum_i w_i x_i)\).

    ein vollständig verbundenes Netz mit \(e\) Eingängen und \(n\) Neuronen: das Neuron \(i\) sieht alle Eingänge sowie die Ausgänge der Neuronen \(1 \dots i-1\).

    Bestimmen Sie (mit stochastischem Gradientenabstieg mit AD) die Gewichte eines vollständigen Netzes (mit möglichst wenig Neuronen) für

    • XOR über alle Eingänge

    • Majoriät (falls \(s\) ungerade)

  5. für Optimierungsverfahren 2. Ordnung benötigt man die Hesse-Matrix einer Funktion (diese enthält alle zweiten Ableitungen). Modellieren und berechnen Sie diese durch eine Erweiterung des Typs data N v z.

    Vergleichen Sie mit exakten Werten (Bsp. maxima: hessian((x^2-y)^2,[x,y]);)

  6. (Forschungsaufgabe) Matrix-Interpretationen für Wortersetzungssysteme

    • verbesserte Modellierung (der Zielfunktion) und Parameter (Schrittweite)

    • stochastischer Abstieg (1. Ordnung)

    • Abstiegsverfahren 2. Ord. (oder Quasi-Newton)

    Testfälle

    • (leicht) \(a\to b\), \(ab\to ba\), \(ab\to bba\), \(aa\to aba\),

    • (schwerer) \(a^2b^2\to b^3a^3\), \(\{a^2\to bc, b^2\to ac, c^2\to ab\}\)

      System mit 3 Regeln: es genügt \(>_M\) für eine Regel, für die anderen \(\ge_M\). Wie kann man diese Bedingung als Zielfunktion einer Optimierung realisieren?

      ganzzahlige Lösungen sind bekannt (gefunden durch Bit-Blasting) gibt es kleinere nicht-ganzzahlige?

Polynome

Motivation (I): Polynom-Interpretationen

Motivation (II): Algebraische Zahlen

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

\[\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 \(\le 6\)), ergibt Darstellung von \(y^6\) als rationale Linearkombination von \(y^0,\dots, y^5\).

Motivation (III): Geometrische Örter

Semantik und Syntax von Polynomen

Gruppen, Ringe, Körper

Polynome in einer Variablen

Polynom-Division (über \(\QQ\))

Polynome in mehreren Variablen

Polynom-Darstellung als geordnete Liste

Listen-Darstellung f. mehr Var.

Ideale

Hausaufgaben

  1. Bezeichnungen:

    arithmetisches Mittel \(A(x_1,\dots,x_n)=(\sum x_i)/n\), geometrisches Mittel \(G(x_1,\dots,x_n)=\sqrt[n]{\prod x_i)}\).

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

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

    \(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(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)\) im Nenner geschrieben werden. Dazu die SOS-Darstellung der A-G-Ungleichung für die 4 Werte \(x_1,x_2,x_3,t=A(x_1,x_2,x_3)\) benutzen, denn \(A(x_1,x_2,x_3,t)=t\) und \(G(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 \(\sqrt{2}+\sqrt[3]{3}\) nach angegebenem Verfahren ausrechnen und überprüfen.

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

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

    o.B.d.A \(A_1=A_2=B_1=0\) annehmen.

    Warum wäre zusätzlich \(C_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 \(X^{pq}-1\) durch \(X^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=X^2Y + XY^2 + Y^2, Q=XY-1, R=Y^2-1\):

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

    Hinweis: nein. Hinweis: Betrachten Sie Werte von \(P\) für die gemeinsamen Nullstellen von \(Q,R\).

  6. gilt \(X^5-Y^2 \in\operatorname{Ideal}(X^2Y-1,XY^2-1)\)?

    Welches Resultat liefert der Nullstellentest?

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

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

  9. der arktische Halbring \(\mathbb{A}=(\{-\infty\}\cup\NN,\max,-\infty,+,0)\).

    Ist \(\deg\) homomorph (strukturerhaltend) von \((\ZZ[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 > Y\)) \(X^3Y^2 > X^1Y^3\), \(X^3Y^2 > X^4Y^1\).

    Welche Eigenschaft(en) gehen dabei ohne Gradierung verloren?

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

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

    Bsp.: für \(X>Y\) ist \(\operatorname{\textsf{mdeg}}(X^2Y^5)=[2,5]\),

    für lex-Ordnung ist \(\operatorname{\textsf{mdeg}}(X^2Y^5-X^8)=[8,0]\).

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

    Welche Beziehung zw. \(\operatorname{\textsf{mdeg}}(f+g)\) und \(\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>Z\): geben Sie möglichst lange \(\gg\)-Ketten an, die bei \(X^3+Y^2Z\) beginnen

    • bzgl. der lexikografische Ordnung auf Monomen

    • bzgl. der grad-lexikografische Ordnung auf Monomen

  3. Kann \(S(f_1,f_2)\) Monome mit höherem Grad enthalten als \(f_1\) und \(f_2\)?

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

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

  5. Benutzen Sie dieses \(B\), um \(X^5 - Y^2\in I\) zu entscheiden.

    (Papier, maxima (poly_grobner_member), eigen)

  6. Geben Sie Polynome \(c_1,c_2\) mit \(X^5-Y^2= c_1(X^2Y-1)+c_2 (XY^2-1)\) an.

    Erweitern Sie dazu den Buchberger-Alg. und das Reduktionsverfahren \(\to_B\).

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

  7. Eine Gröbner-Basis \(B\) heißt reduziert, wenn \(\forall b\in B: \neg\exists c: b\to_{B\setminus\{b\}}c\).

    (\(b\) 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'\).

    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)

Plan (vorläufig)