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

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

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

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

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

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

Терминология [ править ]

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

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

Научное сообщество [ править ]

Не существует научного общества , специализирующегося на компьютерной алгебре, но эту функцию берет на себя специальная группа по интересам Ассоциации вычислительной техники под названием SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation). ^[3]

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

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

Аспекты информатики [ править ]

Представление данных [ править ]

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

Числа [ править ]

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

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

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

Выражения [ править ]

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

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

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

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

Упрощение [ править ]

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

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

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

Это упрощение обычно осуществляется с помощью правил переписывания . ^[8] Есть несколько классов правил перезаписи, которые необходимо учитывать. Самый простой состоит в правилах перезаписи, которые всегда уменьшают размер выражения, например 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 , E ⋅ F ⁻¹ . Другими словами, во внутреннем представлении выражений нет ни вычитания, ни деления, ни унарного минуса, кроме представления чисел.

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

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

Математические аспекты [ править ]

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

${\ Displaystyle (\ грех (х + Y) ^ {2} + \ журнал (z ^ {2} -5)) ^ {3}}$

рассматривается как многочлен от и${\ Displaystyle \ грех (х + у)}$${\ Displaystyle \ журнал (г ^ {2} -5)}$

Равенство [ править ]

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

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

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

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

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

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

История [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

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

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

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