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

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

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

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

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

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

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

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

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

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

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

Существует несколько журналов, специализирующихся на компьютерной алгебре, главный из которых - Журнал символических вычислений основан в 1985 году Бруно Бухбергер.^[5] Есть также несколько других журналов, которые регулярно публикуют статьи по компьютерной алгебре.^[6]

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

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

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

Числа

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

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

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

Выражения

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

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

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

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

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

Упрощение

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

${displaystyle xcdot a^{x-1}cdot 0+a^{x}cdot left(1cdot log a+xcdot {frac {0}{a}}ight).}$

Такое сложное выражение явно неприемлемо, и процедура упрощения необходима, как только кто-то работает с общими выражениями.

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

Первая трудность возникает с ассоциативные операции как сложение и умножение. Стандартный способ справиться с ассоциативностью - это учитывать, что сложение и умножение имеют произвольное количество операндов, то есть а + б + c представлен как "+"(а, б, c). Таким образом а + (б + c) и (а + б) + c оба упрощены до "+"(а, б, c), который отображается а + б + c. Как насчет а − б + c? Чтобы справиться с этой проблемой, самый простой способ - систематически переписать −E, E − F, E/F как, соответственно, (−1)⋅E, E + (−1)⋅F, E⋅F⁻¹. Другими словами, во внутреннем представлении выражений нет ни вычитания, ни деления, ни унарного минуса, кроме представления чисел.

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

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

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

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

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

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

Равенство

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

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

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

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

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

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

История

В начале компьютерной алгебры, примерно в 1970 году, когда давно известные алгоритмы были впервые поставлены на компьютеры, они оказались крайне неэффективными.^[10] Следовательно, большая часть работы исследователей в этой области заключалась в пересмотре классических алгебра чтобы сделать это эффективный и открыть эффективные алгоритмы чтобы реализовать эту эффективность. Типичный пример такой работы - вычисление полиномиальные наибольшие общие делители, который требуется для упрощения дробей. Удивительно, но классический Алгоритм Евклида оказался неэффективным для многочленов над бесконечными полями, и поэтому потребовалось разработать новые алгоритмы. То же самое справедливо и для классических алгоритмов из линейная алгебра.

Смотрите также

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

Рекомендации

1. «Ассоциация ACM по компьютерной алгебре».
2. Ватт, Стивен М. (2006). Сделать компьютерную алгебру более символической (приглашено) (PDF). Proc. Transgressive Computing 2006: конференция в честь Жана Делла Дора (TC 2006). С. 43–49.
3. Официальный сайт SIGSAM
4. «Список конференций SIGSAM». Архивировано из оригинал на 2013-08-08. Получено 2012-11-15.
5. Коэн, Джоэл С. (2003). Компьютерная алгебра и символьные вычисления: математические методы. AK Peters, Ltd. с.14. ISBN  978-1-56881-159-8.
6. Список журналов SIGSAM
7. Кевин Дж. Кэссиди (декабрь 1985 г.). Возможность автоматического восстановления памяти с одновременным выполнением программ в среде LISP (PDF) (Дипломная работа). Военно-морская аспирантура, Монтерей / Калифорния. Здесь: стр.15
8. Бухбергер, Бруно и Рюдигер Лоос. "Алгебраическое упрощение. »Компьютерная алгебра. Springer, Вена, 1982. 11-43.
9. Давенпорт, Дж. Х., Сирет, Ю., и Турнье, Э. (1988). Компьютерная алгебра. Лондон: Академ.
10. Kaltofen, Erich (1982), "Факторизация многочленов", в Buchberger, B .; Loos, R .; Коллинз, Г. (ред.), Компьютерная алгебра, Springer Verlag, CiteSeerX  10.1.1.39.7916

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

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

• Символическое вычисление (редакционная статья), Бруно Бухбергер, Журнал символических вычислений (1985) 1, стр. 1–6.

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

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