线性代数/主题：计算行列式的速度/解法

解法

大多数这些问题假设可以访问计算机。

问题 1

计算机系统生成随机数（当然，这些只是伪随机数，因为它们是由算法生成的，但它们通过了许多合理的统计随机性测试）。

1. 用随机数填充一个$5\!\times \!5$ 数组（例如，在范围$[0..1)$ 内）。查看它是否为奇异矩阵。重复此实验几次。奇异矩阵是频繁出现的还是罕见的（在这个意义上）？
2. 计时您的计算机代数系统计算十个$5\!\times \!5$ 随机数数组的行列式。找到每个数组的平均时间。针对$15\!\times \!15$ 数组、$25\!\times \!25$ 数组和$35\!\times \!35$ 数组重复前面的项目。（请注意，当一个数组为奇异时，有时可以很快地发现它，例如如果第一行等于第二行。根据您对第一部分的答案，您是否认为奇异系统在您的平均值中扮演重要角色？）
3. 绘制输入大小与平均时间的关系图。

答案

1. 在 Octave 中，rank(rand(5))找到一个$5\!\times \!5$ 矩阵的秩，该矩阵的元素在$[0..1)$ 区间内（均匀分布）。此循环运行测试$5000$ 次octave:1> for i=1:5000
   > if rank(rand(5))<5 printf("That's one."); endif
   > endfor
   产生（经过几秒钟后）返回提示，没有任何输出。Octave 脚本
   
   function elapsed_time = detspeed (size)
   a=rand(size);
   tic();
   for i=1:10
   det(a);
   endfor
   elapsed_time=toc();
   endfunction
   
   
   导致此会话。
   
   octave:1> detspeed(5)
   ans = 0.019505
   octave:2> detspeed(15)
   ans = 0.0054691
   octave:3> detspeed(25)
   ans = 0.0097431
   octave:4> detspeed(35)
   ans = 0.017398
   
2. 以下是数据（略微四舍五入）和图表。

   ${\begin{array}{r|ccccccccc}{\textit {matrix\ rows}}&15&25&35&45&55&65&75&85&95\\\hline {\textit {time\ per\ ten}}&0.0034&0.0098&0.0675&0.0285&0.0443&0.0663&0.1428&0.2282&0.1686\end{array}}$

   （此数据来自上述脚本二十次运行的平均值，因为随机选择的矩阵可能恰好需要异常长或短的时间。即使如此，计时也不能过于依赖；这只是一个实验。）

   

问题 2

使用上面讨论的两种方法，手动计算每个行列式。

1. ${\begin{vmatrix}2&1\\5&-3\end{vmatrix}}$
2. ${\begin{vmatrix}3&1&1\\-1&0&5\\-1&2&-2\end{vmatrix}}$
3. ${\begin{vmatrix}2&1&0&0\\1&3&2&0\\0&-1&-2&1\\0&0&-2&1\end{vmatrix}}$

对于每种方法，分别计算每种情况下使用的乘法和除法的次数。（在计算机中，乘法和除法比加法和减法需要更多时间，因此算法设计人员会更多地关注它们。）

答案

操作的次数取决于操作的具体执行方式。

1. 行列式为 $-11$。进行行简化需要一个枢轴，有两个乘法（$-5/2$ 乘以 $2$ 加上 $5$，以及 $-5/2$ 乘以 $1$ 加上 $-3$)，对角线上的乘积还需要一次乘法。排列展开需要两次乘法（$2$ 乘以 $-3$ 以及 $5$ 乘以 $1$）。
2. 行列式为 $-39$。计算操作次数是例行公事。
3. 行列式为 $4$。

问题 3

你能想出一个 $10\!\times \!10$ 数组，让你的计算机系统需要最长时间才能简化？最短时间？

答案

一个开始的方法是使用 Octave 比较：det(rand(10));，与det(hilb(10));，与det(eye(10));，与det(zeroes(10));。你可以像这样计时它们：tic(); det(rand(10)); toc().

问题 4

编写剩下的 FORTRAN 程序，以直接实现通过高斯方法计算行列式。（不要测试零枢轴。）比较你代码的速度和你的计算机代数系统中使用的代码的速度。

答案

这是一个简单的例子。

DO 5 ROW=1, N
PIVINV=1.0/A(ROW,ROW)
DO 10 I=ROW+1, N
DO 20 J=I, N
A(I,J)=A(I,J)-PIVINV*A(ROW,J)
20 CONTINUE
10 CONTINUE
5 CONTINUE

问题 5

FORTRAN 语言规范要求数组“按列”存储，也就是说，整个第一列连续存储，然后是第二列，等等。给定的代码片段是否利用了这一点，或者它是否可以重写以使其更快，通过利用计算机从连续位置获取数据的速度更快这一事实？

答案

是的，因为 $J$ 在最内层循环中。