168 lines
4.9 KiB
Python
168 lines
4.9 KiB
Python
# golden_section_search.py
|
||
# Метод золотого сечения для одномерной оптимизации (10 итераций)
|
||
# Условия из задачи: f(x) = sqrt(x^2 + 9) / 4 + (5 - x) / 5, X = [-3, 8]
|
||
|
||
import math
|
||
from pathlib import Path
|
||
|
||
import matplotlib.pyplot as plt
|
||
import numpy as np
|
||
|
||
# Глобальный счётчик обращений к оракулу
|
||
oracle_calls = 0
|
||
|
||
|
||
def f(x: float) -> float:
|
||
global oracle_calls
|
||
oracle_calls += 1
|
||
return math.sqrt(x**2 + 9) / 4 + (5 - x) / 5
|
||
|
||
|
||
# Параметры
|
||
a_init = -3.0
|
||
b_init = 8.0
|
||
num_iters = 10 # ровно 10 итераций
|
||
|
||
# Константы золотого сечения
|
||
phi = (1 + math.sqrt(5)) / 2.0 # ~1.618...
|
||
r = 1 / phi # ~0.618...
|
||
c = 1 - r # ~0.382...
|
||
|
||
# Создаём папку для графиков
|
||
Path("golden_section_plots").mkdir(exist_ok=True)
|
||
|
||
# История итераций
|
||
history = []
|
||
|
||
# Начальные значения
|
||
a = a_init
|
||
b = b_init
|
||
|
||
# Начальные точки
|
||
y = a + c * (b - a)
|
||
z = a + r * (b - a)
|
||
fy = f(y)
|
||
fz = f(z)
|
||
|
||
print("Метод золотого сечения")
|
||
print("=" * 80)
|
||
|
||
print("\nНачальное состояние:")
|
||
print(f" Интервал: [{a:.6f}, {b:.6f}], длина = {b - a:.6f}")
|
||
print(f" y = {y:.6f}, f(y) = {fy:.6f}")
|
||
print(f" z = {z:.6f}, f(z) = {fz:.6f}")
|
||
|
||
# Основной цикл
|
||
for k in range(1, num_iters + 1):
|
||
# Сохраняем состояние до обновления
|
||
history.append(
|
||
{
|
||
"iter": k,
|
||
"a": a,
|
||
"b": b,
|
||
"y": y,
|
||
"z": z,
|
||
"fy": fy,
|
||
"fz": fz,
|
||
"interval_length": b - a,
|
||
}
|
||
)
|
||
|
||
print(f"\nИтерация {k}:")
|
||
print(f" Интервал: [{a:.6f}, {b:.6f}], длина = {b - a:.6f}")
|
||
print(f" y = {y:.6f}, f(y) = {fy:.6f}")
|
||
print(f" z = {z:.6f}, f(z) = {fz:.6f}")
|
||
|
||
# Построение графика
|
||
x_plot = np.linspace(a_init, b_init, 500)
|
||
y_plot = [f(x) for x in x_plot]
|
||
|
||
plt.figure(figsize=(10, 6))
|
||
plt.plot(x_plot, y_plot, "b-", linewidth=2, label="f(x)")
|
||
plt.axvline(
|
||
a, color="red", linestyle="--", alpha=0.7, label=f"Интервал [{a:.3f}, {b:.3f}]"
|
||
)
|
||
plt.axvline(b, color="red", linestyle="--", alpha=0.7)
|
||
plt.plot(y, fy, "go", markersize=10, label=f"y = {y:.3f}, f(y) = {fy:.4f}")
|
||
plt.plot(z, fz, "mo", markersize=10, label=f"z = {z:.3f}, f(z) = {fz:.4f}")
|
||
|
||
plt.xlabel("x", fontsize=12)
|
||
plt.ylabel("f(x)", fontsize=12)
|
||
plt.title(f"Золотое сечение - Итерация {k}", fontsize=14, fontweight="bold")
|
||
plt.legend(fontsize=10)
|
||
plt.grid(True, alpha=0.3)
|
||
plt.tight_layout()
|
||
plt.savefig(f"golden_section_plots/iteration_{k:02d}.png", dpi=150)
|
||
plt.close()
|
||
|
||
# Обновление интервала
|
||
if fy <= fz:
|
||
print(f" f(y) <= f(z) -> новый интервал: [{a:.6f}, {z:.6f}]")
|
||
b = z
|
||
z = y
|
||
fz = fy
|
||
y = a + c * (b - a)
|
||
fy = f(y)
|
||
else:
|
||
print(f" f(y) > f(z) -> новый интервал: [{y:.6f}, {b:.6f}]")
|
||
a = y
|
||
y = z
|
||
fy = fz
|
||
z = a + r * (b - a)
|
||
fz = f(z)
|
||
|
||
# Итоговая оценка минимума
|
||
x_star = (a + b) / 2.0
|
||
f_star = f(x_star)
|
||
|
||
# Финальный график
|
||
x_plot = np.linspace(a_init, b_init, 500)
|
||
y_plot = [f(x) for x in x_plot]
|
||
|
||
plt.figure(figsize=(10, 6))
|
||
plt.plot(x_plot, y_plot, "b-", linewidth=2, label="f(x)")
|
||
plt.axvline(
|
||
a,
|
||
color="red",
|
||
linestyle="--",
|
||
alpha=0.7,
|
||
label=f"Финальный интервал [{a:.6f}, {b:.6f}]",
|
||
)
|
||
plt.axvline(b, color="red", linestyle="--", alpha=0.7)
|
||
plt.plot(
|
||
x_star,
|
||
f_star,
|
||
"r*",
|
||
markersize=20,
|
||
label=f"x* = {x_star:.6f}, f(x*) = {f_star:.6f}",
|
||
)
|
||
|
||
plt.xlabel("x", fontsize=12)
|
||
plt.ylabel("f(x)", fontsize=12)
|
||
plt.title("Золотое сечение - Финальный результат", fontsize=14, fontweight="bold")
|
||
plt.legend(fontsize=10)
|
||
plt.grid(True, alpha=0.3)
|
||
plt.tight_layout()
|
||
plt.savefig("golden_section_plots/final_result.png", dpi=150)
|
||
plt.close()
|
||
|
||
print("\n" + "=" * 80)
|
||
print(f"\nИтераций выполнено: {num_iters}")
|
||
print(f"x* ~= {x_star:.6f}")
|
||
print(f"f(x*) ~= {f_star:.6f}")
|
||
print(f"Длина финального интервала: {b - a:.6f}")
|
||
# print(f"\nОбращений к оракулу (вычислений функции): {oracle_calls}")
|
||
print("\nГрафики сохранены в папке 'golden_section_plots/'")
|
||
|
||
# Таблица всех итераций
|
||
print("\n" + "=" * 80)
|
||
print("Сводная таблица:")
|
||
print("-" * 80)
|
||
for row in history:
|
||
print(
|
||
f"Итерация {row['iter']:2d}: "
|
||
f"[{row['a']:7.4f}, {row['b']:7.4f}] (D={row['interval_length']:7.4f}), "
|
||
f"y={row['y']:7.4f} (f={row['fy']:.4f}), "
|
||
f"z={row['z']:7.4f} (f={row['fz']:.4f})"
|
||
)
|