This is documentation for Mathematica 4, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.2)

 Documentation /  Mathematica /  Das Mathematica Buch /  Mathematica Nachschlageteil /  Einige Anmerkungen zur internen Implementierung /

Grundlegende SystemeigenschaftenAlgebra und Analysis

A.9.4 Numerische und verwandte Funktionen

Zahlendarstellung und numerische Evaluierung

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

FilledSmallCircle Präzision wird intern als Fließpunktzahl geführt.

FilledSmallCircleIntegerDigits und verwandte Basiskonvertierungsfunktionen verwenden einen rekursiven Teile-und-herrsche-Algorithmus (divide-and-conquer).

FilledSmallCircleN verwendet eine adaptive Prozedur zur Erhöhung ihrer internen Arbeitspräzision, um die jeweils geforderte Gesamtpräzision zu erreichen.

FilledSmallCircleFloor, Ceiling und verwandte Funktionen verwenden eine adaptive Prozedur, ähnlich wie N, um aus exakter Eingabe exakte Ausgabe zu erzeugen.

Grundarithmetik

FilledSmallCircle Die Multiplikation mit großen ganzen Zahlen und mit Fließpunktzahlen hoher Präzision erfolgt mit ineinandergeschachtelten Karatsuba- und FFT (Schnelle Foruriertransformations)-Algorithmen.

FilledSmallCircle Die Potenzen ganzer Zahlen werden mit einem Algorithmus bestimmt, der auf dem Horner-Schema beruht.

FilledSmallCircle Reziproke Werte und rationale Potenzen von Fließpunktzahlen verwenden Newtons Verfahren.

FilledSmallCircle Exakte Nullstellenbestimmung erfolgt ausgehend von numerischen Schätzwerten.

FilledSmallCircle Für Arithmetik mit Fließpunktzahlen, die mehr als Maschinenpräzision haben, wird Signifikanzarithmetik verwendet.

FilledSmallCircle Die Grundarithmetik verwendet etwa 400 Seiten C-Quellcode.

Pseudo-Zufallszahlen

FilledSmallCircleRandom verwendet die Wolfram-Regel 30 mit dem zellulären Automatengenerator für ganze Zahlen.

FilledSmallCircle Es wird ein Marsaglia-Zaman-Generator (Subtraktion mit Übertrag) für reelle Zahlen verwendet.

Zahlentheoretische Funktionen

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

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

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

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

FilledSmallCircleFactorInteger wechselt zwischen Entfernung kleiner Primzahlen mittels versuchsweiser Division und der Verwendung des Pollard -, Pollard Rho- und Kettenbruch-Algorithmus hin und her.

FilledSmallCircle Das Paket NumberTheory`FactorIntegerECM` enthält einen elliptischen Algorithmus, der sich zur Faktorisierung einiger sehr großer ganzer Zahlen eignet.

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

FilledSmallCircleLatticeReduce verwendet den Lenstra-Lenstra-Lovasz-Gitterreduzierungs-Algorithmus.

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

FilledSmallCircleContinuedFraction verwendet Rekursionsformeln, um für quadratische irrationale Zahlen periodische Kettenbrüche zu finden.

FilledSmallCircleFromContinuedFraction verwendet iterierte Matrizenmultiplikation, optimiert durch eine Teile-und-herrsche-Methode.

Kombinatorische Funktionen

FilledSmallCircle Die meisten kombinatorischen Funktionen verwenden geringe Pufferung und Rekursion.

FilledSmallCircleFactorial, Binomial und verwandte Funktionen verwenden einen Teile-und-herrsche-Algorithmus, um die Stellenanzahl in Unterprodukten auszugleichen.

FilledSmallCircleFibonacci[n] verwendet eine iterative Methode, die auf der Binärziffernfolge von n basiert.

FilledSmallCirclePartitionsP[n] verwendet die Eulersche Pentagonalformel für kleine n und die nichtrekursive Hardy-Ramanujan-Rademacher-Methode für größere n.

FilledSmallCircleClebschGordan und verwandte Funktionen verwenden verallgemeinerte hypergeometrische Reihen.

Elementare transzendente Funktionen

FilledSmallCircle Exponentielle und trigonometrische Funktionen verwenden Taylor-Reihen, stabile Rekursion durch Argumentverdopplung und funktionale Relationen.

FilledSmallCircle Logarithmische und inverse trigonometrische Funktionen verwenden Taylor-Reihen sowie funktionale Relationen.

Mathematische Konstanten

FilledSmallCircle Werte von Konstanten werden im Cache abgelegt, sobald sie berechnet sind.

FilledSmallCircle Mit binärer Aufspaltung werden Berechnungen von Konstanten unterteilt.

FilledSmallCirclePi verwendet die Chudnovsky-Formel für Berechnungen von bis zu zehn Millionen Stellen.

FilledSmallCircleE wird aus ihrer Reihenentwicklung berechnet.

FilledSmallCircleEulerGamma verwendet den Brent-McMillan-Algorithmus.

FilledSmallCircleCatalan wird aus einer linear konvergenten Ramanujan-Summe berechnet.

Spezielle Funktionen

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

FilledSmallCircle Orthogonale Polynome verwenden stabile Rekursionsformeln für polynomiale Fälle und hypergeometrische Funktionen im allgemeinen.

FilledSmallCircleGamma verwendet Rekursion, Funktionalgleichungen und die Binetsche asymptotische Formel.

FilledSmallCircle Unvollständige Gamma- und Beta-Funktionen verwenden hypergeometrische Reihen und Kettenbrüche.

FilledSmallCirclePolyGamma verwendet Euler-Maclaurin-Summierung, Funktionalgleichungen und Rekursion.

FilledSmallCirclePolyLog verwendet Euler-Maclaurin-Summierung, Entwicklungen mit unvollständigen Gamma-Funktionen und numerische Quadratur.

FilledSmallCircleZeta und verwandte Funktionen verwenden Euler-Maclaurin-Summierung und Funktionalgleichungen. In der Nähe des kritischen Streifens verwenden sie außerdem die Riemann-Siegel-Formel.

FilledSmallCircleStieltjesGamma verwendet den Keiper-Algorithmus, der auf der numerischen Quadratur einer Integraldarstellung der Zetafunktion basiert.

FilledSmallCircle Die Fehlerfunktion und die mit Exponentialintegralen verwandten Funktionen werden alle mit unvollständigen Gamma-Funktionen evaluiert.

FilledSmallCircle Die inversen Fehlerfunktionen verwenden Binomialsuche und eine verallgemeinerte Newton-Methode hoher Ordnung.

FilledSmallCircle Bessel-Funktionen verwenden Reihen und asymptotische Entwicklungen. Einige verwenden für ganzzahlige Ordnungen auch stabile Vorwärtsrekursion.

FilledSmallCircle Die hypergeometrischen Funktionen verwenden Funktionalgleichungen, stabile rekurrente Relationen, Reihenentwicklung und asymptotische Reihen. Manchmal werden auch Methoden von NSum und NIntegrate verwendet.

FilledSmallCircleProductLog verwendet eine Newton-Methode hoher Ordnung, die von rationalen Näherungen und asymptotischen Entwicklungen aus startet.

FilledSmallCircle Elliptische Integrale werden mit der abfallenden Gauß-Transformation evaluiert.

FilledSmallCircle Elliptische Theta-Funktionen verwenden Reihen-Summierung mit rekursiver Evaluierung von Reihengliedern.

FilledSmallCircle Andere elliptische Funktionen verwenden meistens arithmetisch-geometrische Mittelwert-Methoden.

FilledSmallCircle Mathieu-Funktionen verwenden Fourier-Reihen. Die Mathieu-Charakteristik-Funktionen verwenden Verallgemeinerungen der Blanch-Newton-Methode.

Numerische Integration

FilledSmallCircle Bei Method->Automatic verwendet NIntegrate GaussKronrod in einer Dimension und ansonsten MultiDimensional.

FilledSmallCircle Wenn für MaxPoints eine explizite Einstellung gegeben ist, verwendet NIntegrate vorgabemäßig Method->QuasiMonteCarlo.

FilledSmallCircleGaussKronrod: Adaptive Gauß-Quadratur mit Fehlerabschätzung, die auf der Evaluierung an Kronrod-Punkten basiert.

FilledSmallCircleDoubleExponential: nichtadaptive doppelt-exponentielle Quadratur.

FilledSmallCircleTrapezoidal: elementare Trapez-Methode.

FilledSmallCircleOscillatory: Transformation für die Bearbeitung von Integralen, die trigonometrische und Bessel-Funktionen enthalten.

FilledSmallCircleMultiDimensional: adaptiver Genz-Malik-Algorithmus.

FilledSmallCircleMonteCarlo: nichtadaptive Monte Carlo-Methode.

FilledSmallCircleQuasiMonteCarlo: nichtadaptiver Halton-Hammersley-Wozniakowski-Algorithmus.

Numerische Summen und Produkte

FilledSmallCircle Wenn das Quotientenkriterium nicht 1 ergibt, wird der Wynn-Epsilon-Algorithmus auf eine Folge von Partialsummen oder -produkten angewendet.

FilledSmallCircle Ansonsten wird die Euler-Maclaurin-Summierung mit Integrate oder NIntegrate verwendet.

Numerische Differentialgleichungen

FilledSmallCircle Bei Method->Automatic schaltet NDSolve zwischen einer nichtsteifen Adams-Methode und einer steifen Gear-Methode hin und her, basierend auf LSODE.

FilledSmallCircleAdams: implizite Adams-Methode der Ordnung 1 bis 12.

FilledSmallCircleGear: Rückwärtsdifferenzen-Methode der Ordnung 1 bis 5.

FilledSmallCircleRungeKutta: Runge-Kutta-Methode der Fehlberg-Ordnung 4-5 für nichtsteife Gleichungen.

FilledSmallCircle Für lineare Randwertprobleme wird die Gel'fand-Lokutsiyevskii-Verfolgungs-Methode verwendet.

FilledSmallCircle Für 1+1-dimensionale PDGL wird die Linienmethode verwendet.

FilledSmallCircle Der Code für NDSolve ist ungefähr 500 Seiten lang.

Approximatives Lösen und Minimieren von Gleichungen

FilledSmallCircle Die Ermittlung von Polynomnullstellen erfolgt auf der Grundlage des Jenkins-Traub-Algorithmus.

FilledSmallCircleSolve 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).

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

FilledSmallCircleFindRoot verwendet eine gedämpfte Newton-Methode, die Sekantenmethode und die Brent-Methode.

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

FilledSmallCircle Ist die zu minimierende Funktion eine Summe von Quadraten, so verwendet FindMinimum die Levenberg-Marquant-Methode (Method->LevenbergMarquant).

FilledSmallCircle Mit der Einstellung Method->Newton verwendet FindMinimum die Newton-Methode. Mit der Einstellung Method->QuasiNewton verwendet FindMinimum die BFGS-Version der Quasi-Newton-Methode.

FilledSmallCircleConstrainedMax und verwandte Funktionen verwenden eine erweiterte Version des Simplex-Algorithmus.

Datenmanipulation

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

FilledSmallCircle Für reellwertige Eingabe verwendet Fourier eine reelle Transformationsmethode.

FilledSmallCircleListConvolve und ListCorrelate setzen FFT-Algorithmen ein, wenn dies möglich ist.

FilledSmallCircleInterpolatingFunction verwendet geteilte Differenzen, um Lagrange- oder Hermite-interpolierende Polynome zu konstruieren.

FilledSmallCircleFit berechnet das Produkt aus dem Vektor der abhängigen Variablen mit der Pseudoinversen der Design-Matrix.

Approximative numerische lineare Algebra

FilledSmallCircle In der Regel werden maschinenpräzise Matrizen zur Verarbeitung in eine spezielle interne Darstellung konvertiert.

FilledSmallCircle Es werden, falls es paßt, Algorithmen verwendet, die ähnlich jenen von LINPACK, EISPACK und LAPACK sind.

FilledSmallCircleLUDecomposition, 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.

FilledSmallCircleSingularValues verwendet den QR-Algorithmus mit Givens-Rotationen. PseudoInverse und NullSpace basieren auf SingularValues.

FilledSmallCircleQRDecomposition verwendet Householder-Transformationen.

FilledSmallCircleSchurDecomposition verwendet QR-Iteration.

FilledSmallCircleMatrixExp verwendet die Schur-Zerlegung.

Exakte numerische lineare Algebra

FilledSmallCircleInverse und LinearSolve verwenden eine effiziente Zeilenreduzierung, die auf numerischer Näherung basiert.

FilledSmallCircle Bei Modulus->n wird die modulare Gauß-Elimination verwendet.

FilledSmallCircleDet verwendet modulare Methoden und Zeilenreduzierung und konstruiert ein Ergebnis mit dem chinesischen Restsatz.

FilledSmallCircleEigenvalues arbeitet mit Interpolation des charakteristischen Polynoms.

FilledSmallCircleMatrixExp verwendet die Putzer-Methode oder die Jordan-Zerlegung.

Grundlegende SystemeigenschaftenAlgebra und Analysis