Уроки 112 - 114
Решение уравнений в табличных процессорах
§70. Решение уравнений
Содержание урока
Метод деления отрезка пополам
Использование табличных процессоров
Метод деления отрезка пополам
Есть старая задача-шутка: «Как поймать льва в Африке?» Предлагается перегородить забором всю Африку, разбив её на две равные части, и ждать, где появится лев. Затем часть, в которой есть лев, разделить забором на две равные области и т. д. В конце концов, лев окажется в маленькой клетке. На самом деле эта шутка иллюстрирует метод деления отрезка пополам (метод бисекции), с помощью которого можно найти решение уравнения на некотором интервале (если оно там есть).
Пусть некоторая функция y = f(x) непрерывна на отрезке [а, b] и имеет разные знаки в точках х = а и х = b (рис. 9.6). Тогда в одной из промежуточных точек х = х* она обращается в ноль, т. е. уравнение f(х) = 0 имеет решение. Найти его можно так:
1) вычислить середину отрезка с = а + b / 2;
2) если на отрезке [а, с] есть решение, присвоить b:=с, иначе присвоить а:=с;
3) повторять шаги 1-2 до тех пор, пока b - а < 2ε.
В пункте 2 нам нужно ответить на вопрос, если решение на отрезке [а, с]. Мы уже умеем это делать: решение есть, если f(a) • f(c) ≤ 0.
В простейшем варианте цикл, уточняющий решение, можно записать в виде:
Однако в приведённом алгоритме есть одна проблема, которая проявляется в том случае, когда на очередном шаге f(a) = 0 или f(c) = 0. Предположим, что рассматривается функция f(х) = х - 1, и мы выбрали для поиска отрезок [0, 2]. Тогда на первом же шаге получаем с = 1, так что f(c) = 0; это приводит к выполнению присваивания а:=с. Поэтому на втором шаге получаем f(а) = 0, а на всех последующих шагах — f(а)•f(с)>0, что, в конечном счёте, даёт неверный ответ х = 2.
Чтобы решить эту проблему, вернёмся к формулировке «на отрезке [а, b] есть решение, если функция f(х) имеет разные знаки на концах этого отрезка». В школьном алгоритмическом языке есть функция sign, которая возвращает знак числа, т. е. вычисляет функцию:
Тогда условный оператор в теле цикла можно заменить так:
Теперь программа даёт правильное решение даже для рассмотренных выше особых случаев (проверьте это самостоятельно). К сожалению, во многих версиях Паскаля 1 функции sign нет, но вы легко можете её написать.
1 В среде FreePascal функция sign входит в модуль Math, который нуж но подключить командой uses Math;
На каждом шаге этого цикла ширина отрезка уменьшается в 2 раза, за n шагов она уменьшится в 2n раз. Таким образом, при выборе единичного начального отрезка для получения решения с точностью 0,001 достаточно 10 шагов цикла.
Метод деления отрезка пополам очень прост и надёжен, позволяет найти решение с заданной точностью (в пределах точности машинных вычислений). Однако для его применения нужно заранее отделить корни уравнения, т. е. найти отрезки, каждый из которых содержит только один корень. Для отделения корней можно использовать построенный график функции или метод перебора с некоторым шагом. Таким образом, решение уравнения проводится в два этапа — отделение корней и уточнение корней.
К сожалению, метод деления отрезка пополам неприменим для решения систем уравнений с несколькими неизвестными.
Следующая страница 
Пример: полёт мяча
Cкачать материалы урока
