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.