iconEuler Reference

Broyden Algorithm

Implementation of the Broyden algorithm.

The Broyden algorithm is a Quasi-Newton method for solving F(x)=0 with vectors x. It does not need a derivative. Instead, it uses an approximation of the Jacobian Df to start with, and updates it at each step.

For Newton algorithms see the file about Numerical Algorithms.

function broyden (f:string, xstart:real, A:real=none)

  Finds a zero of f with the Broyden algorithm.
  
  The Broyden algorithm is an iterative algorithm just like the
  Newton method, which solves the equation f(v)=0 for vectors v.
  It tries to approximate the Jacobian of the function f using the
  previous iteration steps. The algorithm will fail, if the Jacobian
  of f in the zero is singular.
  
  The function f must take a vector v, and return a vector.
  Additional parameters to "broyden" after the semicolon are passed
  to f. The function can work with column or row vectors. The start
  vector must be of the same form.
  
  x is the start value, and the optional matrix A is a approximation
  of the Jacobian matrix of f.
  
  To change the accuracy, you can specify an optional eps=... as last
  parameter.
  
  f : function of one vector
  xstart : start point, a row vector
  A : optional start for the Jacobian
  
  Returns the solution as a vector.
  
  See: 
nbroyden (Broyden Algorithm)
function nbroyden (f:string, xstart:real vector, nmax:natural, A:real=none)

  Do nmax steps of the Broyden algorithm.
  
  This function works like "broyden", but returns the steps of the
  algorithm. Moreover, it does at most nmax steps.
  
  f : function of one row vector
  xstart : start point, a row vector
  nmax : maximal number of steps
  A : optional start for the Jacobian
  
  Returns a matrix, with one step of the algorithm in each row,
  and the current approximation of the Jacobian.
  

Documentation Homepage