Введение в системы компьютерной алгебры

Литература

1.Матрос.Д.Ш.,Поднебесова.Г.Б. «Элементы абстрактной и компьютерной алгебры».-М.,:Академия,2004;

Глава 2

Введение в системы компьютерной алгебры

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

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

В качестве демонстрации возможностей систем компьютерной алгебры выбран один из самых распространенных пакетов Mathematica 4.2. В подразделе 2.3. приведены многочисленные примеры важнейших преобразований в рамках этого пакета.

В подразделе 2.4 дан обзор основных результатов по представлению различных типов данных в компьютере.

1. АНАЛИТИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ С ПОМОЩЬЮ КОМПЬЮТЕРА

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

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

Отметим, что численные расчеты не исключают алгебраиче­ских вычислений, так как написание программ сводится к пере­писыванию формул, на которых основан алгоритм. Вот этот про­цесс переписывания и вывода формул можно выполнить на ком­пьютере. Увеличение мощности компьютеров само по себе также не решает всех проблем: расчет развития атмосферных процессов с точностью, необходимой для 48-часового прогноза, на наиболее мощных компьютерах требует значительно больше 48 часов. Уве­личение производительности в 10 раз мало поможет, поскольку одновременно с уточнением теории потребуется в 2 раза умень­шить шаг сетки, что потребует 8-кратного увеличения объема вы­числений.

Приведем два примера из истории великих вычислений XIX века. Во-первых, это расчет Леверье орбиты Нептуна, который был основан на возмущениях орбиты Урана и привел к открытию Не­птуна. Во-вторых, это вывод 40 000 аналитических формул, кото­рые были выполнены Делоне для вычисления орбиты Луны и ко­торые потребовали 10 лет для их проверки. Результат не являлся численным, а представлял собой формулу, занимающую 128 стра­ниц его книги. Отметим, что в 70-х годах XX века этот результат был проверен на компьютерах с ошеломляющим итогом: всего лишь одна (!!) ошибка (подготовка программы заняла около года).

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

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

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

Анализируя различные системы, можно выделить следующие особенности аналитических вычислений на компьютерах [6, 8, 12, 25]:

1)имеется возможность проводить аналитические (и числен­ные) преобразования без погрешностей;

2)в результате не теряется исходная информация о характере исследуемого процесса;

3)на этом этапе аналитических вычислений неустойчивость процесса не проявляется;

4)в ряде случаев наблюдается быстрое разрастание результатов промежуточных вычислений (т.е. объем промежуточных данных в процессе вычислений очень большой);

5)ввиду упомянутого разрастания результатов резко повыша­ются требования к объему памяти и к быстродействию компью­тера;

6)резко повышаются требования к предварительному изуче­нию алгоритма: к оценке его быстродействия, необходимой памя­ти и к эффективному представлению результата;

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

Само понятие «компьютерная алгебра» появилось именно в связи с разработкой и применением систем аналитических вычислений. Основная цель компьютерной алгебры — изучение алгоритмов ана­литических преобразований с точки зрения их эффективной реали­зации на компьютере. В связи с разрастанием промежуточных ре­зультатов главная задача компьютерной алгебры — оценка слож­ности аналитических выражений и длительности аналитических пре­образований.

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

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

Уже имеется целое поколение таких систем — от языка про­граммирования символьных вычислений Reduce до современных интегрированных систем компьютерной алгебры: MathCAD for Windows, Derive, Maple V, Mathematica и др.

Мы выбрали для демонстрации возможностей систем компью­терной алгебры систему Mathematica 4.2. Она создана фирмой Wolfram Research Inc., возглавляемой ее президентом и основным разработчиком программ Стивеном Вольфрамом (Stephen Wolfram). Количество легальных пользователей этой системой к настоящему времени уже превысило 1 млн. чел. Mathematica используется более чем в 50 ведущих университетах мира, в отделениях Госдепарта­мента США, во многих научных центрах и в других организациях и учреждениях. Помимо научных работников и инженеров она полу­чила признание и у специалистов художественного и гуманитар­ного профиля.

2. ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ

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

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

Пример. Если N входных переменных обрабатываются за время cN², где с — некоторая константа, то асимптотическая сложность этого алгоритма есть 0(N²) (порядка N²).

Алгоритм	Временная сложность	Максимальный размер задачи
		1 с	1 мин	1 ч
А,	N		6 - 104	3,6- 106
А,	Nlog2N			20- 105
А3	N2
А,	yv3
А3
Таблица 2.2
Алгоритм	Временная сложность	Максимальный размер задачи
		до ускорения	после ускорения
А,	N	S,	10.У,
А2	N\og2N	s2	105*2 (ПРИ большихS2)
А3	TV2	s,	3,165,
А«	Л"	s<	2,155,
Aj	2N	S5	s5 + 3,3

В табл. 2.1 [25] даны характеристики пяти алгоритмов различной сложности для решения одной и той же задачи. Под временной сложностью понимается число единиц времени (мс) для обработ­ки входа размером N.

Предположим, что быстродействие компьютера возросло в 10 раз. В табл. 2.2 показано, как при этом возрастут размеры (S1...1S5) за­дач. Видно, что увеличение быстродействия приводит к расшире­нию входа только для алгоритмов с малой временной сложностью. Например, для алгоритма А₅ увеличение размера входа вообще не произошло.

Предположим, что вместо увеличения быстродействия исполь­зуется более эффективный алгоритм. Тогда при времени решения 1 мин из табл. 2.1 следует, что замена А4 на А₃ дает шестикратное увеличение размера задачи, а при замене А4 на А₂ — 125-кратное. Комментарии излишни!

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

В зависимости от порядка сложности и вида результирующих данных алгоритмы компьютерной математики можно отнести к четырем уровням [25]:

1)базовые алгоритмические операции. Считается, что их слож­ность 0(1), хотя они отличаются по сложности от битовых опера­ций. Например, умножение двух n-разрядных чисел с фиксиро­ванной точкой требует О (n²) битовых операций, а сложение — О(п);

2) скалярные алгоритмы с вычислительной сложностью О(п). Этот уровень включает вычисление скалярного произведения «n-мерных векторов, вычисление значения полинома по схеме Горнера, численное интегрирование и дифференцирование;

3) векторные алгоритмы сложности О (). Сюда включаются умножение матрицы на вектор для вычисления линейных преобразований, вычисления свертки векторов (полиномов) и т.д.;

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

Некоторые и I этих алгоритмов удается улучшить (например, на третьем уровне до оценки O(n )).

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

Выберем объем задачи и в качестве параметра п разобьем зада­чу на две подзадачи объемом п/2 каждая той же самой структуры, что и исходная задача. Если решения этих подзадач можно скомби­нировать в. решение исходной задачи, то получается эффективный алгоритм. Иными словами, эффективный алгоритм основан на делении задачи пополам и дублировании.

Далее в книге рассматриваются конкретные быстрые алгорит­мы цифровой обработки информации, основанные на вышеизло­женном принципе.

3. КОМПЬЮТЕРНАЯ АЛГЕБРА НА ПРИМЕРАХ

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

3.1. Простые операции с числами

Выражения, которые вычисляются и преобразуются системой Mathematica, записываются с помощью операторов и функций. Для выполнения арифметических операций используются операторы: + (сложение), — (вычитание), * (умножение), / (деление), ^{^} (воз­ведение в степень). Можно производить вычисления непосредствен­но с числами или используя оператор присваивания (:=). В наших примерах жирным шрифтом выделено то, что вводится пользова­телем, и обычным шрифтом — ответ системы.

56*34/8

а:=53

b:=34

с:=25

(а+b^2+с^{^}3)/(3*а-4*с)

В системе возможны целочисленные вычисления. Ниже приве­ден пример вычисления факториала.

Factorial[7]

100!

9332621544394415268169923885626670049071596826438162146859 9296389521759999322991560894146397615651828625369792082722375 8251185210916864000000000000000000000000

Для представления выражения в виде вещественного числа ис­пользуется функция N (записывается в виде N[expr], где ехрг —-выражение).

N[100!]

9.33262х10¹⁵⁷

Арифметика произвольной точности — N[expr, число цифр результата].

N[Pi,18]

3.14159265358979324

Вычисление сумм и произведений:

(1 +х)² (2 + х)²(3 + х)²(4 + х)²(5 + х)²

Sum[i^{^}2,{i,1,10}]

Product[k^2,{k,l,5}]

Имеются также функции работы с простыми числами. Можно получить n-е по счету простое число (Prime[n]) или следующее за п простое число (NextPrime [n])

Prime[7]

<<NumberTheory'NumberTheoryFunctions' {в подпакете расшире­ния «Функции теории чисел»}

NextPrime [500]

Комплексные числа задаются в форме:

2 + i3

2 + 3 i

Re[5 + i 4]

Im[5 + 4*i]

3.2. Полиномы и рациональные функции

Над полиномами можно выполнять обычные арифметические операции: сложение, умножение, вычитание и деление. Для полу­чения результата умножения полиномов можно использовать функ­цию Expand, для получения результата деления — функцию Simplify.

x^{^}4+3*х^{^}3-5*х

- 5 х + 3 х³ + х⁴

р1:=3*х^{^}4-4*х^{^}2+2*х

р2:=х^{^}2-5*х

pl-p2

- 5 х + х² + 2 х⁴ — 4 х⁵ + 3 х⁶

Expand[(x-y)^{^}3]

х³ — 3 х² у + 3 х у² — у³

Expand[(x^{^}1000+1)*(х^{^}1000-1)]

- 1 + х²⁰⁰⁰

Simplify[х^{^}2-2*х*у+у^{^}2]

(х - у)²

Simplify[(х^{^}4+3*х^{^}З-2*х^{^}2-6*х)/(х^{^}2+3*х)]

- 2 + х²

3.3. Действия с матрицами

MatrixForm[m] — представление строкового задания матрицы в матричном виде;

Det[m] — вычисление определителя матрицы m;

Transpose[m] — транспонирование матрицы m.

m:={{1,2},{3,7}}

MatrixForm[m]

Det[m]

Transpose [т]

{{1, 3}, {2, 7}}

3.4. Вычисление производных

D|f, х] — возвращает частную производную функции f по пере­менной х. Возможно вычисление частных производных n-го по­рядка по х, смешанных и обобщенных производных.

Derivative[nl, n2,...] [f] — основная (общая) форма представ­ления функции, полученной в результате nl-кратного дифферен­цирования функции f по первому аргументу, n2-кратного диффе­ренцирования функции f по второму аргументу и т.д.

D[a*Cos[x],x]

-a Sin[x]

D[b*x^{^}3+b*x,x]

b + 3 b х²

D[Log[x]*x^2,x]

x + 2 x Log[x]

D[x^{^}2/b*x,x]

Derivative[2] [x*y]

(xy)"

3.5. Интегрирование

Вычисление неопределенных интегралов в символьном виде: Integrate[f, х] — возвращает неопределенный интеграл (перво­образную) подынтегральной функции f по переменной х. Можно использовать знак интеграла.

Integrate[a*x^b, х]

- Cos[x]

3.6. Уравнения и системы уравнений

Solve[eqns, vars] — решает уравнение или систему уравнений eqns (equations — уравнения) относительно переменных vars.

SoIve[x^{^}2+2*x- 15==0,х] *

{{х->5}, {х->3}}

Solve[x^2+2*x+15= =0,x]

{{x->-l-i }, {x->-l+i }}

Возможно решение систем нелинейных уравнений в символь­ном виде:

Solve[{y==x^A2, x==a+b}, {х,у}]

{{y->a²+2ab+b², x->a+d}}

3.7.Дифференциальные уравнения

DSolve[eqn, у[х], х] — решает дифференциальное уравнение eqn относительно функций у[х] с независимой переменной х.

.

DSolve[Derivative[l] [у] [х]==2*а*х^{^}3, у[х], х]

{{у[х]->ах⁴/2+С[1]}}

DSolve[y'[x]+y[x]==x, у[х], х]

{{у[х]->-1+х+ С[1]}}

3.8. Функции времени и даты

AbsoluteTime[] — возвращает полное количество секунд, про­шедших с 1 января 1900 года;

Date[] — возвращает текущее время;

TimeUsed[] — возвращает полное количество секунд процес­сорного времени, используемого на данный момент в текущем сеансе Mathematica.

AbsoluteTime[]

3.25378948000000х10⁹

Date[]

{2003, 2, 9, 14, 31, 16}

TimeUsed[]

0.9

4. ПРЕДСТАВЛЕНИЕ ДАННЫХ

В этом подразделе дан обзор имеющихся результатов [6, 8, 12]. Здесь изложены основные трудности, связанные с представлени­ем данных в компьютере. Также кратко рассмотрена фундамен­тальная проблема наиболее эффективного представления данных в максимально универсальной постановке, т.е. без технических деталей. Многие из рассматриваемых результатов носят характер рецептов, объяснение или доказательство которых в некоторых случаях являются результатами обширных теорий и поэтому выхо­дят за рамки настоящей работы.

4.1. Представление целых чисел

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

Обычно в системах рассматриваются точные аналитические преобразования и никакие округления или другие искажения це­лых чисел недопустимы. Для иллюстрации приведем известный пример (Д. Кнут, В. Браун) вычисления НОД двух полиномов:

а = х⁸ + х⁶ - Зх⁴ - Зх³ + 8х² + 2х -5;

b= 3x⁶+5x⁴-4x²-9x + 21.

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

Так же необходимо рассматривать целые числа произвольной длины. Почти все системы компьютерной алгебры допускают та­кую возможность и для представления выбирают в качестве осно­вания некоторое число N и представляют числа, по аналогии с обычной десятичной системой, относительно этого основания (с помощью «цифр» от 0 до N- 1) с добавлением знакового бита. Например, на 32-битовых компьютерах можно выбрать в качестве N 10⁹, или 2³⁰, или 2³¹. Как правило, 2³² не используется, чтобы не возникали трудности при сложении, когда сумма уже не умещает­ся в машинное слово.

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

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

Теперь разберемся со временем счета. Достаточно очевидно, что для сложения и вычитания требуется время, пропорциональное числу цифр, т.е. 0(п), а для умножения это время — 0(п²). В 1962 г. студент МГУ (ныне профессор) А. А. Карацуба предложил следующий ме­тод умножения, более эффективный, чем общепринятый [11].

Если у нас имеется два 2n-значных числа u= и v= , то их обычное умножение сводится к четырем ум­ножениям n-значных чисел. Метод Карацубы состоит в следующем.

Запишем наши числа в виде:

U= U₀+ ; V= V₀+ ,

где U₁ = (U_2n-1... ) _l0,

Отсюда легко получить, что

UV=(U₀+ )(V₀ + = U₀V₀( + l) + ( - U₀)(V₀ - ) + ( + ).

4fi

Эта формула сводит задачу умножения 2n-значных чисел к пе­ременным операциям умножения n-значных чисел: V₀, ( - )x (U₀- ) и , плюс некоторые операции сдвига (умножение на степень десяти) и сложения. При этом время, затрачиваемое на умножение, можно сократить с величины O(п²) до величины 0(n ), и, конечно, при большом п алгоритм Карацубы гораз­до быстрее общепринятого.

Используя быстрое дискретное преобразование Фурье, можно довести это время до 0(n log n log log n). Но фактически это время имеет вид 20(п log п log log n) и эффект возникает только для п порядка нескольких тысяч. В большинстве систем этот алгоритм не используется.

Для вычисления НОД двух целых чисел требуется время 0(n³); достаточно просто оно снижается до 0(п²) и даже до 0(nlog² nlog log п), но алгоритм, который имеет последнюю оцен­ку, практически не используется.

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

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

4.2. Представление дробей

Обыкновенные дроби представляются в виде пары целых чи­сел: числителя и знаменателя (p/q, q 0). Вообще говоря, не надо заменять их приближенными значениями (например, числом с плавающей точкой), так как это может привести к неверным ре­зультатам. Так, если НОД полиномов х³ - 8 и (1/3)х² - (4/3) равен (1/3)х - (2/3), то НОД полиномов х³ - 8 и 0,333333х² - 1,33333 равен 0,000001 из-за округления.

Все операции с рациональными числами требуют вычисления НОД, что приводит к большим затратам времени. Если удается каким-то образом избежать таких действий, то это дает серьезную экономию времени. В нашем примере можно ограничиться вычис­лением НОД полиномов х³ - 8 и х² - 4, которое не требует приме­нения обыкновенных дробей.

Алгоритмы сложения, умножения и других операций дробей достаточно просты, но и тут можно оптимизировать процесс вы­числения. Рассмотрим, например, умножение дробей а/b и с/d, представленных в несократимом виде:

Очевидный способ: вычислить р = ас, q = db и затем сократить на НОД этих чисел.

Однако, используя равенство НОД (p,q) = НОД(a,d)-НОД(b,с), более эффективно вычислить два НОД в правой части равенства, чем один НОД в левой, так как аргументы у них меньше. Отсюда получаем такую последовательность действий для вычисления про­изведения:

НОД (а,d); НОД(b,с); а' = а / HOД(a,d); b' = b/ НОД (b,c); c’=c/НОД(b,c); d' = d/НОД (a,d); p = а'с'; q = b'd'. Аналогично для сложения

вместо формул p = ad + bc, q = bd с последующим вычислением HOД(p,q) и сокращением на него чисел р и q более эффективна такая последовательность вычислений:

НОД (b,d); q’ = bd/НОД (b,d)\ b' = b/НОД (b,d);

d' = d/HOД(b,d); p' = ad' + b'c;

HOД(p',q'); p = p'/HOД(p',q'); q = q'/НОД(p',q').

Легко видеть, что и в этом случае мы работаем со значениями меньшими, чем при прямых вычислениях.

4.3. Представление полиномов

Именно работа с полиномами, понимаемыми в обобщенном смысле, отличает системы компьютерной алгебры от других систем.

Отметим важный момент — термин «полиномиальные» отно­сится к программным вычислениям, а не просто к типам данным. Например, вычисление

(х~у)(х + у) = х²-у²

является полиномиальным, но им является также и

(cos a-sin b)(cos a + sin b) = cos²a-sin²b,

в котором фактически произведено то же вычисление, но с заме­ной х на cos а, у — на sin b.

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

Отметим в связи с этим, что запись (х + 1)(х- 1) не слишком интересна; запись х² - 1 гораздо более полезна, хотя это, может, и

не имеет принципиального значения. Однако (х - 1) более «про­стая» запись, чем , но является ли выражение х⁹⁹⁹ - х⁹⁹⁸ + х⁹⁹⁷-... - 1 более «простым», чем далеко не очевидно (!).

Для того чтобы разобраться с понятием «упрощение», сначала уточ­ним два связанных с ним термина.

Представление математических объектов (в рассматриваемом случае это полиномы) называется каноническим, если две различ­ные записи соответствуют всегда двум различным объектам.

Если совокупность объектов обладает структурой моноида (а поч­ти любая совокупность в компьютерной алгебре является по мень­шей мере моноидом), то можно ввести следующее определение.

Представление называется нормальным, если представление нуля моноида единственно.

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

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

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

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

Представление называется разреженным, если нулевые члены явно в нем не представлены.

Представление называется плотным, если в нем явно представ­лены все члены.

Обычное математическое представление является разреженным: мы пишем 8х³ + 7 вместо 8x³ + 0х + 7.

Наиболее очевидным компьютерным представлением полинома

+ +... + +

является его представление таблицей коэффициентов [ ]. Так как в нем записаны все , то такое представление является плотным. В этом случае для сложения необходимо О(п) операций, а для умножения — 0(п²).

Разреженное представление требует, чтобы каждый ненулевой член был представлен в виде пары: показатель степени и коэф­фициент, т.е. пара (i, ). Например, полином 8х³ + 7 предстает в виде ((3,8), (0,7)). В этом представлении порядок задается убыва­нием показателей степеней.

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

(x¹⁰⁰⁰ + 1)(х¹⁰⁰⁰ - 1) = x²⁰⁰⁰ - 1,

а разреженный — всего четыре. Если имеется, например, полином от пяти переменных x⁵ z³u²v, то его плотное представление со­держит 7776 членов, а разреженное — один.

Отметим, что время счета, по крайней мере, для сложения и умножения, является скорее функцией количества членов, чем степени. Хорошо известны соотношения, ограничивающие степень результата, рассматриваемую как функцию от степеней аргументов, но соотношение для количе­ства членов отличается от них. Предположим, что a, b — два поли­нома степеней п_а, , содержащие т_а, членов. Тогда примитив­ные операции над ними удовлетворяют ограничениям, представ­ленным в табл. 2.3.

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

Например, = +... + 1, т.е. полиномы всего из двух слагаемых каждый при делении могут дать полином с каким угод­но большим количеством членов.

Таблица 2.3

Операции	Степень результата	Количество членов в результате
а + b	тах(па, )	та+
а-b	тах(па, )	та +
а * b	па+
a/b '	па -	na + 1
НОД(а,b)	min(, )	min(na, ) + 1
Подстановка полинома а вместо переменной в полином b		na + 1

Рассмотрим вопрос о количестве членов в НОД двух полино­мов. Показано, что для полинома р = (4х⁴ + 4х³ -2х² + 2х+ 1)(84х²⁴ + 28х²⁰ - 10х¹⁶ + 4х¹² - 2х⁸ + 2х⁴ + 1)

полином р² имеет слагаемых меньше, чем р, а НОД(p²,(p²)’) содержит больше слагаемых, чем каждый из этих полиномов.

В заключение остановимся на проблеме подстановки полинома вме­сто переменной в другой полином. Время развертывания, например,

выражений (х¹⁰⁰⁰ + 1)² и отличается в тысячи раз.

4.4. Представление рациональных функций

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

так как это то же, что и вычисления

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

Если мы хотим получить каноническое представление, то воз­никают следующие сложности: например, формулы и представляют один и тот же элемент, но это разные формулы, так как у них разные области определения. Обратим вни­мание на то, что эти формулы равны, так как их разность равна .

Естественно потребовать, чтобы в каноническом представле­нии не существовало какого-либо общего делителя числителя и знаменателя. Отсюда следует, что каноническое представление есть

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

Для устранения этой неоднозначности большинство существу­ющих систем принимают во внимание следующие правила для рациональных функций с коэффициентами из Q:

1)в выражении не должно быть рациональных коэффициентов (что отбрасывает последние два выражения);

2)никакое целое число не может делить как числитель, так и знаменатель (что отбрасывает третье выражение);

3)старший коэффициент знаменателя выражения должен быть положительным (что отбрасывает второе выражение).

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

4.5. Представление алгебраических функций

Под алгебраическими объектами (числами и функциями) по­нимают решение полиномиальных уравнений. Например, — алгебраическое число, как решение уравнения - 3 = 0.

Каждый радикал является корнем алгебраического уравнения, но, как показал Абель, обратное не верно. Более точно, алгебраи­ческое число , являющееся решением уравнения + + l = 0, не может быть выражено в радикалах.

Поэтому различают три класса алгебраи ческих выражений:

1) простые радикалы (например, , );

2) вложенные радикалы (например, , );

3) общие алгебраические выражения (например, алгебраиче-
ское число , определенное уравнением + + 1 = 0).

Каждый из перечисленных классов содержится в следующем.

Простые радикалы

Первая проблема — однозначность представления, так как, например,

Ее универсальное решение очень сложное. Действительно, если потребовать, чтобы радикалы были лишь в числителе, то следу­ющий пример показывает, что все не так просто:

-

Другие варианты универсального представления еще более спорны.

Вторая проблема — взаимная зависимость радикалов. Она со­стоит в том, что корни различных степеней могут выражаться один через другой. Рассмотрим . Тогда, так как х⁴ + 4 = (х² - 2х + 2) (х² + 2х + 2), то получаем

Вложенные радикалы

И в этом случае существует проблема однозначности представ­ления, как и в предыдущем.

Вторая проблема — соотношения между радикалами — в насто­ящее время удовлетворительным образом не решена. Ее сложность подчеркнем рядом примеров:

= 1 + ,

+ ,

,

Алгебраические функции общего вида

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

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

4.6. Представление трансцендентных функций

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

1) класс тригонометрических функций;

2) класс экспоненциальных функций;

3) класс логарифмических функций;

4) класс обратных тригонометрических функций. Известно много правил преобразования, таких, как

sin(x + у) = sin х cos у + cos х sin у; (1)

sin x cos y = (sin(x +y) + sin(x-у)); (2)

log(xy) = log x + log y;

log(exp x) = x;

exp(x + y) = exp x * exp y;

sin = 0.

Естественно, что трансцендентные функции могут являться аргументами и коэффициентами рациональных функций, рассмот­ренных выше, а также входить в алгебраические функции. Преоб­разования таких функций ничем не отличаются от рассмотренных выше. Однако остаются некоторые ловушки. Во-первых, видим, что из (1) следует sin2x = 2 sin х cos х, но во многих системах это не действует, так как постоянно отслеживать, что 2х = х + х очень дорого. Во-вторых, правила (1) и (2) взаимно обратны, т.е. совместное их применение приведет к зацикливанию.

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

log(fg) = log f+ log g,

exp(f + g) = exp f exp g, (3)

exp(log f) = log(exp f) = f,

но являются ли они единственно возможными упрощениями?

Имеются теоремы, которые точно описывают возможные упро­щения.

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

Теорема (Риша).

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

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

Эта теорема применима только к функциям. Ситуация с числа­ми, определяемыми экспонентами и логарифмами, гораздо менее ясна. Есть предположение (но не доказательство), что теорема и в этом случае остается верна. Неизвестно даже, являются ли незави­симыми числа е [е = ехр(1)] и [ = (1/i) log(-l)].

4.7. Представление матриц

Матрица имеет вид

А= .

где — некоторые аналитические выражения, i=1,…,n; j=1,…,m.

Это представление можно записать кратко А = .

Если п и т — заданные явно натуральные числа, то и запись матрицы может быть конкретной. Например, если п = 2, т = 3, то возможна запись

A= .

Если же элементы матрицы заданы явно, то ее запись может иметь, например, такой вид:

A= .

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

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

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

Плотные матрицы

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

Сложение и умножение двух матриц размерами n x n требует O(п²) и O(п³) операций соответственно. Имеются более быстрые алгоритмы, но они эффективны лишь для больших п (алгоритм Штрассена, например, для умножения матриц имеет сложность O(п Iog₂ п) и дает 18 %-ный выигрыш лишь при n 100). Поэтому они пока не применяются в системах компьютерной алгебры.

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

При вычислении определителя возникает проблема деления. Согласно определению, определитель матрицы — это сумма (воз­можно, со знаками минус) произведений элементов матрицы. Та­ким образом, если эти элементы принадлежат кольцу (например, кольцу целых чисел или полиномов), то определитель также при­надлежит кольцу. Но метод исключения Гаусса для вычисления этого определителя требует выполнения делений. Эти деления могут оказаться невыполнимы (например, нельзя делить на 5 или на 2 в кольце вычетов по модулю 10, но тем не менее определитель матрицы определен и равен 1). Даже если деление воз-

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

При вычислении определителя метод Крамера приводит к О (п n!) операциям вместо O(n³) в алгоритме Гауссова исключе­ния и поэтому относится к неэффективным методам. Однако учет необходимости постоянно вычислять НОД и приводить подобные члены позволяет заключить, что алгоритм Гаусса в ряде случаев по числу операций приближается к методу Крамера.

Для матриц целых чисел или полиномов от одной переменной наиболее эффективным представляется алгоритм Барейса.

Алгоритм Барейса

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

Фактически простейший вариант излагаемого метода был извес­тен еще Жордану и

основан на обобщениях тождества Сильвестра. Пусть — определитель вида

В частности, определитель матрицы порядка п, элементы которой есть , равен Тогда

Так как определители не содержат дробей, определитель в правой части делится на
Продемонстрируем метод Барейса на примере. Рассмотрим мат-
рицу третьего порядка

После исключения с помощью первой строки (без деления) получаем

Второе исключение дает матрицу

, и очевидно, что делит все элементы третьей строки.

Общее соотношение имеет вид

Из которого приведенное выше равенство получается при l=k-1.

Разреженные матрицы

Методы запоминания разреженных матриц с символьными эле­ментами аналогичны методам запоминания различных полиномов; в частности, можно использовать списки вида {()},где — значение элемента (аналитическое выражение); i,j — номер стро­ки и номер столбца, указывающие положение этого элемента в матрице.

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

Для вычисления определителя применяется рекурсия, получа­емая разложением определителя по строке или столбцу. При боль­шем числе нулевых элементов это дает достаточно компактные выражения.

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

Имеется три основных способа решения систем линейных ал­гебраических уравнений, применяемых в системах компьютерной алгебры:

1) формулы Крамера. В этом случае основные вычисления — определитель матрицы A хорошо реализуется с использованием предыдущих вычислений. Основной недостаток этого способа — требуется много места для хранения промежуточных результатов;

2) метод Гауссова исключения с переупорядочиванием строк и/или столбцов. В этом случае порядок вычислений 0(п³);

3) итерационные методы, обычно используемые для числовых матриц. Схема их применения в случае, когда элементы матри­цы — аналитические выражения, та же: уравнение Ах = b приво­дят к виду х = Вх + b и применяют итерационный процесс = = В + b, п = 0, 1,..начиная с некоторого аналитического выра­жения х₀. Общий критерий сходимости, как обычно, состоит в том, что ||B|| < q< 1, где q — некоторое положительное число, а в качестве нормы допускается любая операторная норма в рассмат­риваемом конечном пространстве.

Необходимо отметить, что при работе с разреженными матри­цами компьютерная алгебра приближается к методам численного анализа.

4.8. Представление рядов

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

Ряды Тейлора Эти ряды полезны для разных приложений, особенно когда речь идет о нелинейных задачах, которые становятся линейными при пренебрежении некоторыми величинами. В этом случае можно на­деяться, что решение будет представляться в виде ряда Тейлора, причем можно ограничиться достаточно небольшим числом чле­нов, т. е. фактически приходится работать с многочленами. Отли­чие состоит в том, что необходимо предусмотреть алгоритмы «от­брасывания высших степеней».

Например, в сумме

члены результата при i> min(m,n) нельзя определить чисто как функцию указанных в суммах данных. Для получения этих резуль­татов нужно знать больше членов или Отметим, что если на­чальные данные имеют одну и ту же точность, то результат имеет ту же самую точность. В компьютерной алгебре не происходит накопления ошибок в отличии от численного анализа.

Тем не менее в некоторых случаях потеря сложности вполне возможна (это легко увидеть на примере деления, одного ряда на другой или при извлечении корня квадратного из ряда). Для того чтобы избежать этого, необходимо принимать определенные меры предосторожности, хотя сама ситуация здесь гораздо менее слож­ная, чем в численном анализе: нет постепенной потери точности, порожденной округлением.

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

Для операций +, -, *, / эти общие правила выглядят так (здесь С = B= ; ):

C=A+B,

C=A-B,

C=A*B, =

C= .

Последнее равенство выполняется только при 0. Если имеет место равенство нулю, то формула становится немного сложнее. Важно то, что любая функция, определенная линейным диффе­ренциальным уравнением, приводит к аналогичным уравнениям для коэффициентов ряда Тейлора. Легко видеть, что при таком подходе вычисления потребуют не более O(i²) операций (в слу­чае деления).

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

Ряды Фурье

Ряды Фурье имеют вид

f=

Для систем компьютерной алгебры, основанных на полиноми­альных