3.8.5. Решение тригонометрических уравнений. Процедура PRET (М. Grandbastien, 1974)

Исходные условия в данном случае задаются в следующем виде:

где обозначает полином от тригонометрических функций переменной x. Чтобы решить эти уравнения, программа уже заранее должна быть знакома с решением двух типовых случаев

Отметим, что здесь следовало бы подумать о сведении решения заданного уравнения к решению уравнения относительно новой переменной где означает наибольший общий делитель знаменателей в Р. Можно попробовать выполнить замешу по формуле Эйлера. Однако в обоих случаях степень результирующего уравнения в общем случае получится слишком высокой для того, чтобы оно могло быть алгебраически разрешено.

Однако смысл такой замены переменных заключается в том, чтобы показать идентичность этих уравнений с точки зрения

тригонометрии, а не для того, чтобы их решить. Когда речь идет об идентичности, то в действительности достаточно лишь показать, что некий полином равен нулю.

Процедура основывается на выборе цели (в данном случае или и достижении ее всеми возможными средствами.

Рис. 3.17. Узел ИЛИ в схеме доказательства.

Рис. 3.18. Узел И в схеме доказательства..

Общая последовательность действий представляет собой итерацию из трех шагов:

• Шаг 1. Использовать обязательные правила, если это возможно.

• Шаг 2. Использовать какое-то необязательное правило, подобранное соответствующим образом.

• Шаг 3. Выделить среди рассматриваемого множества выражений наиболее подходящее выражение.

• Вернуться к шагу 1.

Каждый из этих трех шагов рассмотрен ниже более подробно. Вначале рассмотрим подробнее выполнение шага 3. По построению последовательность поиска представляет собой древовидную структуру, причем каждое исследуемое выражение порождает несколько дочерних. Если каждое из этих дочерних выражений было порождено различным правилом, начиная с предшествующего материнского выражения, то такая связь между ними обозначается как ИЛИ, и чтобы решить исходное уравнение, необходимо и достаточно решить одно из эквивалентных дочерних уравнений (рис. 3.17).

Если исходное материнское выражение представляет собой произведение нескольких выражений-сомножителей (в левой части), а правая часть уравнения представляет собой нуль, приходится решать отдельно уравнения для каждого из сомножителей. В этом случае порождаются подзадачи, причем связь такого рода обозначается как И (рис. 3.18).

На каждом шаге решения необходимо выбрать выражение, которое будет обрабатываться программой. Этот выбор производится с помощью функции оценивания из дочерних выражений последнего узла ИЛИ, причем программа оставляет выражение с наименьшей степенью сложности. Для всякого выражения сложность определяется следующим образом:

Эта оценка является довольно простой, но достаточно эффективной, так как возрастает очень быстро, если выбрано неудачное выражение, что приводит к отсечению соответствующей ветви решения. В этом случае программа переходит к другому узлу до тех пор пока оценки дочерних выражений не получатся достаточно малыми.

На шаге 2 запускаются в действие необязательные правила вывода (НП). Эти правила являются упорядоченными и применяются везде, где только возможно. Данные правила представляют собой правила переписывания. Полный перечень этих правил приведен в краткой форме записи в табл. 3.4, где trigo обозначает обратную тригонометрическую функцию. Совокупность необязательных правил была определена экспериментально — отбирались те правила, которые либо не всегда применимы в тригонометрии, либо порождают более сложные выражения (правило либо удаляют нас от конечной цели (например,

Таблица 3.4. Перечень необязательных правил вывода в тригонометрии

правило с), либо формируют экстенсивные комбинации (правила и (табл. 3.4).

Шаг 1 на самом деле состоит из трех отдельных шагов. В первую очередь программа пытается, если это возможно, упростить задачу, сведя ее к подзадачам путем разложения на множители и создания узла И. Если это не удается сделать, программа пытается упростить выражение путем замены переменной, приводя его к выражению, в котором имеется только одна переменная или единственная обратная тригонометрическая функция. Если ничего из этого сделать не удается, исходное выражение стандартизируется путем унификации с помощью обязательных правил вывода в заданном порядке. Эти правила сведены в 10 групп, приведенных ниже в перечне обязательных правил вывода (табл. 3.5).

С помощью программы PRET более ста примеров были решены за несколько секунд на ЭВМ CII 10070.

Приведем два подобных примера.

Таблица 3.5. (см. скан) Перечень обязательных правил вывода

Пример 1

Здесь невозможны ни разложение на множители, ни замены на стандартные переменные. Однако можно применить обязательное правило

Применение дает при

Теперь исходное выражение преобразовано и программа возвращается к шагу I, производя разложение выражения (III) на множители, вынося за скобки:

Это выражение приводит к двум задачам типа И:

которая тривиальна, и

Рис. 3.19. Дерево решения для уравнения

Это последнее выражение становится текущим. Для него использование обязательных правил ничего не дает, но применение (НП) (h) к подвыражению

приводит к выражению, дающему решение задачи:

На рис. 3.19 показано дерево решения для выражения

Пример 2

Никакое обязательное правило не пригодно для выражения (I). Необязательное правило напротив, приводит нас

к выражению

сложность которого составляет тогда как сложность исходного выражения (I) была равна

В действительности то же правило (а) применяется также для группирования не только к термам 1 и 2 выражения (I), но также к термам 1 и 3 или 2 и 3.

Рис. 3.20. Дерево решения для уравнения

Таким образом, программа одновременно порождает еще выражения (III) и (IV), имеющие ту же степень сложности, равную 7:

Теперь программа применяет необязательное правило к исходному выражению, получая выражение (V), степень сложности которого составляет

Программа затем обращается к выражению с наименьшей степенью сложности — пусть это будет выражение (II). Теперь необязательное правило применяется снова и приводит к выражению

которое тут же разлагается на множители

Из этого выражения порождаются две подзадачи (VIII) и (IX) (рис. 3.20). Обязательное правило преобразует разность (IX) в произведение

и задача, таким образом, в общем, решена. Дерево для нее приведено на рис. 3.20.