### 20.1 Solvers ¶

Octave can solve sets of nonlinear equations of the form

    F (x) = 0

using the function `fsolve`, which is based on the MINPACK subroutine `hybrd`. This is an iterative technique so a starting point must be provided. This also has the consequence that convergence is not guaranteed even if a solution exists.

`x =` fsolve `(fcn, x0)` ¶
`x =` fsolve `(fcn, x0, options)` ¶
`[x, fval] =` fsolve `(…)` ¶
`[x, fval, info] =` fsolve `(…)` ¶
`[x, fval, info, output] =` fsolve `(…)` ¶
`[x, fval, info, output, fjac] =` fsolve `(…)` ¶

  Solve a system of nonlinear equations defined by the function fcn.

  fcn is a function handle, inline function, or string containing the name of the function to evaluate. fcn should accept a vector (array) defining the unknown variables, and return a vector of left-hand sides of the equations. Right-hand sides are defined to be zeros. In other words, this function attempts to determine a vector x such that `fcn (x)` gives (approximately) all zeros.

  x0 is an initial guess for the solution. The shape of x0 is preserved in all calls to fcn, but otherwise is treated as a column vector.

  options is a structure specifying additional parameters which control the algorithm. Currently, `fsolve` recognizes these options: `"AutoScaling"`, `"ComplexEqn"`, `"FinDiffType"`, `"FunValCheck"`, `"Jacobian"`, `"MaxFunEvals"`, `"MaxIter"`, `"OutputFcn"`, `"TolFun"`, `"TolX"`, `"TypicalX"`, and `"Updating"`.

  If `"AutoScaling"` is `"on"`, the variables will be automatically scaled according to the column norms of the (estimated) Jacobian. As a result, `"TolFun"` becomes scaling-independent. By default, this option is `"off"` because it may sometimes deliver unexpected (though mathematically correct) results.

  If `"ComplexEqn"` is `"on"`, `fsolve` will attempt to solve complex equations in complex variables, assuming that the equations possess a complex derivative (i.e., are holomorphic). If this is not what you want, you should unpack the real and imaginary parts of the system to get a real system.

  If `"Jacobian"` is `"on"`, it specifies that fcn—when called with 2 output arguments—also returns the Jacobian matrix of right-hand sides at the requested point.

  `"MaxFunEvals"` proscribes the maximum number of function evaluations before optimization is halted. The default value is `100 * number_of_variables`, i.e., `100 * length (x0)`. The value must be a positive integer.

  If `"Updating"` is `"on"`, the function will attempt to use Broyden updates to update the Jacobian, in order to reduce the number of Jacobian calculations. If your user function always calculates the Jacobian (regardless of number of output arguments) then this option provides no advantage and should be disabled.

  `"TolX"` specifies the termination tolerance in the unknown variables, while `"TolFun"` is a tolerance for equations. Default is `1e-6` for both `"TolX"` and `"TolFun"`.

  For a description of the other options, see `optimset`. To initialize an options structure with default values for `fsolve` use `options = optimset ("fsolve")`.

  The first output x is the solution while the second output fval contains the value of the function fcn evaluated at x (ideally a vector of all zeros).

  The third output info reports whether the algorithm succeeded and may take one of the following values:

  1

    Converged to a solution point. Relative residual error is less than specified by `TolFun`.

  2

    Last relative step size was less than `TolX`.

  3

    Last relative decrease in residual was less than `TolFun`.

  0

    Iteration limit (either `MaxIter` or `MaxFunEvals`) exceeded.

  -1

    Stopped by `OutputFcn`.

  -2

    The Jacobian became excessively small and the search stalled.

  -3

    The trust region radius became excessively small.

  output is a structure containing runtime information about the `fsolve` algorithm. Fields in the structure are:

  `iterations`

    Number of iterations through loop.

  `successful`

    Number of successful iterations.

  `funcCount`

    Number of function evaluations.

  The final output fjac contains the value of the Jacobian evaluated at x.

  Note: If you only have a single nonlinear equation of one variable, using `fzero` is usually a much better idea.

  Note about user-supplied Jacobians: As an inherent property of the algorithm, a Jacobian is always requested for a solution vector whose residual vector is already known, and it is the last accepted successful step. Often this will be one of the last two calls, but not always. If the savings by reusing intermediate results from residual calculation in Jacobian calculation are significant, the best strategy is to employ `OutputFcn`: After a vector is evaluated for residuals, if `OutputFcn` is called with that vector, then the intermediate results should be saved for future Jacobian evaluation, and should be kept until a Jacobian evaluation is requested or until `OutputFcn` is called with a different vector, in which case they should be dropped in favor of this most recent vector. A short example how this can be achieved follows:

      function [fval, fjac] = user_fcn (x, optimvalues, state)
      persistent sav = [], sav0 = [];
      if (nargin == 1)
        ## evaluation call
        if (nargout == 1)
          sav0.x = x;  # mark saved vector
          ## calculate fval, save results to sav0.
        elseif (nargout == 2)
          ## calculate fjac using sav.
        endif
      else
        ## outputfcn call.
        if (all (x == sav0.x))
          sav = sav0;
        endif
        ## maybe output iteration status, etc.
      endif
      endfunction

      ## ...

      fsolve (@user_fcn, x0, optimset ("OutputFcn", @user_fcn, ...))

  See also: fzero, optimset.

The following is a complete example. To solve the set of equations

    -2x^2 + 3xy   + 4 sin(y) = 6
     3x^2 - 2xy^2 + 3 cos(x) = -4

you first need to write a function to compute the value of the given function. For example:

    function y = f (x)
      y = zeros (2, 1);
      y(1) = -2*x(1)^2 + 3*x(1)*x(2)   + 4*sin(x(2)) - 6;
      y(2) =  3*x(1)^2 - 2*x(1)*x(2)^2 + 3*cos(x(1)) + 4;
    endfunction

Then, call `fsolve` with a specified initial condition to find the roots of the system of equations. For example, given the function `f` defined above,

    [x, fval, info] = fsolve (@f, [1; 2])

results in the solution

    x =

      0.57983
      2.54621

    fval =

      -5.7184e-10
       5.5460e-10

    info = 1

A value of `info = 1` indicates that the solution has converged.

When no Jacobian is supplied (as in the example above) it is approximated numerically. This requires more function evaluations, and hence is less efficient. In the example above we could compute the Jacobian analytically as

    function [y, jac] = f (x)
      y = zeros (2, 1);
      y(1) = -2*x(1)^2 + 3*x(1)*x(2)   + 4*sin(x(2)) - 6;
      y(2) =  3*x(1)^2 - 2*x(1)*x(2)^2 + 3*cos(x(1)) + 4;
      if (nargout == 2)
        jac = zeros (2, 2);
        jac(1,1) =  3*x(2) - 4*x(1);
        jac(1,2) =  4*cos(x(2)) + 3*x(1);
        jac(2,1) = -2*x(2)^2 - 3*sin(x(1)) + 6*x(1);
        jac(2,2) = -4*x(1)*x(2);
      endif
    endfunction

The Jacobian can then be used with the following call to `fsolve`:

    [x, fval, info] = fsolve (@f, [1; 2], optimset ("jacobian", "on"));

which gives the same solution as before.

`x =` fzero `(fcn, x0)` ¶
`x =` fzero `(fcn, x0, options)` ¶
`[x, fval] =` fzero `(…)` ¶
`[x, fval, info] =` fzero `(…)` ¶
`[x, fval, info, output] =` fzero `(…)` ¶

  Find a zero of a univariate function.

  fcn is a function handle, inline function, or string containing the name of the function to evaluate.

  x0 should be a two-element vector specifying two points which bracket a zero. In other words, there must be a change in sign of the function between x0(1) and x0(2). More mathematically, the following must hold

      sign (fcn (x0(1))) * sign (fcn (x0(2))) <= 0

  If x0 is a single scalar then several nearby and distant values are probed in an attempt to obtain a valid bracketing. If this is not successful, the function fails.

  options is a structure specifying additional options. Currently, `fzero` recognizes these options: `"Display"`, `"FunValCheck"`, `"MaxFunEvals"`, `"MaxIter"`, `"OutputFcn"`, and `"TolX"`.

  `"MaxFunEvals"` proscribes the maximum number of function evaluations before the search is halted. The default value is `Inf`. The value must be a positive integer.

  `"MaxIter"` proscribes the maximum number of algorithm iterations before the search is halted. The default value is `Inf`. The value must be a positive integer.

  `"TolX"` specifies the termination tolerance for the solution x. The default value is `eps`.

  For a description of the other options, see `optimset`. To initialize an options structure with default values for `fzero` use `options = optimset ("fzero")`.

  On exit, the function returns x, the approximate zero point, and fval, the function evaluated at x.

  The third output info reports whether the algorithm succeeded and may take one of the following values:

  - 1 The algorithm converged to a solution.
  - 0 Maximum number of iterations or function evaluations has been reached.
  - -1 The algorithm has been terminated by a user `OutputFcn`.
  - -5 The algorithm may have converged to a singular point.
  - -6 No valid initial bracketing with a sign change found.

  output is a structure containing runtime information about the `fzero` algorithm. Fields in the structure are:

  - intervaliterations Number of iterations searching for a bracketing interval.
  - iterations Number of iterations searching for a zero.
  - funcCount Number of function evaluations.
  - algorithm The string `"bisection, interpolation"`.
  - message A string with the final status of the algorithm.
  - bracketx A two-element vector with the final bracketing of the zero along the x-axis.
  - brackety A two-element vector with the final bracketing of the zero along the y-axis.

  Programming Notes: The algorithm relies on the function crossing the x-axis and having both positive and negative values. It will not generally work for functions which only touch the x-axis, e.g., x^2. The function will generally be faster if a 2-element bracketing interval x0 is supplied since no interval search will be conducted.

  See also: fsolve, fminbnd, optimset.