有理矩阵有理相似对角化的计算机实现

摘要： 人工计算有理矩阵能否在有理数域上相似对角化是非常困难的，所以需要计算机来辅助实现，然而已有的数学软件对此问题的计算结果却存在着误差，于是需要研究有理矩阵在有理数域上相似对角化的算法及程序.因此在直接进行分数运算的基础上，首先使用矩阵的幂与来计算有理矩阵的特征多项式，克服了直接计算行列式的方法所存在的算法设计上的困难，其次根据有理多项式有理根的求法计算出有理矩阵的有理特征根，进而精确地计算出相应的有理特征向量，从而成功设计出判断及实现有理矩阵在有理数域上对角化的算法及相应的语言程序，使用该程序能够精确地解决有理矩阵在有理数域上相似对角化的问题。

关键词： 有理矩阵；有理相似对角化；算法；程序

中图分类号：O151.21 文献标识码：A 文章编号：1006-4311（2013）16-0194-06

0 引言

矩阵的相似对角化是重要的矩阵方法，然而人工计算却力不能及，所以需要计算机辅助实现。有理数域是常用的数域，有理矩阵更是常用的矩阵，所以判定及求解有理矩阵在有理数域上相似对角化问题非常必要，然而遗憾的是尽管已有的数学软件（如Matlab、Mathematica、Maple）能够解决矩阵对角化问题，但却只是在实数域、复数域上进行，而对于有理矩阵在有理数域上的相似对角化问题的解答存在着误差。

与相应的对角矩阵为

而在Maple中计算，却输出另一结果：可逆矩阵为

与相应的对角矩阵为

显然Mathematica与Maple的输出结果均存在着误差。

除此之外，这些数学软件还存在系统庞大、使用不便、输出的结果不直观等弱点。

上述问题使我们不能不考虑研究有理矩阵在有理数域上相似对角化问题的算法，设计出能够精确解决该问题的专用程序，本文阐述我们为此所做的研究工作。

1 相关概念及理论依据

定义1[1]

定义2[1] 设A是数域F上的n阶矩阵，称fA（x）的根λ为矩阵A的特征根。

定义3 设A是数域F上的n阶矩阵，如果存在F上的可逆矩阵P与F上的对角形矩阵D，使得P-1AP=D，那么即称A在数域F上可以对角化。

定理1

定理2

定理3[1] 设A是数域F上一个n阶矩阵，A可以对角化的充要条件是：

①A的特征多项式的根都在F内。

②对于A的每一特征根λ，秩（λ-A）=n-s，

这里s是λ的重数。

综合除法[1]：设f（x）=a0xn+a1xn-1+…+an-1x+an，用x-c除f（x）所得的商式为q（x）=b0xn-1+b1xn-2+…+bn-2x+bn-1。

且余式为r，那么a0=b0，b1=cb0+a1，b2=cb1+a2，…，bn-1=cbn-2+an-1，r=cbn-1+an。

为了方便，我们把有理数域上的矩阵称为有理矩阵。有理矩阵A在有理数域上的特征根叫作A的有理特征根。如果有理矩阵A在有理数域上可以相似对角化，那么即称A能有理相似对角化。

2 算法设计

2.1 算法设计思想

首先，之所以Matlab、Mathematica和Maple在计算有理矩阵有理相似对角化问题中产生了误差，是因为这些软件的四则运算是建立在实数基础上。因此要精确地解决有理相似对角化问题，就必须在分数运算的基础上设计算法及程序。但因为计算机程序语言系统的四则运算都定义在实数域上，所以算法必须设计分数运算功能，以此为基础进行相关处理。关于分数的存储问题，采用两个矩阵分别存储分子与分母较为方便。

其次，定理3给出了判定数域F上的n阶方阵在F上能否相似对角化的一般方法（如图1所示），因此，对于有理矩阵A，判定、求解其能否有理相似对角化应做好以下主要的工作：

2.1.1 求出A的特征多项式fA（x）=xI-A.此项工作所存在的困难是：因为xI-A是含有未知数x的行列式，如果按照行列式的计算方法直接计算，算法将非常复杂，程序设计也将非常困难.然而定理1为我们提供了不展开行列式的计算方法，据此方法求A的特征多项式，需做以下处理：

①计算Ai（i=2…n）及Ai的迹。

②生成矩阵

③求矩阵A1的逆矩阵A1-1。

④计算A1-1A2即可得到fA（x）的各项系数。

如此处理即避免了直接计算行列式所带来的算法设计上的困难，为设计有理矩阵有理对角化算法开拓了最关键的一步。

2.1.2 判断A特征根是否都是有理数。对此工作，表面地看需要求出A的特征多项式的所有根，然而这是不可能的。不过根据定理2及综合除法原理，我们却能够求出A的所有的有理特征根及其重数，再判断其所有有理特征根的重数和是否等于n即可解决这一问题。要实现此设想，可分以下四步进行：①变有理系数特征多项式为与其同解的本原多项式；②判断0是否为A的特征根，若是则确定其重数；③判断±1是否为A的特征根，若是则确定其重数；④确定A的不为0与±1的特征根及相应的重数，为此又需要做：1）求出fA（x）常数项及最高项系数的所有因子；2）根据定理2及其推论确定fA（x）有理根的可能值；3）使用综合除法判定每个可能值是否为根，若是则继续用综合除法确定其重数。

2.1.3 求A的有理特征根λ的特征子空间的基，亦即是求齐次线性方程组（λI-A）X=0的一个基础解系。这就需要解齐次线性方程组的算法。

2.2 设计有理矩阵有理相似对角化的算法

2.2.1 主算法

S1. 输入有理矩阵A，其元素的分子、分母分别存储在二维数组a1、a2中，并判定A是否为对角矩阵：若是则输出其变换阵为单位阵，算法结束；否则，转S2。

S2. 求A的特征多项式：

S2.1. 调用方阵乘积与求矩阵迹的子函数计算A的

i（i=2，3，…，n）次幂及对应的迹，并将迹的分子、分母对应存储于两个矩阵h、l中。

S2.2. 调用生成矩阵子函数生成矩阵A1（其元素的分子、分母分别存储在二维数组c1、c2中）和矩阵A2（其元素的分子、分母分别存储在二维数组c3、c4中）。

S2.3. 调用求矩阵的逆子函数求A1-1，并将A1-1的元素的分子、分母存储于矩阵c1、c2中。

S2.4. 求A1-1A2，所得为特征多项式系数ai（i=0，1，…，n-1）的矩阵表示，此时，特征多项式最高次项系数为an=1。

S3. 计算有理特征根及对应重数（有理特征根的分子、分母分别存储于一维数组h1、k1中，特征根对应的重数存储于一维数组g1中）。

S3.1. 变特征多项式为本原多项式，具体算法如下：

S3.1.1. 调用最小公倍数子函数求出特征多项式各系数的最小公倍数，将特征多项式各项都乘以其系数的最小公倍数，即得到与其同解的整系数多项式f（x）。

S3.1.2. 调用最大公因数子函数求出f（x）系数的最大公因数d（x），用d（x）除f（x）各系数，即得与f（x）同解的本原多项式，仍记为fA（x）。

S3.2. 判断0是否为A的有理特征根，若是并确定其重数，具体算法为：在fA（x）中，若a0≠0，则0不是有理特征根；否则，从fA（x）最低次项系数开始找出第一个非零系数ai（0

S3.3.判断±1是否为A的有理特征根，若是则确定其重数，具体算法为：调用求多项式值子函数，判断±1是否为fA（x）的根，若是，则调用综合除法子函数计算其重数。

S3.4. 调用求特征根子函数，计算A的不为0与±1的有理特征根及重数。

S4. 判断A所有特征根是否都为有理数，只要判定A所有有理特征根的重数和是否等于n，若是则转S5；否则输出A不能有理相似对角化，算法结束。

S5. 判断A的所有有理特征根的代数重数与几何重数是否相等，进而确定A是否可有理相似对角化。为此，设λ1、…、λr是A所有的特征根，其代数重数依次为s1，…，sr，判定方法如下：

2.2.2 子算法

为了阅读方便，事先说明下文中所用到的函数的意义：

ZXGBS：最小公倍数函数；ZDGYS：最大公因数函数；yf：约分函数；JF：分数加法函数；CF：分数乘法函数；FZCF：方阵乘积函数；JZDE：求矩阵迹函数；SCJZ：生成矩阵函数；

njz：矩阵逆函数；plyv：多项式求值函数；zhcf：综合除法函数；TZG：特征根函数；szjy：有理根判定函数；TZXL：齐次线性方程组基础解系函数；flactional：行初等变换函数。

2.2.2.1 方阵乘积算法

2.2.2.2 求矩阵迹算法

2.2.2.3 生成矩阵算法

2.2.2.4 矩阵逆算法

2.2.2.5 求多项式值算法[3]

在S3.3中需要计算多项式的值，将多项式f（x）表示成

运算以下递推公式

则u0即为多项式f（x）的值.于是如果用一维数组y存储多项式系数，用整型变量n存储最高项次数，那么据（3）和（4）可设计计算多项式值的算法如下：

2.2.2.6 综合除法算法

2.2.2.7 求特征根算法 在S3.4中需要求A的不为0及±1的有理特征根及对应重数，需分三步进行：

2.2.2.8 齐次线性方程组基础解系算法

2.2.2.9 行初等变换算法

2.2.2.10 其它子算法 关于分数的四则运算以及与其相关的最大公因数、最小公倍数、约分等算法容易设计，不多累赘。

3 计算结果

4 结论

有理矩阵有理对角化的算法及程序设计是一个理论与应用并重的课题。本文以有理相似对角化为着重点，研究并设计了有理矩阵在有理数域上相似对角化的算法及程序，该程序能够精确地判定及求解有理相似对角化问题。当然，于本文的研究结果仍有许多问题需要进一步研究。①当输入的矩阵的阶数或元素有效数字较大时，会产生数据溢出现象，因此一方面还需要优化算法以避免运算过程中产生不必要的大数据溢出现象；另一方面需要研究使用大整数运算技巧以使程序的适应性更强。②程序代码较为冗长，因此需进一步优化程序，提高软件运算速度与质量。

注：致谢：感谢韩山师范学院王积社副教授的悉心指导！

参考文献：

[1]张禾瑞，郝炳新.高等代数[M].5版.北京：高等教育出版社，2007.

[2]孙志和，窦在祥.特征多项式系数的矩阵表示[J].青岛理工大学学报，2006，27（3）.

[3]徐士良.常用算法程序集：C语言描述[M].3版.北京：清华大学出版社，2004：1-2.