Метод половинного деления позволяет находить корни нелинейных уравнений на компьютере, не прибегая к аналитическим исследованиям функций. Как я уже понял, большинству читателей на Дзене важно видеть непосредственное применение математики и физики в жизни. Поиск корней различных (желательно, произвольных) уравнений может здорово помочь при оптимизации различных процессов. Например, чтобы хотя бы сколько-то снизить интенсивность автомобильных пробок в городе, не меняя разметки и знаков, можно наилучшим образом настроить светофоры, все времена включения и выключения зеленого света. Например, цитирую компанию SIMETRA: "Оптимизация режимов светофорного регулирования и организация координированного управления светофорами по принципу «зеленая волна» позволяет повысить пропускную способность транспортных узлов, снизить длину очереди и время проезда без серьезных капитальных вложений и трудозатрат на модернизацию транспортной инфраструктуры.".
Не знаю, каким методом пользуются в данной компании, но в любом случае ясно, что это задача со внутренними противоречиями: оптимизация одного выбранного направления ограничивает оптимизацию во всех пересекающих это направление маршрутах. Если постараться сделать так, чтобы все в городе оказались примерно в одинаковых, но, при этом, наилучших условиях, нужно решать задачу оптимизации. Для этого, обычно, для каждой подзадачи (в нашем примере для каждого маршрута) или для всех задач сразу нужно придумать некоторую функцию, которая бы оценивала "успех" настройки. Если задача состоит в оптимизации одной подзадачи, все, обычно, тривиально. В случае одного маршрута оптимальным было бы, чтобы зеленый свет горел всегда на всех перекрестках. Но тогда все очень плохо станет на всех пересекающих направлениях.
Уравнения, которые приходится решать в таких задачах, являются очень сложными. Их сложность заключается не только в том, что нужно много времени для нахождения решения, но и в том, что, чаще всего, любое найденное решение не является наилучшим гарантированно. При решении таких задач исследователь вынужден задать некоторые начальные условия самостоятельно, основываясь на своем опыте, или на интуиции, или просто испытывая удачу. Дальше, применяя тот или иной алгоритм, он движется в сторону оптимизации задачи, это хорошо проверяется самим алгоритмом, и достигает некоторого оптимального минимума. Если минимум найден, можно принять его за наилучшее решение, и воплотить в жизнь, но нет гарантии, что другие начальные параметры не приведут к другому еще более оптимальному решению. Это обычно представляют в виде "ям" на двумерной плоскости. Если ваша цель - максимально низкая точка - вы, как только находите какое-то снижение, движетесь в сторону снижения и успешно приходите на "дно", но вместе с тем оказываетесь в тупике, не зная, стоило ли двигаться в эту "яму", или есть все же "ямы поглубже".
Здесь я отдалился уже от названия статьи, зачем в этой ситуации может понадобиться решение нелинейных уравнений? Допустим, мы нашли некоторый минимум функции стоимости (это та самая функция, которая оценивает "успех" настройки). Образно, оказались в некоторой довольно "глубокой оптимальной яме", сидим там и думаем, могли ли наши конкуренты придумать решение получше. Все, что мы имеем - какая-то сложная функция поверхности, про графическую форму которой мы подробно знаем только в окрестности нашей ямы. Осмелюсь предположить, что можно попробовать найти все решения этой функции, равной нашему найденному минимуму (если вы, мои внимательные читатели, знаете о таком методе, буду признателен, если сообщите в комментариях:)). Если получится найти точку, где функция оказывается на уровне дна нашей "ямы", нужно немедленно покидать ее и спешить к той точке, ведь она, как минимум, не хуже:) Вот пример практического использования:) Дальше скучнее:)
Рассмотрим задачу
в которой нужно найти как можно больше значений переменной x, которые обращают равенство в верное. Для реализации метода поиска нужно создать функцию в программе.
double function (double x) {
double sq = x*x;
double th = sq*x;
double fr = sq*sq;
double fv = th*sq;
return fv + 42.0*fr - 4640.0*th + 37578.0*sq + 4639*x - 37620.0;
}
Метод половинного деления требует задания начального интервала поиска. При этом нужно, чтобы края интервала обращали функцию в левой части уравнения в значения с разными знаками. Если на левом краю функция меньше нулю, то на правом должна быть больше нуля, и наоборот. Это условие позволяет знать, что функция меняет знак внутри тестируемого интервала нечетное количество раз и знать, что хотя бы одно решение мы должны найти. Думаю, метод не учитывает разрывы в функции, так что тоже может дать побочные сложности, но наша функция является гладкой везде, так что можем не беспокоиться об этом. Давайте начнем с интервала [a,b] = [-10:10]. В начале программа пусть проверит края и, если функция имеет один и тот же знак на них, пусть расширяет интервал, пока ситуация не изменится.
int main () {
double a = -10.0;
double b = 10.0;
while ((function(a)*function(b))>0.0) {
a-=1;
b+=1;
}
std::cout << "Starting a=" << a << "\n";
std::cout << "Starting b=" << b << "\n";
return 0;
}
Этот кусок кода дал такой ответ:
Starting a=-10
Starting b=10
Значит, наш интервал оказался удачным и в нем есть хотя бы одно решение. Дополним программу очень простым алгоримом: пусть она в два раза сокращает интервал и выбирает каждый раз ту половину, в которой функция меняет знак. Также установим точность, например, чтобы функция не была дальше чем на 0.000001 от нуля.
int main () {
double a = -10.0;
double b = 10.0;
double epsilon = 0.000001;
while ((function(a)*function(b))>0.0) {
a-=1;
b+=1;
}
std::cout << "Starting a=" << a << "\n";
std::cout << "Starting b=" << b << "\n";
while ( (fabs(function(a))>epsilon) && (fabs(function(b))>epsilon) ) {
double c = a + 0.5*(b-a);
if ((function(c)*function(b))>0.0) {
b = c;
}
else {
a = c;
}
}
std::cout << "Result a=" << a << "\n";
std::cout << "Result b=" << b << "\n";
return 0;
}
Получился ответ a=b=-1. На самом деле, число -1 обращает нашу функцию в 0. Как найти другие возможные решения? Нужно исключить найденное решение из нашей функции, делается это довольно просто:
Во втором уравнении мы исключили найденный корень, так что можем эту модифицированную функцию подставить в алгоритм.
double function (double x) {
double sq = x*x;
double th = sq*x;
double fr = sq*sq;
double fv = th*sq;
return (fv + 42.0*fr - 4640.0*th + 37578.0*sq + 4639*x - 37620.0)/(x+1.0);
}
Эта модифицированная функция имеет теперь разрыв в точке x=-1, но он никак не будет влиять на поиск новых решений, потому что в точке разрыва односторонние пределы совпадают. Во второй раз алгоритм расширил диапазон, потому что на краях интервала [-10:10] знаки функции совпали. В результате найден корень x=44, который мы исключим по такой же схеме.
Аналогичным образом находятся и исключаются корни x=-95; x=1 и x=9.
Метод половинного деления - не самый быстрый, но самый простой способ нахождения корней.
Если знаете другие методы, или интересна тема и есть желание познакомиться с другими методами - пишите в комментариях. Подписывайтесь на канал, если интересны разные вопросы физики и математики.
