Этюды для программистов

Для многих важных математических операций не существует методов, которые позволяли бы всегда вычислять результат в символьном виде. Важное место среди них занимает интегрирование. Хотя любая рациональная функция имеет неопределенный интеграл, простой пример функции 1/х (неопределенный интеграл от нее — ln x) показывает, что нам не надо далеко ходить за функциями, нарушающими границы замкнутого пространства рациональных функций. Расширение пространства функций путем добавления показательных функций и логарифмов, как предложено выше, лишь обостряет проблему. Не решает проблемы даже использование определенного интеграла, поскольку результат определенного интегрирования может и не быть константой, если подинтегральное выражение содержит переменные, отличные от переменной интегрирования, или если пределы интегрирования не константы. Символьные интеграторы были одними из первых программ, написанных для демонстрации «интеллектуального» поведения ЭВМ. Если вы будете работать над предлагаемой задачей в два или три раза дольше, то сможете создать примитивный интегратор.

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

Литература

Мозес (Moses J.). Algebraic Simplification: A Guide for the Perplexed, CACM, 14, 8, pp. 527–537, 1971.

Мозес (Moses J.). Symbolic Integration: The Stormy Decade, CACM, 14, 8, pp. 548–560, 1971.

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

21. Превратное обратное, или Ошибки при работе с плавающей точкой

Многие из методов, которые сейчас изучаются в средней школе, создавались величайшими математиками в течение столетий. Среди них — методы решения системы линейных уравнений, которые неявно включают методы обращения квадратных матриц. Начинающий алгебраист, изучая эти алгоритмы, может усомниться в том, что они всегда будут работать; но, испробовав метод на двух-трех примерах* наш скептик отбросит всякие сомнения. Он даже себе не представляет, какой его ждет удар: программа, написанная им в соответствии с простым и обоснованным алгоритмом, дает совершенно неверные результаты. Разве можно заподозрить, чтобы метод обращения матриц, придуманный королем математиков Гауссом, оказался несостоятельным?

Прежде всего освежим в памяти основные положения. Матрица — это квадратный массив вещественных чисел, в котором по горизонтали и вертикали располагается по n ≥ 1 элементов. Произведение С матрицы А справа на матрицу В записывается в виде С = АВ и задается формулой

Здесь подразумевается, что А, В и С — матрицы размера n × n. Умножение некоммутативно; можно найти такие матрицы А и В, что АВ ≠ ВА. Обратной матрицей к матрице А будет такая матрица А⁻¹, что

AА⁻¹ = А⁻¹A = I

где I — единичная матрица, определяемая формулами I_ii = 1 и I_ij = 0 для i ≠ j. Большинство матриц имеет обратные, но не все. К сожалению, простейший способ обнаружить такие вырожденные матрицы состоит в том, чтобы попытаться вычислить обратную матрицу и потерпеть неудачу.

Как вычислить обратную матрицу? Следующий алгоритм принадлежит Гауссу.

Во-первых, положите матрицу X равной матрице I. В процессе вычислений матрица А будет в конце концов преобразована в I, матрица X, которая изначально была единичной матрицей, станет обратной к матрице А.

Для каждого столбца А, начиная со столбца 1 слева и кончая столбцом n справа, выполните следующее: Обозначим столбец, который будет обрабатываться на каждом этапе, символом j.

Пусть есть наибольший по абсолютной величине элемент в столбце j ниже строки j − 1. Если М равно нулю, то А — вырожденная матрица и продолжать обращение не имеет смысла. В противном случае поменяйте местами в обеих матрицах А и X строку j и строку, в которой находится М. И наконец, разделите каждый элемент в строке j матриц А и X на новое значение A_jj.

Теперь для всех строк i, i ≠ j, выполните все вычитания:

A_ik = A_ik − A_ijA_jk, j ≤ k ≤ n,

X_ik = X_ik − A_ijX_jk, 1 ≤ k ≤ n.