###
DOI:
Journal of Software:2006.17(10):2057-2062

基于0-保留扰动的高斯算法平滑复杂度分析
杨智应,雷向欣,朱洪
(上海海事大学,计算机科学与工程系,上海,200135;复旦大学,计算机科学与工程系,上海,200433)
Smoothed Analysis of Gaussian Algorithm Based on Zero-Preserving Perturbations
YANG Zhi-Ying,LEI Xiang-Xin,ZHU Hong
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3308   Download 3658
Received:December 30, 2004    Revised:March 06, 2006
> 中文摘要: 算法的平滑复杂度能够更合理地反映算法的实际性能.在运行高斯算法求解线性系统过程中,矩阵条件数是导致求解误差偏大的一个因素.Sankar等人用0-保留高斯扰动进行对称矩阵条件数平滑分析.然而,Sankar等人给出的平滑复杂度过高而且复杂.为了解决这个问题,首先提出了两个关键的不等式;然后将这两个不等式用于对称矩阵条件教的平滑分析,得到更简单、更低的平滑复杂度;并利用该结果对高斯算法求解精度进行平滑分析,从而得到更低的平滑复杂度.
Abstract:Smoothed complexity of algorithm can explain the practical performance of algorithm more efficiently. Condition number of matrix is a main root to result in large error in solution during the running of Gaussian algorithm. Sankar, et al. performed a smoothed analysis of condition number of symmetric matrix under zero-preserving perturbations. However, the smoothed complexity presented by Sankar, et al. was higher and more complicated. To solve this problem, two key inequalities are presented. The inequalities are used to improving the smoothed complexity of condition number of symmetric matrix. The smoothed analysis of bits of precision needed by using Gaussian algorithm is performed and lower smoothed complexity is presented.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60496321,60373021(国家自然科学基金);the Shanghai Education Council Science and Technology Development Fund of China under Grant No.05FZ14(上海市教委科技项目);the Shanghai Maritime University ShippingInformation Engineering Core Subject Project Fund under Grant No.XL0101-2(上海海事大学航运信息工程重点学科基金) Supported by the National Natural Science Foundation of China under Grant Nos.60496321,60373021(国家自然科学基金);the Shanghai Education Council Science and Technology Development Fund of China under Grant No.05FZ14(上海市教委科技项目);the Shanghai Maritime University ShippingInformation Engineering Core Subject Project Fund under Grant No.XL0101-2(上海海事大学航运信息工程重点学科基金)
Foundation items:
Reference text:

杨智应,雷向欣,朱洪.基于0-保留扰动的高斯算法平滑复杂度分析.软件学报,2006,17(10):2057-2062

YANG Zhi-Ying,LEI Xiang-Xin,ZHU Hong.Smoothed Analysis of Gaussian Algorithm Based on Zero-Preserving Perturbations.Journal of Software,2006,17(10):2057-2062