Компьютерная алгебра

Символьное интегрирование f алгебраической функции ( x ) = ⁠ x / √ x ⁴ + 10 х ² − 96 x − 71 ⁠ с использованием системы компьютерной алгебры Аксиома

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

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

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

Терминология

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

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

Научное сообщество

Не существует научного общества, специализирующегося на компьютерной алгебре, но эту функцию берет на себя группа по особым интересам Ассоциации вычислительной техники под названием SIGSAM (Специальная группа по интересам). «Символические и алгебраические манипуляции»).

Ежегодно проводится несколько конференций по компьютерной алгебре, главной из которых является ISSAC (Международный симпозиум по символьным и алгебраическим вычислениям), который регулярно спонсируется SIGSAM.

Есть несколько журналов, специализирующихся на компьютерной алгебре, ведущим из которых является Journal of Symbolic Computation, основанный в 1985 году Бруно Бухбергером . Есть также несколько других журналов, которые регулярно публикуют статьи по компьютерной алгебре.

Аспекты информатики

Представление данных

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

Числа

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

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

Программирование эффективной реализации арифметических операций — сложная задача. Поэтому большинство бесплатных систем компьютерной алгебры и некоторые коммерческие, такие как Mathematica и Maple , используйте библиотеку GMP , которая, таким образом, является стандартом де-факто .

Выражения

Представление выражения (8 - 6) × (3 + 1) в виде дерева Лиспа из магистерской диссертации 1985 года.

За исключением чисел и переменных , каждое математическое выражение можно рассматривать как символ оператора, за которым следует последовательность операндов. В программах компьютерной алгебры выражения обычно представляются таким образом. Это представление очень гибкое, и многие вещи, которые на первый взгляд не кажутся математическими выражениями, можно представлять и манипулировать ими как таковые. Например, уравнение — это выражение с «=" в качестве оператора, матрица может быть представлена ​​как выражение с «матрицей» в качестве оператора и ее строками в качестве операндов.

Даже программы можно рассматривать и представлять как выражения с оператором «процедура» и, по крайней мере, двумя операндами, списком параметров и телом, которое само по себе является выражением с «телом» в качестве оператора и последовательностью инструкций в качестве операндов. И наоборот, любое математическое выражение можно рассматривать как программу. Например, выражение a + b можно рассматривать как программу сложения с a и b параметрами . Выполнение этой программы заключается в вычислении выражения для заданных значений a и b ; если им не присвоено никаких значений, результат оценки является просто входными данными.

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

Поскольку размер операндов выражения непредсказуем и может меняться в течение рабочего сеанса, последовательность операндов обычно представляется как последовательность либо указателей (как в Macsyma), либо в виде последовательности указателей (как в Macsyma ). или записи в хэш-таблице (например, в Maple ).

Упрощение

Грубое применение основных правил дифференцирования по x к выражению $a^{x}$ дает результат

$x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).$

Обычно желательно использовать более простое выражение, а при работе с общими выражениями необходимо упрощение.

Это упрощение обычно достигается путем переписывания правил . Следует рассмотреть несколько классов правил переписывания. Самыми простыми являются правила, которые всегда уменьшают размер выражения, например E − E → 0 или sin(0) → 0 . Они систематически применяются в системах компьютерной алгебры.

Трудность возникает с ассоциативными операциями, такими как сложение и умножение. Стандартный способ справиться с ассоциативностью — учитывать, что сложение и умножение имеют произвольное количество операндов, то есть a + b + c представляется как «+»( a , b , c ) . Таким образом, a + ( b + c ) и ( a + b ) + c упрощаются до «+»( a , b , c ) , который отображается как a + b + c . В случае таких выражений, как a − b + c , проще всего систематически переписать − E , E − F , E / F как соответственно (−1)⋅ E , E + (−1)⋅ F , Э ⋅ Ф ⁻¹ . Другими словами, во внутреннем представлении выражений нет ни вычитания, ни деления, ни унарного минуса, вне представления чисел.

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

Некоторые правила перезаписи иногда увеличивают, а иногда уменьшают размер выражений, к которым они применяются. Это случай дистрибутивности или тригонометрических тождеств . Например, закон дистрибутивности позволяет переписать $(x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1$ и $(x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.$ Поскольку не существует способа сделать правильный общий выбор, применять или нет такое правило перезаписи, такое переписывание выполняется только при явном вызове пользователя. Что касается дистрибутивности, компьютерная функция, применяющая это правило перезаписи, обычно называется «расширением». Правило обратной переписывания, называемое «фактором», требует нетривиального алгоритма, который, таким образом, является ключевой функцией в системах компьютерной алгебры (см. Полиномиальная факторизация ).

Математические аспекты

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

$(\sin(x+y)^{2}+\log(z^{2}-5))^{3}$

рассматривается как многочлен $\sin(x+y)$ и $\log(z^{2}-5)$

Равенство

Есть два понятия равенства математических выражений . Синтаксическое равенство — это равенство их представления в компьютере. Это легко проверить в программе. Семантическое равенство — это когда два выражения представляют один и тот же математический объект, как в

$(x+y)^{2}=x^{2}+2xy+y^{2}.$

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

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

В компьютерной алгебре «каноническая форма» и «нормальная форма» не являются синонимами. Каноническая форма такова, что два выражения в канонической форме семантически равны тогда и только тогда, когда они синтаксически равны, в то время как нормальная форма такова, что выражение в нормальной форме семантически равно нулю только в том случае, если оно синтаксически равно нулю. Другими словами, ноль имеет уникальное представление как выражение в нормальной форме.

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

История

Компьютерная алгебра, управляемая человеком

Ранние системы компьютерной алгебры, такие как ENIAC в Пенсильванском университете , полагались на человеческие компьютеры или программистов, чтобы перепрограммировать их между вычислениями, манипулировать многочисленными физическими модулями (или панелями) и снабжать устройство считывателя карт IBM. Женщины-математики занимались большей частью программных вычислений ENIAC, управляемых человеком: Джин Дженнингс , Марлин Вескофф , Рут Лихтерман , Бетти Снайдер , Фрэнсис Билас и Кей МакНалти возглавляли указанные усилия.

Основы и ранние приложения

В 1960 году Джон Маккарти исследовал расширение примитивных рекурсивных функций для вычисления символических выражений с помощью языка программирования Лисп в Массачусетском технологическом институте . Хотя его серия «Рекурсивные функции символьных выражений и их машинное вычисление» осталась незавершенной, Маккарти и его вклад в программирование искусственного интеллекта и компьютерную алгебру с помощью Lisp помогли основать проект MAC в Массачусетском технологическом институте и организацию, которая позже стала Стэнфордской лабораторией искусственного интеллекта (SAIL) в Стэнфордском университете , чье соревнование способствовало значительному развитию компьютерной алгебры на протяжении всего конец 20 века.

Первые попытки символьных вычислений, предпринятые в 1960-х и 1970-х годах, столкнулись с проблемами, связанными с неэффективностью давно известных алгоритмов при переносе их в системы компьютерной алгебры. Предшественники проекта MAC, такие как ALTRAN , стремились преодолеть алгоритмические ограничения за счет усовершенствований в аппаратном обеспечении и интерпретаторах, а более поздние усилия были направлены на оптимизацию программного обеспечения.

Исторические проблемы

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

Алгоритмы, используемые в компьютерной алгебре

Этот раздел представляет собой отрывок из «Списка алгоритмов § Компьютерной алгебры» . [ редактировать ]

• Алгоритм Бухбергера : находит базис Грёбнера.
• Алгоритм Кантора – Цассенхауза : фактор-полиномы над конечными полями
• Алгоритм Фожера F4 : находит базис Грёбнера (также упоминается алгоритм F5).
• Алгоритм Госпера : найти суммы гипергеометрических терминов, которые сами являются гипергеометрическими терминами.
• Алгоритм завершения Кнута – Бендикса : для переписывания систем правил.
• Алгоритм многомерного деления : для многочленов от нескольких неопределенных
• Алгоритм кенгуру Полларда (также известный как лямбда-алгоритм Полларда): алгоритм решения задачи дискретного логарифмирования.
• Полиномиальное деление в длину : алгоритм деления многочлена на другой многочлен той же или меньшей степени.
• Алгоритм Риша : алгоритм вычисления операции неопределенного интегрирования (т.е. поиска первообразных )

См. также

• Автоматизированное средство доказательства теорем
• Компьютерное доказательство
• Вычислительная алгебраическая геометрия
• Система компьютерной алгебры
• Дифференциальный анализатор
• Проверка доказательств
• Проверка модели
• Символьно-числовое вычисление
• Символическое моделирование
• Символический искусственный интеллект

Дальнейшее чтение

Для детального определения предмета:

• Бухбергер, Бруно (1985). «Символические вычисления (Редакционная статья)» (PDF) . Журнал символических вычислений . 1 (1): 1–6. дои : 10.1016/S0747-7171(85)80025-0 .

Для учебников, посвященных данному предмету:

• Давенпорт, Джеймс Х .; Сирет, Ивон; Турнье, Эвелин (1988). Компьютерная алгебра: системы и алгоритмы алгебраических вычислений . Перевод с французского А. Давенпорта и Дж. Х. Давенпорта. Академическая пресса. ISBN  978-0-12-204230-0 .
• фон цур Гатен, Иоахим; Герхард, Юрген (2003). Современная компьютерная алгебра (2-е изд.). Издательство Кембриджского университета. ISBN  0-521-82646-2 .
• Геддес, КО; Чапор, СР; Лабан, Г. (1992). Алгоритмы компьютерной алгебры . Бибкод : 1992afca.book.....G . дои : 10.1007/b102438 . ISBN  978-0-7923-9259-0 .
• Бухбергер, Бруно; Коллинз, Джордж Эдвин; Лоос, Рюдигер; Альбрехт, Рудольф, ред. (1983). Компьютерная алгебра: символические и алгебраические вычисления . Вычислительное дополнение. Том. 4. дои : 10.1007/978-3-7091-7551-4 . ISBN  978-3-211-81776-6 . S2CID   5221892 .