The Research Of Perturbation Analysis Based On Exact Real Arithmetic

Ⅲ-conditioned problems of numerical programs mean significant errors exist in the outputs when the input or the programs themselves been changed slightly. The detection of ill-conditioned problems is named perturbation. Perturbation is one of the critical practices to build reliable numerical programs. However, traditional perturbation needs a lot of manual work and is not suitable for large-scale problems. Recently, some automatic analysis frameworks with floating-point arithmetic are produced for perturbation. These tools would not tell whether the errors from are perturbation caused by ill-conditioned problems of numerical programs or the precision lost of floating-point arithmetic.In this paper, we introduce an automatic framework that utilizes exact real arithmetic to analyze large-scale ill-conditioned problems by computer. Using root mean square error to quantify the ill-conditioning, we compare the result from exact real number perturbation with the result from floating-point perturbation. We define perturbation magnitude factor to overcome the restriction of fixed magnitude in traditional perturbation. Meanwhile, we define perturbation probability factor to select part of the programs to perturb while traditional perturbation can not do that. Also, we design perturbation stub algorithm to insert perturbation code into the target source file.In this paper, we evaluate a bunch of classical ill-conditioned and non-ill-conditioned problems. The evaluation shows that our framework is able to detect the ill-conditioning in large-scale problems effectively. We are encouraged that exact real number perturbation can detect some ill-conditioned problems while floating-point perturbation can not. We also find that root mean square error from real number perturbation is large than the one from floating-point perturbation in ill-conditioned programs. We see root mean square error changed as perturbation magnitude or perturbation probability changed in ill-conditioned programs. What is more, we confirm that different ill-conditioned programs have different ill-conditioning.