67811

АРИФМЕТИКА МНОГОЧЛЕНІВ

Лабораторная работа

Математика и математический анализ

Множина всіх многочленів від однієї змінної над полем утворює комутативне кільце з одиницею. Будь-який ненульовий елемент поля можна розглядати як многочлен нульового степеня нуль поля також належить до многочленів його називають нульовим многочленом.

Украинкский

2014-09-15

456.5 KB

9 чел.

PAGE   \* MERGEFORMAT 5

Лабораторна робота № 4

Тема: АРИФМЕТИКА МНОГОЧЛЕНІВ

Мета роботи – вивчити основні поняття, необхідні для обґрунтування модульної арифметики і операцій в розширеннях скінченних полів.

Короткі теоретичні відомості.

1. Многочлени над полем.

Многочлен над полем  – це функція вигляду , де , . Ціле число  називається степенем многочлена і позначається . Числа  називаються коефіцієнтами,  – вільним членом. Областю зміни аргументу  є . Множення і додавання є операціями в полі. Константи (елементи поля ) розглядаються як многочлени нульового степеня.

Множина  всіх многочленів від однієї змінної над полем  утворює комутативне кільце з одиницею. Над многочленами можна проводити операції додавання і множення, причому ці дії мають всі властивості операцій в комутативному кільці (асоціативність, комутативність, дистрибутивність, існування нульового елементу, і т. д.). Будь-який ненульовий елемент поля можна розглядати як многочлен нульового степеня, нуль поля також належить до многочленів, його називають нульовим многочленом. Роль одиниці кільця  відіграє одиничний елемент 1 поля , який розглядається як многочлен нульового степеня.

Якщо , по многочлен називається зведеним (нормованим, унітарним). Будь-який многочлен над полем можна привести до нормованого, помноживши його на , але в кільці це не так, оскільки не для всіх елементів існують обернені.

В кільці многочленів  має місце алгоритм ділення з остачею, аналогічний тому, який має місце для цілих чисел.

Означення. Якщо для многочленів  і  в кільці  існують такі многочлени  і , що многочлен  можна представити у вигляді 

де степінь многочлена  не більше степеня многочлена  (), то говорять, що многочлен  ділиться на многочлен  з остачею.

2. Подільність многочленів

При діленні многочленів з остачею застосовують ту ж термінологію, що і для цілих чисел: многочлен  називається діленим, многочлен  – дільником, многочлен  – неповною часткою, а многочлен  – остачею.

На практиці ділення з остачею для двох заданих многочленів виконується аналогічно діленню багатозначних чисел – "кутом".

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

Покладемо

.

Прирівнявши коефіцієнти в обох частинах останньої рівності, отримаємо:

Звичайно процес ділення на лінійний двочлен оформляють у вигляді таблиці:

3. Алгоритм Евкліда для многочленів

Многочлен  називається спільним дільником многочленів  і , якщо він є дільником кожного з них.

Спільний дільник многочленів  і , який ділиться на будь-який спільний дільник цих многочленів, називається найбільшим спільним дільником (НСД) многочленів  і . Позначається символом  або .

Звичайно за   вибирається нормований многочлен.

Два многочлени   і  називаються взаємно простими, якщо кожен їх спільний дільник є многочленом нульового степеня (константою, що відрізняється від нуля).

Для визначення НСД двох многочленів використовується аналог класичного алгоритму Евкліда для чисел.

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

;

;

;

....................................................

;

.

Остання відмінна від нуля остача  і буде найбільшим спільним дільником многочленів  і .

Теорема (про лінійне представлення НСД двох многочленів). Для будь-яких двох многочленів  і  з  існує найбільший спільний дільник , який можна представити у вигляді:

,

де .

Два многочлени  і  є взаємно простими тоді і тільки тоді, коли існують многочлени  такі, що

.

Для визначення лінійного представлення НСД двох многочленів використовується аналог розширеного алгоритму Евкліда для чисел.

4. Многочлени над полем .

Додавання і множення в полі  визначається наступними таблицями

+

0

1

х

0

1

0

0

1

0

0

0

1

1

0

1

0

1

Якщо многочлен  незвідний, то остачі від ділення всіх многочленів з  на  утворюють поле  відносно операцій множення і складання многочленів з коефіцієнтами з . Поле  є розширенням. Кількість його елементів дорівнює . Рівність в полі  є конгруенцією вигляду . Елемент, обернений  обчислюється як многочлен  з рівняння , оскільки всі многочлени степеня менше  взаємно прості з .

Якщо многочлену ,  поставити у відповідність вектор , то операції в полі  можна інтерпретувати як операції над векторами – розширеними числами, праві крайні координати яких належать .

5. Незвідність многочленів

Многочлен ненульового степеня називається незвідним, якщо він ділиться лише на константи і сам на себе.

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

Як простих чисел в, так і незвідних  многочленів над довільним полем  існує нескінченна множина.

Над будь-яким скінченним полем існують незвідні многочлени скільки завгодно високого степеня.

Порядок виконання роботи.

1. Вивчити короткі теоретичні відомості про властивості многочленів.

2. Користуючись схемою Горнера, обчислити :

  1.  ,   ;
    1.  ,   ;
    2.  ,   ;
    3.  ,  ;
    4.  ,   ;
    5.  ,  ;
    6.  , ;
    7.  , ;
    8.  ,   ;
    9.  ,  ;
  2.  ,   ;
  3.  ,  ;
  4.  ,  ;
  5.  ,  ;
  6.  ,  ;
  7.  ,   ;
  8.  ,  ;
  9.  ,   ;
  10.  ,   ;
  11.  ,  ;
  12.  ,   ;
  13.  ,   ;
  14.  ,  ;
  15.  ,  ;
  16.  , .

2. За допомогою розширеного алгоритму Евкліда знайти лінійне представлення найбільшого спільного дільника многочленів  і :

  1.  ,
  2.  ,
  3.  ,
  4.  ;
  5.  ,
  6.  ,
  7.  ,
  8.  ,
  9.  ,
  10.  ,
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  ;
  23.  ;
  24.  ;
  25.  .

3. За допомогою розширеного алгоритму Евкліда знайти лінійне представлення найбільшого спільного дільника многочленів  і  над полем .

1

2

3

4

5

6

7

8

9

10

11

12

13

4

5

8

6

5

6

5

7

4

6

6

7

7

3

4

4

1

3

5

1

3

2

3

4

2

4

14

15

16

17

18

19

20

21

22

23

24

25

6

8

6

7

8

9

8

7

9

8

5

8

2

5

5

6

3

5

2

5

4

1

2

5

4. Скласти звіт, приєднавши отримані результати.

Вимоги до звіту.

У звіті мають бути приведені:

1. Короткі відомості про вивчені властивості многочленів.

2. Розв'язання свого варіанту з необхідними поясненнями.

3. Відповіді на контрольні питання.

Контрольні питання.

  1.  Що таке многочлен?
    1.  Що таке многочлен над полем?
      1.  Як знайти НСД двох многочленів?
      2.  Як знайти лінійне представлення НСД двох многочленів?
      3.  Чому лишки за модулем незвідного над  многочлена не утворюють поле?
      4.  Чому операції додавання і віднімання в розширенні поля  збігаються?


 

А также другие работы, которые могут Вас заинтересовать

23026. Дослідження моделей лінійних динамічних систем з розподіленими параметрами при скінченновимірних варіаціях параметрів 330 KB
  22 нескінченні прирости. Пройти ці неприємності на шляху до оптимального розвязання задач розміщення спостерігачів та керувачів можна надаючи координатам та скінченні прирости та досліджуючи прирости .6 заключаємо що прирости та можуть бути вирахувані якщо будуть відомі прирости для та для .11 заключаємо що прирости та можуть бути вирахувані якщо будуть відомі прирости для та для .
23027. Псевдоінверсні методи моделювання задач керування лінійними динамічними системами 652 KB
  Інтегральні моделі динаміки лінійних систем і можливості по їх використанню в розвязанні обернених задач.13 були успішно розвязані в попередніх лекціях. Задачі були розвязані точно якщо це можливо або з деяким наближенням якщо точний розвязок задачі не можливий. Цим самим були дані розвязки або найкраще середньоквадратичне наближення до них для задач моделювання зовнішньодинамічної обстановки в якій функціонує система та прямих задач динаміки таких систем.
23028. Задачі ідентифікації динаміки систем з розподіленими параметрами 276.5 KB
  Псевдоінверсні методи [2227] обернення алгебраїчних інтегральних та функціональних перетворень дозволяють виконати таку заміну побудувати моделюючі функції в неперервному або дискретному вигляді тільки при відомій функції матриці Гріна в необмеженій просторовочасовій області. Викладена ж в лекції 2 методика побудови функції дозволяє виконати це для систем динаміка яких описана вже диференціальним рівнянням вигляду 1.7 зведеться до знаходження перетворюючої функції функції Гріна в нашому розумінні такої що 15.4 побудови...
23029. Задачі ідентифікації лінійних алгебраїчних, інтегральних та функціональних перетворень 487 KB
  Постановка та план розвязання задачі. Далі розвязки ідентифікаційних задач 16.3 отримаємо із розвязку допоміжних задач 16. Розглянемо розвязок задачі 16.
23030. Проблеми моделювання динаміки систем з розподіленими параметрами 1.64 MB
  4 і модель ця адекватно описує динаміку фізикотехнічного обєкту процесу то можна ставити і розвязувати: Прямі задачі динаміки визначення векторфункції стану ys при заданих зовнішньодинамічних факторах ; Обернені задачі динаміки визначення векторфункцій які б згідно певного критерію дозволяли отримувати задану картину змін векторфункції ys або наближатися до неї.4 побудовані апробовані практикою а відповідні математичні теорії дозволяють розвязувати як прямі так і обернені задачі динаміки таких систем....
23031. Побудова матричної функції Гріна та інтегральної моделі динаміки систем з розподіленими параметрами в необмеженій просторово-часовій області 249.5 KB
  Функція Гріна динаміки систем з розподіленими параметрами в необмежених просторовочасових областях.10 а також з того що шукана матрична функція Gss' є розвязком рівняння 1.1 де визначені вище матричні диференціальні оператори та матрична функція одиничного джерела. А це означає що матрична функція відповідає фізичному змісту задачі а розвязок її дійсно представляється співвідношенням 1.
23032. Дискретний варіант побудови та дослідження загального розв’язку задачі моделювання динаміки систем з розподіленими параметрами 586 KB
  Псевдообернені матриці та проблеми побудови загального розвязку системи лінійних алгебраїчних рівнянь. З цією метою виділимо в матриці C r лінійно незалежних стовпців. Враховуючи що всякий стовпець матриці C може бути розкладений за системою векторів як за базисом матрицю C подамо у вигляді де вектор коефіцієнтів розкладу стовпця матриці С за базисом .10 ранг основної матриці дорівнює рангу розширеної.
23033. Моделювання дискретизованих початково-крайових 244 KB
  Постановка задачі та проблеми її розвязання.4 в розвязку 1.23 вектора векторфункції та матричної функції проблему розвязання задачі 4.6 в залежності від співвідношень між та може мати точний розвязок або визначене згідно 4.
23034. Моделювання неперервної початково-крайової задачі динаміки систем з розподіленими параметрами 355.5 KB
  Моделювання неперервної початковокрайової задачі динаміки систем з розподіленими параметрами 5. Постановка задачі та проблеми її розвязання. Розглянутий вище варіант постановки та розвязання проблеми моделювання початковокрайової задачі динаміки системи 1.5 Для того щоб методику розвязання дискретизованої задачі моделювання динаміки розглядуваної системи розвинуту в рамках лекції 3 успішно узагальнену далі лекція 4 на задачі моделювання дискретизованих початковокрайових умов неперервними функціями та поширити на задачу 5.