<br><br><div class="gmail_quote">On Sat, May 21, 2011 at 4:24 PM, Gökhan Sever <span dir="ltr"><<a href="mailto:gokhansever@gmail.com">gokhansever@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hello,<div><br></div><div>Could we add "tolf" argument into the newton function signature?</div><div><br></div><div>I am guessing this should match the tolf argument in IDL newton (<a href="http://star.pst.qub.ac.uk/idl/NEWTON.html" target="_blank">http://star.pst.qub.ac.uk/idl/NEWTON.html</a>)</div>
<div><br></div><div>TOLF: <span style="font-family: Arial,Verdana,Helvetica,sans-serif;">Set the convergence criterion on the function values. The default value is 1.0 x 10<sup style="font-size: smaller; vertical-align: super;">-4</sup>.</span></div>
<div><br></div><div><br></div><div><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">def</span> <span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(153, 0, 0); font-weight: bold;">newton</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">(</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">func</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">,</span> <span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">x0</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">,</span> <span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">fprime</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">=</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(153, 153, 153);">None</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">,</span> <span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">args</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">=</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">(),</span> <span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">tol</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">=</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(0, 153, 153);">1.48e-8</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">,</span> <span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">maxiter</span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">=</span><span style="margin: 0px; padding: 0px;"><font color="#009999" face="'Bitstream Vera Sans Mono', 'Courier New', monospace"><span style="line-height: 1.4em; white-space: pre-wrap; font-size: 12px;">50, </span></font>tolf=<font color="#009999" face="'Bitstream Vera Sans Mono', 'Courier New', monospace"><span style="line-height: 1.4em; white-space: pre-wrap; font-size: 12px;">1.e-4</span></font></span><span style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; white-space: pre-wrap; font-size: 12px; margin: 0px; padding: 0px; line-height: 1.4em;">)</span><br clear="all">
<br></div><div>In second method part of the newton function (from <a href="https://github.com/scipy/scipy/blob/master/scipy/optimize/zeros.py" target="_blank">https://github.com/scipy/scipy/blob/master/scipy/optimize/zeros.py</a>)</div>
<div>
<br></div><div><pre style="margin: 0px; padding: 0px;"><div style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; font-size: 12px; margin: 0px; padding: 0px 0px 0px 1em; line-height: 1.4em;">
<span style="margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(153, 153, 136); font-style: italic;"># Secant method</span></div>
<div style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; font-size: 12px; margin: 0px; padding: 0px 0px 0px 1em; line-height: 1.4em;">
<span style="margin: 0px; padding: 0px; line-height: 1.4em;">p0</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">=</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em;">x0</span></div>
<div style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; font-size: 12px; margin: 0px; padding: 0px 0px 0px 1em; line-height: 1.4em;">
<span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">if</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em;">x0</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">>=</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(0, 153, 153);">0</span><span style="margin: 0px; padding: 0px; line-height: 1.4em;">:</span></div>
<div style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; font-size: 12px; margin: 0px; padding: 0px 0px 0px 1em; line-height: 1.4em;">
<span style="margin: 0px; padding: 0px; line-height: 1.4em;">p1</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">=</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em;">x0</span><span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">*</span><span style="margin: 0px; padding: 0px; line-height: 1.4em;">(</span><span style="margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(0, 153, 153);">1</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">+</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(0, 153, 153);">1e-4</span><span style="margin: 0px; padding: 0px; line-height: 1.4em;">)</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">+</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(0, 153, 153);">1e-4</span></div>
<div style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; font-size: 12px; margin: 0px; padding: 0px 0px 0px 1em; line-height: 1.4em;">
<span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">else</span><span style="margin: 0px; padding: 0px; line-height: 1.4em;">:</span></div>
<div style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; font-size: 12px; margin: 0px; padding: 0px 0px 0px 1em; line-height: 1.4em;">
<span style="margin: 0px; padding: 0px; line-height: 1.4em;">p1</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">=</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em;">x0</span><span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">*</span><span style="margin: 0px; padding: 0px; line-height: 1.4em;">(</span><span style="margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(0, 153, 153);">1</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">+</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(0, 153, 153);">1e-4</span><span style="margin: 0px; padding: 0px; line-height: 1.4em;">)</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; font-weight: bold;">-</span> <span style="margin: 0px; padding: 0px; line-height: 1.4em; color: rgb(0, 153, 153);">1e-4</span></div>
<div style="font-family: 'Bitstream Vera Sans Mono','Courier New',monospace; font-size: 12px; margin: 0px; padding: 0px 0px 0px 1em; line-height: 1.4em;">
<font color="#009999"><br></font></div><font face="arial, helvetica, sans-serif" size="2">without increasing the tolf or (1e-4) in these statements I can't get a proper root solution for my function.</font></pre>
<pre style="margin: 0px; padding: 0px;"><font face="arial, helvetica, sans-serif" size="2"><br></font></pre><pre style="margin: 0px; padding: 0px;"><font face="arial, helvetica, sans-serif" size="2"><br></font></pre><pre style="margin: 0px; padding: 0px;">
<font face="arial, helvetica, sans-serif" size="2">The reason that I am experiencing with newton is because fsolve seems slower comparing to the newton for scalar root finding for a given function.</font></pre>
<pre style="margin: 0px; padding: 0px;"><font face="arial, helvetica, sans-serif" size="2">Consider this example run Sage v4.6.1 notebook:</font></pre><pre style="margin: 0px; padding: 0px;"><font face="arial, helvetica, sans-serif" size="2"><br>
</font></pre><pre style="margin: 0px; padding: 0px;"><font face="arial, helvetica, sans-serif" size="2">%cython
cpdef double myfunc(double x):
return x**3 + 2*x - 1</font></pre><pre style="margin: 0px; padding: 0px;"><font face="arial, helvetica, sans-serif" size="2"><br></font></pre><pre style="margin: 0px; padding: 0px;"><font face="arial, helvetica, sans-serif" size="2">timeit('scipy.optimize.newton(myfunc,1)')</font></pre>
<pre style="margin: 0px; padding: 0px;"><font face="arial, helvetica, sans-serif" size="2"><span style="font-family: 'Times New Roman'; white-space: normal; font-size: medium;"><div style="font-size: 12pt; margin: 0px; padding-left: 0px; color: rgb(0, 0, 170);">
<div style="font-size: 12pt; margin: 0px; padding: 0px; color: rgb(0, 0, 170);">
<pre style="font-size: 12pt; margin: 0px;">625 loops, best of 3: 22.1 µs per loop</pre></div><div style="font-family: monospace; font-size: 12pt;">
</div></div></span></font></pre></div><div><br></div><div>timeit('scipy.optimize.fsolve(myfunc,1)')</div><div><span style="font-family: 'Times New Roman'; font-size: medium;"><div style="font-size: 12pt; margin: 0px; padding-left: 0px; color: rgb(0, 0, 170);">
<div><pre style="font-size: 12pt; margin: 0px;">625 loops, best of 3: 86.5 µs per loop</pre></div><div style="font-family: monospace; font-size: 12pt;">
</div></div></span><div><br></div><div>I am also experimenting to Cythonize the Newton secant method, which the Cython written version shows significant speed-ups comparing to the Python version. Without going any further, I would like to know if there is any Cythonized code around for newton or any other approach to make fsolve faster? </div>
<div><br></div><div>Thanks.</div><div><br></div><div><br></div></div></blockquote><div><br>You could probably adapt one of the other 1d zero finders, say ritter, just ignore all the fancy stuff for the bounding interval and such.<br>
<br>I don't much like the stopping criterion in newton either and ftol would probably help, but it might be worth thinking about overstepping and looking for a sign change. Or something like that that would give more assurance that a zero was at hand. Note that there is also a pull request for using the second derivative as well as the first.<br>
<br>Chuck <br></div></div>