DocumentCode :
1513406
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
Volume :
50
Issue :
7
fYear :
2001
fDate :
7/1/2001 12:00:00 AM
Firstpage :
689
Lastpage :
698
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;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.936235
Filename :
936235
Link To Document :
بازگشت