Broyden's method
/ BROY-dun /
Newton's method for systems is powerful but pays a steep tax: every single iteration it must form a fresh Jacobian matrix — all n-by-n partial derivatives — and solve a linear system with it. When the function is expensive, or you have no formula for the derivatives, recomputing that whole matrix each step is painful. Broyden's method is the clever shortcut: keep an APPROXIMATE Jacobian and update it cheaply from the step you just took, instead of building it from scratch.
It is the multidimensional cousin of the secant method. Recall the secant method estimated the 1-D slope from two successive points; Broyden does the analogous thing for the whole matrix. Starting from some approximation B_0 of the Jacobian (often a finite-difference estimate, or even the identity), each step solves B_n * s = -F(x_n) for the step, updates x_{n+1} = x_n + s, then adjusts B by the rank-one 'good Broyden' update B_{n+1} = B_n + ((y - B_n s) s^T) / (s^T s), where y = F(x_{n+1}) - F(x_n). This update is the smallest change to B consistent with the new function values (the secant condition B_{n+1} s = y). Crucially, the rank-one change lets you update the matrix FACTORIZATION cheaply (in O(n^2) work) rather than refactoring from scratch (O(n^3)).
The trade-off is the familiar one. Broyden converges only SUPERLINEARLY, not quadratically like full Newton — it takes more iterations — but each iteration is far cheaper because there is no Jacobian to evaluate and no fresh O(n^3) factorization, so total work often wins, especially when derivatives are costly. It is the systems-level analogue of choosing the secant method over Newton in one dimension, and it belongs to the broader quasi-Newton family (BFGS is its symmetric optimization cousin). Like all Newton-type methods it still needs a reasonable starting guess and can fail far from a solution.
For the same circle-meets-parabola system, you could start Broyden with B_0 equal to a finite-difference Jacobian at the initial guess, then NEVER compute another derivative: each step solves B s = -F, takes the step, and nudges B by the rank-one formula. It reaches the intersection in a few more iterations than Newton but with no further Jacobian evaluations.
Update the Jacobian cheaply (rank one) instead of rebuilding it — superlinear, derivative-free.
Broyden trades Newton's quadratic speed for cheaper steps: it converges superlinearly, not quadratically, and the approximate Jacobian can drift, so a periodic restart (recompute B exactly) is sometimes needed. It still needs a decent starting guess.