54
Заочная школа программирования
Урок 13: Прближенное решение уравнения с помощью ЭВМ
Из школьного курса математики вы знакомы с линейными и квадратными уравнениями, корни которых могут быть найдены по известным вам формулам. Существуют такие формулы и для решения уравнения третьей и четвертой степени. А вот уравнение обещено вида пятой и более высоких степеней неразрешимо в радиках: решения таких уравнений (в общем случае) нельзя выразить через коэффициенты с помощью арифметических действия и извлечения корней*). Задча еще больше усложняется, если рассматривать неалгебраические уравнения**). В этом случае найти для корней явные выражения, за редким исключением, неудается. Но означает ли это, что такие уравнения нельзя решить?
Объчно для нахождения корней уравнения, возникающих при решении большинства прикладных хзач, и не нужно точная формула. Чаще всего для таких задач достаточно получить ответ с определенной степенью точности. Поэтому важно и уметь применять тот или иной способ вычисления корня уравнения с необходимой степенью точности. Известен цель ряд методов приближенного решения уравнения. Описанию некоторых из них и посыщен этот урок.
Рассмотрим один из них на примере решения задачи 26 Олимпiadы по программированию («Квант», 1980, № 3): пусть Ф1(M) — описанная на Рапире функция с одним параметром (M). Нужно найти и отпечать все целые корни уравнения Ф1(M) = 0, лежащие на отрезке [0; 100].
Большинство ребят, принявших участие в Олимпiadе, хорошо справились с этой задачей. Действительно, алгоритм ее решения несложен. Сначала вычислите Ф1(M) при M = 0. Если результат равен нулю, то число 0 — корень данного уравнения. Теперь найдем значение Ф1(M) при M = 1 и опять сравним полученное значение с нулем. Последовательно вычисля значения Ф1(M) при всех целых M ∈ [0; 100], найдем те из них, при которых Ф1(M) = 0. Эти значения M и являются корнями уравнения Ф1(M) = 0. Заметим, что в этом случае найдены точные значения корней.
Реализация этого алгоритма посылана любому школьнику, который имеет нахождение значения выражений и сравнивать их с нулем. Но сколько времени потребуется для решения уравнения этим способом «вручную»? А если левая часть уравнения достаточно сложна и отрезок, на котором нужно искать решения, велик? Здесь на помощь человеку приходит вычислительная техника. Проверьте, что по следующей программе будет отпечать все целые решения уравнения Ф1(M) = 0 из отрезка [0; 100], а их количество накапливается в счетчике корней СЧЕТКОР.
ПЕЧАТЬ (‘РЕШЕНИЯ НА [0; 100]’);
0-> M; 0-> СЧЕТКОР;
ПОКА M = <100::
ЕСЛИ Ф1(M) = 0 TO
ПЕЧАТЬ(M);
СЧЕТКОР+1 -> СЧЕТКОР
ВСЕ;
1+M -> M
ВСЕ;
ЕСЛИ СЧЕТКОР=0 TO
ПЕЧАТЬ(‘КОРНЕЙ НЕТ’) ВСЕ;
А если нужно организовать поиск требуемых решений на различных отрезках? В этом случае удобно
55
описать процедуру с двумя параметрами НАЧ и КОН, которая организаует поиск всех целых решений уравнения Ф1(M)=0 на отрезке [НАЧ; КОН].
ПРОЦ ПОИСК НАЧ КОН;
ПЕЧАТЬ (‘РЕШЕНИЯ НА [’,
НАЧ,’’,КОН,’]’);
НАЧ—>M; 0—>СЧЕТКОР;
ПОКА M=<КОН::
ЕСЛИ Ф1(M)=0 TO ПЕЧАТЬ (M);
СЧЕТКОР+1—>СЧЕТКОР ВСЕ;
M+1—>M
ВСЕ;
ЕСЛИ СЧЕТКОР=0 TO
ПЕЧАТЬ (‘КОРНЕЙ НЕТ’) ВСЕ;
КНЦ;
Задание 13.1. Составить программу для поиска всех целых решений уравнения X³—10X²—27X+36=0 на отрезках [−10; 0], [1; 100].
- Задание 13.2. Составить программу, по которой будет найдены все пары целых чисел вида (X; Y), являющиеся решениями уравнения 2Y—X²=4, если X ∈ [−50; 25], Y ∈ [100; 300].
Прежде, чем перейти к описанию других методов решения уравнения, сделаем несколько заменений. Мы будем предполагать рассматриваемые функции непрерывными, то есть имеющими графики в виде линейных без разрывов*. Кроме того, мы используем из рассмотрения случай, когда график функции касается оси ОX с одной стороны (рис. 1). Тогда легко видеть **), что
1°. Если уравнение F(X)=0 имеет на некотором интервале N различных корней, то график функции F пересекает ось ОX на этом интервале тоже N раз (рис. 2,a).
2°. Если на концах отрезка [A; B] функции F принимает значения различных знаков, то уравнение F(X)=0 имеет на этом отрезке нечетное число корней (рис. 2,a), а если — одного знака, то — четное число корней (рис. 2,б,в). Заметим, что в последнем случае корней может не оказаться (0 — тоже четное число!).
Проверить, одинаковы или различны знаки y F(A) и F(B), можно простым способом: если произведение F(A)·F(B) отличается, то F(A) и F(B) имеют разные знаки, а если положительное — одинаковые.
Метод положенного деления
Будем искать корни уравнения F(X)=0 на отрезке [A; B] с точностью до 0,001. Будем считать, что C — корень уравнения с точностью до 0,001, если |F(C)|<0,001. (Заметим, что в Рапире есть стандартная функция ABS(X), которая вычисляет модуль выражения X.)
Разумеется, |F(C)|<0,001 не означает F(C)=0; поэтому «корень уравнения с точностью до 0,01»
*) Точно определение непрерывности, которое здесь не требуется, можно прочитать в пособии «Алгебра и начала анализа 9—10», п. 13.
**) Доказательство мы приводить не будем.
56
Рис. 3.
не обязательно является корнем.
Рассмотрим случай, когда на этом отрезке существует точное один корень данного уравнения (для того, чтобы выделить такой отрезок, существуют специальные методы; об одном из них расссказано ниже) и числа F(A) и F(B) имеют разные значения. Предположим для определения, что F(A) < 0, F(B) > 0 (рис. 3). Середина отрезка [A; B] имеет абсциссу C = (A + B)/2. Вычислим |F(C)| и сравним его с 0,001. Если оказывается, что |F(C)| < 0,001, то C — искомое число. Если же |F(C)| ≥ 0,001, поступим следующим образом: из отрезков [A; C] , [C; B] выберем тот, на концах которого функция F принимает значения различных значков; обозначим теперь его через [A; B]. Убедитесь, что нужный отрезок можно выбрать с помощью следующого предложения:
ECЛИ F(C)*F(B) < 0 TO C -> A ИНАЧЕ C -> B ВСЕ;
По построению, для нового отрезка [A; B] справедливый соответствия F(A) < 0, F(B) > 0. Читатель уже, наверное, договорая, что нужно делать дальше. Опять рассмотрим середину отрезка [A; B], вычислим в ней значение функции F и сравним
Рис. 5.
модуль этого значения с 0,001. Если новое значение C удовлетворяет условиям |F(C)| < 0,001, то это и есть искомое число. В противном случае — опять из двух отрезков [A; C] и [C; B] нужно выбрать тот, на концах которого функция F принимает значения разных значков. Описанный процесс нужно продолжать до тех пор, пока искомое число не будет найдено.
Внимательный читатель наверное заметил, что данный метод не всегда дает нужный ответ: случай, когда получается «ненастоящий» корень уже на первом шагу показан на рисунке 4.
Задание 13.3. Запроетримировать решение уравнения X³ + 3X - 1 = 0 на отрезке [A; B] с точностью ЭПСИЛОН методом поливинного деления.
Метод перебора с возвратом
Снова рассмотрим задачу поиска корня уравнения F(X) = 0 с точностью до 0,001 на отрезке [A; B], но на этот раз не будем делать никаких предположений о наличии корней на отрезке.
Рассмотрим отрезок [A; A + H], где H — произвольное «малое» чис-
Рис. 4.
Рис. 6.