矩阵条件数及高斯算法平滑分析的进一步研究
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

supported by the National Natural science Foundation of China under Grant No.60273045(国家自然科学基金);the shanghai science and Technology Development Fund of China under Grant No.025115032(上海市科技发展基金)


Further Study on the Smoothed Analysis of Condition Number of Matrix and Gaussian Algorithm
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n3).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ2≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og2(n)+3log2(1/σ)+log2log2n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og2n+3log2(1/σ)+4√2+log2n+log2(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n2)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og2n+3log2(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.

    Abstract:

    Smoothed analysis aims to explain the success of algorithms that work well in practice while performing poorly in worst-case analysis. High performance computers have been used extensively in solving large scale linear systems and decomposition of matrix. The simplest and most implemented method of solving linear systems is Gaussian elimination (Gaussian algorithm). Natural implementations of Gaussian elimination use O(n3) arithmetric operations to solve a system of n linear equations in n variables. If the coefficients of these equations are specified using m bits, in the worst case it suffices to perform the elimination using mn bits of precision, because the elimination may produce large intermediate entries. However, a large number of experiments in numerical analysis have indicated that this high precision is necessary rarely in practice. Huge condition number and growth factors of matrix are always the main roots that make the matrix ill-conditioned and lead to produce a large error in solution. Let A be the matrix of independent Gaussian random variables centered at A, each of the variances12s, K(A) be the condition number of matrix A. Sankar et al. performed a smoothed analysis of condition numbers and growth factors of matrices. They showed that for any matrixnnRAand a>0, ()saanAK)log(413.64])(Pr[+, and the smoothed complexity of bits of precision needed to solve Ax=b to m bits of accuracy using Gaussian algorithm is at most: .7loglog)/1(log3)(log72222++++nnms They made some mistake in their proof. The mistake is corrected in this paper, and the smoothed complexity of bits of precision is corrected as: m+71og2n+3log2(1/σ)+4√2+log2n+log2(1/σ)+7.367. Two inequalities on norm of the matrix and product of the two random variables respectively are presented, and the smoothed analysis of condition number of matrix is simplified to .26])(Pr[2saanAK The conjecture asOanAK])(Pr[ is solved to some extent. The smoothed complexity of bits of precision is improved to 7.)(1/3log8log22+++snm And the experimental results show that the new smoothed analysis results are much better.

    参考文献
    相似文献
    引证文献
引用本文

杨智应,朱洪,宋建涛.矩阵条件数及高斯算法平滑分析的进一步研究.软件学报,2004,15(5):650-659

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2003-03-24
  • 最后修改日期:2003-10-08
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号