Accurate solution of dense linear systems, part I: Algorithms in rounding to nearest

作者：Rump Siegfried M^*

来源：Journal of Computational and Applied Mathematics, 2013, 242: 157-184.

DOI：10.1016/j.cam.2012.10.010

• Linear system
• Rounding to nearest (extremely) ill-conditioned
• Error-free transformation
• Error analysis
• Rigorous error bounds

We investigate how extra-precise accumulation of dot products can be used to solve ill-conditioned linear systems accurately. For a given p-bit working precision, extra-precise evaluation of a dot product means that the products and summation are executed in 2p-bit precision, and that the final result is rounded into the p-bit working precision. Denote by u = 2(-p) the relative rounding error unit in a given working precision. We treat two types of matrices: first up to condition number u(-1), and second up to condition number u(-2). For both types of matrices we present two types of methods: first for calculating an approximate solution, and second for calculating rigorous error bounds for the solution together with the proof of non-singularity of the matrix of the linear system. In the first part of this paper we present algorithms using only rounding to nearest, in Part II we use directed rounding to obtain better results. All algorithms are given in executable Matlab code and are available from my homepage.

• 出版日期2013-4