神马作文网矩阵求特征值 和矩阵求逆 计算复杂度分析,
来源：学生作业帮 编辑：神马作文网作业帮 分类：综合作业 时间：2024/11/10 18:39:44
矩阵求特征值 和矩阵求逆 计算复杂度分析,
上次您给我解答了,可是貌似这样一个结论无法令别人信服,所以我还是需要更详细和准确的解答.请问你给我的那个关于o（n^3）的答案是如何得到的,具体它是计算次数,还是什么,另外,我需要具体算出 o（n^3）前面的系数,我应该如何做,具体可以参考什么数学书?
上次您给我解答了,可是貌似这样一个结论无法令别人信服,所以我还是需要更详细和准确的解答.请问你给我的那个关于o（n^3）的答案是如何得到的,具体它是计算次数,还是什么,另外,我需要具体算出 o（n^3）前面的系数,我应该如何做,具体可以参考什么数学书?
首先要明确,一般计算复杂度是针对算法的,而不是针对问题本身,对于问题本身的分析要复杂得多,远远超出你目前的知识范围.
一般稠密矩阵计算的各种算法复杂度都是O(n^3),这个需要对每个算法都进行分析,我只是把各种结论归结起来告诉你.对于具体的算法而言,这个是数出来了,不需要很特别的技巧（某些含log的需要解递归,但这里一般不用）,比如说m*k的矩阵和k*n的矩阵相乘,最平凡的算法的计算次数是2mnk,就是从下面的循环里数出来的
for i=1:m
for j=1:n
for r=1:k
c(i,j)=c(i,j)+a(i,r)*b(r,j)
endfor
endfor
endfor
至于LU分解和Cholesky分解的计算次数分别是2/3*n^3和1/3*n^3,也是直接从循环里数出来的,不需要什么技巧.特征值的QR算法本质是迭代法,由于大致知道一般来讲总是很快进入局部的二次收敛,平均一个特征值需要2步（这个统计数据只适合于古典的Francis QR）,才能估计出具体的系数.
你最好是找一本矩阵计算的书自己先学一遍,不然我再多罗嗦也没用.
一般稠密矩阵计算的各种算法复杂度都是O(n^3),这个需要对每个算法都进行分析,我只是把各种结论归结起来告诉你.对于具体的算法而言,这个是数出来了,不需要很特别的技巧（某些含log的需要解递归,但这里一般不用）,比如说m*k的矩阵和k*n的矩阵相乘,最平凡的算法的计算次数是2mnk,就是从下面的循环里数出来的
for i=1:m
for j=1:n
for r=1:k
c(i,j)=c(i,j)+a(i,r)*b(r,j)
endfor
endfor
endfor
至于LU分解和Cholesky分解的计算次数分别是2/3*n^3和1/3*n^3,也是直接从循环里数出来的,不需要什么技巧.特征值的QR算法本质是迭代法,由于大致知道一般来讲总是很快进入局部的二次收敛,平均一个特征值需要2步（这个统计数据只适合于古典的Francis QR）,才能估计出具体的系数.
你最好是找一本矩阵计算的书自己先学一遍,不然我再多罗嗦也没用.