Linearization Estimates Of The Optimal Backward Errors For Least Squares Problems

The backward error is a basic concept in numerical algebra and the back-ward error analysis is useful in many respects. For example, it is applied to examine the stability of new algorithms. There has been a lot of work on the backward error analysis for the least squares problem. A explicit formula was discovered for the backward error of an approximate solution to the ordinary least squares problem (OLS) by Walden, Karlson, and Sun, which raises a lot of subsequent researches. Higham presented a numerically stable version. Note that the computation of the backward error through this formula is expensive, recent attention has been focussed on obtaining more easily computable bounds on it. Karlson and Walden derive upper and lower bounds of the backward error. For large sparse problem, Malyshev and Sadkane suggest using Lanczos bidiago-nalization to evaluate Walden, Karlson, and Sun's formula. The backward errors for the constrained least squares problems, including the equality constrained least squares problem (LSE) and the least squares minimization over a sphere (LSS), are studied by Cox and Higham. They obtain an upper bound and a lower bound of the backward error. Malyshev studies LSS problem and prove that the optimal backward error of LSS problem is either the upper bound or the lower bound derived by Cox and Higham. Chang and Titley-Peloquin present an estimate for the extended minimal backward error of the scaled total least squares problem (STLS) which is an asymptotically tight lower bound on the true backward error.In this thesis, the author applies the linearization method to estimate the backward error of approximate solutions to several least squares problems, in-cluding the ordinary least squares problem(OLS), the equality constrained least squares problem(LSE), the least squares problem over a sphere(LSS), and the scaled total least squares problem(STLS). For the OLS and the STLS problems, it proves several new results about the linearization estimates derived by Higham and Higham, Chang and Titley-Peloquin, respectively. For the LSS and the LSE problems, the author derives linearization estimates of the backward errors and numerically compare them with existing backward error bounds. Experiments show that the linearization estimates are good enough approximations of the backward errors as the approximate solution approaches the exact one.This thesis includes five parts.The first section is preface. The background, the stage of development about optimal backward errors for least squares problems, status about the research of optimal backward errors for least squares problems are introduced and the main problems to be solved in this paper are also shown in this part.The second section is focused on linearization estimates of the optimal back-ward errors for the ordinary least squares problems (OLS). First, a formula of the linearization estimates of the optimal backward errors is given for the OLS problem. Second, the relationship between the linearization estimates and the optimal backward errors is addressed. Also, the relationship between the lin-earization estimates and the estimates derived from Walden, Karlson is studied and numerical tests are carried out in the end of this section.The third section deals with the estimates for equality constrained least squares problems (LSE). In this section, first of all, the author shows the lin-earization estimates of the backward errors for the LSE problem. And then gives a further estimate of the linearization estimate owing to the computation of the latter one is rather difficult. Second, the relationship between the linearization estimates and the optimal backward errors is discussed and numerical experi-ments are done to test the new result. Finally, the author gives the linearization estimate of the upper bound on the backward errors derived by Cox and Higham.The fourth section is about the estimates of the backward errors for the least squares problem over a sphere(LSS). First, it presents the linearization estimate of the LSS problem, and then analyses the relationship between the linearization estimate and the optimal backward errors. Lastly, the author proves that the linearization estimate is a good approximation to the optimal backward error in the asymptotic situation and tests the new estimate by numerical experiments. The last section deals with the relationship between the approximate esti-mate and the linearization estimate of the backward errors for the scaled total least squares problem (STLS) obtained by Chang and Titley-Peloquin.