Optimization (Part 5, Bisection search)

In [1]:
import pandas, numpy
import bisection

import matplotlib.pyplot as plt
%matplotlib inline

plt.style.use('seaborn-whitegrid')

x (x - 2)

In [2]:
df1  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])
df2  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])
df3  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn1  = lambda x: x * (x - 2.0)
fn2  = lambda x: numpy.fabs(x * (x - 2.0))
fn3  = lambda x: (lambda x: 0.0 if x < 0.0 else x)(x * (x - 2.0))

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn1, -1.5, 20.1, e, 10000)
    df1 = df1.append({'status'          : st,
                      'eps'             : e,
                      'n'               : n,
                      'en'              : en,
                      'xmin'            : xm,
                      'str(xmin)'       : '%.15e' % (xm,)},
                     ignore_index=True)
    
    st, xm, n, en = bisection.optim(fn2, -20.1, 0.9, e, 10000)
    df2 = df2.append({'status'          : st,
                      'eps'             : e,
                      'n'               : n,
                      'en'              : en,
                      'xmin'            : xm,
                      'str(xmin)'       : '%.15e' % (xm,)},
                     ignore_index=True)
    st, xm, n, en = bisection.optim(fn3, -1.5, 20.1, e, 10000)
    df3 = df3.append({'status'          : st,
                      'eps'             : e,
                      'n'               : n,
                      'en'              : en,
                      'xmin'            : xm,
                      'str(xmin)'       : '%.15e' % (xm,)},
                     ignore_index=True)
In [3]:
df1
Out[3]:
status eps n en xmin str(xmin)
0 0 10 1 1.0 6.400000 6.400000000000000e+00
1 0 1 5 5.0 1.253125 1.253125000000000e+00
2 0 0.1 8 8.0 1.027539 1.027539062500000e+00
3 0 1e-05 22 22.0 1.000002 1.000002030612230e+00
4 0 1e-08 32 32.0 1.000000 1.000000004867048e+00
5 0 1e-10 38 38.0 1.000000 1.000000284305724e+00
6 0 1e-12 45 45.0 1.000026 1.000026000014040e+00
7 0 1e-14 51 51.0 1.002637 1.002636739875156e+00
8 -2 1e-15 0 55.0 0.000000 0.000000000000000e+00
9 -2 5e-16 0 56.0 0.000000 0.000000000000000e+00
10 -2 1e-16 0 58.0 0.000000 0.000000000000000e+00
In [4]:
df2
Out[4]:
status eps n en xmin str(xmin)
0 0 10 1 1.0 -6.850000e+00 -6.850000000000001e+00
1 0 1 5 5.0 8.750000e-02 8.749999999999997e-02
2 0 0.1 8 8.0 -7.226563e-03 -7.226562500000137e-03
3 0 1e-05 22 22.0 2.366549e-06 2.366548776593275e-06
4 0 1e-08 31 31.0 -4.711127e-09 -4.711127167271556e-09
5 0 1e-10 38 38.0 5.581193e-12 5.581192652293885e-12
6 0 1e-12 45 45.0 -1.928602e-13 -1.928602305138552e-13
7 0 1e-14 51 51.0 3.073142e-15 3.073142056508032e-15
8 -2 1e-15 0 55.0 0.000000e+00 0.000000000000000e+00
9 -2 5e-16 0 56.0 0.000000e+00 0.000000000000000e+00
10 -2 1e-16 0 58.0 0.000000e+00 0.000000000000000e+00
In [5]:
df3
Out[5]:
status eps n en xmin str(xmin)
0 0 10 1 1.0 6.400000 6.400000000000000e+00
1 0 1 5 5.0 1.253125 1.253125000000000e+00
2 0 0.1 8 8.0 1.951367 1.951367187500000e+00
3 0 1e-05 22 22.0 1.999993 1.999992603114842e+00
4 0 1e-08 32 32.0 2.000000 1.999999996767239e+00
5 0 1e-10 38 38.0 2.000000 1.999999999982865e+00
6 0 1e-12 45 45.0 2.000000 1.999999999999440e+00
7 0 1e-14 51 51.0 2.000000 1.999999999999999e+00
8 -2 1e-15 0 55.0 0.000000 0.000000000000000e+00
9 -2 5e-16 0 56.0 0.000000 0.000000000000000e+00
10 -2 1e-16 0 58.0 0.000000 0.000000000000000e+00
In [6]:
fig, ax = plt.subplots(3, 1, figsize=(30, 50), sharex='col', sharey='row')

x1 = numpy.linspace(-2.0, 7.0, 5000)
x2 = numpy.linspace(-2.0, 7.0, 5000)
x3 = numpy.linspace(-2.0, 7.0, 5000)

ax[0].plot(x1, fn1(x1), color='black', linestyle='solid')
ax[0].set(xlim=(-2.0, 7.0))
m0 = df1.loc[df1['status'] == 0]['xmin'].values
ax[0].scatter(m0, fn1(m0), s= 40, color='red')

ax[1].plot(x2, fn2(x2), color='black', linestyle='solid')
ax[1].set(xlim=(-2.0, 7.0))
m1 = df2.loc[df2['status'] == 0]['xmin'].values
ax[1].scatter(m1, fn2(m1), s= 40, color='red')

ax[2].plot(x3, numpy.vectorize(fn3)(x3), color='black', linestyle='solid')
ax[2].set(xlim=(-2.0, 7.0))
m2 = df3.loc[df3['status'] == 0]['xmin'].values
ax[2].scatter(m2, numpy.vectorize(fn3)(m2), s= 40, color='red')
Out[6]:
<matplotlib.collections.PathCollection at 0x7f31e5d9a6d8>

|x ^ 3|

In [7]:
df  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn = lambda x: numpy.fabs(x ** 3)

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn, -1.5, 20.1, e, 10000)
    df = df.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,)},
                   ignore_index=True)
In [8]:
df
Out[8]:
status eps n en xmin str(xmin)
0 0 10 1 1.0 6.400000e+00 6.400000000000000e+00
1 0 1 5 5.0 -3.437500e-02 -3.437499999999993e-02
2 0 0.1 8 8.0 1.972656e-02 1.972656250000020e-02
3 0 1e-05 22 22.0 1.158432e-06 1.158431768464456e-06
4 0 1e-08 32 32.0 -2.120570e-09 -2.120570084236500e-09
5 0 1e-10 38 38.0 2.122766e-11 2.122766182075590e-11
6 0 1e-12 45 45.0 -2.174322e-13 -2.174321539169064e-13
7 0 1e-14 51 51.0 3.957352e-15 3.957351585638196e-15
8 -2 1e-15 0 55.0 0.000000e+00 0.000000000000000e+00
9 -2 5e-16 0 56.0 0.000000e+00 0.000000000000000e+00
10 -2 1e-16 0 58.0 0.000000e+00 0.000000000000000e+00
In [9]:
fig, ax = plt.subplots(1, 1, figsize=(10, 5), sharex='col', sharey='row')

x = numpy.linspace(-1.5, 20.1, 5000)

ax.plot(x, fn(x), color='black', linestyle='solid')
ax.set(xlim=(-1.5, 20.1))

m = df['xmin'].values

ax.scatter(m, fn(m), s= 40, color='red')
Out[9]:
<matplotlib.collections.PathCollection at 0x7f31e450d320>

x (x - 2) (x - 3)

In [10]:
df1  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)', 'delta'])
df2  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])
df3  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn1 = lambda x: x * (x - 2.0) * (x - 3.0)
fn2 = lambda x: numpy.fabs(x * (x - 2.0) * (x - 3.0))
fn3 = lambda x: (lambda x: 0.0 if x < 0.0 else x)(x * (x - 2.0) * (x - 3.0))

xmin = (5.0 + numpy.sqrt(7.0)) / 3.0

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn1, 1.1, 20.1, e, 10000)
    df1 = df1.append({'status'          : st,
                      'eps'             : e,
                      'n'               : n,
                      'en'              : en,
                      'xmin'            : xm,
                      'str(xmin)'       : '%.15e' % (xm,),
                      'delta'           : numpy.fabs(xm - xmin)},
                     ignore_index=True)
    st, xm, n, en = bisection.optim(fn2, 1.1, 2.5, e, 10000)
    df2 = df2.append({'status'          : st,
                      'eps'             : e,
                      'n'               : n,
                      'en'              : en,
                      'xmin'            : xm,
                      'str(xmin)'       : '%.15e' % (xm,)},
                     ignore_index=True)
    st, xm, n, en = bisection.optim(fn3, 1.1, 20.1, e, 10000)
    df3 = df3.append({'status'          : st,
                      'eps'             : e,
                      'n'               : n,
                      'en'              : en,
                      'xmin'            : xm,
                      'str(xmin)'       : '%.15e' % (xm,)},
                     ignore_index=True)   

/home/pushkov/teach/sem/2/ipynb/optim/bisection.py:9: RuntimeWarning: invalid value encountered in log
  return numpy.ceil(numpy.log(x) / numpy.log(2))
In [11]:
df1
Out[11]:
status eps n en xmin str(xmin) delta
0 0 10 0 -0.0 10.600000 1.060000000000000e+01 8.051416e+00
1 0 1 5 5.0 2.443750 2.443750000000001e+00 1.048338e-01
2 0 0.1 8 8.0 2.515820 2.515820312500000e+00 3.276346e-02
3 0 1e-05 21 21.0 2.548588 2.548588078911305e+00 4.308556e-06
4 0 1e-08 31 31.0 2.548584 2.548583770357142e+00 2.278622e-12
5 0 1e-10 38 38.0 2.548584 2.548583822461472e+00 5.210661e-08
6 0 1e-12 45 45.0 2.548600 2.548600056750150e+00 1.628640e-05
7 0 1e-14 51 51.0 2.549578 2.549577567392443e+00 9.937970e-04
8 -2 1e-15 0 55.0 0.000000 0.000000000000000e+00 2.548584e+00
9 -2 5e-16 0 56.0 0.000000 0.000000000000000e+00 2.548584e+00
10 -2 1e-16 0 58.0 0.000000 0.000000000000000e+00 2.548584e+00
In [12]:
df2
Out[12]:
status eps n en xmin str(xmin)
0 0 10 0 NaN 1.800000 1.800000000000000e+00
1 0 1 0 -1.0 1.800000 1.800000000000000e+00
2 0 0.1 4 4.0 2.003125 2.003125000000000e+00
3 0 1e-05 18 18.0 2.000000 2.000000478763579e+00
4 0 1e-08 28 28.0 2.000000 1.999999999689016e+00
5 0 1e-10 34 34.0 2.000000 2.000000000003177e+00
6 0 1e-12 41 41.0 2.000000 1.999999999999811e+00
7 0 1e-14 48 47.0 2.000000 2.000000000000002e+00
8 0 1e-15 50 51.0 2.000000 2.000000000000000e+00
9 -2 5e-16 51 52.0 0.000000 0.000000000000000e+00
10 -2 1e-16 0 54.0 0.000000 0.000000000000000e+00
In [13]:
df3
Out[13]:
status eps n en xmin str(xmin)
0 0 10 0 -0.0 10.600000 1.060000000000000e+01
1 0 1 5 5.0 2.443750 2.443750000000001e+00
2 0 0.1 8 8.0 2.958789 2.958789062500000e+00
3 0 1e-05 21 21.0 2.999998 2.999997658069134e+00
4 0 1e-08 31 31.0 3.000000 2.999999992498167e+00
5 0 1e-10 38 38.0 3.000000 2.999999999977791e+00
6 0 1e-12 45 45.0 3.000000 2.999999999999482e+00
7 0 1e-14 51 51.0 3.000000 2.999999999999993e+00
8 -2 1e-15 0 55.0 0.000000 0.000000000000000e+00
9 -2 5e-16 0 56.0 0.000000 0.000000000000000e+00
10 -2 1e-16 0 58.0 0.000000 0.000000000000000e+00
In [14]:
fig, ax = plt.subplots(3, 1, figsize=(40, 40), sharex='col', sharey='row')

x1 = numpy.linspace(1.0, 3.5, 5000)
x2 = numpy.linspace(1.0, 3.5, 5000)
x3 = numpy.linspace(1.0, 3.5, 5000)

ax[0].plot(x1, fn1(x1), color='black', linestyle='solid')
ax[0].set(xlim=(1.0, 3.5), ylim=(-1.0, 0.0))
m0 = df1.loc[df1['status'] == 0]['xmin'].values
ax[0].scatter(m0, fn1(m0), s= 40, color='red')

ax[1].plot(x2, fn2(x2), color='black', linestyle='solid')
ax[1].set(xlim=(1.0, 3.5))
m1 = df2.loc[df2['status'] == 0]['xmin'].values
ax[1].scatter(m1, fn2(m1), s= 40, color='red')

ax[2].plot(x3, numpy.vectorize(fn3)(x3), color='black', linestyle='solid')
ax[2].set(xlim=(1.0, 3.5), ylim=(-0.1, 1.0))
m2 = df3.loc[df3['status'] == 0]['xmin'].values
ax[2].scatter(m2, numpy.vectorize(fn3)(m2), s= 40, color='red')
Out[14]:
<matplotlib.collections.PathCollection at 0x7f31e44a3470>

|sin x ^ 2|

In [15]:
df1  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)', '|xmin - pi^0.5|'])
df2  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)', '|xmin - (2pi)^0.5|'])
df3  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn1 = lambda x: numpy.fabs(numpy.sin(x ** 2))
fn2 = lambda x: numpy.fabs(numpy.sin(x ** 2))
fn3 = lambda x: (lambda x: 0.0 if x < 0.0 else x)(numpy.sin(x ** 2))

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn1, 1.5, 2.0, e, 10000)
    df1 = df1.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,),
                     '|xmin - pi^0.5|' : '%.15e' % (numpy.fabs(xm - numpy.sqrt(numpy.pi)),)},
                   ignore_index=True)

    st, xm, n, en = bisection.optim(fn2, 2.3, 2.7, e, 10000)
    df2 = df2.append({'status'             : st,
                     'eps'                : e,
                     'n'                  : n,
                     'en'              : en,
                     'xmin'               : xm,
                     'str(xmin)'          : '%.15e' % (xm,),
                     '|xmin - (2pi)^0.5|' : '%.15e' % (numpy.fabs(xm - numpy.sqrt(2.0 * numpy.pi)),)},
                   ignore_index=True)

    st, xm, n, en = bisection.optim(fn3, 1.5, 2.0, e, 10000)
    df3 = df3.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,)},
                   ignore_index=True)
In [16]:
df1
Out[16]:
status eps n en xmin str(xmin) |xmin - pi^0.5|
0 0 10 0 NaN 1.750000 1.750000000000000e+00 2.245385090551588e-02
1 0 1 0 NaN 1.750000 1.750000000000000e+00 2.245385090551588e-02
2 0 0.1 3 2.0 1.775000 1.775000000000000e+00 2.546149094484029e-03
3 0 1e-05 16 16.0 1.772457 1.772456673660278e+00 2.822754762377144e-06
4 0 1e-08 26 26.0 1.772454 1.772453847823485e+00 3.082030630707777e-09
5 0 1e-10 33 33.0 1.772454 1.772453850916520e+00 1.100364244166485e-11
6 0 1e-12 39 39.0 1.772454 1.772453850905959e+00 4.432010314303625e-13
7 0 1e-14 46 46.0 1.772454 1.772453850905517e+00 8.881784197001252e-16
8 0 1e-15 49 49.0 1.772454 1.772453850905516e+00 0.000000000000000e+00
9 0 5e-16 50 50.0 1.772454 1.772453850905516e+00 2.220446049250313e-16
10 -2 1e-16 0 53.0 0.000000 0.000000000000000e+00 1.772453850905516e+00
In [17]:
df2
Out[17]:
status eps n en xmin str(xmin) |xmin - (2pi)^0.5|
0 0 10 0 NaN 2.500000 2.500000000000000e+00 6.628274631000242e-03
1 0 1 0 NaN 2.500000 2.500000000000000e+00 6.628274631000242e-03
2 0 0.1 2 2.0 2.537500 2.537500000000000e+00 3.087172536899985e-02
3 0 1e-05 16 16.0 2.506631 2.506631303939819e+00 3.029308818902621e-06
4 0 1e-08 26 26.0 2.506628 2.506628271771664e+00 2.859336323268735e-09
5 0 1e-10 32 32.0 2.506628 2.506628274589982e+00 4.101829986780103e-11
6 0 1e-12 39 39.0 2.506628 2.506628274631276e+00 2.762234885267389e-13
7 0 1e-14 46 46.0 2.506628 2.506628274631000e+00 4.440892098500626e-16
8 0 1e-15 49 49.0 2.506628 2.506628274631000e+00 0.000000000000000e+00
9 -2 5e-16 50 50.0 0.000000 0.000000000000000e+00 2.506628274631000e+00
10 -2 1e-16 0 52.0 0.000000 0.000000000000000e+00 2.506628274631000e+00
In [18]:
df3
Out[18]:
status eps n en xmin str(xmin)
0 0 10 0 NaN 1.750000 1.750000000000000e+00
1 0 1 0 NaN 1.750000 1.750000000000000e+00
2 0 0.1 2 2.0 1.900000 1.900000000000000e+00
3 0 1e-05 16 16.0 1.999991 1.999991185379028e+00
4 0 1e-08 26 26.0 2.000000 1.999999991274710e+00
5 0 1e-10 33 33.0 2.000000 1.999999999920896e+00
6 0 1e-12 39 39.0 2.000000 1.999999999999045e+00
7 0 1e-14 46 46.0 2.000000 1.999999999999992e+00
8 0 1e-15 49 49.0 2.000000 1.999999999999999e+00
9 0 5e-16 50 50.0 2.000000 2.000000000000000e+00
10 -2 1e-16 0 53.0 0.000000 0.000000000000000e+00
In [19]:
fig, ax = plt.subplots(1, 2, figsize=(30, 10), sharex='col', sharey='row')

x  = numpy.linspace(0.5, 3.0, 6000)

ax[0].plot(x, fn1(x), color='black', linestyle='solid')
ax[0].set(xlim=(0.5, 3.0), ylim=(-0.1, 1.1), xlabel='x', ylabel='|sin x^2|')
m1 = df1.loc[df1['status'] == 0]['xmin'].values
ax[0].scatter(m1, fn1(m1), s= 40, color='red')
m2 = df2.loc[df2['status'] == 0]['xmin'].values
ax[0].scatter(m2, fn2(m2), s= 40, color='red')

ax[1].plot(x, numpy.vectorize(fn3)(x), color='black', linestyle='solid')
ax[1].set(xlim=(0.5, 3.0), ylim=(-0.1, 1.1))
m3 = df3.loc[df3['status'] == 0]['xmin'].values
ax[1].scatter(m3, numpy.vectorize(fn3)(m3), s= 40, color='red')
Out[19]:
<matplotlib.collections.PathCollection at 0x7f31e449f710>

|e^{0.1 x} sin(x)|

In [20]:
df1  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)', '|xmin - pi|'])
df2  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)', '|xmin - 2pi|'])
df3  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn1 = lambda x: numpy.fabs(numpy.exp(0.1 * x) * numpy.sin(x))
fn2 = lambda x: numpy.fabs(numpy.exp(0.1 * x) * numpy.sin(x))
fn3 = lambda x: (lambda x: 0.0 if x < 0.0 else x)(numpy.exp(0.1 * x) * numpy.sin(x))

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn1, 2.0, 4.5, e, 10000)
    df1 = df1.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,),
                     '|xmin - pi|' : '%.15e' % (numpy.fabs(xm - numpy.pi),)},
                   ignore_index=True)
    
    st, xm, n, en = bisection.optim(fn2, 4.9, 7.5, e, 10000)
    df2 = df2.append({'status'             : st,
                     'eps'                : e,
                     'n'                  : n,
                     'en'                 : en,
                     'xmin'               : xm,
                     'str(xmin)'          : '%.15e' % (xm,),
                     '|xmin - 2pi|' : '%.15e' % (numpy.fabs(xm - 2.0 * numpy.pi),)},
                   ignore_index=True)

    st, xm, n, en = bisection.optim(fn3, 2.5, 7.5, e, 10000)
    df3 = df3.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,)},
                   ignore_index=True)
In [21]:
df1
Out[21]:
status eps n en xmin str(xmin) |xmin - pi|
0 0 10 0 NaN 3.250000 3.250000000000000e+00 1.084073464102069e-01
1 0 1 1 1.0 2.875000 2.875000000000000e+00 2.665926535897931e-01
2 0 0.1 5 5.0 3.137500 3.137500000000000e+00 4.092653589792938e-03
3 0 1e-05 18 18.0 3.141592 3.141591505718231e+00 1.147871562245939e-06
4 0 1e-08 28 28.0 3.141593 3.141592651107913e+00 2.481880478910625e-09
5 0 1e-10 35 35.0 3.141593 3.141592653625382e+00 3.558930927738402e-11
6 0 1e-12 42 42.0 3.141593 3.141592653589542e+00 2.513544927751354e-13
7 0 1e-14 48 48.0 3.141593 3.141592653589797e+00 3.552713678800501e-15
8 0 1e-15 52 52.0 3.141593 3.141592653589793e+00 0.000000000000000e+00
9 -2 5e-16 52 53.0 0.000000 0.000000000000000e+00 3.141592653589793e+00
10 -2 1e-16 0 55.0 0.000000 0.000000000000000e+00 3.141592653589793e+00
In [22]:
df2
Out[22]:
status eps n en xmin str(xmin) |xmin - 2pi|
0 0 10 0 NaN 6.200000 6.200000000000000e+00 8.318530717958605e-02
1 0 1 1 1.0 6.600000 6.600000000000000e+00 3.168146928204134e-01
2 0 0.1 5 5.0 6.317188 6.317187500000000e+00 3.400219282041395e-02
3 0 1e-05 18 18.0 6.283189 6.283188690662385e+00 3.383482798824389e-06
4 0 1e-08 28 28.0 6.283185 6.283185305498971e+00 1.680614758470256e-09
5 0 1e-10 35 35.0 6.283185 6.283185307215611e+00 3.602451670303708e-11
6 0 1e-12 42 42.0 6.283185 6.283185307179465e+00 1.207922650792170e-13
7 0 1e-14 48 48.0 6.283185 6.283185307179585e+00 8.881784197001252e-16
8 -2 1e-15 52 52.0 0.000000 0.000000000000000e+00 6.283185307179586e+00
9 -2 5e-16 0 53.0 0.000000 0.000000000000000e+00 6.283185307179586e+00
10 -2 1e-16 0 55.0 0.000000 0.000000000000000e+00 6.283185307179586e+00
In [23]:
df3
Out[23]:
status eps n en xmin str(xmin)
0 0 10 0 NaN 5.000000 5.000000000000000e+00
1 0 1 3 2.0 5.750000 5.750000000000000e+00
2 0 0.1 6 6.0 6.263281 6.263281249999999e+00
3 0 1e-05 19 19.0 6.283181 6.283180531473159e+00
4 0 1e-08 29 29.0 6.283185 6.283185297850874e+00
5 0 1e-10 36 36.0 6.283185 6.283185307121840e+00
6 0 1e-12 43 43.0 6.283185 6.283185307179364e+00
7 0 1e-14 49 49.0 6.283185 6.283185307179578e+00
8 -2 1e-15 52 53.0 0.000000 0.000000000000000e+00
9 -2 5e-16 0 54.0 0.000000 0.000000000000000e+00
10 -2 1e-16 0 56.0 0.000000 0.000000000000000e+00
In [24]:
fig, ax = plt.subplots(1, 2, figsize=(30, 5), sharex='col', sharey='row')

x  = numpy.linspace(2.5, 7.5, 6000)

ax[0].plot(x, fn1(x), color='black', linestyle='solid')
ax[0].set(xlim=(2.5, 7.5), ylim=(-0.1, 1.7), xlabel='x', ylabel='|sin x^2|')
m1 = df1.loc[df1['status'] == 0]['xmin'].values
ax[0].scatter(m1, fn1(m1), s= 40, color='red')
m2 = df2.loc[df2['status'] == 0]['xmin'].values
ax[0].scatter(m2, fn2(m2), s= 40, color='red')

ax[1].plot(x, numpy.vectorize(fn3)(x), color='black', linestyle='solid')
ax[1].set(xlim=(2.5, 7.5), ylim=(-0.1, 1.7))
m3 = df3.loc[df3['status'] == 0]['xmin'].values
ax[1].scatter(m3, numpy.vectorize(fn3)(m3), s= 40, color='red')
Out[24]:
<matplotlib.collections.PathCollection at 0x7f31e4398978>

-5 x^5 + 4 x^4 -12 x^3 + 11 x^2 -2 x + 1 [-0.5, 0.5]

In [25]:
df  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn = lambda x: -5.0 * x**5 + 4.0 * x**4 - 12.0 * x**3 + 11.0 * x**2 - 2.0 * x + 1.0

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn, -0.5, 0.5, e, 10000)
    df = df.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,)},
                   ignore_index=True)

/home/pushkov/teach/sem/2/ipynb/optim/bisection.py:9: RuntimeWarning: divide by zero encountered in log
  return numpy.ceil(numpy.log(x) / numpy.log(2))
In [26]:
df
Out[26]:
status eps n en xmin str(xmin)
0 0 10 0 NaN 0.000000 0.000000000000000e+00
1 0 1 0 -inf 0.000000 0.000000000000000e+00
2 0 0.1 4 4.000000 0.084375 8.437500000000002e-02
3 0 1e-05 17 17.000000 0.109858 1.098583679580688e-01
4 0 1e-08 27 27.000000 0.109860 1.098599162142613e-01
5 0 1e-10 34 34.000000 0.109860 1.098599358410145e-01
6 0 1e-12 40 40.000000 0.109862 1.098619605894594e-01
7 0 1e-14 47 47.000000 0.110432 1.104319170813166e-01
8 0 1e-15 50 50.000000 0.118652 1.186523442230513e-01
9 0 5e-16 51 51.000000 0.124237 1.242372395936686e-01
10 0 1e-16 54 54.000000 0.437500 4.375000144279872e-01
In [27]:
fig, ax = plt.subplots(1, 1, figsize=(30, 10), sharex='col', sharey='row')

x = numpy.linspace(-0.5, 0.5, 5000)

ax.plot(x, fn(x), color='black', linestyle='solid')
ax.set(xlim=(-0.7, 0.7))

m = df.loc[df['status'] == 0]['xmin'].values

ax.scatter(m, fn(m), s= 40, color='red')
Out[27]:
<matplotlib.collections.PathCollection at 0x7f31e4372a90>

- ln^2 (x - 2) + ln^2 (10 - x) - x ^ 0.2 [6, 9.9]

In [28]:
df  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn = lambda x: - numpy.log(x - 2.0) ** 2 + numpy.log(10.0 - x) ** 2 - numpy.power(x, 0.2)

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn, 6.0, 9.9, e, 10000)
    df = df.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,)},
                   ignore_index=True)
In [29]:
df
Out[29]:
status eps n en xmin str(xmin)
0 0 10 0 NaN 7.950000 7.950000000000000e+00
1 0 1 2 2.0 9.037500 9.037500000000001e+00
2 0 0.1 6 6.0 9.226562 9.226562500000000e+00
3 0 1e-05 19 19.0 9.206241 9.206241342916488e+00
4 0 1e-08 29 29.0 9.206243 9.206243220568945e+00
5 0 1e-10 36 36.0 9.206245 9.206244624493941e+00
6 0 1e-12 42 42.0 9.206370 9.206370443593691e+00
7 0 1e-14 49 49.0 9.218939 9.218939452678878e+00
8 -2 1e-15 1 52.0 0.000000 0.000000000000000e+00
9 -2 5e-16 0 53.0 0.000000 0.000000000000000e+00
10 -2 1e-16 0 56.0 0.000000 0.000000000000000e+00
In [30]:
fig, ax = plt.subplots(1, 1, figsize=(30, 10), sharex='col', sharey='row')

x = numpy.linspace(6.0, 9.9, 5000)

ax.plot(x, fn(x), color='black', linestyle='solid')
ax.set(xlim=(6.0, 10.0))

m = df.loc[df['status'] == 0]['xmin'].values

ax.scatter(m, fn(m), s= 40, color='red')
Out[30]:
<matplotlib.collections.PathCollection at 0x7f31e43374e0>

-3 x sin(0.75 x) + e^{-2 x} [0, 2pi]

In [31]:
df  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn = lambda x: - 3.0 * x * numpy.sin(0.75 * x) + numpy.exp(-2.0 * x)

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn, 0.0, 2.0 * numpy.pi, e, 10000)
    df = df.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,)},
                   ignore_index=True)
In [32]:
df
Out[32]:
status eps n en xmin str(xmin)
0 0 10 0 NaN 3.141593 3.141592653589793e+00
1 0 1 3 3.0 2.811394 2.811393571891069e+00
2 0 0.1 6 6.0 2.706837 2.706837436678728e+00
3 0 1e-05 20 20.0 2.706473 2.706473104297706e+00
4 0 1e-08 30 30.0 2.706476 2.706475575303731e+00
5 0 1e-10 36 36.0 2.706477 2.706477142912043e+00
6 0 1e-12 43 43.0 2.706709 2.706709100224640e+00
7 0 1e-14 50 50.0 2.714668 2.714667976252385e+00
8 0 1e-15 53 53.0 2.945246 2.945246108900244e+00
9 -2 5e-16 53 54.0 0.000000 0.000000000000000e+00
10 -2 1e-16 0 56.0 0.000000 0.000000000000000e+00
In [33]:
fig, ax = plt.subplots(1, 1, figsize=(30, 10), sharex='col', sharey='row')

x = numpy.linspace(0.0, 2.0 * numpy.pi, 5000)

ax.plot(x, fn(x), color='black', linestyle='solid')
ax.set(xlim=(0.0, 2.0 * numpy.pi))

m = df.loc[df['status'] == 0]['xmin'].values

ax.scatter(m, fn(m), s= 40, color='red')
Out[33]:
<matplotlib.collections.PathCollection at 0x7f31e42f9be0>

e^{3 x} +5 e^{-2 x} [0, 1]

In [34]:
df  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn = lambda x: numpy.exp(3.0 * x) + 5.0 * numpy.exp(-2.0 * x)

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn, 0.0, 1.0, e, 10000)
    df = df.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,)},
                   ignore_index=True)
In [35]:
df
Out[35]:
status eps n en xmin str(xmin)
0 0 10 0 NaN 0.500000 5.000000000000000e-01
1 0 1 0 -inf 0.500000 5.000000000000000e-01
2 0 0.1 4 4.000000 0.246875 2.468750000000000e-01
3 0 1e-05 17 17.000000 0.240798 2.407977275466919e-01
4 0 1e-08 27 27.000000 0.240795 2.407945606701050e-01
5 0 1e-10 34 34.000000 0.240795 2.407947342694569e-01
6 0 1e-12 40 40.000000 0.240799 2.407989405763010e-01
7 0 1e-14 47 47.000000 0.242680 2.426802210470801e-01
8 0 1e-15 50 50.000000 0.257328 2.573281862023904e-01
9 0 5e-16 51 51.000000 0.269395 2.693948146915884e-01
10 -2 1e-16 1 54.000000 0.000000 0.000000000000000e+00
In [36]:
fig, ax = plt.subplots(1, 1, figsize=(30, 10), sharex='col', sharey='row')

x = numpy.linspace(0.0, 1.0, 5000)

ax.plot(x, fn(x), color='black', linestyle='solid')
ax.set(xlim=(0.0, 1.0))

m = df.loc[df['status'] == 0]['xmin'].values

ax.scatter(m, fn(m), s= 40, color='red')
Out[36]:
<matplotlib.collections.PathCollection at 0x7f31e42bbe80>

0.2 x ln x + (x - 2.3)^2 [0.5, 2.5]

In [37]:
df  = pandas.DataFrame(columns=['status', 'eps', 'n', 'en', 'xmin', 'str(xmin)'])

fn = lambda x: 0.2 * x * numpy.log(x) + (x - 2.3)**2

for e in [10, 1, 1e-1, 1e-5, 1e-8, 1e-10, 1e-12, 1e-14, 1e-15, 5e-16, 1e-16]:
    st, xm, n, en = bisection.optim(fn, 0.5, 2.5, e, 10000)
    df = df.append({'status'          : st,
                     'eps'             : e,
                     'n'               : n,
                     'en'              : en,
                     'xmin'            : xm,
                     'str(xmin)'       : '%.15e' % (xm,)},
                   ignore_index=True)
In [38]:
df
Out[38]:
status eps n en xmin str(xmin)
0 0 10 0 NaN 1.500000 1.500000000000000e+00
1 0 1 1 0.0 1.750000 1.750000000000000e+00
2 0 0.1 5 5.0 2.123438 2.123437500000000e+00
3 0 1e-05 18 18.0 2.124642 2.124642109928131e+00
4 0 1e-08 28 28.0 2.124640 2.124639772480811e+00
5 0 1e-10 35 35.0 2.124640 2.124639821935181e+00
6 0 1e-12 41 41.0 2.124649 2.124648983403091e+00
7 0 1e-14 48 48.0 2.125651 2.125650962558844e+00
8 0 1e-15 51 51.0 2.122559 2.122558593595385e+00
9 -2 5e-16 52 52.0 0.000000 0.000000000000000e+00
10 -2 1e-16 0 55.0 0.000000 0.000000000000000e+00
In [39]:
fig, ax = plt.subplots(1, 1, figsize=(30, 10), sharex='col', sharey='row')

x = numpy.linspace(0.5, 2.5, 5000)

ax.plot(x, fn(x), color='black', linestyle='solid')
ax.set(xlim=(0.5, 2.5))

m = df.loc[df['status'] == 0]['xmin'].values

ax.scatter(m, fn(m), s= 40, color='red')
Out[39]:
<matplotlib.collections.PathCollection at 0x7f31e41ff588>