Verified Error Bounds for Sparse Systems Part II: Inertia-Based Bounds, Least Squares and Nonlinear Systems

Verification methods provide mathematically correct error bounds for the solution of a numerical problem. That includes the proof of solvability of the problem and often uniqueness of the solution within the computed bounds. There are many verification methods for standard problems in numerical analysis, including linear and nonlinear systems of equations, matrix decompositions, eigenproblems, local and global optimization, and ordinary and partial differential equations. Many of those verification methods are included in INTLAB, the MATLAB/Octave toolbox for reliable computing. Despite many efforts, the solution of general sparse linear systems was an open problem. In Part I of this note, we presented an algorithm computing verified bounds for the solution of general real or complex sparse linear systems with condition number up to the limit [Formula: see text] in double precision. That algorithm splits into three subalgorithms for symmetric positive definite, symmetric indefinite, and general input matrix [Formula: see text]. It is based on a mathematically correct lower bound on the smallest singular value [Formula: see text]. In this Part II, we use a method published by the author in 1995 based on the inertia of a symmetric matrix. A key point is, as in Part I, a factorization [Formula: see text] such that [Formula: see text] and [Formula: see text] have identical sets of singular values with the smallest one close to [Formula: see text]. Numerical evidence suggests that the method is often a little slower than that in Part I, however, more robust. That means, for some of the few cases where the method in Part I could not compute verified bounds successfully, the method in this Part II succeeded. Furthermore, we show how to compute inclusions with almost maximal accuracy for all entries, i.e., all bounds differ by few bits, that is, based on a fast method to compute accurate approximations and bounds for extremely ill-conditioned dot products using a very efficient MATLAB implementation. We show how to treat a system with nearly symmetric input matrix in the sense that [Formula: see text] is small compared to [Formula: see text]. That is useful if symmetry is lost due to rounding and may improve the performance significantly. We show that Algorithm “verifySparseNearSym1” in Part I of the note is correct for unsymmetric input matrix without change. Moreover, algorithms are given to compute verified error bounds for a least squares problem and an underdetermined system of linear equations with sparse input matrix. Furthermore, we show how to compute verified error bounds for the solution of a system of nonlinear equations with sparse Jacobian. In all cases, the algorithms for sparse square linear systems of Part I and this Part II can be used.