Solving Separable Nonlinear Equations Using LU Factorization

Separable nonlinear equations have the form where the matrix and the vector are continuously differentiable functions of and . We assume that and has full rank. We present a numerical method to compute the solution for fully determined systems ( ) and compatible overdetermined systems ( ). Our method reduces the original system to a smaller system of equations in alone. The iterative process to solve the smaller system only requires the LU factorization of one matrix per step, and the convergence is quadratic. Once has been obtained, is computed by direct solution of a linear system. Details of the numerical implementation are provided and several examples are presented. 1. Introduction Many applications [1, 2] lead to a system of separable nonlinear equations: where the matrix and the vector are continuously differentiable functions of and with . Typically is very small, and for compatible systems (i.e., those with exact solutions) is usually close to . We assume that is Lipschitz continuous and has full rank in a neighborhood of a solution ; thus, we assume that has full rank in this neighborhood. Standard projection methods, such as VARPRO [3, 4], transform the problem (1) to the minimization of a function in alone: where we use the Euclidean norm throughout this paper. In [5, 6], we proposed a different method, using left orthonormal null vectors of , to reduce (1) to an equation of the form in alone. We assumed that the system is fully determined ( ), and has full rank . That algorithm was extended to overdetermined systems ( ) with full rank in [7]. One QR factorization of is required in each iterative step of the methods used to solve these smaller systems for . For details of these methods and their relationship to other methods, see [1, 7]. In this paper, we use a special set of linearly independent left null vectors of to construct a bordered matrix which inherits the smoothness of . We use this to construct a system of equations of the form in the unknowns alone. The smaller system inherits the Lipschitz continuity and nonsingularity of the Jacobian matrix of the original system (1) so that quadratic convergence of the Newton or Gauss-Newton method for solving is guaranteed. The QR factorization of used in previous methods is here replaced by an LU factorization of , so the cost of each iterative step may be significantly reduced. The method works for both fully determined systems and compatible overdetermined systems. This paper extends the work using bordered matrices and LU factorization for underdetermined systems in [8] ( ) to fully