2

作为一个实验，我只是想看看 Cayley-Hamilton 理论和 MATLABinv()函数之间的计算时间。由于矩阵产品的数量，我知道 CH 在 CPU 上会变慢，但是我没想到随着 N 的增加它们会给我不同的答案。

对于小于 30 * 30 左右的方阵，逆矩阵大致相同。但是在这一点之后，它们开始彼此之间发生很大的不同。到 N = 100 时，它们完全没有相似之处。

这是一个数值计算问题，还是这里发生了其他事情？还有我可以信任哪个？我假设inv()它是高度优化的并且值得信赖，但是从其他人那里获得一些输入会很好。

这是代码： 

n = 100;
A = randn(n);

% MATLAB inv()

tic;
initime = cputime;
time1   = clock;
A_inv = inv(A);
fintime = cputime;
elapsed = toc;
time2   = clock;
fprintf('TIC TOC: %g\n', elapsed);
fprintf('CPUTIME: %g\n', fintime - initime);
fprintf('CLOCK:   %g\n', etime(time2, time1));

% Cayley-Hamilton inversion

tic;
initime = cputime;
time1   = clock;
p_coeff = poly(A);
A_inv_2 = 0;
for ii = 1:n-1
    A_inv_2 = A^(ii)*p_coeff(end-1-ii) + A_inv_2;
end
A_inv_2 = 1/-p_coeff(end) * (A_inv_2 + eye(n)*p_coeff(end-1));    

fintime = cputime;
elapsed = toc;
time2   = clock;
fprintf('TIC TOC: %g\n', elapsed);
fprintf('CPUTIME: %g\n', fintime - initime);
fprintf('CLOCK:   %g\n', etime(time2, time1));

感谢任何花时间回答的人。

4

1 回答 1

1

Cayley-Hamilton 方法是一种非常不稳定的逆计算方法，因为它涉及将矩阵提升到高次幂。

考虑一个可以对角化的矩阵，A=inv(P)DP其中 D 是对角矩阵。当提高到 100 次方时，它变为A^100 = inv(P) D^100 P。D 中对角线条目之间的任何大小差异都将被此操作放大。例如，考虑 2^100 和 0.5^100 之间的差异。

在您的 Matlab 程序中实际上很容易看到这一点。打印出 A * A_inv 和 A * A_inv_2。第一个非常接近身份，而第二个包含废话：

A*A_inv_2
ans = 1.0e10 *
  0.2278  0.3500 -0.2564 ...
于 2017-04-18T14:59:48.493 回答