Лекция: Метод дихотомии
Пусть функция f (x) отрицательна в точке a (f (a) < 0), положительна в точке b (f (b) > 0), и непрерывна на отрезке [a, b] график функции пересекает ось Х, т. е. на этом отрезке имеется корень уравнения – точка, в которой
f(х)= 0.
Тот же вывод следует, если f(а) > 0, f(b) < 0. В общем виде это формулируется так: в точках а и b функция f(х) принимает значения разных знаков. Если нам известен хотя бы один такой отрезок, пусть и большой длины, мы можем построить процедуру быстрого и сколь угодно точного поиска корня уравнения. Найдем значение функции в точке с, находящейся в середине отрезка: с =(a + b)/2. Знак f(с) совпадает со знаком функции на одном из концов отрезка и противоположен знаку функции на другом конце.
Пусть разные знаки f(х) в точках а и с. Значит на [а, с] наверняка есть искомый корень уравнения.
Таким образом, мы получили задачу, эквивалентную исходной, но теперь длина отрезка, на котором, как нам известно, находится корень, в два раза короче. Отрезок [а, с] опять можно разделить пополам и оставить в рассмотрении только один из двух получившихся (учитывая знаки значений f(х) на концах этих отрезков). Выбранный отрезок вновь разделить, и продолжать так до тех пор, пока отрезок, на котором находится корень, не станет достаточно мал.
Как написать программу на QuickВаsic, соответствующую этому методу?
Прежде всего, функцию, корень которой мы ищем, лучше всего описать в виде отдельной function. Во время выполнения программа должна запросить начальные значения а и b.
Далее нужно проверить, что f(а) и f(b) действительно разных знаков.
Это условие можно записать двумя разными способами:
1. ((f (а) <= 0) and (f (b) > 0)) or ((f (b) <= 0) and (f (a) > 0))
2. f (a) * f(b) <= 0
Если это не так, нужно только напечатать сообщение об ошибке, иначе можно приступать к поиску корня. Поиск проще всего оформить в виде цикла:
Do until (b-а) < eps… loop
Здесь eps — константа, равная, например 10ˉ5. На каждой итерации цикла нужно вычислить значение точки с и сравнить знак функции в этой точке со знаком f(а). Если знаки разные, о точке b можно «забыть»: b:=с. Иначе – «забываем» о точке а. После окончания цикла остается лишь напечатать найденный корень. Ближе всего к корню будет, середина окончательного отрезка [а,d], длина которого не превышает заданной точности eps.