電腦代數系統

電腦代數系統（英語：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.