Алгоритмические языки METAFONT и METAPOST, пожалуй, единственные, которые имеют встроенную поддержку линейных уравнений. Числовые переменные (а также основанные на наборах чисел — координатные пары, цветовые тройки, шестёрки чисел, задающие аффинные преобразования, — все они могут получать значения не только с помощью присваивания, но и в результате их участия в линейных уравнениях.
Посмотрим, как в METAPOST решается задача об отрезках, на которые стороны , , треугольника делятся точками касания со вписанной окружностью:
METAPOSTnumeric p, q, r; message "В самом начале:"; show p, q, r; p+q=3; message "После первого уравнения:"; show p, q, r; q+r=4; message "После второго уравнения:"; show p, q, r; r+p=5; message "После третьего уравнения:"; show p, q, r; bye.
Сохраняем текст программы в файле equations.mp
и запускаем
транслятор:
%
mpost equations.mp
This is MetaPost, version 1.504 (kpathsea version 6.0.1) (mpost.mp (/usr/share/texmf-dist/metapost/base/plain.mp Preloading the plain mem file, version 1.004)) (./equations.mp В самом начале: >> p >> q >> r После первого уравнения: >> p >> -p+3 >> r После второго уравнения: >> p >> -p+3 >> p+1 После третьего уравнения: >> 2 >> 1 >> 3 ) Transcript written on equations.log.
Видно, что числовые переменные могут находиться в одном из трёх состояний: полностью неопределённом (тогда команды show показывают их имена), полностью определённом (показываются числовые значения переменных). Кроме того, возможно и промежуточное состояние переменной, когда она выражена через другие полностью неопределённые переменные — тогда показывается соответствующее линейное выражение. В терминологии METAPOST структура данных, которая может быть или неопределённой, или хранить линейное выражение, в котором участвуют переменные, или хранить число, называется капсулой (capsule).
Можно заметить, как влияет появление очередного уравнения в программе на состояния переменных: одна из участвующих в уравнении букв выражается через остальные. В этом и заключается метод последовательного исключения неизвестных.
Нам нужен тип данных для представления в программе переменных в уравнениях. Мы
могли бы назвать соответствующий класс Variable
(variable — переменная), но тогда
будет путаница между переменными в математике и переменными в языке
программирования. Назовём этот класс Capsule
.
Объекты класса должны подходить для хранения линейных выражений c участием других капсул. В частном случае, если в линейном выражении отсутствуют другие капсулы, там остаётся только лишь число — это тот самый случай, когда капсула становится «известной». Особый случай, когда значение капсулы полностью неизвестно, также следует предусмотреть.
Итак, придётся хранить в одном и том же объекте выражения наподобие этих:
В линейных выражениях имеется чёткая структура: это список слагаемых, каждое из
которых, за исключением последнего, является переменной (капсулой), умноженной
на числовой коэффициент. Последнее слагаемое, свободный член выражения — число.
Таким образом, подходящей структурой данных для линейных выражений служит
массив, в котором ячейки с чётными индексами заняты коэффициентами и свободным
членом. На нечётных местах располагаются капсулы. Этот массив должен иметь
нечётный размер. В особом случае, когда значение капсулы полностью неизвестно,
массив будет пустым — этот случай мы ни с чем не спутаем. На языке Perl
значения переменной $x
для приведённых выше примеров будут
такими: []
, [-8, $y, 11, $z,
-1, $w, 3]
, [22]
, если в переменных
$y
, $z
, $w
находятся
другие капсулы.
Линейное уравнение, после переноса всего в левую часть, задаётся линейным
выражением — тем, что окажется в левой части. Процедура
equation
, обрабатывающая уравнение, будет получать
в качестве параметра список, в котором чередуются числовые коэффициенты
и капсулы, а завершит список свободный член.
Типичная программа equation-345.pl, решающая систему линейных уравнений могла бы выглядеть так:
#!/usr/bin/perl use warnings; use Capsule; my $p=Capsule->new; my $q=Capsule->new; my $r=Capsule->new; Capsule::equation(1, $p, 1, $q, -3); Capsule::equation(1, $q, 1, $r, -4); Capsule::equation(1, $r, 1, $p, -5); print "p=", $p->value, "\n"; print "q=", $q->value, "\n"; print "r=", $r->value, "\n";
%
./equation-345.pl
p=2 q=1 r=3
В процессе решения линейной системы нам придётся многократно упрощать линейные выражения, заданные как массив с коэффициентами и капсулами. Пора обсудить, в чём же заключается упрощение.
Линейное выражение не нуждается в упрощении, если оно
Если первые два случая легко выявляются (в обоих случаях длина списка не превышает единицы), то в третьем и четвёртом случаях требуется полный просмотр списка. Этот просмотр можно совместить с устранением тех явлений, которые делают линейное выражение нуждающимся в упрощении.
Рассмотрим процесс упрощения на примере линейного выражения , предполагая, что , , а переменные и полностью неизвестны.
Первый проход по списку делает подстановки тех переменных, которые не являются полностью неизвестными:
Во втором проходе приводятся подобные слагаемые:
В третьем проходе удаляются одночлены с нулевыми коэффициентами:
Самое время обсудить те действия, которые совершаются при обработке очередного уравнения.
Процедура equation
получает список, представляющий
линейное выражение — то самое, которое приравнивается нулю. Прежде всего
выражение упрощается. После этого возможны следующие ситуации:
Разберёмся сначала со вторым, более простым случаем, когда после упрощения уравнение свелось к тривиальному или , где — ненулевое число.
Уравнение , очевидно, не добавляет никакой информации о неизвестных, и поэтому бесполезно. Такое уравнение назовём избыточным. METAPOST при появлении избыточного уравнения выдаёт предупреждение Redundant equation. По желанию можно или игнорировать избыточные уравнения, или выдавать подобное предупреждение.
Уравнение , где , конечно же ставит крест на наших попытках определить неизвестные из линейных уравнений. Такие уравнения назовём несовместными; METAPOST откликается на их появление сообщением Inconsistent equation. Нам нет никакого смысла продолжать исполнение программы, если встретилось несовместное уравнение.
Тут однако есть проблема. Рассмотрим следующий пример:
Perl$a=1000; print "РАВНО!\n" if $a/333*333==$a; print $a/333*333-$a, "\n";
Почему-то эта программа не печатает строчку РАВНО!
, как
можно было ожидать. Кроме того, вопреки ожиданиям, она напечатает не ноль,
а что-то вроде этого:
-1.13686837721616e-13
Это очень маленькое по абсолютной величине число, . С чего бы это? Конечно, всё это результат неизбежных ошибок округления. Число представляется в виде бесконечной двоичной дроби, и не может иметь точного двоичного представления в памяти компьютера. Кроме того, сам алгоритм деления целых чисел не обеспечивает абсолютной точности. Поэтому неизбежно происходит округление. В результате число не равно в точности , а отличается на очень маленькую, но ненулевую величину. Это обстоятельство следует всегда иметь в виду, когда сравниваются между собой числа, которые получаются в результате более-менее сложных арифметических вычислений. Стоит ещё добавить, что эффект от округления при арифметических вычислениях может быть разным на компьютерах разных моделей и с разной разрядностью.
Может так случиться, что из-за ошибок округления после упрощения получится несовместное уравнение с близким к нулю свободным членом, когда при абсолютно точных вычислениях получилось бы избыточное уравнение. Поскольку наша тактика в случае избыточных уравнений (наплевать и забыть) сильно отличается от тактики в случае несовместных (остановить программу с формулировкой «Несовместное уравнение»), ошибки округления могут сильно повлиять на работоспособность программы.
Мы предлагаем следующий план действий, когда упрощённое уравнение содержит лишь
свободный член: мы признаём такое уравнение избыточным, если свободный член по
модулю меньше некоторого маленького положительного числа, которое будет порогом
терпимости (tolerance) при сравнении
свободного члена с нулём. Включим в класс Capsule
переменную, которую так и назовём $tolerance
, и присвоим ей
маленькое значение, скажем, 1E-8
.
Обсудив случаи тривиальных уравнений, перейдём к типичному случаю, когда после упрощения в уравнении остаются капсулы, и они полностью неизвестны.
В таком случае уравнение можно разрешить относительно одной из капсул. Чтобы не мучиться с выбором, разрешим уравнение относительно самой первой капсулы. Для этого удалим капсулу и предшествующий ей в списке множитель (коэффициент), сохранив их при этом. Затем всё, что останется в списке уравнения, вставим в пока ещё пустой список капсулы. В завершение разделим все коэффициенты и свободный член в капсуле на сохранённый множитель со знаком минус.
Центральное место в классе Capsule
займут конструктор
капсул new
и обработчик уравнений
equation
. Кроме них потребуются вспомогательные
методы.
new()
Конструктор капсул.
simplify()
Упрощает линейное выражение, хранящееся в капсуле.
known()
Возвращает истинное или ложное значение в зависимости от того, является ли значение капсулы полностью известным.
value()
Возвращает числовое значение для известной капсулы, и неопределённое значение для неизвестной.
equation(@equation
)
Метод класса, который получает уравнение
в виде списка,
и обрабатывает это уравнение.
@equation