-
Notifications
You must be signed in to change notification settings - Fork 0
/
one_variable.py
182 lines (149 loc) · 6.58 KB
/
one_variable.py
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
# MAX_ITERATIONS = 3
# PRECISION = 1e-2
'''
Description: finds a local minimum given an initial interval
Input params: f => function that
will be minimize
search_interval => interval where the
minimum will be searched in
uncertainty_distance => mean point displacement
Output params: local minimum value
'''
def bisection_search(f, search_interval, uncertainty_distance=1e-7, linear_precision=1e-6, linear_max_iterations=1000, **kwargs):
if(uncertainty_distance > linear_precision):
raise ValueError('O intervalo de incerteza precisa ser menor que a precisão')
i = 0
solution = None
while(i < linear_max_iterations and abs(search_interval[1] - search_interval[0]) >= linear_precision):
mean_point = (search_interval[0] + search_interval[1])/2
uncertainty_left = mean_point - uncertainty_distance
uncertainty_right = mean_point + uncertainty_distance
f_uncertainty_left = f(uncertainty_left)
f_uncertainty_right = f(uncertainty_right)
if(f_uncertainty_left == f_uncertainty_right):
search_interval = [uncertainty_left, uncertainty_right]
elif(f_uncertainty_left < f_uncertainty_right):
search_interval = [search_interval[0], uncertainty_right]
else:
search_interval = [uncertainty_left, search_interval[1]]
i += 1
solution = (search_interval[0] + search_interval[1])/2
return solution
'''
Description: calculates terms of the Fibonacci sequence
until finds a number which is bigger than
a desired value
Input params: desired_value => desired value on the Fibonacci sequence
Output params: a list of Fibonacci numbers
'''
def fibonacci_sequence(desired_value):
if (desired_value == 1): return [1, 1]
fibonacci_numbers = [1, 1]
i = 1
while(fibonacci_numbers[i] <= desired_value):
i += 1
fibonacci_numbers.append(fibonacci_numbers[i - 1] + fibonacci_numbers[i - 2])
return fibonacci_numbers
'''
Description: finds a local minimum given an initial interval
Input params: f => function that
will be minimize
search_interval => interval where the
minimum will be searched in
uncertainty_distance => mean point displacement
Output params: local minimum value
'''
def fibonacci_search(f, search_interval):
solution = None
f_n = (search_interval[1] - search_interval[0])/PRECISION
fibonacci_elements = fibonacci_sequence(f_n)
n = len(fibonacci_elements) - 1
i = 1
while(i < MAX_ITERATIONS + 1 and abs(search_interval[1] - search_interval[0]) >= PRECISION):
left_test_point = search_interval[0] + (fibonacci_elements[n - i - 1]/fibonacci_elements[n - i + 1])*(search_interval[1] - search_interval[0])
right_test_point = search_interval[0] + (fibonacci_elements[n - i]/fibonacci_elements[n - i + 1])*(search_interval[1] - search_interval[0])
f_left_point = f(left_test_point)
f_right_point = f(right_test_point)
if(f_left_point == f_right_point):
search_interval = [left_test_point, right_test_point]
elif(f_left_point < f_right_point):
search_interval = [search_interval[0], right_test_point]
else:
search_interval = [left_test_point, search_interval[1]]
i += 1
solution = (search_interval[0] + search_interval[1])/2
return solution
'''
Description: finds a local minimum given an initial value
Input params: f_prime => first derivative
of the function to be minimized
f_second => second derivative
of the function to be minimized
search_point => starting value for the search
Output params: local minimum value
'''
def newton_search(f_prime, f_second, search_point):
i = 0
last_point = 2**64-1 # Maximum 64 bit integer number
while(i < MAX_ITERATIONS and abs(search_point - last_point) >= PRECISION):
last_point = search_point
search_point = search_point - f_prime(search_point)/f_second(search_point)
i += 1
return search_point
'''
Description: finds a local minimum given 3 initial points
Input params: f => function to be minimized
f_prime => first derivative
of the function to be minimized
search_points => starting points x1, x2
and x3 for the search (x3 > x2 > x1)
Output params: local minimum value
'''
def quadratic_fit(f, f_prime, fit_points):
x_bar = min(fit_points[0], fit_points[1], fit_points[2])
i = 0
while(i < MAX_ITERATIONS and abs(f_prime(x_bar)) > PRECISION):
x1 = fit_points[0]
x2 = fit_points[1]
x3 = fit_points[2]
x_bar = ((x2**2 - x3**2)*f(x1) + (x3**2 - x1**2)*f(x2) + (x1**2 - x2**2)*f(x3))/ \
(2* ((x2 - x3)*f(x1) + (x3 - x1)*f(x2) + (x1 - x2)*f(x3)))
p_second = ((x2 - x3)*f(x1) + (x3 - x1)*f(x2) + (x1 - x2)*f(x3))/ \
((x2 - x3)*(x3 - x2)*(x1 - x2))
if(p_second > 0):
return min(f(x1), f(x2), f(x3))
if(x_bar > x1 and x_bar < x2):
if(f(x_bar) < f(x2)):
fit_points = [x1, x_bar, x2]
else:
fit_points = [x_bar, x2, x3]
else:
if(f(x_bar) > f(x2)):
fit_points = [x1, x2, x_bar]
else:
fit_points = [x2, x_bar, x3]
i += 1
return x_bar
def f(x):
y = x**2 + 2*x
return y
def f_prime(x):
y = 2*x + 2
return y
def f_second(x):
y = 2
return y
def f_quad(x):
y = (x-2)**4
return y
def f_quad_prime(x):
y = 4*(x-2)**3
return y
# solution = bisection_search(f, [-3, 5], 1e-3)
# print(f'Dicotômica: {solution}')
# solution = fibonacci_search(f, [-3, 5])
# print(f'Fibonacci: {solution}')
# solution = newton_search(f_prime, f_second, 1)
# print(f'Newton: {solution}')
# solution = quadratic_fit(f_quad, f_quad_prime, [-3, 1, 5])
# print(f'Ajuste Quadrático: {solution}')