CoCalc Shared FilesLine search.sagews
Author: Neil Olver
Views : 56
Description: Line search algorithms
def dichotomous_search(f, a1, b1, eps, Delta):
a = a1
b = b1
while b - a > eps:
l = (a+b)/2 - Delta
r = (a+b)/2 + Delta
if f(l) <= f(r):
b = r
else:
a = l
return (a+b)/2


def golden_section(f, a1, b1, ell):
alpha = 0.61803398874989
a = a1
b = b1
l = a + (1 - alpha)*(b - a)
r = a + alpha*(b - a)
fl = f(l)
fr = f(r)
while b - a > ell:
if fl > fr:
a = l
l = r
r = a + alpha*(b - a)
fl = fr
fr = f(r)
else:
b = r
r = l
l = a + (1 - alpha)*(b - a)
fr = fl
fl = f(l)

return (a+b)/2


def newtons_method(f, start, eps):
fp = f.derivative()
fpp = fp.derivative()
x = start
finished = false
while not finished:
newx = x - fp(x) / fpp(x)
if (abs(newx - x) < eps) or (abs(fp(x)) < eps):
finished = true
x = newx
return x






g(x) = x^4 - 3*x^3 + 2*x^2

plot(g, -1,2)

dichotomous_search(g, 1, 2, 1e-4, 1e-5)

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute flags=compile_flags), namespace, locals) File "", line 1, in <module> NameError: name 'dichotomous_search' is not defined
newtons_method(g, 1.3, 1e-6)

1.64038820320221
newtons_method(g, 0.8, 1e-6)

0.609611796797793
golden_section(g, 1, 2, 1e-4)

1.64040730584972