1. Представление математических объектов в системах компьютерной алгебры

Арифметические вычисления, вычисления с дробями в общем виде.

Представление и работа с алгебраическими объектами.

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

В сист. рассматриваются точные аналит. преобраз-я и никакие округления или др. искажения целых чисел недопустимы. Необходимо рассматривать целые числа произвольной длины. Для представления выбирают в качестве основания некоторое число N и представляют числа, по аналогии с обычной десятичной сист.,отн-но этого основания (с помощью цифр от 0 до N-1) с добавлением знакового бита. Н-р, на 32-битовых компьютерах можно выбрать в качестве N 109, или 230, или 231.

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

Обыкновенные дроби представляются в виде пары целых чисел: числителя и знаменателя (p/q,q≠0). Не нужно их заменять приближенными значениями с плавающей точкой. Н-р: умножение дробей a/b и c/d, представленных в несократимом виде: . НОД (a,d); НОД (b,c); a’=a/НОД(a,d); b’=b/НОД(b,c); c’=c/НОД(b,c); d’=d/НОД(a,d); p=a’c’; q=b’d’.

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

Все сист. могут работать с полиномами произв. числа переменных. Их можно +,-,*,/, операция упрощения. Представление матем. объектов (полиномов) наз-ся каноническим, если две различные записи соответствуют всегда двум различным объектам. Представление наз-ся нормальным, если представление нуля моноида единственно. Представление наз-ся разреженным, если нулевые члены явно в нем не представлены. (мы пишем 8x3+7 вместо 8x3+0x+7) Представление наз-ся плотным, если в нем явно представлены все члены. Наиболее очевидным компьютерным представлением полинома anxn+an-1xn-1+…+a1x+a0 явл-ся его представление таблицей коэффициентов [an,an-1,…,a0].-плотное представление.

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

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

Представление алгебраич. ф-ций.

Под алгебраич. объектами (числами и ф-циями) понимают реш-е полиномиальных ур-ий. Н-р, - алгебраич. число, как реш-е ур-я x2-3=0. Различают три класса алгебраич. выраж-й: 1.- простые радикалы (н-р,,). Две проблемы – однозначность представления (н-р,, ее универсальное реш-е очень сложно) и взаимная зависимость радикалов – корни различных степеней могут выражаться один через др. (рассмотрим, тогда, т.к. x4+4=(x2-2x+2)*(x2+2x+2), то получаем); 2.- вложенные радикалы (н-р,,). Две проблемы однозначности и соотношение между радикалами (н-р,); 3.- общие алгебраич. выраж-я (н-р, алгебраич. число γ, определенное ур-ем γ5+γ+1=0). Требуется, чтобы полиномы, определяющие алгебраич. числа и ф-ции, были неприводимыми (неразложимыми).

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

Трансценд. ф-ции группируются в неск-ко классов ф-ций, каждый из кот. имеет свои правила преобраз-я и упрощения. Классы: 1.- кл. тригонометрич. ф-ций; 2.- кл. экспоненц. ф-ций; 3.- кл. логарифм. ф-ций; 4.- кл. обратных тригонометрич. ф-ций. Трансцед. ф-ции могут явл-ся аргументами и коэфф-ми рацион. ф-ций, а также входить в алгебраич. ф-ции.

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

Матрица имеет вид , где aij-некот. аналитич. выраж-я, i=1,…, n; j=1,…,m. Или A=(aij)n,m. Если n и m – заданные явно натур. числа, то и запись матрицы м.б. конкретной. Если в записи матрицы присутствует только правая часть, то такое представление наз-ся явным. Если запись матриц осуществлена в односимвольном виде, т.е. левой частью (А), то такое представление наз-ся неявным. Плотные матрицы. Это матрицы с большим кол-вом ненулевых эл-тов. Представляются в виде прямоугольной табл. или массива. Алгоритм Барейса. Барейс предложил семейство методов исключения без использования дробей, т.е. таких, где все необходимые деления выполняются точно. Разреженные матрицы. Методы запоминания разреженных матриц с символьными эл-тами аналогичны методам запоминания различных полиномов; можно использовать списки вида {(aij,i,j)}, где aij-знач-е эл-та (аналит. выраж-е), i,j-номер строки и столбца, указывающие положение этого эл-та в матрице.

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

Ряды Тейлора. Необходимо предусмотреть алгоритмы «отбрасывания высших степеней». Для операций +,-,*,/ (C=; B=; A=): C=A+B,; C=A-B,; C=A*B,;,.Ряды Фурье. Имеют вид .