On Piecewise Affine Mappings in $R^n $
Werner C. Rheinboldt, James S. Vandergraft · SIAM Journal on Applied Mathematics · 1975
Let $H_1 , \cdots ,H_p $, be given hyperplanes which divide $R^n $ into finitely many closed, convex polytopes $\bar C_1 , \cdots \bar C_q $, and consider a continuous, piecewise affine mapping $F:R^n \to R^n ,Fx = A_j x + a^J ,\forall x \in \bar C_J ,j = 1, \cdots ,q$, with nonsingular $A_J \in L( {R^n } )$. Such functions arise, for instance, in the piecewise linear analysis of nonlinear resistive electric networks. We prove here that F is surjective if the signs of the determinants of all matrices $A_j $ are the same, and that then the Katzenelson algorithm for solving $Fx = b$ will always reach a solution. This extends recent results of Fujisawa and Kuh who proved a homeomorphism theorem for piecewise affine mappings and considered the Katzenelson algorithm in that case. We also augment their basic theorem in another direction by showing that when all $A_j $ are P- or M-matrices then F is a (surjective) P- or M-function, respectively. In the M-function case this implies, for example, the global convergence of the nonlinear Gauss–Seidel process.