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?