24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

Krasic

新虫 (初入文坛)

应助: 1 (幼儿园)
金币: 29.3
红花: 1
帖子: 24
在线: 12.5小时
虫号: 1748341
注册: 2012-04-10
专业: 系统科学与系统工程

[求助] 请问同阶矩阵求逆和求平方根的计算复杂度哪个高，分别是多少？谢谢

请问同阶矩阵求逆和求平方根的计算复杂度哪个高，分别是多少？谢谢

回复此楼

» 猜你喜欢

职称评审没过，求安慰已经有54人回复
垃圾破二本职称评审标准已经有19人回复
毕业后当辅导员了，天天各种学生超烦已经有5人回复
26申博自荐已经有3人回复
A期刊撤稿已经有4人回复

1楼 2012-05-17 10:58:02

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

acmuser

银虫 (小有名气)

应助: 22 (小学生)
金币: 324.5
红花: 1
帖子: 74
在线: 22.9小时
虫号: 1582407
注册: 2012-01-18
性别: GG
专业: 计算数学与科学工程计算

【答案】应助回帖

★ ★ ★ ★ ★
Krasic: 金币+5, ★★★很有帮助, 非常感谢!我想一下，再继续请教你！ 2012-05-22 11:04:38

引用回帖:

7楼: Originally posted by Krasic at 2012-05-20 09:18:42:
1，非常感谢，我是分别用^(-1)和^(-1/2)做的求逆和求平方根。是不想和inv与sqrtm等价？

2，还有，实际上我不关心那么高阶的矩阵，低阶（5-10阶）的时候，求逆和平方根的计算复杂度如何，能不能请你做个图分析一

不清楚算法的具体实现，所以很难给出定量的复杂度，从图中可以看出，当n不太大时，平方根是n^1.2, 而求逆大概是n^0.6. 你可以用这个code自己算。

function [t1,t2,t3]=test2(t1,t2,t3)

if nargin == 0
N = 30; M = 100;
t1 = zeros(1,N);
t2 = zeros(1,N);
t3 = zeros(1,N);
for n=1:N
      n
      for m=1:M
      A = rand(n);
      tic; inv(A); t1(n)=t1(n)+toc;
      tic; sqrtm(A); t2(n)=t2(n)+toc;
      tic; mpower(A,0.5); t3(n)=t3(n)+toc;
      end
end
end
t1 = t1/M; t2=t2/M; t3=t3/M;
n = 1:N;
loglog(n, t1, 'rx-', n, t2, 'bo-', n, t3, 'g+-')
legend('inv', 'sqrtm', 'mpower','Location','NorthWest');
hold on
p1=polyfit(log(n),log(t1),1);
p2=polyfit(log(n),log(t2),1);
p3=polyfit(log(n),log(t3),1);

f1 = @(x)(p1(1)*log(x)+p1(2));
f2 = @(x)(p2(1)*log(x)+p2(2));
f3 = @(x)(p3(1)*log(x)+p3(2));

X = [min(n)*1.1, max(n)/1.1];

line(X, exp(f1(X)-1));
text(X(1), exp(f1(X(1))-0.5), ['the slope is', num2str(p1(1))])
line(X, exp(f2(X)+1));
text(X(1), exp(f2(X(1))+0.5), ['the slope is', num2str(p2(1))])
line(X, exp(f3(X)-1));
text(X(1), exp(f3(X(1))-0.5), ['the slope is', num2str(p3(1))])