Secant and quasi-Newton methods approximate derivative information when exact Jacobians are expensive, noisy, or unavailable.
Secant method
Definition. For scalar root finding, the secant method replaces \(f'(x_k)\) by the slope through \(x_{k-1}\) and \(x_k\). It uses two previous points and avoids explicit derivative evaluation.
Order of secant convergence
Theorem. Under standard smoothness and simple-root assumptions, the secant method converges superlinearly with order \((1+\sqrt5)/2\). It is slower than Newton per iteration but often cheaper per step.
Quasi-Newton equation
Definition. For systems, a quasi-Newton matrix \(B_k\) approximates the Jacobian and is updated to satisfy the secant equation \(B_{k+1}s_k=y_k\), where \(s_k=x_{k+1}-x_k\) and \(y_k=F(x_{k+1})-F(x_k)\).
Broyden methods
Proposition. Broyden updates choose a low-rank correction satisfying the secant equation while changing the current Jacobian approximation as little as possible in a chosen norm. They are useful for large nonlinear systems.
Derivative-free boundary
Remark. Derivative-free methods are not automatically more robust. They trade derivative cost for interpolation, sampling, or finite-difference error, so conditioning and noise still decide what accuracy is realistic.
The scalar secant method
Replacing \(f'(x_k)\) by a divided difference gives \[ x_{k+1} =x_k-f(x_k) \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}. \] It uses one new function evaluation per step and no derivative.
Theorem. If \(f\in C^2\) near a simple root \(x^*\), \(f'(x^*)\ne0\), and the starting points are sufficiently close, then the secant method has order \[ \varphi=\frac{1+\sqrt5}{2}. \]
Proof. Divided-difference error analysis gives asymptotically \[ e_{k+1} =C e_ke_{k-1}+o(e_ke_{k-1}), \qquad C=\frac{f''(x^*)}{2f'(x^*)}. \] If \(|e_{k+1}|\asymp|e_k|^p\), consistency with \(|e_ke_{k-1}|\) and \(|e_k|\asymp|e_{k-1}|^p\) requires \(p=1+1/p\), hence \(p=\varphi\).
Broyden updates
For systems, maintain an approximate Jacobian \(B_k\). With \[ s_k=x_{k+1}-x_k,\qquad y_k=F(x_{k+1})-F(x_k), \] the secant condition is \(B_{k+1}s_k=y_k\). The good Broyden update \[ B_{k+1} =B_k+\frac{(y_k-B_ks_k)s_k^\top}{s_k^\top s_k} \] is the smallest Frobenius-norm change satisfying that condition.
Proof of minimal change. Write \(\Delta=B_{k+1}-B_k\). The constraint is \(\Delta s=r=y-B_ks\). Among all matrices with \(\Delta s=r\), orthogonal projection in Frobenius inner product gives \(\Delta=rs^\top/(s^\top s)\); every other feasible change adds a matrix annihilating \(s\) and orthogonal to this rank-one update.
Inverse updates and Sherman--Morrison
Updating an inverse approximation \(H_k\approx F'(x_k)^{-1}\) avoids a new factorization. Rank-one formulas cost \(O(n^2)\), but accumulated roundoff and poor curvature can make \(H_k\) unreliable. Periodic refactorization or preconditioned Krylov solves can be more robust in large problems.
Superlinear convergence
Theorem (Dennis--Moré criterion, schematic). Let \(x_k\to x^*\), with nonsingular \(J^*=F'(x^*)\). A quasi-Newton iteration is superlinear if \[ \frac{\|(B_k-J^*)s_k\|}{\|s_k\|}\to0 \] and the approximate Jacobians remain uniformly nonsingular.
The criterion asks for accuracy only along actual steps, not convergence of the entire matrix \(B_k\). Broyden updates can accumulate enough directional information to satisfy it.
Relation to optimization
BFGS and SR1 are quasi-Newton updates for Hessians of scalar objectives and exploit symmetry and curvature; general Broyden updates solve vector equations without those properties. Their detailed global convergence belongs to the optimization note; here the common structure is secant approximation of a derivative operator.