|
A.9.4 Numerische und verwandte Funktionen
Zahlendarstellung und numerische Evaluierung
 Große ganze Zahlen und Fließpunktzahlen hoher Präzision werden als Arrays von Ziffern in Basis  bzw.  gespeichert, entsprechend der Länge einer ganzen Zahl in Maschinengröße.
Präzision wird intern als Fließpunktzahl geführt.
IntegerDigits und verwandte Basiskonvertierungsfunktionen verwenden einen rekursiven Teile-und-herrsche-Algorithmus (divide-and-conquer).
N verwendet eine adaptive Prozedur zur Erhöhung ihrer internen Arbeitspräzision, um die jeweils geforderte Gesamtpräzision zu erreichen.
Floor, Ceiling und verwandte Funktionen verwenden eine adaptive Prozedur, ähnlich wie N, um aus exakter Eingabe exakte Ausgabe zu erzeugen.
Grundarithmetik
Die Multiplikation mit großen ganzen Zahlen und mit Fließpunktzahlen hoher Präzision erfolgt mit ineinandergeschachtelten Karatsuba- und FFT (Schnelle Foruriertransformations)-Algorithmen.
Die Potenzen ganzer Zahlen werden mit einem Algorithmus bestimmt, der auf dem Horner-Schema beruht.
Reziproke Werte und rationale Potenzen von Fließpunktzahlen verwenden Newtons Verfahren.
Exakte Nullstellenbestimmung erfolgt ausgehend von numerischen Schätzwerten.
Für Arithmetik mit Fließpunktzahlen, die mehr als Maschinenpräzision haben, wird Signifikanzarithmetik verwendet.
Die Grundarithmetik verwendet etwa 400 Seiten C-Quellcode.
Pseudo-Zufallszahlen
Random verwendet die Wolfram-Regel 30 mit dem zellulären Automatengenerator für ganze Zahlen.
Es wird ein Marsaglia-Zaman-Generator (Subtraktion mit Übertrag) für reelle Zahlen verwendet.
Zahlentheoretische Funktionen
GCD verwendet den nach Jebelean-Weber beschleunigten ggT-Algorithmus zusammen mit einer Kombination des Euklidschen Algorithmus mit einem Algorithmus, der auf der iterativen Entfernung der 2er-Potenzen basiert.
PrimeQ testet die Teilbarkeit zuerst mit kleinen Primzahlen, dann mit dem strengen Miller-Rabin-Pseudo-Primzahlentest zur Basis 2 und 3 und anschließend mit einem Lucas-Test.
Nach dem Stand von 1997 ist diese Prozedur nur für  als korrekt bewiesen, für größere  könnte eine zusammengesetzte Zahl als Primzahl ausgewiesen werden.
Das Paket NumberTheory`PrimeQ` enthält einen viel langsameren Algorithmus, dessen Korrektheit für alle  bewiesen ist. Er kann eine explizite Bestätigung der Primzahleneigenschaft liefern.
FactorInteger wechselt zwischen Entfernung kleiner Primzahlen mittels versuchsweiser Division und der Verwendung des Pollard  -, Pollard Rho- und Kettenbruch-Algorithmus hin und her.
Das Paket NumberTheory`FactorIntegerECM` enthält einen elliptischen Algorithmus, der sich zur Faktorisierung einiger sehr großer ganzer Zahlen eignet.
Prime und PrimePi verwenden Pufferung einzelner Werte und Sieben. Für große  wird für PrimePi der Lagarias-Miller-Odlyzko-Algorithmus verwendet, der auf asymptotischen Schätzungen der Primzahlendichte basiert und invertiert wird, um Prime zu liefern.
LatticeReduce verwendet den Lenstra-Lenstra-Lovasz-Gitterreduzierungs-Algorithmus.
Für die Ermittlung einer gewünschten Anzahl Terme setzt ContinuedFraction eine Modifizierung von Lehmers indirekter Methode ein, dabei wird zur Reduzierung der in jedem Schritt erforderlichen numerischen Präzison ein von selbst erneut startender Teile-und-herrsche-Algorithmus eingesetzt.
ContinuedFraction verwendet Rekursionsformeln, um für quadratische irrationale Zahlen periodische Kettenbrüche zu finden.
FromContinuedFraction verwendet iterierte Matrizenmultiplikation, optimiert durch eine Teile-und-herrsche-Methode.
Kombinatorische Funktionen
Die meisten kombinatorischen Funktionen verwenden geringe Pufferung und Rekursion.
Factorial, Binomial und verwandte Funktionen verwenden einen Teile-und-herrsche-Algorithmus, um die Stellenanzahl in Unterprodukten auszugleichen.
Fibonacci[n] verwendet eine iterative Methode, die auf der Binärziffernfolge von n basiert.
PartitionsP[n] verwendet die Eulersche Pentagonalformel für kleine n und die nichtrekursive Hardy-Ramanujan-Rademacher-Methode für größere n.
ClebschGordan und verwandte Funktionen verwenden verallgemeinerte hypergeometrische Reihen.
Elementare transzendente Funktionen
Exponentielle und trigonometrische Funktionen verwenden Taylor-Reihen, stabile Rekursion durch Argumentverdopplung und funktionale Relationen.
Logarithmische und inverse trigonometrische Funktionen verwenden Taylor-Reihen sowie funktionale Relationen.
Mathematische Konstanten
Werte von Konstanten werden im Cache abgelegt, sobald sie berechnet sind.
Mit binärer Aufspaltung werden Berechnungen von Konstanten unterteilt.
Pi verwendet die Chudnovsky-Formel für Berechnungen von bis zu zehn Millionen Stellen.
E wird aus ihrer Reihenentwicklung berechnet.
EulerGamma verwendet den Brent-McMillan-Algorithmus.
Catalan wird aus einer linear konvergenten Ramanujan-Summe berechnet.
Spezielle Funktionen
Für Berechnungen in Maschinenpräzision verwenden die meisten speziellen Funktionen mit Mathematica hergeleitete rationale Minimax-Näherungen. Die folgenden Anmerkungen gelten hauptsächlich bei beliebiger Präzision.
Orthogonale Polynome verwenden stabile Rekursionsformeln für polynomiale Fälle und hypergeometrische Funktionen im allgemeinen.
Gamma verwendet Rekursion, Funktionalgleichungen und die Binetsche asymptotische Formel.
Unvollständige Gamma- und Beta-Funktionen verwenden hypergeometrische Reihen und Kettenbrüche.
PolyGamma verwendet Euler-Maclaurin-Summierung, Funktionalgleichungen und Rekursion.
PolyLog verwendet Euler-Maclaurin-Summierung, Entwicklungen mit unvollständigen Gamma-Funktionen und numerische Quadratur.
Zeta und verwandte Funktionen verwenden Euler-Maclaurin-Summierung und Funktionalgleichungen. In der Nähe des kritischen Streifens verwenden sie außerdem die Riemann-Siegel-Formel.
StieltjesGamma verwendet den Keiper-Algorithmus, der auf der numerischen Quadratur einer Integraldarstellung der Zetafunktion basiert.
Die Fehlerfunktion und die mit Exponentialintegralen verwandten Funktionen werden alle mit unvollständigen Gamma-Funktionen evaluiert.
Die inversen Fehlerfunktionen verwenden Binomialsuche und eine verallgemeinerte Newton-Methode hoher Ordnung.
Bessel-Funktionen verwenden Reihen und asymptotische Entwicklungen. Einige verwenden für ganzzahlige Ordnungen auch stabile Vorwärtsrekursion.
Die hypergeometrischen Funktionen verwenden Funktionalgleichungen, stabile rekurrente Relationen, Reihenentwicklung und asymptotische Reihen. Manchmal werden auch Methoden von NSum und NIntegrate verwendet.
ProductLog verwendet eine Newton-Methode hoher Ordnung, die von rationalen Näherungen und asymptotischen Entwicklungen aus startet.
Elliptische Integrale werden mit der abfallenden Gauß-Transformation evaluiert.
Elliptische Theta-Funktionen verwenden Reihen-Summierung mit rekursiver Evaluierung von Reihengliedern.
Andere elliptische Funktionen verwenden meistens arithmetisch-geometrische Mittelwert-Methoden.
Mathieu-Funktionen verwenden Fourier-Reihen. Die Mathieu-Charakteristik-Funktionen verwenden Verallgemeinerungen der Blanch-Newton-Methode.
Numerische Integration
Bei Method->Automatic verwendet NIntegrate GaussKronrod in einer Dimension und ansonsten MultiDimensional.
Wenn für MaxPoints eine explizite Einstellung gegeben ist, verwendet NIntegrate vorgabemäßig Method->QuasiMonteCarlo.
GaussKronrod: Adaptive Gauß-Quadratur mit Fehlerabschätzung, die auf der Evaluierung an Kronrod-Punkten basiert.
DoubleExponential: nichtadaptive doppelt-exponentielle Quadratur.
Trapezoidal: elementare Trapez-Methode.
Oscillatory: Transformation für die Bearbeitung von Integralen, die trigonometrische und Bessel-Funktionen enthalten.
MultiDimensional: adaptiver Genz-Malik-Algorithmus.
MonteCarlo: nichtadaptive Monte Carlo-Methode.
QuasiMonteCarlo: nichtadaptiver Halton-Hammersley-Wozniakowski-Algorithmus.
Numerische Summen und Produkte
Wenn das Quotientenkriterium nicht 1 ergibt, wird der Wynn-Epsilon-Algorithmus auf eine Folge von Partialsummen oder -produkten angewendet.
Ansonsten wird die Euler-Maclaurin-Summierung mit Integrate oder NIntegrate verwendet.
Numerische Differentialgleichungen
Bei Method->Automatic schaltet NDSolve zwischen einer nichtsteifen Adams-Methode und einer steifen Gear-Methode hin und her, basierend auf LSODE.
Adams: implizite Adams-Methode der Ordnung 1 bis 12.
Gear: Rückwärtsdifferenzen-Methode der Ordnung 1 bis 5.
RungeKutta: Runge-Kutta-Methode der Fehlberg-Ordnung 4-5 für nichtsteife Gleichungen.
Für lineare Randwertprobleme wird die Gel'fand-Lokutsiyevskii-Verfolgungs-Methode verwendet.
Für 1+1-dimensionale PDGL wird die Linienmethode verwendet.
Der Code für NDSolve ist ungefähr 500 Seiten lang.
Approximatives Lösen und Minimieren von Gleichungen
Die Ermittlung von Polynomnullstellen erfolgt auf der Grundlage des Jenkins-Traub-Algorithmus.
Solve und NSolve verwenden für schwach besetzte lineare Systeme verschiedene effiziente numerische Methoden, wobei die meisten auf der Gauß-Faktorisierung mit Markowitz-Produkten basieren (ungefähr 250 Seiten Code).
Für Systeme algebraischer Gleichungen berechnet NSolve eine numerische Gröbner-Basis und verwendet dabei eine effiziente monomiale Ordnung, anschließend werden die numerischen Wurzeln mit Eigenwertmethoden herausgezogen.
FindRoot verwendet eine gedämpfte Newton-Methode, die Sekantenmethode und die Brent-Methode.
Bei Method->Automatic verwendet FindMinimum unterschiedliche, auf Brent zurückgehende, Methoden: den konjugierten Gradienten bei einer Dimension und eine Modifikation der Powell-Methode bei mehreren Dimensionen.
Ist die zu minimierende Funktion eine Summe von Quadraten, so verwendet FindMinimum die Levenberg-Marquant-Methode (Method->LevenbergMarquant).
Mit der Einstellung Method->Newton verwendet FindMinimum die Newton-Methode. Mit der Einstellung Method->QuasiNewton verwendet FindMinimum die BFGS-Version der Quasi-Newton-Methode.
ConstrainedMax und verwandte Funktionen verwenden eine erweiterte Version des Simplex-Algorithmus.
Datenmanipulation
Fourier verwendet den FFT-Algorithmus mit Zerlegung der Längen in Primfaktoren. Sind die Primfaktoren groß, so werden schnelle Faltungsmethoden eingesetzt, um eine asymptotische Komplexität  zu erhalten.
Für reellwertige Eingabe verwendet Fourier eine reelle Transformationsmethode.
ListConvolve und ListCorrelate setzen FFT-Algorithmen ein, wenn dies möglich ist.
InterpolatingFunction verwendet geteilte Differenzen, um Lagrange- oder Hermite-interpolierende Polynome zu konstruieren.
Fit berechnet das Produkt aus dem Vektor der abhängigen Variablen mit der Pseudoinversen der Design-Matrix.
Approximative numerische lineare Algebra
In der Regel werden maschinenpräzise Matrizen zur Verarbeitung in eine spezielle interne Darstellung konvertiert.
Es werden, falls es paßt, Algorithmen verwendet, die ähnlich jenen von LINPACK, EISPACK und LAPACK sind.
LUDecomposition, Inverse, RowReduce und Det verwenden die Gauß-Elimination mit Teilpivotisierung. LinearSolve verwendet die gleichen Methoden zusammen mit iterativer Nachbesserung für Zahlen hoher Präzision.
SingularValues verwendet den QR-Algorithmus mit Givens-Rotationen. PseudoInverse und NullSpace basieren auf SingularValues.
QRDecomposition verwendet Householder-Transformationen.
SchurDecomposition verwendet QR-Iteration.
MatrixExp verwendet die Schur-Zerlegung.
Exakte numerische lineare Algebra
Inverse und LinearSolve verwenden eine effiziente Zeilenreduzierung, die auf numerischer Näherung basiert.
Bei Modulus->n wird die modulare Gauß-Elimination verwendet.
Det verwendet modulare Methoden und Zeilenreduzierung und konstruiert ein Ergebnis mit dem chinesischen Restsatz.
Eigenvalues arbeitet mit Interpolation des charakteristischen Polynoms.
MatrixExp verwendet die Putzer-Methode oder die Jordan-Zerlegung.
|
