Interactive Educational Modules in
Scientific Computing

Broyden's Method

This module demonstrates Broyden's method for solving a system of nonlinear equations f (x, y) = 0 in two dimensions. Given an approximate solution, Broyden's method produces a new approximate solution based on approximate local linearization about the current point using an approximate Jacobian matrix, which results in a linear system to be solved for the step to the new approximate solution. This process is repeated until convergence, which is usually quite rapid.

The user selects a problem either by choosing a preset example or typing in desired functions f1(x, y) and f2(x, y). The user can also select a starting point (x, y) or accept a default value. The successive steps of Broyden's method are then carried out sequentially by repeatedly clicking on NEXT or on the currently highlighted step. The current point (x, y) is indicated by a bullet on the plot, and all values are also shown numerically in the table below. At each iteration of Broyden's method, the step s to the next approximate solution is given by the solution to the approximating linear system B s = − f, where B is an approximation to the Jacobian matrix. The approximate Jacobian B is updated at the new point based on the change in function values, and the process is then repeated. If the starting guess is close enough to the true solution, then Broyden's method converges to it, typically with a superlinear convergence rate.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 5.6.3, especially Algorithm 5.5 and Example 5.16.

Developers: Jeffrey Naisbitt and Michael Heath