Title :
Optimal algorithms for well-conditioned nonlinear systems of equations
Author :
Bianchini, Monica ; Fanelli, Stefano ; Gori, Marco
Author_Institution :
Dipt. di Ingegneria dell´´Inf., Siena Univ., Italy
fDate :
7/1/2001 12:00:00 AM
Abstract :
We propose solving nonlinear systems of equations by function optimization and we give an optimal algorithm which relies on a special canonical form of gradient descent. The algorithm can be applied under certain assumptions on the function to be optimized, that is, an upper bound must exist for the norm of the Hessian, whereas the norm of the gradient must be lower bounded. Due to its intrinsic structure, the algorithm looks particularly appealing for a parallel implementation. As a particular case, more specific results are given for linear systems. We prove that reaching a solution with a degree of precision ε takes Θ(n2k2 log k/ε ), k being the condition number of A and n the problem dimension. Related results hold for systems of quadratic equations for which an estimation for the requested bounds can be devised. Finally, we report numerical results in order to establish the actual computational burden of the proposed method and to assess its performances with respect to classical algorithms for solving linear and quadratic equations
Keywords :
Newton method; computational complexity; parallel algorithms; function optimization; gradient descent; intrinsic structure; numerical results; optimal algorithm; optimal algorithms; quadratic equations; upper bound; well-conditioned nonlinear systems of equations; Acceleration; Differential algebraic equations; Differential equations; Iterative methods; Jacobian matrices; Linear systems; Newton method; Nonlinear equations; Nonlinear systems; Upper bound;
Journal_Title :
Computers, IEEE Transactions on