Regularization of ill - conditioned linear systems

Abstract

The numerical solution of the linear system Ax = b, arises in many branches of applied mathematics, sciences, engineering and statistics. The most common source of these problems is in the numerical solutions of or dinary and partial differential equations, as well as integral equations. The process of discretization by means of finite differences often leads to the solu tion of linear systems, whose solution is an approximation to the solution of the original differential equation. If the coefficient matrix is ill-conditioned or rank-deficient, then the computed solution is often a meaningless approx imation to the unknown solution. Regularization methods are often used to obtain reasonable approximations to ill-conditioned systems. However, the methods for choosing an optimal regularization parameter is not always clearly defined. In this dissertation, we have studied various methods for solving ill-conditioned linear systems, using the Hilbert system as a prototype. These systems are highly ill-conditioned. We have examined various regularization methods for obtaining meaningfully approximations to such systems. Tikhonov Regularization method proved to be the method of choice for regularizing rank deficient and discrete ill-posed problems com pared to the Truncated Singular Values decomposition and the Jacobi and Gauss-Seidel Preconditioner’s for boundary values problems. The truncated singular value decomposition truncate the harmful effect of the small singu lar values on the solution by replacing them with exact zero. The truncation improves the solution to an extent and the solution deteriorates again. The maximum error in the solution occurs at the cut-off level λ = 2.2520×10−10. The optimal solution was obtained at λ = 2.2520 × 10−10 . The Jacobi and the Gauss-Seidel preconditioner’s for sparse systems also gave an optimal solution. Our results using Tikhonov method, shows that in order 0 regularization, the accuracy of the solution increases with increasing values of the regular ization parameter, with optimal regularization parameter of 100, giving an accuracy of 15 digits. Order 2 regularization gave an accuracy of about 13 digits, with optimal parameter of 10−9, while order 1 regularization gave an accuracy of only 3 digits, corresponding to an optimal parameter of 10−13. In all the three cases, the optimal regularization parameters were determined by inspection, using the minimum error. The L-Curve method failed to in dicate the optimal regularization parameter. We applied regularization to the solution of an ill-conditioned discretized Fredholm integral equation of the first kind. First, we transformed the integral equation into a linear system Ax = b, where A is a 17×17 positive definite matrix. None of the standard meth ods for solving linear systems gave the desired solution. The accuracy of the solution increases with increasing values of the regularization parame ter. The regularized solutions of order one and two, gave an accuracy of about 3 digits accuracy, with parameter values λ = 10−1 and λ = 10−3 re spectively, while order zero shows no accuracy in the regularized solutions. The L-curve was applied to determine the optimal regularization parameter. The optimal regularization parameter corresponding to the optimal solution was determined at the corner part of the L-curve. The L-curve for order two regularization gave us the optimal solution with a regularization param eter value λ = 10−3. For order zero and one, the regularization parameter concentrated at the sharp corner of the L-curve did not approximate to the exact solution. Order zero and one in this case has no optimal regularization parameter on the L-curve.