Superlinear convergence

In the above equation, the norm is usually the Euclidean norm. We have a linear convergence rate when 0 is equal to 1. Superlinear convergence rate refers to the case where 0=1 and the limit is equal to zero. When 0=2 the convergence rate is called quadratic. In general, the value of 0 depends on the algorithm while the value of the limit depends upon the function that is being minimized. 

This method is called regula falsi, and it has superlinear convergence, which means that 70 > 1. In this one-dimensional case, 70 = 1.618. 

Note that quadratic convergence implies superlinear convergence. 

Quadratic convergence means that eventually the number of correct figures in Xc doubles at each step, clearly a desirable property. Close to x Newton s method Eq. (3.9) shows quadratic convergence while quasi-Newton methods Eq. (3.8) show superlinear convergence. The RF step Eq. (3.20) converges quadratically when the exact Hessian is used. Steepest descent with exact line search converges linearly for minimization. 

At least superlinear convergence rates as the solution is approached. 

Two specific classes are emerging as the most powerful techniques for large-scale applications limited-memory quasi-Newton (LMQN) and truncated Newton methods. LMQN methods attempt to combine the modest storage and computational requirements of CG methods with the superlinear convergence properties of standard (i.e., full memory) QN methods. Similarly, TN... 

An alternative quadratic truncation test (QT) has also been suggested with associated asymptotic superlinear convergence.116 This criterion monitors, instead of the relative residual, the sufficient decrease of the quadratic model, 4 (p). Specifically, it checks whether qk p) has decreased sufficiently from one inner iteration to the next, in relation to the progress realized per inner iteration ... 

Han, S. P. (1976), Superlinearly Convergent Variable Metric Algorithms for General Nonlinear Programming Problems, Mathematical Programming, Vol. 11, pp. 263—282. 

The rank one update formulas for Broyden s method that approximate the Jacobian ensure superlinear convergence that is slower than Newton s method but significantly faster than direct substitution. 

Convergence properties, comparable with those of the Newton process, cannot be expected for quasi-Newton methods, because a certain charge must be paid for the use of estimates to the Hessian matrix. But superlinear convergence, at least, should occur. 

Kastner J, Sherwood P (2008) Superlinearly converging dimer method for transition state search. J Chem Phys 128 014106... 

---