Linear systems, underdimensioned

Since these underdimensioned nonlinear systems will also be solved using a modified Newton method, it is essential to tackle the subproblem of the solution of underdimensioned linear systems. 

The m equations (8.3) with the n — m conditions (8.12) make the system square and, consequently, solvable through an appropriate algorithm (i.e.. Gauss factorization) when the resulting matrix is nonsingular. As special but important case, the values cj are all zero. Also to obtain a solution of the underdimensioned linear system that can exploit the Gauss factorization, the variables x are separated into m dependent variables, x, and into n — m independent variables, x , to which a numerical value is assigned. 

The first defect is common to both the factorizations and is shared with traditional ways of solving square and underdimensioned linear systems. It has been highlighted in the literature recently (Buzzi-Ferraris, 2011a). 

The problem of selecting the most reasonable pivot to detect real linearly dependent equations occurs not only for underdimensioned linear systems but also in the solution of singular square systems. It happens, for instance, when a Newton s method is adopted to solve a square nonlinear system and the resulting... 

The BzzFactorizedGaussAttic class in the BzzMath library solves square or underdimensioned linear systems with dense matrices using a stable Gauss factorization. 

If the linearized system together with the linear equations has some linear dependencies, the program switches to the underdimensioned nonlinear system of the active constraints solution. A BzzNonLinearUnderdimen-sionedSystem class object is adopted to solve this underdimensioned... 

Buzzi-Ferraris and Tronconi (1986) illustrated a methodolo that could be adopted when the Jacobian is ill-conditioned or singular In this situation, some of the equations in (7.38) are linearly dependent consequently, it is possible to eliminate the corresponding rows. Since the resulting system becomes underdimensioned, it is appropriate to adopt the LQ factorization that produces the solution with the minimum Euclidean norm for the vector d . This makes it possible to avoid an excessively large correction on a vector of this kind. The numerical solution satisfies not only the subsystem but also the equations that were removed, since, if compatible, they are almost a linear combination of the others. 

The second defect of LQ factorization is important for sparse matrices. In fact, dense matrices require double the computational effort of Gauss factorization. If the matrix is sparse, this gap may become larger and a dramatic filling of the factorized matrix may occur. The advantages of LQ factorization are a stable solution of an underdimensioned system (if the system is standardized), and the easy and safe removal of all linear combinations among equations. 

With square systems with very ill-conditioned (or singular) matrices and underdimensioned systems, it is mandatory to swap the columns during pivoting. This is the only way to obtain a reasonable solution and identify the real linearly dependent equations. 

---