Допустим, нам требуется найти точку, в которой пересекаются две функции. Для большей простоты будем искать точку пересечения двух прямых, заданных уравнениями y(x) = 2*x + 1 и g(x) = 5 - x. С этой задачей в первый раз можно столкнуться в школе, примерно в 6-7 классе при изучении графиков функций.
С помощью графического решение можно уточнить количество корней и примерное их значение. А вот аналитическое решение уже дает точные результаты. Лучше всего совмещать два таких решения, так как вы будете получать и визуальное представление, и точное решение.
Итак, решим эту задачу следующим образом:
Давайте посмотрим на рисунок, чтобы убедиться, что графики пересекаются именно в этой одной точке, координаты которой у нас уже есть перед глазами:
Казалось бы, если мы имеем простое аналитическое решение, то зачем нужно применять численные методы? Зачем искать решение методом перебора и тратить на это драгоценные такты процессора?
Давайте теперь рассмотрим немного другой пример
Построим график, который будет показывать нам, что решение уравнения y(x) = g(x) эквивалентно решению уравнения f(x) = 0, где f(x) = y(x) - g(x).
Именно в этом случае проще будет написать код, который в определенной области переберет все решения. В обоих случаях хорошо видно, что корень принадлежит интервалу [1; 2]. Значит на нем мы и можем начать поиск решения.
Первый метод: простой перебор
x_start - начальное значение диапазона, x_end - конечное значение для x. Между этими значениями будем искать решение. eps - наперед заданная погрешность. x - текущая переменная, которая вначале равна x_start, а затем каждый раз увеличивается на dx. Цикл while() выполняется до тех пор, пока x не дойдет до конца заданного интервала, то есть до x_end. В цикле каждый раз проверяется момент, когда абсолютная разница между функциями в текущей точке не станет меньше допустимой погрешности. Именно в этот момент осуществляется выход. И это будет момент нахождения ближайшего решения к точке x_start.
Внимание: если вы попробуете прописать в условии if ( y(x) == g(x) ), то у вас никогда не зайдет в ветку if, т.к. при вычислениях в десятичных дробях всегда теряется точность. Поэтому вероятность того, что y(x) сравняется с g(x) в точности до последнего знака стремится к нулю. А если же они будут отличаться даже в 10-м знаке после запятой, то оператор "==" будет давать false и не станет заходить в ветку. То есть всегда считается через допустимую погрешность.
И вроде всё нормально в этом решении. Оно небольшое, дает вполне точный ответ. Проблема только в том, что из-за маленького шага dx, программе нужно совершить 20935 итераций, чтобы получить ответ с заданной точностью. И это довольно большое число, которое нужно стремиться уменьшить.
Лучше всего для этого подойдет модификация перебора в виде метода половинного деления (метод бисекции, метод дихотомии). Немного теории почитать можно здесь . На википедию не даю даже ссылку, потому что считаю этот сайт поганым для изучения физико-математических проблем или алгоритмов. Мало того, что статьи там нагло передирают из книг, да еще и самым сложным образом, не объясняя сопутствующих терминов, и делая кучи ошибок. Поэтому советую искать хорошие книги или простые статьи.
В двух словах о методе бисекции
Если мы четко знаем, что функция f(x) на некотором отрезке [a; b] имеет единственный корень, то значение функции на краях этого интервала всегда имеют противоположные знаки. Где какой - зависит от убывания или возрастания функции. Но одно выражение легко позволяет проверить верность этого условия, если мы напишем f(a) * f(b) < 0. Только в случае разных знаков произведение всегда будет отрицательно, а в случае одинаковых знаков - положительно. Далее мы вычисляем середину интервала xm = (a + b) / 2 . А затем проверяем условия:
1. Если f(a) * f(xm) < 0 - верно, тогда корень лежит на интервале [a; xm] и нам необходимо точку b (текущий правый край нашего интервала поиска) сдвинуть в точку xm, тем самым сузив интервал поиска в два раза. Делается это присваиванием b = xm. В результате мы получаем интервал [a ; (a + b)/2 ]. И повторяем поиск на нем.
2. Если f(xm) * f(b) < 0 - верно, тогда корень лежит на интервале [xm; b] и нам необходимо точку a (текущий левый край нашего интервала поиска) сдвинуть в точку xm, тем самым сузив интервал поиска в два раза. Делается это присваиванием a = xm. В результате мы получаем интервал [(a + b)/2; b ]. И повторяем поиск на нем.
В итоге, каждый раз проверяя значение нашей функции в середине интервала, мы получаем условие, когда |f(xm)| не будет превышать заданную погрешность, что будет означать достижение решения.
С аналогичной точностью eps = 0.0001 мы получаем решение задачи за 12 итераций, что даже на интерпретируемом языке выполняться будет вполне быстро.
Выводы
1. Если задачу можно решить аналитически, то лучше её решить аналитически и закодить в программе готовую функцию, выдающую ответ по выведенной вами формуле. Это будет быстрее всего.
2. Есть задачи, которые либо не решаются аналитически, либо нужно затратить большие силы и много времени для их подробного решения. В этом случае лучше использовать численные методы, которые с помощью нескольких строк кода помогают справиться со сложным нелинейным уравнением, отыскав решение с нужной точностью за приемлемое количество шагов.
4. Не стоит пренебрегать аналитическим решением. Это тренирует мозг и разгружает вычислительные способности устройства, на котором выполняется ваша программа. Простое решение делает код более быстрым и оптимальным.
А чем вам помогают численные методы? Сталкивались ли вы уже с ними? Напишите об этом в комментариях! :)
Спасибо, что дочитали до конца :) Если вам нравятся такие разборы, и вы хотите видеть их чаще, то оставьте обратную связь (лайки, комментарии, ваши мысли).
Еще много полезного и интересного вы сможете найти на ресурсах:
Репетитор IT mentor в Instagram
Physics.Math.Code в контакте (VK)
