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
Department of Computer Science