MATLAB的答案

有什么方法来计算矩阵的逆改变几个值吗?

20视图(30天)
(音译)
(音译) 2020年8月1日
评论道: (音译) 2020年8月2日
我有一个大型稀疏矩阵及其逆矩阵得到发票(a)。然后我需要改变一个元素的值来得到一个新的矩阵,A1。我试图让A1的倒数。有什么方法去做,而不是重新计算发票(A1) ?我可以得到一些好处或发票(一)?
例如(不是一个稀疏矩阵)
一个=魔法(5);
再次=发票(一个);
A1 =一个;
A1 (1、5) = 1;
invA1 =发票(A1);%有方法吗?
我知道这可能是一个数学问题。这对我来说似乎是不可能的。我只是想知道对方的观点。谢谢你！

在回答这个问题。

接受的答案

约翰D 'Errico
约翰D 'Errico 2020年8月1日
编辑:约翰D 'Errico 2020年8月1日
布鲁诺是正确的在如何解决问题,也与它的一些问题。如果你多次使用这个工具,浮点错误将开始积累。
然而,仍然是个严重的问题。这是时间。我记得看着这个公式很久以前,当我第一次了解它。(35 - 40年前。)当时,我认为这个可能不是这样一个伟大的工具,由于数值问题,以及所需的时间来执行计算。
在等级1的概念更新一个矩阵的逆矩阵似乎很有趣,它在实践中严重的问题。天哪,必须更有效,只是验算的逆矩阵,对吧?这些事情总是测试。
我跑的测试代码。在我的测试中,我计算了随机矩阵大小N,那么这个矩阵的逆。接下来,我选择一个随机元素修改一些新的随机值。
最后,我用时间测量所需的时间矩阵的逆矩阵。然后我用时间测量所需的时间更新矩阵的逆。结果发现在下面的表。
Ninvtimeupdatetime更新率
_______________________________
50 4.6589 e-05 9.3269 e-05 2.0019
100 0.00012982 0.00048521 3.7375
200 0.0004016 0.0018684 4.6524
400 0.0014756 0.0073921 5.0094
600 0.0041071 0.017325 4.2183
800 0.0070771 0.032447 4.5848
1000 0.012438 0.055685 4.4771
1300 0.025226 0.11205 4.4419
1600 0.045956 0.31944 6.9509
1900 0.075096 0.81713 10.881
2200 0.11136 1.6726 15.019
2500 0.16798 3.0376 18.083
3000 0.29141 6.2889 21.581
所以,表中第一列的顺序矩阵用于测试。
invtime是用于计算的一个矩阵的逆矩阵的大小。
updatetime是updateinv所需的时间函数来完成工作。你应该看到,updateinv远远慢于一个简单的、直接的逆矩阵。
最后一列是相对成本。你应该看到,updateinv实际上开始恶化随着矩阵大小本身。
重对数图,您应该看到反矩阵本身需要更少的时间来执行。,你可以看到更大的矩阵的微分恶化。
如果你不相信我提供的数据,运行测试自己。甚至一个2 kx2k矩阵逆不是昂贵的计算。
一个=兰德(2000);
时间(@()发票(A))
ans =
0.084881
正如您可以看到的,这反映了在第2列在我的桌子上。我停在3 k方阵,因为所需的时间更新开始变得昂贵,我想把这反应。
我附加脚本用来做这些时间测试,如果你想验证我的结果。
所以你真的需要考虑如果这是一个好主意。虽然我一直强烈建议考虑如果你想计算矩阵的逆的几乎总是有更重要的事情要做,更新逆使用布鲁诺从未发布的代码很节省时间。如果您将执行多个更新,那么你是落后的,因为现在你还将处罚由于积累的错误。
终于,布鲁诺希望soend应该在优化自己的代码,我将添加配置文件工具告诉我大部分所需的时间似乎是在创建的宽容。
一个=兰德(2000);
时间(@()标准(一))
ans =
1.0575
时间(@()标准(一))
ans =
0.011862
规范(一)
ans =
1000.1
规范(一)
ans =
1000.1
所以,如果我只是修改一行代码写的布鲁诺,取代与调用标准规范,
函数[Amod, iAupdate] = updateinv (A, i, j, newAij iA)
%的输入:
% (n x n)矩阵
% i, j, newAij标量:newAij (i, j)将会改变
%的iA逆
%输出:
% Amod: n x n矩阵进行修改
% iAupdate:逆Amod,更新使用Shermana€“莫里森公式
Amod =一个;
Amod (i, j) = newAij;
d = newAij-A (i, j);
c = 1 + d * iA (j,我);
托尔= max(大小(A)) * eps(规范(A));
如果abs (c) <托尔
警告(更新矩阵可能是不准确的);
如果c > 0
c =托尔;
其他的
c =托尔;
结束
结束
iAupdate = iA - d / c * (iA (:, i) * iA (j,:));
结束
所需的时间已经倒在他们的行为。
Ninvtimeupdatetime更新率
_______________________________
50 4.0205 e-05 9.2221 e-06 0.22938
100 0.0001385 3.005 0.21697 e-05
200 0.00039433 7.6963 0.19517 e-05
400 0.0018709 0.00019188 0.10256
600 0.0040269 0.0012491 0.31018
800 0.0071675 0.0025266 0.3525
1000 0.012501 0.0052236 0.41786
1300 0.023901 0.011431 0.47824
1600 0.044222 0.01764 0.3989
1900 0.073962 0.024691 0.33384
2200 0.10989 0.033139 0.30156
2500 0.17115 0.043476 0.25402
3000 0.29513 0.063203 0.21415
使用规范的成本只是一个近似的估计a的规范,但在这里,我们看到我们可以做一些更新所需的时间的逆逆。积累的错误是另一个问题的问题,本身价值的研究。
2的评论
显示1年长的评论
(音译)
(音译) 2020年8月2日
谢谢你的澄清,特别是耗时比较。我想放弃这个想法来更新。直接逆重新计算似乎是最好的解决方案。

登录置评。

更多的答案(2)

弗拉基米尔•Sovkov
弗拉基米尔•Sovkov 2020年8月1日
我不确定有多少盈利数字,但谢尔曼莫里森定理可以某种程度上,看到的 https://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula
在你的例子中,u向量应该有选择,只有第一个非零元素和v向量只有5非零元素以便u1 * v5 = (1-A15)。
布鲁诺陈德良
布鲁诺陈德良 2020年8月1日
编辑:布鲁诺陈德良 2020年8月1日
应用这个谢尔曼Morisson的公式在弗拉基米尔•提供的页面,如果一组一个变化: (i, j) 新价值 newAij ,更新应该是这样的
函数[Amod, iAupdate] = updateinv (A, i, j, newAij iA)
%的输入:
% (n x n)矩阵
% i, j, newAij标量:newAij (i, j)将会改变
%的iA逆
%输出:
% Amod: n x n矩阵进行修改
% iAupdate:逆Amod,更新使用Sherman-Morrison公式
Amod =一个;
Amod (i, j) = newAij;
d = newAij-A (i, j);
c = 1 + d * iA (j,我);
托尔= max(大小(A)) * eps(规范(A));
如果abs (c) <托尔
警告(更新矩阵可能是不准确的);
如果c > 0
c =托尔;
其他的
c =托尔;
结束
结束
iAupdate = iA - d / c * (iA (:, i) * iA (j,:));
结束
测试脚本
% testupdate.m
%随机矩阵测试
一个=兰德(5);
iA =发票(一个);
%的随机变化
i =兰迪(大小(A, 1));
j =兰迪(大小(A, 2));
newAij = 10;
%更新矩阵及其逆矩阵
[Amod, iAupdate] = updateinv (A, i, j, newAij iA);
%检查
iAmod =发票(Amod)
iAupdate
relerr =规范(iAupdate-iAmod,“摇来摇去”)/规范(iAmod,“摇来摇去”)
结果:
> > testupdate
iAmod =
0.3427 -0.2397 0.0926 -0.1965 -0.0649
-3.1551 3.3784 0.1696 1.3277 -0.5608
-4.7509 1.9002 0.1144 2.6354 0.9978
5.2877 -3.8865 -0.3091 -2.5948 1.2505
-1.4484 1.5561 0.1196 1.7662 -1.5276
iAupdate =
0.3427 -0.2397 0.0926 -0.1965 -0.0649
-3.1551 3.3784 0.1696 1.3277 -0.5608
-4.7509 1.9002 0.1144 2.6354 0.9978
5.2877 -3.8865 -0.3091 -2.5948 1.2505
-1.4484 1.5561 0.1196 1.7662 -1.5276
relerr =
4.0984 e-16
从我的经验公式对两个原因并不特别有用
  • 我很少存储矩阵的逆,epsecially中型/大型规模。
  • 一个人可以失去精度多次当应用这个公式。
1评论
(音译)
(音译) 2020年8月2日
非常感谢您的回答!很遗憾我不能设置和约翰D 'Errico答案的答案。你的答案是直接的和伟大的。他的回答显示了一些时间分析更清楚地阐明这个问题,包括你的评论。原谅我接受。

登录置评。

类别

找到更多的在点云处理在帮助中心和文件交换

标签

s manbetx 845


释放

R2019a

社区寻宝

找到宝藏在MATLAB中央,发现社区如何帮助你!

开始狩猎!