A.9.4 数值及相关函数

数的表示和数值计算

进制的数组存储,这取决于机器整数的长度.
精确度在内部作为浮点数保存.
IntegerDigits和相关的进制转换函数使用了一种递归除法和占优算法.
N使用一个自适应过程来提高它内部工作精确度以便达到任意一种总精度所要求的精确度.
Floor, Ceiling和相关的函数使用类似于N的自适应过程由准确输入生成准确的结果.

基本算法

大整数和高精度近似数的乘法通过使用交叉存储Karatsuba和FFT算法实现.
整数幂通过一个基于Horner法则的算法实现.
近似数的倒数和有理数幂使用Newton法实现.
准确的根由数值估计起始得到.
重要的算法用来实现超过机器精度的近似数的所有运算.
基本算法使用了约400页的 C 源代码.

伪随机数

Random使用Wolfram法则30细胞自动生成元处理整数.
它使用Marsaglia-Zaman借位减法生成实数.

数论函数

GCD 使用Jebelean-Weber加速GCD算法,加上一个由Euclid算法与一个基于2的幂循环排除算法组合而成的算法.
PrimeQ 首先使用小素数检测整除性,然后使用2进制和3进制强伪素数检测,最后使用一个Lucas测试检测.
至1997为止,该过程仅对证明是正确的,并且可以猜想的是,对于更大的,该过程仍可能判定一个复合数是素数.
NumberTheory`PrimeQ`包中包含了一个较慢的算法,该算法被证明对所有的都是正确的.它能对是否是素数返回一个明确认证.
FactorInteger通过试除法和使用Pollard p-1,Pollard rho和连续分式法实现在除去小素数之间的转化.
NumberTheory`FactorIntegerECM`包包括了适于对某些很大的整数的因数分解的椭圆曲线方法.
Prime和PrimePi使用稀疏存储和筛选.对于较大的n,PrimePi使用基于素数密度的渐进估计的Lagarias Miller Odlyzko算法,并被转换给出Prime.
LatticeReduce使用Lenstra Lenstra Lovasz网格缩减算法.
为了找到所要求的项,ContinuedFraction使用修正Lehmer间接法,并通过重新自分块和贪心法来减少每一步所必需的数值精确度.
ContinuedFraction使用循环关系为无理二次函数寻找周期连续分段.
FromContinuedFraction使用由分块和贪心法优化的迭代矩阵乘法.

复合函数

大部分复合函数使用稀疏缓存和递归法.
Factorial, Binomial及其相关函数使用一个分块和贪心算法来平衡乘积中数位个数.
Fibonacci[n]使用了基于n的二进制序列的迭代方法.
对较小的n，PartitionsP[n]使用Euler 五边形公式,而对较大的n，则使用非递归的Hardy Ramanujan Rademacher方法.
ClebschGordan及其相关函数使用了广义超几何分布序列.

初等超越函数

指数和三角函数使用Taylor级数,参数加倍的稳定递归,以及函数关系.
对数和反三角函数使用Taylor级数以及函数关系.

数学常数

常数的值在计算后就存储.
二进位分裂被用来对常数计算进行细分.
Pi使用Chudnovsky公式计算到10,000,000位之后.
E通过它的级数展开进行计算.
EulerGamma使用Brent McMillan算法.
Catalan通过一个线性收敛的Ramanujan和进行计算.

特殊函数

对机器精度，大部分特殊函数使用Mathematica所导出的有理极小极大近似.下面的注释主要应用到任意精确度.
一般来说,对多项式和超几何函数,正交多项式使用稳定递归公式.
Gamma使用递归,函数方程和Binet渐进公式.
不完全gamma和beta函数使用超几何级数及连分式.
PolyGamma使用了Euler-Maclaurin和式,函数方程和递归.
PolyLog使用Euler-Maclaurin公式,不完全gamma函数的展开和数值积分.
Zeta及其相关函数使用Euler-Maclaurin公式以及函数方程.在临界区附近它们也使用 Riemann Siegel公式.
StieltjesGamma使用用Keiper算法,该算法基于zeta函数的一个积分表示的数值积分.
误差函数和与指数积分相关的函数都使用不完全gamma函数进行求值.
逆误差函数使用二分法搜索和推广的高阶Newton法.
贝塞尔函数使用级数和渐进展开式.对于整数次,有些也使用稳定向前递归格式.
超几何函数使用函数方程,稳定循环法,级数展开和渐进级数展开方法.而且Nsum和与NIntegrate有时也可以使用.
ProductLog使用始于有理近似和渐进展开的高阶牛顿法.
椭圆积分使用递减高斯变换来求值.
椭圆theta函数使用以递归计算级数项的级数和.
另外一些椭圆函数主要使用代数几何平均数方法.
Mathieu函数使用傅立叶级数.Mathieu特征函数使用广义Blanch-牛顿法.

数值积分

当Method->Automatic时,NIntegrate在一维情形下使用GaussKronrod,而在其它的情形下使用MultiDimensional.
如果直接给出了MaxPoints设置,NIntegrate缺省使用Method->QuasiMonteCarlo.
GaussKronrod: 基于Kronrod点计算的带误差估计的自适应Gaussian积分.
DoubleExponential:非自适应双指数积分.
Trapezoidal:基本梯形法.
Oscillatory:用来实现包括三角函数和Bessel函数的积分的变换.
MultiDimensional:自适应Genz Malik算法.
MonteCarlo:非自适应Monte Carlo方法.
QuasiMonteCarlo:非自适应Halton Hammersley Wozniakowski算法.

数值加法和乘法

如果比率测试比不为1,则使用Wynn epsilon算法求解一系列部分和或部分积.
否则,则使用Euler-Maclaurin公式用于Integrate或NIntegrate.

数值微分方程

在Method->Automatic时,NDSolve可选择非刚性的Adams法和刚性Gear方法,它们都基于LSODE.
Adams:1-12阶的隐式Adams方法.
Gear:1-5阶的向后差分格式方法.
RungeKutta:非刚性方程的Fehlberg 4-5阶Runge-Kutta方法.
对线性边值问题使用Gel'fand Lokutsiyevskii追赶法.
对1+1维PDEs问题使用直线方法.
NDSolve的代码约有500页.

近似方程求解和最小值

多项式求根的实现基于Jenkins Traub算法.
对于稀疏线性系统,Solve和NSolve使用一些有效的数值方法,这些方法主要基于带Markowitz乘积的Gauss因数分解(约250页代码).
对代数方程组,NSolve首先使用一个有效的单项式排序计算出一个数值的Grobner基,然后使用特征值方法来确定根的数值解.
FindRoot使用了减幅Newton法,正割法和Brent方法.
在Method->Automatic时,FindMinimum使用了基于Brent的不同方法:在一维上时使用共轭梯度法,而在多维时使用修正Powell方法.
如果极小化函数是一个平方式的和, FindMinimum则使用Levenberg-Marquardt方法(Method->LevenbergMarquardt).
在Method->Newton时，FindMinimum使用Newton法.而在Method->QuasiNewton时，FindMinimum使用BFGS形式的拟牛顿法.
ConstrainedMax及其相关函数使用改进单纯形法.

数据处理

Fourier使用带长度素因子分解的FFT算法.当素数因子很大时, 则使用快速卷积方法来保持的渐进复杂度.
对实输入,Fourier使用一个实变换方法.
如果可能,ListConvolve和ListCorrelate使用FFT算法.对于准确的整数输入,则需要计算足够多的数位以得出准确的整数结果.
InterpolatingFunction使用离散差分来构造Lagrange或者Hermite插值多项式.
Fit 通过计算构造矩阵伪逆的相应向量的乘积来实现.

近似数值线性代数

机器精度矩阵通常被转化为一个特殊的内部表示来进行处理.
在适当的时候会使用与LINPACK,EISPACK和LAPACK等类似的算法.
LUDecomposition, Inverse, RowReduce和Det使用带主元的Gaussian消去法.LinearSolve使用同样的方法,和高精度数的迭代改进.
SingularValues使用带Givens变换的QR算法.PseudoInverse和NullSpace则基于SingularValues.
QRDecomposition使用Householder变换.
SchurDecomposition使用QR迭代.
MatrixExp使用Schur分解.

准确数值线性代数

Inverse和LinearSolve使用基于数值近似的有效行变换法.
当Modulus->n时,则使用模Gaussian消元法.
Det使用模方法和行变换,通过使用Chinese Remainder Theorem构造出结果.
Eigenvalues通过对特征多项式进行插值来实现.
MatrixExp使用Putzer方法或者Jordan分解.