lines 456-614 of file: example/multi_thread/multi_newton.cpp

{xrst_begin multi_newton_run}
{xrst_spell
   df
   xlow
   xout
   xup
}

A Multi-Threaded Newton's Method
################################

Syntax
******

| ``ok`` = ``multi_newton_run`` ( *xout* ,
| |tab| ``fun`` , ``num_sub`` , ``xlow`` , ``xup`` , ``epsilon`` , ``max_itr`` , ``num_threads``
| )

Purpose
*******
Multi-threaded determination of the argument values :math:`x`,
in the interval :math:`[a, b]` (where :math:`a < b`),
such that :math:`f(x) = 0`.

Thread
******
It is assumed that this function is called by thread zero,
and all the other threads are blocked (waiting).

Method
******
For :math:`i = 0 , \ldots , n`,
we define the *i*-th grid point :math:`g_i` by

.. math::

   g_i = a \frac{n - i}{n} +  b \frac{i}{n}

For :math:`i = 0 , \ldots , n-1`,
we define the *i*-th sub-interval of :math:`[a, b]` by

.. math::

   I_i = [ g_i , g_{i+1} ]

Newton's method is applied starting
at the center of each of the sub-intervals :math:`I_i` for
:math:`i = 0 , \ldots , n-1`
and at most one zero is found for each sub-interval.

ok
**
The return value *ok* has prototype

   ``bool`` *ok*

If an error occurs, it is false, otherwise it is true.

xout
****
The argument *xout* has the prototype

   ``vector<double>&`` *xout*

The input size and value of the elements of *xout* do not matter.
Upon return from ``multi_newton`` ,
the size of *xout* is less than or equal
the number of sub-intervals :math:`n` and

.. math::

   | f( xout[i] ) | \leq epsilon

for each valid index 0 <= ``i`` < ``xout`` . *size* () .
Two :math:`x` solutions are considered equal (and joined as one) if
the absolute difference between the solutions is less than
:math:`(b - a) / n`.

fun
***
The argument *fun* has prototype

   ``void`` *fun* ( ``double`` *x* , ``double&`` *f* , ``double&`` *df* )

This function must evaluate :math:`f(x)`,
and its derivative :math:`f^{(1)} (x)`,
using the syntax

   *fun* ( *x* , *f* , *df* )

where the arguments to *fun* have the prototypes

| |tab| ``double`` *x*
| |tab| ``double&`` *f*
| |tab| ``double&`` *df*

.
The input values of *f* and *df* do not matter.
Upon return they are :math:`f(x)` and :math:`f^{(1)} (x)` respectively.

num_sub
*******
The argument *num_sub* has prototype

   ``size_t`` *num_sub*

It specifies the number of sub-intervals; i.e., :math:`n`.

xlow
****
The argument *xlow* has prototype

   ``double`` *xlow*

It specifies the lower limit for the entire search interval; i.e., :math:`a`.

xup
***
The argument *xup* has prototype

   ``double`` *xup*

It specifies the upper limit for the entire search interval; i.e., :math:`b`.

epsilon
*******
The argument *epsilon* has prototype

   ``double`` *epsilon*

It specifies the convergence criteria for Newton's method in terms
of how small the function value must be.

max_itr
*******
The argument *max_itr* has prototype

   ``size_t`` *max_itr*

It specifies the maximum number of iterations of Newton's method to try
before giving up on convergence (on each sub-interval).

num_threads
***********
This argument has prototype

   ``size_t`` *num_threads*

It specifies the number of threads that are available for this test.
If it is zero, the test is run without the multi-threading environment.

Source
******
{xrst_literal
   // BEGIN SOLVE C++
   // END SOLVE C++
}

{xrst_end multi_newton_run}
