Newton's Method is an important algorithm for solving nonlinear systems of equations. For any solution algorithm, the principle concerns are robustness (finding a solution reliably) and efficiency (finding a solution quickly). Newton is simple in principle, but a useful implementation must deal with a variety of practical and theoretical obstacles.By using partial derivatives, Newton's Method can model the shape of the residual surface to provide quadratic convergence near the solution: the number of correct digits doubles each iteration. But far from the solution, the full Newton step may go too far, leading to divergence or oscillation. Or the full step may be illegal, leading to economic nonsense like negative prices and numerical problems like taking the log of a negative number. Automatic damping -- taking shorter steps along the Newton direction -- can improve global convergence in such cases.The most expensive part of Newton's Method is factoring the Jacobian matrix. The Jacobian can be very large in contemporary macroeconometric models, particularly forward-looking models that introduce simultaneity across time periods as well as between equations. Newton is impractical for such large models unless it can exploit the sparsity of the Jacobian. Sparse direct methods can be applied to the entire Jacobian; one advantage of direct methods is that after the first iteration, subsequent factorings can be extremely fast. An alternative is iterative Krylov subspace methods; their small memory requirements are an advantage, but they may fail to converge. In the case of forward-looking models, the stacked Jacobian has a block band-diagonal structure that can be exploited by direct methods or for preconditioning iterative methods.his paper describes enhancements to Newton's Method used in the TROLL modeling system and illustrates them with a variety of contemporary models.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
file. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Length: Date of creation: 05 Jul 2000 Date of revision: Handle: RePEc:sce:scecf0:308
Contact details of provider: Postal: CEF 2000, Departament d'Economia i Empresa, Universitat Pompeu Fabra, Ramon Trias Fargas, 25,27, 08005, Barcelona, Spain Fax: +34 93 542 17 46 Email: Web page: http://enginy.upf.es/SCE/ More information through EDIRC
For technical questions regarding this item, or to correct its listing, contact: (Christopher F. Baum).
Related research
Keywords:
References listed on IDEAS Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.: