Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik ::

Numerische Algorithmen und Mathematik

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik ::

Numerische Algorithmen und Mathematik

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik ::

Numerische Algorithmen und Mathematik

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Mathematik

Mathematik

Algorithmen

Funktionen

Datenstrukturen

Funktionen (!), Vektoren, Matrizen, Tensoren usw.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Künstliche Intelligenz

Künstliche Intelligenz

Algorithmen

Iterative Trainingsalgorithmen, Vereinfachung

Datenstrukturen

Funktionen, Datengraphen und Bäume, Funktionsgraphen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Numerik

Numerik

numalg Beziehung der Numerik zu anderen Bereichen:

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Numerik

Numerik

Das Ziel der Numerik ist die Konstruktion ökonomischer (effizienter) und stabiler Algorithmen. Speziell gilt es, mögliche Fehlerquellen zu berücksichtigen. Diese ergeben sich durch Modellierungsfehler, durch Fehler in den Eingangsdaten, durch Fehler im Algorithmus, und durch Diskretisierungsfehler in der Numerik.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Numerik: Anwendungen und Probleme

Numerik: Anwendungen und Probleme

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Numerik: Anwendungen und Probleme

Numerik: Anwendungen und Probleme

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Numerik: Anwendungen und Probleme

Numerik: Anwendungen und Probleme

• Wir werden einige überraschende Ergebnisse sehen und dass Numerik (und die Ergebnisse daraus) ähnlich verwirrend und unerwartet sein können wie bei der Betriebssystemprogrammierung!

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Numerik: Fehleranalyse

Numerik: Fehleranalyse

Wir haben bei numerischen Problemen folgende Randbedingungen zu berücksichtigen:

1. Kondition
2. Rundungsfehler
3. Stabilität

algomat Beim Ausführen von Rechnungen gibt es verschiedene Fehlerquellen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Numerik: Fehleranalyse

Numerik: Fehleranalyse

Kondition eines Problems

Die Kondition eines Problems gibt an, welche Genauigkeit man bei exakter Lösung bestenfalls erreichen kann: Ein Problem heißt gut konditioniert, wenn kleine Störungen der Eingangsdaten kleine Änderungen im Ergebnis bewirken, sonst schlecht konditioniert.

Rundungsfehler

In der Mathematik werden kontinuierliche und gar unendlich große Zahlenmenge betrachtet (reele Zahlen). In der Numerik haben wir immer diskerete und begrenzte Wertemengen!. Daher sind numerische Verfahren immer ungenauer als mathematische.

Stabilität

Iterative Algorithmen können eine "richtige" Lösung liefern (Konvergenz), können aber auch falsche Ergebnisse liefern (Divergenz). Man versucht Algorithmen stabil gegen Divergenz zu machen.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Numerik und Zahlensysteme

Numerik und Zahlensysteme

Mathematisch können wir zwei Basismengen von Zahlen unterscheiden:

Ganze Zahlen ℕ

Eine unendlich große Menge ganzer positiver und negativer Zahlen inklusive 0. Aber die Menge ist abzählbar! Es gibt keine weitere ganze Zahl in jedem Intervall [x,x+1].

Reelle Zahlen ℝ

Eine unendlich große Menge kontinuierlicher positiver und negativer Zahlen inklusive 0. Aber die Menge ist nicht abzählbar! Es gibt unendlich viele weitere Zahlen in jedem Intervall [x,x+δ], egal wie klein man das Intervall macht.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Computer Zahlensysteme

Computer Zahlensysteme

Maschinenzahlen und Rundungsfehler

Maschinenzahlen werden durch Datenbits repräsentiert (kodiert).

Ganze Zahlen (Integer Datentyp)

Eine endlich große Menge ganzer positiver und negativer Zahlen inklusive 0. Es gibt keine weitere ganze Zahl in jedem Intervall [x,x+1].

Festpunktzahlen (Fixed Point Datentyp)

Eine endlich große Menge diskreter positiver und negativer Zahlen inklusive 0. Aber es gibt keine weiter Zahl in einem kleinen Intervall [x,x+δ_min], δ_min ist absolut und hängt von der Anzahl der Datenbits und der absoluten Größe des Zahlenintervalls ab! Eigentlich ganze Zahlen mit einem festen verschobenen Dezimalpunkt.

Gleitkommazahlen (Floating Point Datentyp)

Eine endlich große Menge diskreter positiver und negativer Zahlen inklusive 0. Aber es gibt keine weiter Zahl in einem kleinen Intervall [x,x+δ_min], δ_min ist relativ und hängt von der Anzahl der Datenbits ab!

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Computer Zahlensysteme

Computer Zahlensysteme

Integer Zahlen

Die digitalen Zahlen (Kodierung) d kann man in dezimale mit der gewichteten Summe umrechnen (Binärzahlensystem mit Basis b=2):

$${a}={\left(-{1}\right)}^{{s}}{\sum_{{{i}={0}}}^{{{m}-{1}}}}{d}_{{i}}\cdot{b}^{{i}}$$

algomat Zahlenbereich hängt von der Anzahl Bits ab (m). Für das Vorzeichen kommt noch ein Bit hinzu (oder der Zahlenbereich verringert sich). Es gibt keinen Rundungsfehler!

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Arithmetik

Arithmetik

Es gibt die grundlegenden numerischen arithmetischen Operationen:

1. Addition (Subtraktion)
2. Multiplikation (Division)
3. Negierung

a=1; b=10; c=100;
x1 = (a/b)*c
x2 = (a*c)/b
print(x1,x2)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Arithmetik

Das Experiment (Hinweis: JavaScript verarbeitet alle Zahlen als Gleitkommazahlen, daher ist Umwandlung in Integer erforderlich)

+

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Arithmetik

Gleitkommazahlen

$${a}={\left(-{1}\right)}^{{s}}{\sum_{{{i}={0}}}^{{{m}-{1}}}}{d}_{{i}}\cdot{b}^{{-{i}+{e}}}$$

Eigenschaften verschiedener Datenformate bei Gleitkommazahlen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Rundungsfehler

Rundungsfehler

• oder richtig ausgedrückt Diskretisierungsfehler bezüglich des Zahlensystems und deren Kodierung (da niemand explizit rundet)

• Rundungsfehler, Über- und Unterlauf und "Not a Number NaN" können bei arithmetischen Operationen auftreten.

Diskretisierung

• Die Diskretisierung von Integer Zahlen ist ohne Genauigkeitsverlust möglich, nur die Wertemenge ist begrenzt

• Die Diskretisierung von reellen Zahlen ist i.A. immer mit Genauigkeitsverlust und einer Einschränkung der Wertemenge verbunden (also schon hier Rundungsfehler möglich)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Rundungsfehler

Rundungsfehler

Arithmetik

• Arithmetische Operationen wie Division können bei ganzen Zahlen zu erheblichen Rundungsfehlern führen (bis zu 100%), Addition und Multiplikation führen keine weiteren Rundungsfehler ein, können aber zum Überlauf bei Integer Zahlen führen!

• Arithmetische Operationen können bei Gleitkommazahlen (aber nicht reellen) zu Rundungsfehlern führen (bis zu 1%), und es kann zum Überlauf kommen!

• Im Bereich der ML Algorithmen spricht man vom verschwindenden Gradienten (auch ein Quotient mit Divisionsoperation)
• Bei Gleitpunktarithmetik gibt es eine Fehlerverstärkung bei den elementaren Rechenoperationen!

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Funktionen und Schleifen

Funktionen und Schleifen

• Funktionsrekursion ist eine gängige Methode in der Mathematik um eine Berechnung auszudrücken.
• Programmatisch können wir in fast allen Programmiersprachen die Funktionsrekursion nutzen, es gibt aber auch Nachteile (welche?)
• Man kann rekursive Funktionen in Schleifen transformieren und umgekehrt!

function fac(n) {
  if (n<2) return 1
  else return n*fac(n-1)
}

y=1
for(i=2;i<=n;i++) {
  y=y*i
}

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Algorithmus 1: Berechnung von e

Algorithmus 1: Berechnung von e

numalg pp 6

1. Grenzwert

$${e}=\lim_{{{n}\to\infty}}{\left({1}+\frac{{x}}{{n}}\right)}^{{n}}$$

für x=1 berechnen.

⇒ Grenzwerte können nicht direkt prozedural (iterativ) algorithmisch gelöst werden (deklarative und symbolische Methodik erforderlich). Nur endliche Approximation möglich!

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Algorithmus 1: Berechnung von e

Algorithmus 1: Berechnung von e

n=100
e=pow(1+1/n,n)
print(e)

+

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Algorithmus 1: Berechnung von e

Algorithmus 1: Berechnung von e

2. Summe: Eine andere Möglichkeit ist, die Funktion

$${e}^{{x}}={\sum_{{{n}={0}}}^{{\infty}}}\frac{{x}^{{n}}}{{{n}!}}$$

für x=1 zu berechnen.

e=0;N=100
function fac(n) { return n<2?1:n*fac(n-1) } 
for(n=0;n<=N;n++) {
  e=e+1/fac(n)
}
print(e)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Algorithmus 1: Berechnung von e

Algorithmus 1: Berechnung von e

+

Stefan Bosse - Algorithmen und Datenstrukturen - Modul B Numerische Algorithmen und Mathematik :: Algorithmus 1: Berechnung von e

Algorithmus 1: Berechnung von e

numalg