-
题名矩阵条件数及高斯算法平滑分析的进一步研究
被引量：5
- 1
-
-
作者
杨智应
朱洪
宋建涛
-
机构
复旦大学计算机科学与工程系
复旦大学智能信息处理实验室
-
出处
《软件学报》
EI
CSCD
北大核心
2004年第5期650-659,共10页
-
基金
国家自然科学基金60273045
上海市科技发展基金025115032 ~~
-
文摘
算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n3).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设A为任意矩阵,A是A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差12s.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了()saanAK)log(413.64])(Pr[+.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为7.loglog)(1/3log)(7log2222++++nnms在上述结果的证明过程中存在错误,将其纠正后得到以下结果:7.367.)/1(loglog24)(1/3log7log2222++++++ssnnm通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到saa226])(Pr[nAK.部分地解决了Sankar等人提出?
-
关键词
平滑复杂度
矩阵条件数
矩阵增长因子
平滑精度
-
Keywords
smoothed complexity
condition number of matrix
growth factor of matrix
smoothed precision
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
