计算机代数系统

计算机代数系统（英语：computer algebra system，缩写作：CAS），或符号代数系统（symbolic algebra system，缩写作SAS），是能够以类似于数学家和科学家传统手动计算的方式操作数学表达式的数学软件。这种系统的要件是数学表达式的符号运算。20世纪下半叶计算机代数系统的发展是“计算机代数”或“符号计算”学科的一部分，它刺激了多项式等数学对象的算法工作。

计算机代数系统按用途可分为两大类：专用、通用。

专用的计算机代数系统致力于数学的特定部分，例如数论、群论，亦或是初等数学的教学。

通用的计算机代数系统致力于任何需要操作数学表达式的科学领域。为了发挥其作用，通用计算机代数系统必须包含各种功能，例如：

- 允许用户输入和显示数学公式的用户界面，通常通过键盘、菜单选择、鼠标或触笔。
- 一个编程语言和与之配套的解释器（计算结果通常具有不可预测的形式和大小，因此经常需要用户通过其干预）。
- 简化器，一个用于简化数学公式的重写系统。
- 内存管理器，包括垃圾收集器，用于处理可能在计算过程中出现的庞大中间数据。
- 高精度计算算法，用于处理可能出现的巨大整数。
- 大型的数学算法库、特殊函数库。

数学算法库、特殊函数库不仅要满足用户的需求，还要满足简化器的需求。例如，多项式最大公约数的计算被系统地用于简化涉及分数的表达式。

这些繁杂的功能要求解释了通用计算机代数系统的数量为何如此之少。一些重要的系统包括Axiom_计算机代数系统、Maxima、MAGMA、Maple、Mathematica和SageMath。

## 发展历史

<image>

20世纪50年代，当计算机主要被用于数值计算时，已有研究项目探索其在符号运算中的应用。计算机代数系统于于 20世纪60年代开始兴起，其发展源自两个截然不同的领域：理论物理学家的研究需求和人工智能领域的探索。

第一个领域的一个典型例子是后来的诺贝尔物理学奖获得者马丁纽斯·韦尔特曼（Martinus J. G. Veltman）在1963年设计的用于高能物理的符号数学程序，名为Schoonschip（荷兰语，意指“干净的船”）。其他早期系统包括FORMAC。

在第二个人工智能领域中，Carl Engelman使用Lisp作为编程基础，于1964年在MITRE的人工智能研究所中创建了MATHLAB。后来MATHLAB可供大学中运行TOPS-10或TENEX的PDP-6和PDP-10系统上的用户使用。如今，它仍然可以在PDP-10的SIMH仿真环境中运行。注意，MATHLAB（"mathematical laboratory"）不是MATLAB（"matrix laboratory"），后者是新墨西哥大学在15年后建立的数值计算系统。

1987 年，惠普推出了第一台带有 CAS 的手持计算器——HP-28系列。首次在计算器中实现了整理代数表达式，求导，有限符号积分，泰勒级数构建的功能，以及一个代数方程的求解器。1999年，为HP 48系列自主研发的Erable CAS正式成为新兴的HP 49/50系列固件中的一个集成部分，并在一年后也集成到了HP 40系列中，而在2013年，HP Prime则采用了Xcas系统。

1995年，德州仪器发布了TI-92计算器，该计算器搭载了基于Derive_计算机代数系统软件开发的CAS；TI-Nspire系列于2007年取代了 Derive。1998年首次发布的TI-89 系列也包含CAS。

Casio在1999年推出了他们的第一款带有CAS的计算器———CFX-9970G。并在1999年至2003年，推出了替代CFX-9970G的Algebra FX 系列，直到现在的ClassPad 系列。

第一个流行的计算机代数系统是muMATH、Reduce、Derive（基于 muMATH）和Macsyma；Macsyma的一个流行的Copyleft版本是Maxima，目前正在积极维护。Reduce于 2008 年成为自由软件。截至今日，最流行的商业系统是Mathematica和Maple，它们通常被研究数学家、科学家和工程师使用。免费提供的替代方案包括SageMath（它可以充当其他几个免费和非自由 CAS 的前端）。其他重要的系统包括Axiom、Maxima、Magma和SageMath。

2000 年代初期，向基于Web的应用程序的转变的趋势促使了WolframAlpha的发布，它由一个在线搜索引擎和一个包含Mathematica的功能的CAS组成。

最近，计算机代数系统开始使用人工神经网络来实现，但截至2020年，它们尚未商用。

## 符号运算

通常支持的符号运算功能包括：

- 表达式简化：简化为较小的表达式或一些标准形式，包括带假设的自动简化和带约束的简化。
- 对表达式求值：用符号或数值替换（逻辑）某些表达式。
- 表达式的变换：乘积和幂展开、部分和全部因式分解、重写为部分分数、约束满足、将三角函数变换为指数函数、变换逻辑表达式等。
- 部分微分和全微分。
- 一些不定积分和定积分（参见符号积分），包括多维积分。
- 符号约束和无约束全局优化。
- 不同领域的线性和一些非线性方程的解。
- 一些微分方程和差分方程的解。
- 一些极限计算。
- 积分变换。
- 展开、求和、乘积等系列运算。
- 矩阵运算包括乘积、逆矩阵等。
- 统计计算。
- 定理证明和验证（在实验数学领域非常有用）。
- 生成优化的代码。

注：上文所述“一些”表示该功能存在运算限制，无法保证所有情况均可执行。

## 其它功能

很多CAS还包括：

- 一种编程语言，允许用户实现自己的算法，将自定义的数学方法和操作集成到系统中。
- 任意精度数值运算
- 精确整数算术和数论功能
- 二维形式的数学表达式编辑
- 画2D、3D函数图，并对其进行动画处理
- 绘制图表和图示
- 用于将其链接到外部程序（例如数据库）或在编程语言中使用计算机代数系统的API
- 字符串操作，例如匹配和搜索
- 用于物理、生物信息学、计算化学等应用数学的附加组件以及物理计算包
- 微分方程求解器

其中一些CAS包括：

- 声音合成
- 图形生成和编辑，例如计算机生成图像、信号处理、计算机图像处理

一些计算机代数系统专注于特定学科领域；这些系统通常由学术界开发，并且是免费的。与数值系统相比，它们在数值运算方面可能效率较低。

## 表达式的类别

CAS 操作的表达式通常包括：

- 多变元多项式
- 标准函数（三角函数、指数函数等等）
- 各种特殊函数（Γ函数、ζ函数、误差函数、贝塞尔函数等）
- 表达式的导函数、积分、和与积
- 以表达式为系数的级数
- 表达式构成的矩阵

支持的数字域通常包括实数的浮点表示、（无限大小的）整数、（浮点表示的）复数、实数的区间表示、有理数（精确表示）和代数。

## 教育方面

近年来，有许多倡导者呼吁在中小学课堂中增加计算机代数系统的使用。这种倡导的主要原因是计算机代数系统比基于纸笔或手持计算器的数学更能代表现实世界的数学。一些教育委员会支持增加数学课堂中计算机的使用。它甚至被纳入一些地区的课程中。

计算机代数系统已广泛应用于高等教育。许多大学要么提供有关开发其用途的特定课程，要么隐含地期望学生在课程作业中使用它们。开发计算机代数系统的公司已努力提高其在大学和学院课程中的普及率。

配备CAS的计算器在ACT、PLAN等考试中不允许使用，尽管在所有允许使用计算器的美国大学理事会考试中可能是允许的，包括SAT、一些SAT科目考试以及AP微积分、化学、物理和统计学考试中可能允许使用。

## 在计算机代数系统中应用的数学算法

- Knuth-Bendix 完成算法
- 求根算法
- 符号积分算法，例如Risch 算法或Risch-Norman 算法
- Wilf Zeilberger pair 算法，例如高斯珀算法
- 计算极限的算法，例如格伦茨算法
- 在有限域上的多项式因式分解，由伯利坎普算法或康托尔-扎森豪斯算法实现。
- 最大公约数算法，例如欧几里得算法
- 高斯消去法
- Gröbner基，例如Buchberger算法；这是欧几里德算法和高斯消去法的推广。
- 帕德近似
- Schwartz–Zippel引理和多项式恒等式测试
- 中国剩余定理
- 丢番图方程
- 朗道算法（嵌套根式算法）
- 初等函数和特殊函数的导数。（例如：不完全伽玛函数的导数。）
- 圆柱代数分解
- 通过圆柱代数分解实现实数域上的量词消除

## 外部链接

- Richard J. Fateman. Essays in algebraic simplification. Technical report MIT-LCS-TR-095, 1972.
- Curriculum and Assessment in an Age of Computer Algebra Systems - From the教育资源信息中心 Clearinghouse for Science, Mathematics, and Environmental Education, Columbus, Ohio.