Компьютерная алгебра это что за предмет

Обновлено: 04.07.2024

Компьютерная алгебра – это наука об эффективных алгоритмах вычислений математических объектов.

Компьютерная алгебра — область математики, лежащая на стыке алгебры и вычислительных методов.

Компьютерная алгебра есть та часть информатики, которая занимается разработкой, анализом, реализацией и применением алгебраических алгоритмов.

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

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

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

Система компьютерной алгебры (СКА, англ. computer algebra system, CAS) — это прикладная программа для символьных вычислений, то есть выполнения преобразований и работы с математическими выражениями в аналитической (символьной) форме.

На рынке современных математических систем в настоящее время присутствует целый ряд крупных фирм: Macsyma, Inc., Waterloo Maple Software, Inc., Wolfram Research, Inc., MathWorks, Inc., MathSoft, Inc., SciFace GmbH и др.

Maple позволяет выполнять как численные, так и аналитические расчеты с возможностью редактирования текста и формул на рабочем листе.

Основные качественные отличия MuPAD — невысокие требования к ресурсам PC, наличие собственного ядра символьной математики, способность к развитию самим пользователем и мощные средства визуализации решения математических задач.

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

MATLAB — одна из старейших, тщательно проработанных и проверенных временем систем автоматизации математических расчетов, построенная на расширенном представлении и применении матричных операций. Это нашло отражение в названии системы — MATrix LABoratory — матричная лаборатория.

MATLAB как язык программирования был разработан Кливом Моулером (англ. Cleve Moler) в конце 1970-х годов, когда он был деканом факультета компьютерных наук в Университете Нью-Мексико. Целью разработки служила задача дать студентам факультета возможность использования программных библиотек Linpack и EISPACK без необходимости изучения Фортрана. Вскоре новый язык распространился среди других университетов и был с большим интересом встречен учёными, работающими в области прикладной математики.

В настоящее время система MATLAB далеко вышла за пределы специализированной матричной системы и стала одной из наиболее мощных универсальных интегрированных СКМ. Слово «интегрированная» указывает на то, что в этой системе объединены удобная оболочка, редактор выражений и текстовых комментариев, вычислитель и графический программный процессор.

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

Области применения системы MATLAB:

- математика и вычисление;

- вычислительный эксперимент, имитационное моделирование;

- анализ данных, исследования и визуализация результатов;

- научная и инженерная графика;

- разработка приложений, включая графический интерфейс пользователя и др.

Система MATLAB является одновременно операционной средой и языком программирования. Пользователь может написать специализированные функции и программы, которые оформляются в виде М-файлов.

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

Основной особенностью языка MATLAB является его широкие возможности по работе с матрицами, которые создатели языка выразили в лозунге «думай векторно» (англ. Think vectorized).

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

В настоящее время система инженерных и научных расчетов MATLAB широко распространена в университетах всего мира. Она является интерактивной средой, имеет математический сопроцессор и допускает возможность обращения к программам на языках Fortran, C и С++. Система MatLab занимает одно из лидирующих мест на рынке специализированных систем компьютерной математики, наряду с MathCad, Maple, Mathematica и др.

Основные преимущества системы MatLab – удобство пользовательского интерфейса, высокие вычислительные возможности (богатая библиотека) и широкая область применение результатов расчета.

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

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

Термин «компьютерная алгебра» возник как синоним терминов «символьные вычисления», «аналитические вычисления», «аналитические преобразования» и т.д. Даже в настоящее время этот термин на французском языке дословно означает «формальные вычисления».

В чем основные отличия символьных вычислений от численных и почему возник термин компьютерная алгебра?

Когда говорим о вычислительных методах, то считаем, что все вычисления выполняются в поле вещественных или комплексных чисел. В действительности же всякая программа для ЭВМ имеет дело только с конечным набором рациональных чисел, поскольку только такие числа представляются в компьютере. Для записи целого числа отводится обычно 16 или 32 двоичных символа (бита), для вещественного — 32 или 64 бита. Это множество не замкнуто относительно арифметических операций, что может выражаться в различных переполнениях, например, приумножении достаточно больших чисел или при делении на маленькое число. Еще более существенной особенностью вычислительной математики является то, что арифметические операции над этими числами, выполняемые компьютером, отличаются от арифметических операций в поле рациональных чисел, более того, для компьютерных операций не выполняются основные аксиомы поля (ассоциативности, дистрибутивности). Эти особенности компьютерных вычислений выражаются в терминах погрешности или точности вычислений. Оценка погрешности представляет одну из основных проблем вычислительной математики. Каждую задачу требуется решить с использованием имеющихся ресурсов ЭВМ, за обозримое время, с заданной точностью.

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

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

Ограничения на алгоритмы решаемых компьютерной алгеброй задач накладываются имеющимися ресурсами ЭВМ и обозримостью времени счета. Однако ограничения по времени счета и по используемой памяти в символьных вычислениях существенно более обременительны, чем в вычислительных методах.

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

Под системами компьютерной алгебры (или системами символьных вычислений) подразумевают такие программные продукты, как Maple, Maxima, Reduce, Derive и другие.

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

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

Когда, в не слишком далеком 2003 году я начал работать над кандидатской диссертацией, я столкнулся с необходимостью решать систему тригонометрических уравнений вида

Параметры a, b, A, B — положительны. На корни уравнения накладываются условия

Где мы сталкиваемся с такими системами? При расчете кинематики замкнутых четырехзвенников, например. Такой замкнутый четырехзвенник был в моей работе, почти такой же попался мне около года назад, когда я взялся сделать «шабашку» (помог одному профессору в его работе).

Тогда, в 2003-м я только познакомился с системой Maple и был в восторге от её возможностей, естественно я поручил эту систему ей. И меня ждал «облом»… Посмотрим, какое решение дают Maple 18 и Mathematica 10 для этой задачи сегодня.

2. Решение задачи в СКА «в лоб»

В моем любимом Maple задаем систему уравнений

и пробуем решить

и получаем…

Эта бяка не влезла в онлайн-LaTeX, поэтому пришлось привести скриншот. Такой результат получается из-за того, что постановка задачи слишком общая. Необходимо указать системе, какое решение нас интересует, воспользовавшись условием (3)

В этом случае результат выглядит получше

Ещё раз попрошу прощения у читателя за корявый скриншот и замечу, что мы получили два решения системы (1) — (3) и нам теперь ещё предстоит разобраться, какой ответ соответствует механическому смыслу задачи (он там есть, да), а учитывая, что за a, b, A и B могут таится довольно значительные выражения (не зависящие, естественно, от x и y) нам должно стать довольно грустно в этот момент.

У системы Mathematica 10 с этими уравнениями лучше дела обстоят в том смысле, что она получает конечную форму общего решения, часть которого на скрине

Если систему дополнить условием (3), то Вольфрам говорит нам, что Solve[. ] не имеет метода решения для такого случая (был бы признателен читателю за подсказку по этому вопросу, ибо считаю что сам я вопрос изучил не полностью, а пока продолжу повествование).

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

Когда мой покойный ныне «шеф» увидел эти решения в 2003 году, он задумался и изрек, что «эти крокодилы надо причесать», чем заставил меня погрузится в дальнейшие раздумья. И я снова вооружился листком бумаги и карандашом…

Чтобы получить достаточно компактное решение, надо преобразовать систему (1) — (3) к линейной относительно неизвестных. Для этого надо воспользоваться школьными знаниями по тригонометрии.

Итак, возведем уравнения (1) и (2) в квадрат и сложим, перенеся всё, что не зависит от x и y в правую часть уравнения

используя формулу «косинус суммы», получим новое уравнение

Теперь, разрешая его относительно суммы неизвестных приходим к линейному уравнению

Линейное уравнение оно и в Африке линейное — найдя одну неизвестную, получим и другую. Займемся другой неизвестной, исключив x из одного их уравнений. Так как у нас есть условие (3), то очевидно, что

а это дает нам возможность воспользоваться основным тригонометрическим тождеством без неоднозначности «плюс-минус»

Косинус икса берем из первого уравнения

получая, таким образом для синуса икс

Чтобы не пыхтеть над бумагой, поручим всё это Maple

имея на выходе уравнение

Уравнение (7) надо возвести в квадрат и провести некоторые преобразования

придя к уравнению вида

А теперь выполним, известный многим, «финт ушами»

то есть, делим обе части уравнения на и сворачиваем левую часть по формуле косинуса суммы, справедливо полагая что

Получаем новое уравнение,

которое успешно решаем относительно y

Как видим, игрек вышел довольно компактным. Возвращаемся к уравнению (5) и находим икс

А теперь сравнив полученное с вышеприведенными «крокодилами», сделаем

Системы компьютерной алгебры — незаменимый помощник современного ученого, упрощающий ему жизнь и избавляющий от необходимости зарываться в «простыни» решений на бумаге, избавляющий от досадных ошибок/описок, освобождающий мозг для продуктивной деятельности. Но, их успешное применение неотделимо от общей математической культуры и знания элементарных вещей. Иначе, решение лежащее на почти поверхности имеет шанс не увидеть свет никогда.

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

Числа

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

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

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

Выражения

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

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

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

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

Упрощение

Грубое применение основных правил дифференцирования по x в выражении дает результат а Икс >

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

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

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

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

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

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

Равенство

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

( Икс + y ) 2 знак равно Икс 2 + 2 Икс y + y 2 . = x ^ + 2xy + y ^ .>

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

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

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

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

История

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

Настоящее пособие составлено на основе спецкурсов, читавшихся автором на механико-математическом факультете в течение более 10 лет. Выбор материала в значительной мере определялся пристрастиями автора. Наряду с классическими результатами компьютерной алгебры в этих спецкурсах (и в настоящем пособии) нашли отражение исследования нашего коллектива. Прежде всего, это относится к теории дифференциальной размерности. Теорией дифференциальной размерности мы начали заниматься по инициативе, под руководством и при активном участии А.В. Михалева в конце 70-х—начале 80-х годов прошлого века [ 13 ] . Наряду с теоретическими исследованиями, нами был разработан комплекс программ на алгоритмическом языке REFAL для вычислений в дифференциальных и разностных модулях [ 11 ] . Результаты многолетних исследований, связанных с конструктивными методами в кольцах дифференциальных и разностных многочленов и теорией дифференциально-разностной размерности, опубликованы в монографии [ 20 ] . Частично эти результаты отражены в настоящем курсе. Пользуюсь случаем выразить глубокую признательность Алексадру Васильевичу Михалеву, в значительной мере благодаря которому появился этот курс. Я также очень благодарен Марине Владимировне Кондратьевой, Александру Борисовичу Левину, Андрею Витальевичу Астрелину, Олегу Дмитриевичу Голубицкому, Алексею Игоревичу Зобнину и другим коллегам, работавшим вместе с нами в области компьютерной алгебры . Исследования выполнялись в лаборатории вычислительных методов и на кафедре высшей алгебры механико-математического факультета МГУ, и я признателен коллективу лаборатории и кафедры за очень доброжелательное отношение к нашей группе.

Преподавание компьютерной алгебры я начинал с двух полугодовых спецкурсов, по материалам которых были опубликованы учебные пособия [ 15 ] и [ 14 ] . В дальнейшем конспекты курса компьютерной алгебры были выложены на сайт и активно использовались студентами и аспирантами при подготовке к экзамену по компьютерной алгебре . Размещение конспектов на сайте позволило оперативно исправлять опечатки, замеченные студентами в процессе подготовки к экзамену, и вносить изменения в изложение материала. Всем внимательным читателям данного курса я выражаю глубокую благодарность.

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

Введение

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

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

В чем основные отличия символьных вычислений от численных и почему возник термин " компьютерная алгебра " ?

Когда мы говорим о вычислительных методах, то считаем, что все вычисления выполняются в поле вещественных или комплексных чисел. В действительности же всякая программа для ЭВМ имеет дело только с конечным набором рациональных чисел, поскольку только такие числа представляются в компьютере. Для записи целого числа отводится обычно 16 или 32 двоичных символа (бита), для вещественного—32 или 64 бита. Это множество не замкнуто относительно арифметических операций, что может выражаться в различных переполнениях, например, при умножении достаточно больших чисел или при делении на маленькое число. Еще более существенной особенностью вычислительной математики является то, что арифметические операции над этими числами, выполняемые компьютером, отличаются от арифметических операций в поле рациональных чисел,—более того, для компьютерных операций не выполняются основные аксиомы поля (ассоциативности, дистрибутивности). Эти особенности компьютерных вычислений оцениваются в терминах погрешности или точности вычислений. Оценка погрешности представляет одну из основных проблем вычислительной математики. Каждую задачу требуется решить с использованием имеющихся ресурсов ЭВМ, за обозримое время, с заданной точностью.

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

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

В научных исследованиях и технических расчетах специалистам приходится гораздо больше заниматься преобразованиями формул , чем собственно численным счетом. Тем не менее, с появлением ЭВМ основное внимание уделялось автоматизации численных вычислений, хотя ЭВМ начали применяться для решения таких задач символьных преобразований, как, например, символьное дифференцирование , еще в 50-х годах прошлого века. Активная разработка систем компьютерной алгебры началась в конце 60-х годов. С тех пор создано значительное количество различных систем, получивших различную степень распространения; некоторые системы продолжают развиваться, другие отмирают, и постоянно появляются новые.

Системы компьютерной алгебры. Системы компьютерной алгебры можно условно разделить на системы общего назначения и специализированные. К системам общего назначения относятся MACSYMA, REDUCE , MATEMATICA, MAPLE , AXIOM и другие системы. В 80-е годы прошлого века широкое распространение в СССР получила система REDUCE . Она первоначально предназначалась для решения физических задач, разрабатывалась на наиболее широко распространенных компьютерах, разработка до определенного времени не носила коммерческого характера (система до конца 80-х годов распространялась бесплатно), открытый характер системы позволил привлечь к ее разработке огромную армию пользователей, обогативших систему многочисленными пакетами для решения отдельных задач. MACSYMA, так же, как и REDUCE , является "старой" системой. В отличие от системы REDUCE , MACSYMA разрабатывалась с самого начала как коммерческий продукт. В ней более тщательно проработаны алгоритмические вопросы, ее эффективность существенно выше, но меньшее ее распространение можно объяснить двумя обстоятельствами: длительное время она была реализована только на малом числе "экзотических" компьютеров и распространялась только на коммерческой основе. Система MAPLE , созданная в 80-х годах прошлого века в Канаде, с самого начала была задумана как система для персональных компьютеров, учитывающая их особенности. Она развивается "вширь и вглубь" , даже ее ядро переписывалось с одного алгоритмического языка на другой. В настоящее время MAPLE широко применяется во многих странах (в частности, в США и Канаде) в учебном процессе, а также в различных областях научных и технических исследований. В конце прошлого века получила широкое распространение и сейчас быстро развивается система MATEMATICA. Ее успех в значительной степени объясняется ее широкими графическими возможностями, а также электронной документацией, которую можно рассматривать как электронную библиотеку, посвященную различным разделам математики и информатики. Особое место среди систем компьютерной алгебры занимает система AXIOM . В отличие от остальных систем, представляющих собой пакеты программ, общение с которыми осуществляется на некотором алголоподобном языке, система AXIOM , развившаяся из системы SCRATCHPAD -II, имеет дело с более привычными для математиков объектами. В частности, в ней ключевым понятием является понятие категории: здесь можно рассматривать, например, категории множеств, полугрупп , дифференциальных колец, левых модулей и т. д. Система имеет высокую степень универсальности, требует для своей реализации мощных компьютеров, распространяется за достаточно высокую плату, поэтому используется только в ограниченном числе мощных университетских и научных центров.

Специализированные системы отличаются более высокой эффективностью, но область их применения ограничена. К специализированным системам относятся такие системы, как CALEY и GAP — специализированные системы для вычислений в теории групп, MACAULEY, CoCoA, Singular — системы разной степени универсальности для вычислений в кольце многочленов, SCHOONSHIP — специализированная система для вычислений в физике высоких энергий, muMATH и ее правонаследница DERIVE — системы, широко используемые в учебном процессе (в частности, в Австрии лицензия на установку системы DERIVE приобретена для всех средних школ), и многие другие.

Читайте также: