Algorithmen der Computeralgebra
und Schulmathematik
Prof. Dr. Wolfram Koepf
Fachbereich Mathematik/Informatik
Universität Gh Kassel
[email protected]
http://www.mathematik.uni-kassel.de/~koepf
T3 - Tagung
Ludwig-Windthorst-Haus
Lingen (Ems)
19. Oktober 2001
Fachgruppe Computeralgebra
•
•
•
•
Fachgruppe der DMV, GI, GAMM
Regelmäßige Herausgabe des Rundbriefs
Referent für Didaktik
Regelmäßige Tagungen zum Thema
„Computeralgebra in Lehre, Ausbildung und
Weiterbildung“
• Informationen auf meiner Homepage
http://www.mathematik.uni-kassel.de/~koepf
• Homepage http://www.gwdg.de/~cais
Mein persönlicher ComputeralgebraWerdegang
• 1988: Erster Kontakt mit Computeralgebra
(Reduce, Maple, Mathematica, DERIVE)
• 1990: Stipendium der Alexander von Humboldt-Stiftung. Forschungsprojekt zur
Verwendung von Computeralgebrasystemen im
Mathematikunterricht
• 1992: Analysis-Vorlesungen an der Freien
Universität Berlin mit DERIVE
• 1993: Lehrbuch Mathematik mit DERIVE
• 1993-1997: Mitarbeiter am Konrad-ZuseZentrum für Informationstechnik in Berlin
• 1994: Buch Höhere Analysis mit DERIVE
• 1996: Buch DERIVE für den Mathematikunterricht
• 1996-heute: Gewähltes Mitglied der
Leitung der Fachgruppe Computeralgebra
der DMV/GI/GAMM, Referent für Lehre
und Didaktik
• 1997-2000: Professor für Angewandte
Mathematik an der Hochschule für Technik,
Wirtschaft und Kultur Leipzig
• 1998: Buch Hypergeometric Summation
• seit 2000: Professor für Computational
Mathematics an der Universität Gh Kassel
• 2000: Buch Die reellen Zahlen als
Fundament und Baustein der Analysis
Kleiner Satz von Fermat
• Für eine Primzahl p   und a  gilt
ap = a (mod p)
• Fermattest: Ist diese Beziehung für eine
Zahl a  nicht erfüllt, so ist p keine
Primzahl!
Euklidischer Algorithmus
• Den größten gemeinsamen Teiler von a und
b berechnet man so:
•
•
•
•
ggT(a,b) = ggT(|a|,|b|), falls a<0 oder b<0
ggT(a,b) = ggT(b,a), falls a<b
ggT(a,0) = a
ggT(a,b) = ggT(b, a mod b)
Effiziente Berechnung von
Potenzen
• Die modulare Potenz an (mod p) berechnet
man am besten durch Zurückführen auf
Exponenten der Größe n/2 (Divide-andConquer-Algorithmus):
• a0 mod p = 1
• an mod p = (an/2 mod p)2 mod p für gerade n
• an mod p = (an-1 mod p) . a mod p
Algebraische Zahlen
• Algebraische Zahlen sind als Nullstellen
ganzzahliger Polynome erklärt, z. B.
• 2: x2 - 2
• i: x2 + 1
• 2 + 3: x4 - 10 x2 + 1
• 2 + 3 + 5 :
x8 - 40 x6 + 352 x4 - 960 x2 + 576
Faktorisierung von Polynomen
• Polynome mit rationalen Koeffizienten können
algorithmisch faktorisiert werden!
• Dies funktioniert sogar, wenn mehrere Variablen
im Spiel sind.
• Algorithmische Faktorisierungen über  dagegen
sind nur unter Verwendung algebraischer Zahlen
möglich, z. B. x2-2 = (x-2)(x+2).
• Moderne schnelle Algorithmen gibt es nicht in
DERIVE, aber in Maple, Mathematica, ...
Wo ist der zweite Pol?
• Während graphische Taschenrechner und
Computeralgebrasysteme im Allgemeinen
auf Anhieb Funktionsgraphen darstellen,
gibt es auch Fälle, wo hierzu
Kurvenuntersuchungen nötig sind.
• Wo ist der zweite Pol der Funktion
1000 ( x 1)
(101 x 100 )(100 x 99 )
Lineare Gleichungssysteme
• Lineare Gleichungssysteme sind schlecht
konditioniert, wenn die zugehörigen
Geraden bzw. Ebenen etc. fast parallel sind.
• Dann lassen sich offenbar die Schnittpunkte
bzw. Schnittgeraden etc. nur ungenau
bestimmen.
Kondition einer Matrix
• Eine Matrix ist schlecht konditioniert, wenn
sie oder ihre Inverse Eingabefehler stark
vergrößern.
• Für eine Matrixnorm, z. B.
A : a jk  max a jk
ist die Konditionszahl
1


A
:

A

A
cond
ein Maß für die Kondition der Matrix A.
Hilbertmatrix
• Die n  n Hilbertmatrix
1
1
2
:

1
n
1
2
1
3
..
:
1
j  k 1
1
n 1
..
..



: 

1 
2 n 1 
1
n
1
n 1
ist schlecht konditioniert. Daher ist die Numerik
instabil. Rationale Arithmetik lässt ein Studium
der Matrizen aber zu.
Differentiation
• Ableiten ist algorithmisch, wenn wir die üblichen
Ableitungsregeln verwenden:
• Konstantenregel c´ = 0
• Potenzregel (xn)´ = n xn-1
• Linearität (f + g)´ = f ´ + g´
• Produktregel (f · g)´ = f ´·g + g´·f
• Quotientenregel (f / g)´ = (f ´·g - g´·f)/g2
• Kettenregel f(g)´ = f ´(g) · g´
• Ableitungen spezieller Funktionen
Integration
• Auch für die Integration gibt es Algorithmen,
welche entscheiden, ob ein Integral eine
elementare Funktion ist.
• Die übliche Methode zur rationalen Integration
benötigt eine reelle Faktorisierung des Nenners
und ist daher kein guter Algorithmus.
• Der Risch-Algorithmus und seine Verwandten
sind erheblich komplizierter, verwenden aber nur
quadratfreie Faktorisierungen.
Vereinfachung
• Rationale Funktionen lassen sich durch
Bestimmung des ggT vereinfachen.
• Trigonometrische Polynome lassen sich
durch Anwendung der Additionstheoreme
vereinfachen.
• Man kann zeigen, dass es für allgemeine
Terme keinen generellen
Vereinfachungsalgorithmus geben kann.
Das Hofstadterproblem
• Hofstadters geometrische Vermutung ist
richtig, wenn die Determinante der Matrix





sin( r )
sin((1 r ) )
sin( r )
sin((1 r )  )
sin( r )
sin((1 r ) )
sin( 2 )
sin(  )
sin( 2  )
sin(   )
sin( 2 )
sin(  )
sin(( 2  r ) )
sin(( r 1) )
sin(( 2  r )  )
sin(( r 1)  )
sin(( 2  r ) )
sin(( r 1) )





gleich 0 ist, sofern  +  +  =
 ist.
Reihenentwicklungen
• In der speziellen Relativitätstheorie ergibt
sich die Energie aus der Formel
 1

E (v)  m c  v2  1
 1 c2 
2
• Wie erhält man hieraus die klassische
Formel E  12 mv2 ?

Algorithmen der Computeralgebra und Schulmathematik