§8.Кольцо многочленов от одной переменной

Пусть F-некоторое поле. Выражение вида f(x)=a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀ называется многочленом от одной переменной с коэффициентами a_i∈F.

x∈F-переменная. Или необязательно принадлежит.

Пример. Многочлен с коэффициентами из R.

многочлен с коэффициентами из Q или R.

мн-н с коэффициентами из поля Z/_(p),p≥3.

a_n≠0 a_nxⁿ-старший член

a_n-коэфициент старшего члена

a₀-свободный член

опр. Под степенью многочлена deg f(x) понимают степень его старшего члена.

Обозначим через F[x] множество всех чмноголенов c коэфициентами из поля F.

Многочлены f(x) и g(x) равны если равны коэффициенты этих многочленов при соответствующих степенях х.

Под суммой многочленов f(x) и g(x) ∈F[x] будем понимать многочлен h(x)∈F[x] коэффициенты которого равны суммам коэффициентов многочленов f(x) и g(x) при соответствующих степенях х.

Степень суммы многочленов не превышает наибольшую из степеней слагаемых.

Deg h(x) ≤max{deg f(x), deg g(x)}

Опр. Пусть f(x) и g(x) ∈F[x]

произведением многочленов f(x) и g(x) называется многочлен , где

(F[x],+)-абелева группа

1)группоид.

Так как сложение многочленов сводится к сложению коэффициентов, принадлежащих полю F, а сложение в поле F является бинарной операцией. То многочлен h(x) существует и единственный в F[x].

2) полугруппа. Так как сложение многочленов сводится к сложению коэффициентов F, а сложение в поле F ассоциативно, то ассоциативность имеет место и для сложения многочленов.

3)моноид. Многчлен с нулевыми коэффициентами называется нулевым. Его степень не опеределена.

4)группа

Поле комплексных чисел

z=a+bi-алгебраическая форма записи комплексного числа

Rez=a, Im=b,

|z|=

cos  =a/|z|

sin = b/|z|

z=|z|(cos+sin)-тригонометрическая запись комплексного числа.

Рассмторим 2 комплексных числа

z₁=|z₁|(cos_+sin_),z₂=|z₂|(cos_+sin_)

z₁*z₂=|z₁||z₂|(cos(₁+₂)+sin(₁+₂))

z₁ⁿ=|z₁|ⁿ(cosn_+sinn_)

z₁/z₂=|z₁|/|z₂|(cos(_1-₂)+sin(_1-₂))

Действия с комплексными числами в алгебраической форме

5.(F[x],+)-абелева группа

∀f(x),g(x) ∈F[x], f(x)+g(x)=g(x)+f(x) так как сложение элементов поля F коммутативно, а сложение многочленов сводится к сложению коэффициентов из поля F, то сложение многочленов коммутативно в F[x].

дистрибутивность слева и справа имеет место в F[x] т. к. она сводится к дистрибутивности слева и справа умножения относительно сложения элементов поля F.

(F[x],+)-кольцо

(F[x],+,*)-ассоциативное кольцо

ассоциативность умножения многочленов имеет место в F[x] так как она сводится к ассоциативности умножения и сложения коэфициентов многочленов, лежащих в поле F.

Коммутативность умножения многочленов также имеет место в силу коммутатвиности умножения и сложения коэффициентво многочленов

кольцо с 1

кольцо акс 1 называется кольцом многочленов от одной переменной

Теорема Безу и ее следствия

Опр. Пусть f(x) ∈F[x] многочлен с коэфициентами из поля F. a∈F. Тогда f()=a_nⁿ+a_n-1^n-1+...+a₁+a₀ -называется значением многочлена f(x)=a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀ при x=.

Опр.Если f()=0, то  -корень многочлена f(x).

Опр.Пусть f(x),g(x) ∈ F[x], g(x) ≠ 0(ненулевой многочлен). Говорят, что f(x) делится на g(x), если существует h(x) из F[x], такой что f(x)=g(x)*h(x).

Опр.Пусть  -корень многочлена f(x). Говорт, что корень кратности n, если f(x) делится на (x-)ⁿ и не делится(x-)ⁿ⁺¹.

Опр. Пусть f(x),g(x) ∈ F[x], говорят, что f(x) разделен на g(x) евклидово, если ∃g(x),h(x) ∈F[x].

f(x)=g(x)g(x)+h(x), где 0 ≤ deg h(x) < deg g(x) или h(x)=0.

Многочлен g(x)-неполное частное, а h(x) остаток от деления f(x) на g(x).

Опр. Многочлен r(x)=ax+b, где a,b ∈F, называется линейным двучленом.

Теорема Безу.

∀f(x)∈F[x] ∀h(x)=x-a∈F[x] ∃!g(x)∈F[x] ∃!c∈F

f(x)=(x-a)g(x)+c (*)

доказательство:

1) существование g(x)∈F[x] и c∈F докажем методом математической индукции по степени многочлена f(x). если f(x)=0 (нулевой многочлен). То 0=(x-a)*0+0, g(x)=0∈F[x],c=a∈F, в эл.сл.утв.теоремы верно. Пусть deg f(x)=0, тогда f(x)=a₀. a₀=0*(x-a)+a₀, g(x)=0∈F[x],c=a₀∈F, в этом случае утвердение теоремы верно. Пусть deg f(x)=1, тогда f(x)=a₁x+a₀, a₁x+a₀=a₁(x-a)+aa₁+a₀, g(x)a₁∈F[x], c=aa₁+a₀∈F. Предположим, что разложение (*) имеет место для всех f(x), у которых deg f(x) ≤ n. Докажем, что любой многочлен степени n+1 представим в виде (*).

f(x)=a_n+1xⁿ⁺¹+a_nxⁿ+...+a₁x+a₀.

f(x)=a_n+1xⁿ⁺¹+a_nxⁿ+...+a₁x+a₀=x(a_n+1xⁿ+a_nx^n-1+...+a₁)+a₀=((x-a)+a) (g(x)(x-a)+c)+a₀=(x-a)(g(x)(x-a)+c+ag(x))+ac+a₀=

g₁(x)∈F[x],c₁∈F

f(x)=(x-a)g₁(x)+c₁, в этом случае утверждение теремы верно.

Из этого всего следует, что согласно ММИ утверждение теоремы о существовании g(x) и с верно для многочленов f(x) любой степени n.

2) единственность докажем методом от противного.

Пусть ∃g₁(x)∈F[x] ≠ g(x) и ∃с₁∈F, ≠ c

f(x)=(x-)g(x)+c

f(x)=(x-)f(x)+c₁

(x-)g(x)+c=(x-)g₁(x)+c₁

(x-)f(x)-g₁(x))=c₁-c

deg(c₁-c)=0, Что невозможно. ⇒ g(x)∈F[x] c∈F-единстве. Таки что вып рав-во (*).

Следствия из теоремы Безу

значение многочлена f(x) при х= совпадает с остатком от деления f(x) на линейный двучлен x-.

Док-во: по теореме Безу ∃!g(x)∈F[x] ∃!с∈F f(x)=(x-)g(x)+c

f()=(-)g()+c f()=c

следствие 2

является корнем многочлена f(x) тогда и только тогда, когда f(x) вертикальное троеточкие (x-)

доказательство. Необходимость. является корнем многочлена f(x) ⇒ f()=0

По теореме Безу ∃!g(x)∈F[x]

∃!с∈F f(x)=(x-)g(x)+c

f()=()g()+c=c

f(x)=(x-)g(x) ⇒ f(x) вертикальное троеточкие (x-)

достаточность

f(x)=(x-)g(x) ⇒ f(x) вертикальное троеточкие (x-) ⇒ ∃!g(x)∈F[x] f(x)=(x-)g(x)

f()=()g()=0 ⇒ - корень f(x)

Разделить многочлен f(x) на x-a с остатком если f(x)=x⁴-2x³+4x²-6x+8 x-a=x-1

cхема горнера (действительна только для линейного (1 степени) делителя):

выписываем коэффициенты по убыванию степеней

1 -2 4 -6 -8

1(корень x-1) 1 1*1+(-2)=-1 1*(-1)+4=3 1*3+(-6)=-3 1*(-3)+8=5

коэффициент неполн.частного остаток

Ответ f(x)=(x-1)(x³-x²+3x-3)+5.

Найти кратность корня многочлена f(x)=x⁵-5x⁴+7x³-2x²+4x-8. =2 — корень f(x).

делим по схеме горнера

	1	-5	7	-2	4	-8
2	1 (тупо переносим)	2*1 -5=-3	1	0	4	0

	1	-3	1	0	4
2	1	-1	-1	-2	0

	2	-1	-1	-2
2	1	1	1	0

	1	1	1
2	1	3	7 ≠ 0

f(x)=(x-2)³(x²+x+1)

ответ: кратность корня равна 3.

Разложить многочлен f(x)=х4+2х3-3х2-4х+1 по степеням х-а=х+1

делить его полностью :)

	1	2	-3	-4	1
-1	1	1	-4	0	1=A0
-1	1	0	-4	4=A1
-1	1	-1	-3=A2
-1	1	-2=A3
-1	1=A4

f(x)=A₄(x-a)⁴+A₃(x-a)³+A₂(x-a)²+A₁(x-a)+A0 -разложение по степеням x-a.

f(x)=(x+1)⁴-2(x+1)³-3(x+1)²+4(x+1)+1

разложение по степеням х+1

найти НОД (максимальный многочлен, на который делятся оба) и НОК многочленов f(x) и g(x).

f(x)=x⁶+x⁵+x⁴-3x²+2x-6

g(x)=x⁵+3x²-2x+2

оба могут разделиться на многочлен 5 степени. (как минимальная)

делим большей степени на меньшую столбиком, потом наоборот и так полностью.

При получении в остатке нуля. Тогда предыдущий ненулевой остаток и есть НОД f(x) и g(x).

Домашнее задание:

1. выполнить деление с остатком

f(x)=x⁵+3x⁴+2x³-8x+40 на x+3

2. определить кратность корня f(x)=x⁶+4x⁵+4x⁴-4x³-11x²-8x-2, =-1 — корень f(x)

3. разложить f(x)=x⁴-8x³+24x²-50x+90 по степеням x-a=x-2

4. найти НОД и НОК f(x)=x⁴+x²-3x²-4x-1 g(x)=2x³+2x²-2x-2

Элементы компьютерной алгебры

Аналитические преобразования с помощью компьютера

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

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

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

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

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

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

Выделим следующие особенности аналитических вычислений на компе:

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

2. В полученном результате не теряется исходная информация о характере исследуемого процесса

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

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

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

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

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

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

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

Имеется целое поколение таких систем:от языка программирования символьных вычислений Reduce до современных систем компьюетрной алгебры MathCAD, Dirive, Maple, etc.

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

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

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

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

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

Пример: при нахождении НОД многочленов a(x)=x⁸+x⁶-3x⁴-3x³+8x²+2x-5 и b(x)=2x⁶+5x⁴-4x²-9x+21 проводя вычисления по алгоритму Евклида в итоге мы получим целое число, содержащие 35 десятичных цифр, то есть 117 бит. Отсюда следует, что многочлены взаимнопросты. Полученный ответ (да/нет) потребует для хранения 1 бит, исходные данные малы (наибольший из коэффициентов многочленов a(x) и b(x), а промежуточные результаты очень велики)

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

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

Время счета, необходимые для сложения и вычитания, пропорционально числу цифр большего числа О(n-число цифр большего числа), а для умножения О(n²).

Метод карацубы:

Два 2n-значных числа

u=(u_2n-1...u₁u₀)₁₀ v=(V_2n+1...V₁V₀)₁₀

Обычное умножение можно свести к 4 умножениям n значных чисел.

U=U₀+10ⁿU₁

V=V₀+10ⁿV₁

где U₁=(u_2n-1..u_n)₁₀ U₀=(u_n-1..u₀)₁₀

где U₁=(u_2n-1..u_n)₁₀ V₀=(v_n-1..v₀)₁₀

U₀,U₁,V₁,V₀ — n-значные числа

uv=(U₀-10ⁿU₁)(V₀+10ⁿV₁)=U₀V₀(10ⁿ+1)+(U₁-U₀)(V₀-V₁)10ⁿ+U₁V₁(10²ⁿ+10ⁿ)

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

Представление рациональных дробей в СКА

обыкновенные дроби представляются в виде пары целых чисел числителя p и знаменателя q. Рациональные не рекомендуется заменять их приближенными значениям, например числом с плавающей точкой, так как это может привести к неверным результатам. Например НОД.

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

1. m=ac,n=bd, k=НОД(m,n),

2. s=НОД(a,d), r=НОД(b,c), ,p=a'c',q=b'd'.

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

Сложение:

1. , m=ad,n=bd,k-bc, p'=m+k, s=НОД(p',n),

2. , r= НОД(b,d), , ab'=a',cd'=c',a'+c'=p', НОД(p',r)=r',

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

Представление многочленов в СКА

Именно работа с многочленами, понимаемыми в обощенном смысле отличает СКА от других систем. Заметим, что термин-многочленные пробразования относится к програмным вычислениям. Многочленом считается и (cos+sin)(cos-sin)=cos²-sin².

Все СКА могут работать с многочленами проивзольного числа переменных. Их можно складывать, вычитать, умножать и делить (если деление выполняется без остатка), но самой интересной и важной является операци упрощения. Например запись (x+1)(x-1). Запись x²-1 гораздо полезнее, но не всегда.

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

Любая совокупность объектов в компьюетрной алгебре является моноидом.

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

Любое каноническое представление является нормальным. Поэтому упрощение символьных выражений должно давать по крайней мере нормальное представление, а если возможно, то и каноническое. В этом случае для определения совпадения двух объектов моноида составляют их разность и смотрят ее представление. Если это представление нуля, то объекты считают совпадающими, то есть равными. В противном случае различными. Для многочленов от одной переменной представление с математической точки зрения очевидно, так как каждая степень переменной х присутствует не более одного раза и равенство многочленов сводится к равенству коэффициентов, но представление многочленов в СКА не такое простое. Оно называется разреженным, если нулевые члены многочлена в нем не представленным.

Представление плотное, если в нем явно представлены все члены многочлена. Например обычное математическое представление многочлена является. В компьютерном представлении многочлен является таблицей коэффициентов. Так как в нем записаны все коэффициенты a_i, то представление является плотным. Для сложения необходимо O(n) операций, а для умножения O(n²). Разреженное представление требует, что бы каждый ненулевой член многочлена a_ixⁱ был представлен в виде пары, в которую входит показатель степени i и коэффициент a_i. Например многочлен 8x³+7 в компьютерной алгебре имеет вид.

((3,8),(0,7)). В этом представлении порядок задается убыванием показателей степенй.

Большинство встречающихся на практике многочленов не является плотными, поэтому разреженное представление дает существенную экномию компьютерной памяти. Например плотный метод потребует миллион умножений для проверки равенства (x¹⁰⁰⁰+1)(x¹⁰⁰⁰-1)=x²⁰⁰⁰-1, а разреженной всего 4. Если имеется многочлен от 5 переменных f(x,y,z,u,v)=x⁵y⁴z³u²v, то его плотное представление содержит 7776, а разреженное 1.

Заметим, что время счета для сложения и умножения многочленов является функцией, зависящей от количества членов многочлена. Нам известны соотношения, ограничивающие степень результата сложения и умножения многочленов, рассматриваемую как функцию от степеней аргументов. Но соотношения для количества членов отличаются от них. Пусть А и В 2 многочлена, имеющие степени n_a и n_b, содержащие m_a и m_b слагаемых.

Количество членов в результате.

a+b: степень max(n_a,n_b) количество ma+mb

a-b также

a*b na+nb ma*mb

a/b na-nb na-nb+1

НОД min(na,nb) ≤ min(na,nb)+1

подстановка вместо многочлена А вместо переменной в многочлен В

nanb nanb+1

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

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

Рассмотрим вопрос о количестве членов в НОД двух многочленов. Например, для многочлена p(x)=(4x⁴+4x³-2x²+2x+1)(84x²⁴+28x³⁰-10x¹⁶+4x¹²-2x⁸+2x⁴+1) многочлен p²(x) имеет слагаемых меньше, чем р(х), а НОД (p²,(p²)') содержит больше слагаемых, чем p² и (p²)'.

При подстановке многочлена вместо переменной в другой многочлен, существует проблема времени выполнения этой операции. Например время развертывания выражений (х¹⁰⁰⁰+1)² и ((t-1)¹⁰⁰⁰+1)² при подстановке вместо х многочлена t-1 отличается в тысячи раз.

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

Рациональная функция-функция вида f(x)=p(x)/g(x), где p(x),q(x)-многочлены, q(x) ≠ 0.

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

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

1. в выражении не должно быть рациональных коэффициентов (следовательно отбрасываются выражения 4 и 5.

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

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

Таким образом каноническим является выражение 1.

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

Под алгебраическими объектами (числами и функциями) понимают решение алгебраических уравнений вида f(x)=0, где f(x)-многочлен. Например корень из 3 является алгебраическим числом, так как является корнем уравнения. Числа, которые в записи имеют арифметический корень называют радикалами. Каждый радикал является корнем алгебраического уравнения, но обратное не верно. Например алгебраическое число  является решением уравнения ²++1=0 не может быть выражено в радикалах. Поэтому различают 3 класса алгебраических выражений

1. простые радикалы

2. вложенные радикалы

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

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

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

В этом случае также существует проблема однозначности представления. Вторая проблема-соотношение между радикалами удовлетворительным образом не решена, ее сложность подчеркивается первым примером

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

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

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

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

2. класс экспоненциальных

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

4. класс обратных тригонометрических функций

Известно много правил преобразования, таких как

sin(x+y)=sin(x)cos(y)+cos(x)sin(y) (1)

sinxsiny=0.5(sin(x+y)+sin(x-y)) (2)

log_a(ay)=log_ax+log_ay

ln(exp(x))=x

exp(x+y)=exp(x)exp(y)

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

sin(2x)=sin(x+x)=2sin(x)cos(x)

Но во многих СКА такая формула не выводится, так как постоянно отслеживать, что 2х=х+х требует много времени. Во вторых правила (1) и (2) взаимообратны, то есть совместное их применение приведет к зацикливанию. Такие проблемы связаны с тем, что мы используем общий подход к преобразованию выражений. Имеется различие между знанием некоторых возможных упрощений и знанием не только этих упрощений, но и того, что они являются единственно возможными. Например нам известны правила:

log_a(fg)=log_af+log_ag, exp(f+g)=exp(f)exp(g), exp(ln f)=ln(exp f)=f (3)

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

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

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

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

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

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

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

Символьные преобразования

1. Вычисление значений числовых выражений

• с помощью кнопки = (13.706)

• с помощью кнопки → 43/2 -4.6 sqrt(3)

2. упростить выражение simplify (2x²-4x+8x-5x² simplify→-3x²+4x)

3. разложить на множители factor (x²-3x-4 factor → )

4. решить уравнение f(x)=0 x²-3x-4 solve x (-1,4)

5. разложить по степеням expand (a+b)³ expand a a3+3a2b+3ab2+b3

6. выполнить действия с комплексными числами complex -14+27i

7. выполнить замену переменных substitute можно заменять на переменную или цифру.

8. Выписать коэффициенты при заданной переменной coeffs

Геометрия на комплексной плоскости

y=ImZ, x=ReZ