<jupyter_start><jupyter_text>Метод золотого сечения для сравнения с исследуемым методом<jupyter_code>def gold_ratio(f, a: float, b: float, eps: float = 1e-8):
    n_it = 0
    k = (sqrt(5) - 1) / 2
    I = b - a
    z = k*I
    x1 = b - z
    x2 = a + z
    while I > eps:
        n_it += 1
        z = k*I
        x1 = b - z
        x2 = a + z
        fx1, fx2 = f(x1)[0], f(x2)[0]
        if fx1 >= fx2:
            a = x1
        else:
            b = x2
        I = b - a
    x = (b + a) / 2
    return x, f(x)[0], n_it<jupyter_output><empty_output><jupyter_text>Метод Брента с производной<jupyter_code>from d1_optimization import optimize
a, b = -10, 10
print(optimize(f2, a, b), f2(optimize(f2, a, b)))
print(gold_ratio(f2, a, b))
from random import uniform, seed
a = uniform(-100, 100)
b = uniform(a, 1000)
print('a: ', a, ' b: ', b)
print('BRENT+DERIVATIVE:')
print(optimize(f1, a, b))
print('GOLD_RATIO:')
print(gold_ratio(f1, a, b))
import matplotlib.pyplot as plt
import numpy as np
from functools import partial
#костыль для вывода числа итераций, не возвращая их
def counter(func, *args, **kwargs):
    res = func(*args, **kwargs)
    return func.n_it


counter(optimize, f1, a, b)<jupyter_output><empty_output><jupyter_text>Графики "количество итераций vs точность" и "время работы vs точность" для параболы для отрезка $[a, b]$, содержащего минимум.<jupyter_code>def it_graph(f, a, b):
    tols = [10**(-2-i) for i in range(14)]
    opt_tol = partial(counter, optimize, f, a, b)
    opt_tol_gold = partial(gold_ratio, f, a, b)
    its = [opt_tol(tol) for tol in tols]
    its_gold = [opt_tol_gold(tol)[2] for tol in tols]
    plt.plot(tols, its, label='Brent+der')
    plt.plot(tols, its_gold, label='golden ratio')
    plt.xscale('log')
    plt.ylabel('количество итераций')
    plt.xlabel('точность')
    plt.yticks([4,10,20,30,40,50])
    plt.ylim(bottom = 0, top = 50)
    plt.legend()
    plt.title('кол-во итераций vs точность')

    plt.show()



a, b = -11, 239
it_graph(f1, a, b)
import time

def timed(f, *args, n_iter=100):
    acc = float('inf')
    for i in range(n_iter):
        t0 = time.perf_counter()
        f(*args)
        t1 = time.perf_counter()
        acc = min(acc, t1-t0)
    return acc


def time_graph(f, a, b):
    tols = [10**(-2-i) for i in range(14)]
    opt_tol = partial(optimize, f, a, b)
    opt_tol_gold = partial(gold_ratio, f, a, b)
    tm = [timed(opt_tol, tol) for tol in tols]
    tm_gold = [timed(opt_tol_gold, tol) for tol in tols]

    plt.plot(tols, tm, label='Brent+der')
    plt.plot(tols, tm_gold, label='golden ratio')
    plt.xscale('log')
    plt.ylabel('Время работы')
    plt.xlabel('точность')
    plt.legend()
    plt.title('Время работы vs точность')

    plt.show()
    
    
time_graph(f1, a, b)<jupyter_output><empty_output><jupyter_text>Графики "количество итераций vs точность" и "время работы vs точность" для параболы для отрезка  [𝑎,𝑏], не содержащего минимум.<jupyter_code>seed(0)
a = uniform(0, 1)
b = uniform(a, 10)
print(a, b)
it_graph(f1, a, b)
time_graph(f1, a, b)<jupyter_output>0.8444218515250481 7.78393262062566<jupyter_text>На этом примере видно, что для монотонных на отрезке функций метод хоть и делает меньше операций, чем золотое сечение, но проигрывает ему во времени работы. Скорее всего это происходит потому, что почти на каждом шаге, например в данном случае, реализуется ситуация $a = x = u$, и метод заходит в ветку с большим количеством условий. По количеству вызовов оракула на итерацию метод выигрывает у золотого сечения (1 против 2).  Графики для функции $f_2$ (см. начало файла) степени для отрезка, содержащего локальный минимум.<jupyter_code>a, b = -10, 10
it_graph(f2, a, b)
time_graph(f2, a, b)<jupyter_output><empty_output><jupyter_text>Графики для $f_3$, отрезок содержит локальный минимум<jupyter_code>a, b = 1.9, 3.9
it_graph(f2, a, b)
time_graph(f2, a, b)<jupyter_output><empty_output><jupyter_text>На примере $f_2$ можно убедиться, что метод сходится в какой-то локальный минимум. Заранее сказать в какой именно, для произвольной функции на произвольном отрезке довольно сложно, если не невозможно.<jupyter_code>a, b = -10, 10
print(optimize(f2, a, b))<jupyter_output>2.0654526331291647
{'fraction_non_alphanumeric': 0.13127229488703923, 'fraction_numerical': 0.03852556480380499, 'mean_word_length': 3.7152466367713006, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '151490', 'license': 'Apache-2.0', 'n_tokens_mistral': 1912, 'n_tokens_neox': 1948, 'n_words': 466, 'path': 'HW_1/hw1_opt_prazd.ipynb', 'repo_name': 'AntonPrazdnichnykh/HSE.optimization', 'size': '4205'}