A new approach for solving ill-posed problems is proposed. The approach makes it possible to effectively calculate normal pseudosolutions for ill-conditioned systems of linear algebraic equations and to find an acceptable solution with a minimum filling of sparse matrices. Many practical problems of finding solutions based on available data are typical representatives of ill-posed problems. It should be noted that such problems have a number of unpleasant properties of manipulating, and for their solution standard methods are inapplicable. Thanks to the works of academician A.N. Tikhonov developed a general strategy for constructing stable methods for solving ill-posed (unstable problems) in operator form [1]. It is based on the notion of a regularizing operator or a regularizing algorithm. Realizing this algorithm, it is necessary to solve the normal regularized systems of linear algebraic equations. This system is often ill-conditioned. It is necessary to choose the regularization parameter correctly in order to reduce the condition number. It is also important to choose a solution method that is numerically stable. Often ill-posed problems lead to systems with large and sparse coefficient matrices, in which most of the elements are zero.
Consider the system linear algebraic equations
where ∈ × , ∈ .
the regularized normal system
The regularized solution of the system (
The condition number of the system (3) is found as = , ( + 2 ) = , 2( + 2 ) = 12+ 2 2 + 2
Instead of system (3), it is proposed to consider the equivalent system of algebraic equations [2]: where = −
is the residual vector.
The condition number of the system matrix (3) is slightly less than the condition number of the normal system equations matrix (2). Therefore, in order to reduce the condition number, the parameter > 0 is introduced into the system (3): ( − 2 ) ( ) = (
) 2 ) ( ) = (
) ↔ С( ) = . the matrix (4) is attained for ∗ = √ 2
+ 2, where is the minimal singular number of the matrix A.
When choosing ∗∗ = √ 2the spectral condition number of the system matrix (4) will be √ 12 +2 2. Thus, this approach
make it possible to increase the numerical stability of the problem and to reduce errors in solving of the equations system (
The augmented system of equations modification leads to an increase in the dimension of the original problem. Using known methods to solve it leads to computational difficulties. Therefore, it is proposed to consider the modification of the direct projection method [4, 6] with the pivoting, which allows to reduce the number of arithmetic operations to obtain the augmented system of equations solution.
Due to the special structure of the linear algebraic equations augmented system matrix and direct projection method vectors in the augmented system, from = +
equations n are solved analytically. This means that it is possible to calculate in advance the values of the first n vectors and indicate the vectors structure in the next steps of the algorithm.
For sparse systems, in order to reduce the fill-in, it is proposed to apply the Markowitz strategy in the direct projection method.[3] Markowitz count of an entry с
( )is a value
Let the k-th step of the direct projection method be performed. The number ( , ) denotes the number of non-zero entries in the i-th row of the active submatrix С and ( , ) is the number of non-zero elements in the j-th column of С .The
= ( ( , ) − 1)( ( , ) − 1), ( , = 1 … ).
is equal to the number of elements that change the value at the transition to the next elimination step, if the entry с ( ) is chosen as the pivot one, it is the upper border for the fill-in that occurs when с ( ) is selected. = min{ | , = … }. count is much easier than calculating the value of the fill for each entry С . condition
The Markowitz strategy is that at each step k, the entry with the Markowitz count is taken as the pivot. This does not necessarily mean that the fill-in minimum at the k-th step will be obtained; however, finding Markowitz To ensure numerical stability, we will choose the elements of the active submatrix for the role of the pivot, satisfying the |с ( )| ≥
max ≤ ≤ , ≤ ≤ |с ( )|, (4)
We give the system of equations solution (
A new approach to solving ill-posed problems is considered. This approach makes it possible to effectively calculate normal pseudosolutions of ill-conditioned linear equations systems and to find an acceptable solution in accuracy. Its modification for this problem, taking into account the sparseness of the augmented system, allows to significantly reduce the number of steps of the algorithm, as well as to reduce the amount of random-access memory and arithmetic operations. The Markowitz strategy in this modification allows to reduce the fill-in of a sparse matrix. This fact significantly simplifies the problem solving and reduces the time for calculation, which is a rather significant advantage.