New quasi-Newton method for solving systems of nonlinear equations

Ladislav Lukšan; Jan Vlček

Applications of Mathematics (2017)

  • Volume: 62, Issue: 2, page 121-134
  • ISSN: 0862-7940

Abstract

top
We propose a new Broyden method for solving systems of nonlinear equations, which uses the first derivatives, but is more efficient than the Newton method (measured by the computational time) for larger dense systems. The new method updates QR or LU decompositions of nonsymmetric approximations of the Jacobian matrix, so it requires O ( n 2 ) arithmetic operations per iteration in contrast with the Newton method, which requires O ( n 3 ) operations per iteration. Computational experiments confirm the high efficiency of the new method.

How to cite

top

Lukšan, Ladislav, and Vlček, Jan. "New quasi-Newton method for solving systems of nonlinear equations." Applications of Mathematics 62.2 (2017): 121-134. <http://eudml.org/doc/287947>.

@article{Lukšan2017,
abstract = {We propose a new Broyden method for solving systems of nonlinear equations, which uses the first derivatives, but is more efficient than the Newton method (measured by the computational time) for larger dense systems. The new method updates QR or LU decompositions of nonsymmetric approximations of the Jacobian matrix, so it requires $O(n^2)$ arithmetic operations per iteration in contrast with the Newton method, which requires $O(n^3)$ operations per iteration. Computational experiments confirm the high efficiency of the new method.},
author = {Lukšan, Ladislav, Vlček, Jan},
journal = {Applications of Mathematics},
keywords = {nonlinear equation; system of equations; trust-region method; quasi-Newton method; adjoint Broyden method; numerical algorithm; numerical experiment},
language = {eng},
number = {2},
pages = {121-134},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {New quasi-Newton method for solving systems of nonlinear equations},
url = {http://eudml.org/doc/287947},
volume = {62},
year = {2017},
}

TY - JOUR
AU - Lukšan, Ladislav
AU - Vlček, Jan
TI - New quasi-Newton method for solving systems of nonlinear equations
JO - Applications of Mathematics
PY - 2017
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 62
IS - 2
SP - 121
EP - 134
AB - We propose a new Broyden method for solving systems of nonlinear equations, which uses the first derivatives, but is more efficient than the Newton method (measured by the computational time) for larger dense systems. The new method updates QR or LU decompositions of nonsymmetric approximations of the Jacobian matrix, so it requires $O(n^2)$ arithmetic operations per iteration in contrast with the Newton method, which requires $O(n^3)$ operations per iteration. Computational experiments confirm the high efficiency of the new method.
LA - eng
KW - nonlinear equation; system of equations; trust-region method; quasi-Newton method; adjoint Broyden method; numerical algorithm; numerical experiment
UR - http://eudml.org/doc/287947
ER -

References

top
  1. Bennett, J. M., 10.1007/BF01436076, Numer. Math. 7 (1965), 217-221. (1965) Zbl0132.36204MR0177503DOI10.1007/BF01436076
  2. Broyden, C. G., 10.2307/2003941, Math. Comput. 19 (1965), 577-593. (1965) Zbl0131.13905MR0198670DOI10.2307/2003941
  3. Conn, A. R., Gould, N. I. M., Toint, P. L., 10.1137/1.9780898719857, MPS/SIAM Series on Optimization 1, Society for Industrial and Applied Mathematics, Philadelphia; Mathematical Programming Society, Philadelphia (2000). (2000) Zbl0958.65071MR1774899DOI10.1137/1.9780898719857
  4. J. E. Dennis, Jr., R. B. Schnabel, 10.1137/1.9781611971200, Classics in Applied Mathematics 16, Society for Industrial and Applied Mathematics, Philadelphia (1996). (1996) Zbl0847.65038MR1376139DOI10.1137/1.9781611971200
  5. Gay, D. M., 10.1137/0716047, SIAM J. Numer. Anal. 16 (1979), 623-630. (1979) Zbl0453.65034MR0537276DOI10.1137/0716047
  6. Griewank, A., Walther, A., 10.1137/1.9780898717761, Society for Industrial and Applied Mathematics, Philadelphia (2008). (2008) Zbl1159.65026MR2454953DOI10.1137/1.9780898717761
  7. Ip, C. M., Todd, M. J., 10.1137/0725015, SIAM J. Numer. Anal. 25 (1988), 206-221. (1988) Zbl0638.65041MR0923935DOI10.1137/0725015
  8. Lukšan, L., 10.1007/BF02193101, J. Optimization Theory Appl. 81 (1994), 569-590. (1994) Zbl0803.65071MR1281739DOI10.1007/BF02193101
  9. L. Lukšan, M. Tůma, J. Vlček, N. Ramešová, M. Šiška, J, Hartman, C. Matonoha, UFO 2014. Interactive System for Universal Functional Optimization, Technical Report V-1218. Prague, Institute of Computer Science AS CR, Praha (2014). (2014) 
  10. Lukšan, L., Vlček, J., 10.1023/A:1022678023392, J. Optimization Theory Appl. 95 (1997), 637-658. (1997) Zbl0902.90146MR1600609DOI10.1023/A:1022678023392
  11. Lukšan, L., Vlček, J., 10.1080/10556789808805677, Optim. Methods Softw. 8 (1998), 201-223. (1998) Zbl0927.65068MR1623249DOI10.1080/10556789808805677
  12. Powell, M. J. D., 10.1016/b978-0-12-597050-1.50006-3, Nonlinear Programming, Proc. Sympos., Univ. of Wisconsin, Madison (J. B. Rosen, O. L. Mangasarian, K. Ritter, eds.) Academic Press, London (1970), 31-65. (1970) Zbl0228.90043MR0272162DOI10.1016/b978-0-12-597050-1.50006-3
  13. Powell, M. J. D., 10.1007/BF02591998, Math. Program. 29 (1984), 297-303. (1984) Zbl0569.90069MR0753758DOI10.1007/BF02591998
  14. Schlenkrich, S., Griewank, A., Walther, A., 10.1007/s10107-008-0232-y, Math. Program. 121 (2010), 221-247. (2010) Zbl1185.90207MR2524890DOI10.1007/s10107-008-0232-y
  15. Schlenkrich, S., Walther, A., 10.1016/j.apnum.2008.05.007, Appl. Numer. Math. 59 (2009), 1120-1136. (2009) Zbl1163.65025MR2495142DOI10.1016/j.apnum.2008.05.007
  16. Yuan, Y.-X., 10.3934/naco.2011.1.15, Numer. Algebra Control Optim. 1 (2011), 15-34. (2011) Zbl1226.65045MR2806290DOI10.3934/naco.2011.1.15
  17. Yuan, Y.-X., 10.1007/s10107-015-0893-2, Math. Program. 151 (2015), 249-281. (2015) Zbl1317.65141MR3347556DOI10.1007/s10107-015-0893-2

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.