Каганов. Одномерная минимизация. 3 лабка.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def BinarySearch(left, right, eps = 0.000001):
steps_count = 0
while right - left > eps:
steps_count += 1
m1 = left + (right - left) / 3.0
m2 = right - (right - left) / 3.0
if (f(m1) < f(m2)):
right = m2
else:
left = m1
return (f((right+left) / 2.0), (right+left) / 2.0, steps_count)
def GoldenSection(left, right, eps = 0.000001):
x = left + (right - left) * (3 - sqrt(5)) / 2.0
y = left + right - x
steps_count = 0
while right - left > eps:
steps_count += 1
if f(x) < f(y):
right = y
y = x
x = left + right - y
else:
left = x
x = y
y = left + right - x
return (f((right+left) / 2.0), (right+left) / 2.0, steps_count)
def FibonachiSection(left, right, eps = 0.000001):
def fib(n):
if n < 3:
return 1.
return fib(n-1) + fib(n-2)
steps_count = 0
while right - left > eps:
steps_count += 1
x = left + fib(steps_count+2)/fib(steps_count+3) * (right - left)
y = left + right - x
if f(x) > f(y):
right = y
else:
left = x
return (f((right+left) / 2.0), (right+left) / 2.0, steps_count)