TY - JOUR

T1 - On the order of convergence of Broyden’s method

T2 - Faster convergence on mixed linear–nonlinear systems of equations and a conjecture on the q-order

AU - Mannel, Florian

N1 - Publisher Copyright:
© 2021, The Author(s).

PY - 2021/12

Y1 - 2021/12

N2 - We present two theoretical results and two surprising conjectures concerning convergence properties of Broyden’s method for smooth nonlinear systems of equations. First, we show that when Broyden’s method is applied to a nonlinear mapping F: Rn→ Rn with n- d affine component functions and the initial matrix B is chosen suitably, then the generated sequence (uk,F(uk),Bk)k≥1 can be identified with a lower-dimensional sequence that is also generated by Broyden’s method. This property enables us to prove, second, that for such mixed linear–nonlinear systems of equations a proper choice of B ensures 2d-step q-quadratic convergence, which improves upon the previously known 2n steps. Numerical experiments of high precision confirm the faster convergence and show that it is not available if B deviates from the correct choice. In addition, the experiments suggest two surprising possibilities: It seems that Broyden’s method is (2 d- 1) -step q-quadratically convergent for d> 1 and that it admits a q-order of convergence of 2 1/(2d). These conjectures are new even for d= n.

AB - We present two theoretical results and two surprising conjectures concerning convergence properties of Broyden’s method for smooth nonlinear systems of equations. First, we show that when Broyden’s method is applied to a nonlinear mapping F: Rn→ Rn with n- d affine component functions and the initial matrix B is chosen suitably, then the generated sequence (uk,F(uk),Bk)k≥1 can be identified with a lower-dimensional sequence that is also generated by Broyden’s method. This property enables us to prove, second, that for such mixed linear–nonlinear systems of equations a proper choice of B ensures 2d-step q-quadratic convergence, which improves upon the previously known 2n steps. Numerical experiments of high precision confirm the faster convergence and show that it is not available if B deviates from the correct choice. In addition, the experiments suggest two surprising possibilities: It seems that Broyden’s method is (2 d- 1) -step q-quadratically convergent for d> 1 and that it admits a q-order of convergence of 2 1/(2d). These conjectures are new even for d= n.

UR - http://www.scopus.com/inward/record.url?scp=85117610881&partnerID=8YFLogxK

U2 - 10.1007/s10092-021-00441-6

DO - 10.1007/s10092-021-00441-6

M3 - Journal articles

AN - SCOPUS:85117610881

SN - 0008-0624

VL - 58

JO - Calcolo

JF - Calcolo

IS - 4

M1 - 47

ER -