Назначение: Поиск минимума унимодальной функции на
заданном интервале Принцип: Деление интервала пополам с использованием
двух близких точек Преимущества: Простота реализации, надежность
Метод дихотомии предназначен для поиска минимума унимодальной функции
на заданном интервале [a, b]. В отличие от метода бисекции, метод
дихотомии использует две близкие точки внутри интервала для сравнения
значений функции.
Алгоритм:
Задаются начальные значения a и b, а также точность ε
Вычисляются две близкие точки x1 и x2 внутри интервала:
x1 = (a + b)/2 - δ
x2 = (a + b)/2 + δ
где δ = ε/2
Сравниваются значения функции f(x1) и f(x2):
Если f(x1) < f(x2), то минимум находится на интервале [a, x2], и
b = x2
Если f(x1) ≥ f(x2), то минимум находится на интервале [x1, b], и
a = x1
Шаги 2-3 повторяются до тех пор, пока длина интервала |b - a| не
станет меньше заданной точности ε
Результатом является середина последнего интервала: (a + b)/2
function dichotomySearch(a, b, testFunction) {
const epsilon = 1e-5;
const delta = epsilon / 2;
let iterations = 0;
while (Math.abs(b - a) > epsilon) {
++iterations;
const mid = (a + b) / 2;
const x1 = mid - delta;
const x2 = mid + delta;
if (testFunction(x1) < testFunction(x2)) {
b = mid;
} else {
a = mid;
}
}
return [(a + b) / 2, iterations];
}
Метод золотого сечения
Назначение: Поиск минимума унимодальной функции на
заданном интервале Принцип: Использование золотого сечения для деления
интервала Преимущества: Эффективность, оптимальное соотношение
точности и количества вычислений
Метод золотого сечения — это численный метод оптимизации, который
используется для поиска минимума унимодальной функции на заданном
интервале. Он основан на принципе деления интервала в пропорции
золотого сечения.
let x1 = b - goldenRatio * (b - a);
let x2 = a + goldenRatio * (b - a);
let f1 = testFunction(x1);
let f2 = testFunction(x2);
while (Math.abs(b - a) > epsilon) {
++iterations;
if (f1 < f2) {
b = x2;
x2 = x1;
f2 = f1;
x1 = b - goldenRatio * (b - a);
f1 = testFunction(x1);
} else {
a = x1;
x1 = x2;
f1 = f2;
x2 = a + goldenRatio * (b - a);
f2 = testFunction(x2);
}
}
return [(a + b) / 2, iterations];
}
Метод средней точки
Назначение: Поиск минимума унимодальной функции на
заданном интервале Принцип: Сравнение значений функции в концах и
середине интервала Преимущества: Простота, эффективность для гладких
функций
Метод средней точки — это простой метод оптимизации, который
использует сравнение значений функции в концах интервала и в его
середине для определения половины интервала, где расположен минимум.
Алгоритм:
Задаются начальные значения a и b, а также точность ε
Вычисляется середина интервала: mid = (a + b) / 2
Сравниваются значения функции f(a) и f(mid):
Если f(a) < f(mid), то минимум находится на левой половине
интервала [a, mid], и b = mid
Если f(a) ≥ f(mid), то минимум находится на правой половине
интервала [mid, b], и a = mid
Шаги 2-3 повторяются до достижения заданной точности ε
Результатом является середина последнего интервала
function middlePointSearch(a, b, testFunction) {
const epsilon = 1e-5;
let iterations = 0;
while (Math.abs(b - a) > epsilon) {
++iterations;
const mid = (a + b) / 2;
if (testFunction(a) < testFunction(mid)) {
b = mid;
} else {
a = mid;
}
}
return [(a + b) / 2, iterations];
}
Метод релаксации (градиентный спуск)
Назначение: Поиск минимума функции методом
градиентного спуска Принцип: Движение в направлении, противоположном
градиенту Преимущества: Применим к дифференцируемым функциям
Метод релаксации (или метод градиентного спуска) — это метод
оптимизации, который использует информацию о производной функции для
поиска минимума. Метод заключается в многократном движении в
направлении, противоположном градиенту функции.
Алгоритм:
Выбирается начальная точка x₀ (обычно середина интервала [a, b])
Задается фиксированный шаг λ (лямбда)
Выполняется итерационный процесс:
x_{n+1} = x_n - λ * f'(x_n)
где f'(x_n) — производная функции в точке x_n
Процесс продолжается до тех пор, пока норма градиента |f'(x)| не
станет меньше заданной точности ε
Если новая точка выходит за границы интервала [a, b], она
проектируется на ближайшую границу
function easeItterations(a, b, func, epsilon = 1e-5) {
const lambda = 0.1;
let x0 = (a + b) / 2;
let x1;
let iterations = 0;
const maxIterations = 1000000;
// Производная функции x^3
const derivative = x => 3 * Math.pow(x, 2);
do {
x1 = x0 - lambda * derivative(x0);
// Проекция на интервал [a, b]
if (x1 < a || x1 > b) {
x1 = Math.max(a, Math.min(b,
x1));
}
x0 = x1;
if (++iterations > maxIterations) {
throw new Error('Превышено
максимальное количество итераций');
}
} while (Math.abs(derivative(x1)) > epsilon && iterations
< maxIterations);
return [x1, iterations];
}
Метод хорд
Назначение: Поиск корня уравнения f(x) = 0 Принцип: Аппроксимация кривой хордой и нахождение её
пересечения с осью x Преимущества: Быстрая сходимость, надежность
Метод хорд — это численный метод для нахождения корня уравнения f(x) =
0. Он основан на идее аппроксимации кривой хордой и нахождении точки
пересечения этой хорды с осью x.
Алгоритм:
Проверяется условие f'(a) * f'(b) < 0 (производная меняет знак на
интервале)
iteration++;
} while (true);
}
else {
throw new Error('Метод хорд не применим:
производная не меняет знак на отрезке. Минимум на границе.');
}
}
Метод Ньютона
Назначение: Поиск корня уравнения f(x) = 0 Принцип: Использование касательной к графику функции
для приближения корня Преимущества: Очень быстрая квадратичная сходимость
вблизи корня
Метод Ньютона — это численный метод для нахождения корня уравнения
f(x) = 0. Он использует касательную к графику функции для приближения
корня. Метод также известен как метод касательных.