@c DO NOT EDIT!  Generated automatically by munge-texi.pl.

@c Copyright (C) 1996-2013 John W. Eaton
@c
@c This file is part of Octave.
@c
@c Octave is free software; you can redistribute it and/or modify it
@c under the terms of the GNU General Public License as published by the
@c Free Software Foundation; either version 3 of the License, or (at
@c your option) any later version.
@c 
@c Octave is distributed in the hope that it will be useful, but WITHOUT
@c ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
@c FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
@c for more details.
@c 
@c You should have received a copy of the GNU General Public License
@c along with Octave; see the file COPYING.  If not, see
@c <http://www.gnu.org/licenses/>.

@node Nonlinear Equations
@chapter Nonlinear Equations
@cindex nonlinear equations
@cindex equations, nonlinear

@menu
* Solvers::
* Minimizers::
@end menu

@node Solvers
@section Solvers

Octave can solve sets of nonlinear equations of the form
@tex
$$
 f (x) = 0
$$
@end tex
@ifnottex

@example
F (x) = 0
@end example

@end ifnottex

@noindent
using the function @code{fsolve}, which is based on the @sc{minpack}
subroutine @code{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.

@c fsolve scripts/optimization/fsolve.m
@anchor{XREFfsolve}
@deftypefn  {Function File} {} fsolve (@var{fcn}, @var{x0}, @var{options})
@deftypefnx {Function File} {[@var{x}, @var{fvec}, @var{info}, @var{output}, @var{fjac}] =} fsolve (@var{fcn}, @dots{})
Solve a system of nonlinear equations defined by the function @var{fcn}.
@var{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 @var{x} such
that @code{@var{fcn} (@var{x})} gives (approximately) all zeros.
@var{x0} determines a starting guess.  The shape of @var{x0} is preserved
in all calls to @var{fcn}, but otherwise it is treated as a column vector.
@var{options} is a structure specifying additional options.
Currently, @code{fsolve} recognizes these options:
@qcode{"FunValCheck"}, @qcode{"OutputFcn"}, @qcode{"TolX"},
@qcode{"TolFun"}, @qcode{"MaxIter"}, @qcode{"MaxFunEvals"},
@qcode{"Jacobian"}, @qcode{"Updating"}, @qcode{"ComplexEqn"}
@qcode{"TypicalX"}, @qcode{"AutoScaling"} and @qcode{"FinDiffType"}.

If @qcode{"Jacobian"} is @qcode{"on"}, it specifies that @var{fcn},
called with 2 output arguments, also returns the Jacobian matrix
of right-hand sides at the requested point.  @qcode{"TolX"} specifies
the termination tolerance in the unknown variables, while
@qcode{"TolFun"} is a tolerance for equations.  Default is @code{1e-7}
for both @qcode{"TolX"} and @qcode{"TolFun"}.

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

If @qcode{"Updating"} is @qcode{"on"}, the function will attempt to use
@nospell{Broyden} updates to update the Jacobian, in order to reduce the
amount of Jacobian calculations.  If your user function always calculates the
Jacobian (regardless of number of output arguments), this option provides
no advantage and should be set to false.

@qcode{"ComplexEqn"} is @qcode{"on"}, @code{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,
should unpack the real and imaginary parts of the system to get a real
system.

For description of the other options, see @code{optimset}.

On return, @var{fval} contains the value of the function @var{fcn}
evaluated at @var{x}, and @var{info} may be one of the following values:

@table @asis
@item 1
Converged to a solution point.  Relative residual error is less than
specified by TolFun.

@item 2
Last relative step size was less that TolX.

@item 3
Last relative decrease in residual was less than TolF.

@item 0
Iteration limit exceeded.

@item -3
The trust region radius became excessively small.
@end table

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

Note about user-supplied Jacobians:
As an inherent property of the algorithm, 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:

@example
function [fvec, fjac] = user_func (x, optimvalues, state)
persistent sav = [], sav0 = [];
if (nargin == 1)
  ## evaluation call
  if (nargout == 1)
    sav0.x = x; # mark saved vector
    ## calculate fvec, 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

## @dots{}

fsolve (@@user_func, x0, optimset ("OutputFcn", @@user_func, @dots{}))
@end example
@seealso{@ref{XREFfzero,,fzero}, @ref{XREFoptimset,,optimset}}
@end deftypefn


The following is a complete example.  To solve the set of equations
@tex
$$
 \eqalign{-2x^2 + 3xy + 4\sin(y) - 6 &= 0\cr
           3x^2 - 2xy^2 + 3\cos(x) + 4 &= 0}
$$
@end tex
@ifnottex

@example
@group
-2x^2 + 3xy   + 4 sin(y) = 6
 3x^2 - 2xy^2 + 3 cos(x) = -4
@end group
@end example

@end ifnottex

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

@example
@group
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
@end group
@end example

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

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

@noindent
results in the solution

@example
@group
x =

  0.57983
  2.54621

fval =

  -5.7184e-10
   5.5460e-10

info = 1
@end group
@end example

@noindent
A value of @code{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

@iftex
@tex
$$
\left[\matrix{ {\partial f_1 \over \partial x_1} &
               {\partial f_1 \over \partial x_2} \cr
               {\partial f_2 \over \partial x_1} &
               {\partial f_2 \over \partial x_2} \cr}\right] =
\left[\matrix{ 3 x_2 - 4 x_1                  &
               4 \cos(x_2) + 3 x_1            \cr
               -2 x_2^2 - 3 \sin(x_1) + 6 x_1 &
               -4 x_1 x_2                     \cr }\right]
$$
@end tex
and compute it with the following Octave function
@end iftex

@example
@group
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
@end group
@end example

@noindent
The Jacobian can then be used with the following call to @code{fsolve}:

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

@noindent
which gives the same solution as before.

@c fzero scripts/optimization/fzero.m
@anchor{XREFfzero}
@deftypefn  {Function File} {} fzero (@var{fun}, @var{x0})
@deftypefnx {Function File} {} fzero (@var{fun}, @var{x0}, @var{options})
@deftypefnx {Function File} {[@var{x}, @var{fval}, @var{info}, @var{output}] =} fzero (@dots{})
Find a zero of a univariate function.

@var{fun} is a function handle, inline function, or string
containing the name of the function to evaluate.
@var{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 @var{x0}(1) and @var{x0}(2).  More mathematically, the
following must hold

@example
sign (@var{fun}(@var{x0}(1))) * sign (@var{fun}(@var{x0}(2))) <= 0
@end example

If @var{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.
@var{options} is a structure specifying additional options.
Currently, @code{fzero}
recognizes these options: @qcode{"FunValCheck"}, @qcode{"OutputFcn"},
@qcode{"TolX"}, @qcode{"MaxIter"}, @qcode{"MaxFunEvals"}.
For a description of these options, see @ref{XREFoptimset,,optimset}.

On exit, the function returns @var{x}, the approximate zero point
and @var{fval}, the function value thereof.
@var{info} is an exit flag that can have these values:

@itemize
@item 1
 The algorithm converged to a solution.

@item 0
 Maximum number of iterations or function evaluations has been reached.

@item -1
The algorithm has been terminated from user output function.

@item -5
The algorithm may have converged to a singular point.
@end itemize

@var{output} is a structure containing runtime information about the
@code{fzero} algorithm.  Fields in the structure are:

@itemize
@item iterations
 Number of iterations through loop.

@item nfev
 Number of function evaluations.

@item bracketx
 A two-element vector with the final bracketing of the zero along the x-axis.

@item brackety
 A two-element vector with the final bracketing of the zero along the y-axis.
@end itemize
@seealso{@ref{XREFoptimset,,optimset}, @ref{XREFfsolve,,fsolve}}
@end deftypefn


@node Minimizers
@section Minimizers
@cindex local minimum
@cindex finding minimums

Often it is useful to find the minimum value of a function rather than just
the zeroes where it crosses the x-axis.  @code{fminbnd} is designed for the
simpler, but very common, case of a univariate function where the interval
to search is bounded.  For unbounded minimization of a function with
potentially many variables use @code{fminunc} or @code{fminsearch}.  The two
functions use different internal algorithms and some knowledge of the objective
function is required.  For functions which can be differentiated, @code{fminunc}
is appropriate.  For functions with discontinuities, or for which a gradient
search would fail, use @code{fminsearch}.  @xref{Optimization}, for
minimization with the presence of constraint functions.  Note that searches
can be made for maxima by simply inverting the objective function
@tex
($F_{max} = -F_{min}$).
@end tex
@ifnottex
(@code{Fto_max = -Fto_min}).
@end ifnottex

@c fminbnd scripts/optimization/fminbnd.m
@anchor{XREFfminbnd}
@deftypefn {Function File} {[@var{x}, @var{fval}, @var{info}, @var{output}] =} fminbnd (@var{fun}, @var{a}, @var{b}, @var{options})
Find a minimum point of a univariate function.

@var{fun} should be a function handle or name.  @var{a}, @var{b} specify a
starting interval.  @var{options} is a structure specifying additional
options.  Currently, @code{fminbnd} recognizes these options:
@qcode{"FunValCheck"}, @qcode{"OutputFcn"}, @qcode{"TolX"},
@qcode{"MaxIter"}, @qcode{"MaxFunEvals"}.  For a description of these
options, see @ref{XREFoptimset,,optimset}.

On exit, the function returns @var{x}, the approximate minimum point
and @var{fval}, the function value thereof.
@var{info} is an exit flag that can have these values:

@itemize
@item 1
The algorithm converged to a solution.

@item 0
Maximum number of iterations or function evaluations has been exhausted.

@item -1
The algorithm has been terminated from user output function.
@end itemize

Notes: The search for a minimum is restricted to be in the interval
bound by @var{a} and @var{b}.  If you only have an initial point
to begin searching from you will need to use an unconstrained
minimization algorithm such as @code{fminunc} or @code{fminsearch}.
@code{fminbnd} internally uses a Golden Section search strategy.
@seealso{@ref{XREFfzero,,fzero}, @ref{XREFfminunc,,fminunc}, @ref{XREFfminsearch,,fminsearch}, @ref{XREFoptimset,,optimset}}
@end deftypefn


@c fminunc scripts/optimization/fminunc.m
@anchor{XREFfminunc}
@deftypefn  {Function File} {} fminunc (@var{fcn}, @var{x0})
@deftypefnx {Function File} {} fminunc (@var{fcn}, @var{x0}, @var{options})
@deftypefnx {Function File} {[@var{x}, @var{fval}, @var{info}, @var{output}, @var{grad}, @var{hess}] =} fminunc (@var{fcn}, @dots{})
Solve an unconstrained optimization problem defined by the function
@var{fcn}.

@var{fcn} should accept a vector (array) defining the unknown variables,
and return the objective function value, optionally with gradient.
@code{fminunc} attempts to determine a vector @var{x} such that
@code{@var{fcn} (@var{x})} is a local minimum.  @var{x0} determines a
starting guess.  The shape of @var{x0} is preserved in all calls to
@var{fcn}, but otherwise is treated as a column vector.
@var{options} is a structure specifying additional options.
Currently, @code{fminunc} recognizes these options:
@qcode{"FunValCheck"}, @qcode{"OutputFcn"}, @qcode{"TolX"},
@qcode{"TolFun"}, @qcode{"MaxIter"}, @qcode{"MaxFunEvals"},
@qcode{"GradObj"}, @qcode{"FinDiffType"},
@qcode{"TypicalX"}, @qcode{"AutoScaling"}.

If @qcode{"GradObj"} is @qcode{"on"}, it specifies that @var{fcn},
when called with 2 output arguments, also returns the Jacobian matrix
of partial first derivatives at the requested point.
@code{TolX} specifies the termination tolerance for the unknown variables
@var{x}, while @code{TolFun} is a tolerance for the objective function
value @var{fval}.  The default is @code{1e-7} for both options.

For a description of the other options, see @code{optimset}.

On return, @var{x} is the location of the minimum and @var{fval} contains
the value of the objective function at @var{x}.  @var{info} may be one of the
following values:

@table @asis
@item 1
Converged to a solution point.  Relative gradient error is less than
specified by @code{TolFun}.

@item 2
Last relative step size was less than @code{TolX}.

@item 3
Last relative change in function value was less than @code{TolFun}.

@item 0
Iteration limit exceeded---either maximum numer of algorithm iterations
@code{MaxIter} or maximum number of function evaluations @code{MaxFunEvals}.

@item -1
Alogrithm terminated by @code{OutputFcn}.

@item -3
The trust region radius became excessively small.
@end table

Optionally, @code{fminunc} can return a structure with convergence statistics
(@var{output}), the output gradient (@var{grad}) at the solution @var{x},
and approximate Hessian (@var{hess}) at the solution @var{x}.

Notes: If have only a single nonlinear equation of one variable then using
@code{fminbnd} is usually a much better idea.  The algorithm used is a
gradient search which depends on the objective function being differentiable.
If the function has discontinuities it may be better to use a derivative-free
algorithm such as @code{fminsearch}.
@seealso{@ref{XREFfminbnd,,fminbnd}, @ref{XREFfminsearch,,fminsearch}, @ref{XREFoptimset,,optimset}}
@end deftypefn


@c fminsearch scripts/optimization/fminsearch.m
@anchor{XREFfminsearch}
@deftypefn  {Function File} {@var{x} =} fminsearch (@var{fun}, @var{x0})
@deftypefnx {Function File} {@var{x} =} fminsearch (@var{fun}, @var{x0}, @var{options})
@deftypefnx {Function File} {[@var{x}, @var{fval}] =} fminsearch (@dots{})

Find a value of @var{x} which minimizes the function @var{fun}.
The search begins at the point @var{x0} and iterates using the
Nelder & Mead Simplex algorithm (a derivative-free method).  This algorithm
is better-suited to functions which have discontinuities or for which
a gradient-based search such as @code{fminunc} fails.

Options for the search are provided in the parameter @var{options} using 
the function @code{optimset}.  Currently, @code{fminsearch} accepts the
options: @qcode{"TolX"}, @qcode{"MaxFunEvals"}, @qcode{"MaxIter"},
@qcode{"Display"}.  For a description of these options, see
@code{optimset}.

On exit, the function returns @var{x}, the minimum point,
and @var{fval}, the function value thereof.

Example usages:

@example
@group
fminsearch (@@(x) (x(1)-5).^2+(x(2)-8).^4, [0;0])

fminsearch (inline ("(x(1)-5).^2+(x(2)-8).^4", "x"), [0;0])
@end group
@end example
@seealso{@ref{XREFfminbnd,,fminbnd}, @ref{XREFfminunc,,fminunc}, @ref{XREFoptimset,,optimset}}
@end deftypefn