WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«Уральский федеральный университет Институт естественных наук и математики Департамент математики, механики и компьютерных наук Алгебра и геометрия для механиков (1 семестр) А. ...»

Тема 1-9: Многочлены

А. Я. Овсянников

Уральский федеральный университет

Институт естественных наук и математики

Департамент математики, механики и компьютерных наук

Алгебра и геометрия для механиков (1 семестр)

А. Я. Овсянников Тема 1-9: Многочлены

Многочлены как последовательности

Пусть F – поле. Рассмотрим множество F [x] всех последовательностей с

элементами из F вида (0, 1,..., n,...) таких что для некоторого

m N {0} справедливы равенства k = 0 при всех k m. Элементы из F [x] будем называть многочленами над полем F и обозначать малыми латинскими буквами. Для любого f = (0, 1,..., n,...) F [x] и j N {0} положим f [j] = j.

Два многочлена называются равными, если на соответствующих местах в них стоят одинаковые элементы:

f = g f [n] = g [n] для всех n N {0}.

Определим сумму двух многочленов f, g F [x] поэлементно:

(f + g )[n] = f [j] + g [n], n N {0} .

Произведение двух многочленов f, g F [x] определяется так:

(f · g )[n] = f [k] · g [ ], n N {0}. (1) k+ =n Очевидно, что сумма любых двух многочленов из F [x] принадлежит F [x] .

Легко проверить, что и произведение любых двух многочленов из F [x] также принадлежит F [x] .

А. Я. Овсянников Тема 1-9: Многочлены Многочлен и его степень. Свойства сложения Последовательность из нулей обозначим через o и назовем нулевым многочленом .



Пусть f F [x]. Если f = o, то существует m N такое что f [m] = 0, f [k] = 0 для любого k m. В таком случае говорят, что многочлен f имеет степень m, обозначаемую через deg(f ). Для нулевого многочлена o полагаем deg(o) =. Символ по определению считается меньше любого целого числа, и для любого целого m по определению принимается, что m + () = + m =. Нетрудно убедиться, что deg(f · g ) = deg(f ) + deg(g ), deg(f + g ) = max{deg(f ), deg(g )} при deg(f ) = deg(g ) и deg(f + g ) deg(f ), deg(g ) при deg(f ) = deg(g ) .

Непосредственно проверяются следующие свойства операций сложения многочленов:

f, g, h F [x] f + g = g + f ; f + (g + h) = (f + g ) + h; f + o = f ;

u F [x] v F [x]: u + v = o .

Таким образом, относительно сложения F [x] является абелевой группой .

А. Я. Овсянников Тема 1-9: Многочлены Свойства умножения многочленов Свойства умножения не столь очевидны. Докажем, что f, g, h F [x] f · g = g · f ; f · (g · h) = (f · g ) · h; f · (g + h) = f · g + f · h .

Первое равенство вытекает непосредственно из определения произведения (1) сл.2 .

Докажем второе. Имеем ((f · g ) · h)[n] = (f · g )[m]h[r ] = m+r =n f [p]g [q] h[r ] =

–  –  –

f [p]g [q]h[r ], откуда следует требуемое равенство p+q+r =n f · (g · h) = (f · g ) · h .

Равенство f · (g + h) = f · g + f · h доказывается аналогично .

Таким образом, F [x] является ассоциативным коммутативным кольцом с единицей (очевидно, что многочлен (1, 0, 0,...) является единицей относительно умножения многочленов) .

А. Я. Овсянников Тема 1-9: МногочленыПривычная запись многочленов

Многочлены вида (0, 0, 0,...) складываются и умножаются, как элементы поля F : имеем (, 0, 0,...) + (, 0, 0,...) = ( +, 0, 0,...);

(, 0, 0,...) · (, 0, 0,...) = ( ·, 0, 0,...) .

Условимся отождествлять такие многочлены с их первыми элементами .

Например, нулевой многочлен o отождествляется с числом 0. Нетрудно проверить, что · (0, 1,...) = (0, 1,...) .



Многочлен (0, 1, 0, 0,...) обозначим через x. Легко проверить, что x 2 = x · x = (0, 0, 1, 0, 0...), x 3 = x 2 · x = (0, 0, 0, 1, 0...), и x m [m + 1] = 1, x m [n] = 0 при n = m + 1 .

Ясно, что выражение вида

f = n x n + n1 x n1 +... + 1 x + 0, (2)

где 0, 1,..., n F, n – натуральное число, представляет собой многочлен f = (0, 1,..., n, 0,...), в котором f [m] = 0 при m n. В дальнейшем мы будем придерживаться этой привычной записи многочленов. Элементы поля F 0,..., n называются коэффициентами многочлена f. Если n = 0, то n = deg(f ) и n x n называется старшим членом, а n – старшим коэффициентом многочлена f. Элемент поля 0 называется свободным членом многочлена f .

–  –  –

Докажем единственность. Предположим, что f = q1 g + r1 и f = q2 g + r2 для некоторых многочленов q1, q2, r1, r2 таких что deg(r1 ), deg(r2 ) deg(g ). Из равенства q1 g + r1 = q2 g + r2 получаем (q1 q2 )g = r2 r1. Если q1 q2 = 0, то deg((q1 q2 )g ) deg(g ), а deg(r2 r1 ) deg(g ) получили противоречие. Следовательно, q1 q2 = 0, откуда q1 = q2 и r1 = r2. Теорема доказана .

В равенстве (3) сл.6 многочлен q называется частным, а многочлен r – остатком от деления (с остатком) f на g. Если r = 0, то говорят, что многочлен f делится на многочлен g ; в этом случае f = qg. При этом говорят также, что многочлен g делит многочлен f ; этот факт будем обозначать через g |f .

–  –  –

Шаги повторяются до тех пор, пока deg(f1 ) m. Так как степень f1 на каждом шаге уменьшается на m, алгоритм закончит работу. При этом частное будет равно q, а остаток – последнему значению f1 .

–  –  –

Многочлены f и g называются ассоциированными, если существует ненулевой элемент F такой, что f = g. Легко проверить, что многочлены f и g ассоциированы тогда и только тогда, когда f |g и g |f, а также что отношение ассоциированности является отношением эквивалентности на множестве F [x]. Каждый класс эквивалентности по этому отношению, содержащий ненулевой многочлен, содержит единственный многочлен со старшим коэффициентом 1. Поэтому справедливо Наблюдение Для любого ненулевого многочлена существует единственный ассоциированный с ним многочлен со старшим коэффициентом 1 .

–  –  –

Пусть f, g F [x]. Многочлен d называется наибольшим общим делителем(НОД) многочленов f, g, если d |f, d |g, и для любого h F [x] из h|f и h|g следует, что h|d. Из определения НОД вытекает, что если он существует для многочленов f, g, то любые два НОД ассоциированы. Для того, чтобы НОД был определен однозначно, требуют, чтобы его старший коэффициент был равен 1 .

В доказательстве утверждения на следующем слайде излагается алгоритм Евклида построения НОД двух многочленов .





–  –  –

Процесс (5) на сл. 12 должен завершиться получением нулевого остатка, так как степень g натуральное число, и степени остатков r1,..., rk,.. .

убывают .

Докажем, что rk+1 является НОД многочленов f и g. Поднимаясь по цепочке равенств (5) снизу вверх, покажем, что rk+1 |f и rk+1 |g. Из последнего равенства получаем, что rk+1 |rk, из предпоследнего в силу предложения сл.10 – что rk+1 |rk1, из каждого последующего рассматриваемого равенства rs = qs+2 rs+1 + rs+2, получаем по предложению сл.10, что rk+1 |rs, так как уже доказано, что rk+1 |rs+1 и rk+1 |rs+2. Дойдя до второго и первого равенства, получим rk+1 |g и rk+1 |f .

Опускаясь по цепочке равенств (5) сверху вниз, покажем, что если h|f и h|g, то h|rk+1. Пусть h|f и h|g. Из первого равенства получаем r1 = f q1 g ; по предложению сл.10 получаем h|r1. Рассматривая следующее равенство, получаем r2 = g q2 r1, откуда следует в силу предложения сл.10, что h|r2. Опускаясь по цепочке равенств (5) сверху вниз, докажем, что h|rs при s = 3,..., k + 1 .

А. Я.

Овсянников Тема 1-9: Многочлены Окончание доказательства Чтобы доказать равенство (4), нужно выразить из предпоследнего равенства в (5) rk+1 = rk1 qk+1 rk, затем подставить в это равенство выражение rk = rk2 qk rk1, полученное из предыдущего равенства:

rk+1 = rk1 qk+1 (rk2 qk rk1 ) = qk+1 rk2 + (qk+1 qk + 1)rk1 = u2 rk2 + v2 rk1. Получаем равенство rk+1 = u2 rk2 + v2 rk1. Подставляя в это равенство выражение rk1 = rk3 qk1 rk2, полученное из 4-го снизу равенства rk3 = qk1 rk2 + rk1, получим rk+1 = u2 rk2 + v2 (rk3 qk1 rk2 ) = v2 rk3 + (u2 v2 qk+1 )rk2 = u3 rk3 + v3 rk2. Продолжая движение снизу вверх, на каждом шаге будем получать равенство rk+1 = us rks + vs rks+1, где s = 4,..., k 1. При s = k 1 получаем rk+1 = uk1 r1 + vk+1 r2. Подставляя в это равенство выражение r2 = g q2 r1, полученное из 2-го равенства, получаем rk+1 = uk1 r1 + vk+1 (g q2 r1 ) = vk+1 g + (uk1 vk+1 q2 )r1. Подставляем в равенство rk+1 = vk+1 g + (uk1 vk+1 q2 )r1 выражение r1 = f q1 g, полученное из 1-го равенства, окончательно имеем rk+1 = vk+1 g + (uk1 vk+1 q2 )(f q1 g ) = vk+1 q2 f + (vk+1 + vk+1 q2 q1 )g = uf + vg, что и требовалось доказать .

Если многочлены f, g F [x] имеют ненулевой НОД, то через (f, g ) обозначим НОД этих многочленов со старшим коэффициентом 1 .

Равенство (4) на сл.12 дает линейную форму наибольшего общего делителя .

А. Я. Овсянников Тема 1-9: Многочлены Пример нахождения НОД многочленов Приведем конкретный пример. Найти НОД многочленов

–  –  –

Разделив столбиком g на x 2 с остатком, получим g = (x 1)(x 2), т.е. g = 2 (x 1)2(x 2). Алгоритм завершается. НОД многочленов f, g равен x 2 (старший коэффициент берем равным 1). Из равенства (6) находим линейную форму НОД: x 2 = 2 f 1 (x + 1)g .

–  –  –

Многочлены f, g называются взаимно простыми, если их наибольший общий делитель (f, g ) равен 1. Из теоремы сл.12 получается такое Следствие Многочлены f, g являются взаимно простыми тогда и только тогда, когда существуют такие многочлены u, v, что выполняется равенство

–  –  –

Если равенство (7) имеет место, то 1 делится на любой общий делитель многочленов f, g, поэтому они взаимно просты. Обратное утверждение обеспечивается равенством (4) сл.12 .

–  –  –

Докажем утверждение 1. Пусть h = fp, h = gq для некоторых многочленов p, q. Так как f, g взаимно просты, в силу следствия существуют многочлены u, v такие, что выполняется равенство uf + vg = 1. Умножая обе части этого равенства на h, получим h = huf + hvg, откуда h = gquf + fpvg = fg (qu + pv ), что и требуется доказать .

Докажем утверждение 2. Пусть gh = fp для некоторого многочлена p. Так как f, g взаимно просты, в силу следствия существуют многочлены u, v такие, что выполняется равенство uf + vg = 1. Умножая обе части этого равенства на h, получим h = huf + hvg, откуда h = huf + fpv = f (hu + pv ), что и требуется доказать .

Докажем утверждение 3. Так как f, h взаимно просты, в силу следствия существуют многочлены u, v такие, что выполняется равенство uf + vh = 1.Умножая обе части этого равенства на g, получим g = ufg + vhg. От противного, предположим, что fg и h не взаимно просты. Пусть p = (fg, h). Тогда p|h и p|g в силу равенства g = ufg + vgh и предложения сл.10. Получили противоречие с условием, что g, h взаимно просты. Следовательно,fg и h взаимно просты .

А. Я. Овсянников Тема 1-9: Многочлены Неприводимые многочлены Пусть F – поле .

Определение Многочлен f F [x] называется неприводимым над полем F, если deg(f ) 1 и для любых многочленов g, h F [x] из равенства f = gh следует deg(g ) = deg(f ) или deg(h) = deg(f ) .

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

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

Предложение Пусть p F [x] –неприводимый многочлен. Для любого f F [x] либо p|f, либо (p, f ) = 1 .

Доказательство. Предположим, что p |f. Пусть q = (p, f ). Тогда q не ассоциирован с p и q|p, откуда следует deg(q) = 0, т.е. q = 1 .

Из этого утверждения и утверждения 2 предложения сл.16 вытекает Следствие Если неприводимый многочлен p делит произведение fg некоторых многочленов f, g, то p делит f или p делит g .

А. Я. Овсянников Тема 1-9: Многочлены Предложение Если неприводимый многочлен p делит произведение q1... qm некоторых неприводимых многочленов q1,..., qm, то p ассоциирован по крайней мере с одним многочленом qj (j = 1,..., m) .

Доказательство. Проведем индукцию по m. При m = 2 из следствия сл.18 получаем, что p|q1 или p|q2, откудв в силу неприводимости p, q1, q2 следует требуемое. Предположим, что утверждение уже доказано для всех 2 k m и неприводимый многочлен p делит произведение q1... qm некоторых неприводимых многочленов q1,..., qm. Так как p1 |(q1 · q2... qm ), согласно следствию сл.18 p1 |q1 или p1 |(q2 · q3... qm ). В первом случае p1 ассоциирован c q1, а во втором по предположению индукции p1 ассоциирован c qj для некоторого 2 j m, что и требуется доказать .

А. Я. Овсянников Тема 1-9: МногочленыТеорема о неприводимом разложении многочлена

Теорема Пусть F – поле. Любой многочлен из F [x] степени больше 0 либо является неприводимым, либо разлагается в произведение неприводимых многочленов, причем это разложение определяется однозначно с точностью до замены неприводимых множителей ассоциированными многочленами и перестановки сомножителей .

Доказательство. Пусть f F [x] – многочлен. Докажем существование разложения индукцией по deg(f ). База индукции: deg(f ) = 1. Тогда f – неприводимый многочлен. Шаг индукции. Пусть для всех многочленов степени меньше deg(f ) утверждение доказано. Если многочлен f не является неприводимым, то f = gh для некоторых многочленов g, h F [x], причем deg(g ) deg(f ) и deg(h) deg(f ). По предположению индукции каждый из многочленов g, h либо неприводим, либо разлагается в произведение неприводимых многочленов, поэтому f также разлагается в произведение неприводимых многочленов .

Доказательство единственности на следующем слайде .

А. Я. Овсянников Тема 1-9: МногочленыОкончание доказательства теоремы

Предположим, что многочлен f разлагается в произведение неприводимых многочленов двумя способами f = p1 p2... pm и f = q1 q2... q, где m .

Индукцией по m покажем, что m = и для некоторой перестановки (i1, i2,..., im ) чисел {1, 2,..., m} каждый многочлен pj ассоциирован с qij при j = 1, 2,..., m. Пусть m = 1. Так как p1 – неприводимый многочлен, ясно, что = 1 и p1 = q1. Предположим, что m 1 и для любого 1 k m утверждение доказано. Так как p1 |(q1 · q2... q ), согласно предложению сл.19 p1 ассоциирован c qi1 для некоторого 1 i1 m .

Пусть p1 = qi1. Сокращая в равенстве p1 p2... pm = q1 q2... q на qi1, получим равенство p2... pm = j=i1 qj. Многочлен p2 является неприводимым. Обозначим его снова через p2. Применяя предположение индукции к равенству p2... pm = j=i1 qj, получаем, что m 1 = 1 и для некоторой перестановки (i2,..., im ) чисел {1, 2,..., m}\{i1 } каждый многочлен pj ассоциирован с qij при j = 2,..., m. Таким образом, шаг индукции доказан .

Доказательство теоремы закончено .

–  –  –

где старший коэффициент многочлена f, p1, p2,..., pm – все различные неприводимые над полем F делители многочлена f, имеющие старший коэффициент 1. Это представление называется разложением многочлена f на неприводимые множители. Число kj в равенстве (8) называется кратностью неприводимого многочлена pj в разложении многочлена f на неприводимые множители. Легко понять, что deg(f ) = m kj deg(pj ) .

j=1

–  –  –

Напомним, что через char(F ) обозначается характеристика поля F (см .

сл.13 т.1-4) .

Предложение Пусть F – поле, char(F ) = 0 и f F [x], p неприводимый множитель многочлена f кратности k. Если k = 1, то p не делит f. Если k 1, то p

– неприводимый множитель многочлена f кратности k 1 .

Доказательство. Пусть f = p k g, где (p, g ) = 1 .

Если k = 1, то f = (pg ) = p g + pg. Так как deg(p ) = deg(p) 1, по определению неприводимого многочлена (p, p ) = 1. Из (p, g ) = 1, в силу утверждения 3 предложения сл.16, следует, что (p, p g ) = 1 .

Следовательно, p не делит f .

Пусть k 1. Тогда k = 0 в поле F, и f = (p k g ) = kp k1 p g + p k g = p k1 (kp g + pg ) .

Поскольку p не делит kp g + pg, утверждение доказано .

–  –  –

многочлен в нулевой степени равен 1). Следовательно, частное f /(f, f ) = p1 p2... pm есть произведение первых степеней всех неприводимых множителей многочлена f. Применяя эти рассуждения к многочлену f1 = (f, f ) в случае, когда его степень больше нуля, получим произведение первых степеней тех неприводимых множителей многочлена f, которые имеют кратности больше 1. Продолжая таким образом, получим произведения первых степеней тех неприводимых множителей многочлена f, которые имеют кратности больше s. Эта процедура называется отделением кратных множителей многочлена f .

–  –  –

Решение. Вычислим f = 8x 7 + 14x 6 + 30x 5 + 30x 4 + 32x 3 + 18x 2 + 10x + 2 и с помощью алгоритма Евклида найдем (f, f ) = x 4 + x 3 + 2x 2 + x + 1 .

При вычислениях можно заменять многочлены на ассоциированные, в частности, вместо производной взять многочлен 2 f. Разделив столбиком f на (f, f ), найдем частное x + x + 2x + x + 1. Таким образом, f = (x 4 + x 3 + 2x 2 + x + 1)2, а произведение первых степеней всех неприводимых множителей многочлена f есть x 4 + x 3 + 2x 2 + x + 1, и каждый неприводимый множитель имеет кратность 2. Легко заметить, что x 4 + x 3 + 2x 2 + x + 1 = x 4 + x 3 + x 2 + x 2 + x + 1 = (x 2 + 1)(x 2 + x + 1), т.е .

f = (x 2 + 1)2 (x 2 + x + 1)2.




Похожие работы:

«Тренинг для учителей "Конфликты и пути их решения". Составила: Щаднева Е.А. Педагог – психолог МКОУ "СШИ р.п.Межевой" Один философ сказал: „.тот, кто умеет управиться с конфликтами путем их признания и регуля...»

«ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2017 Математика и механика № 47 УДК 620.178.7+678.067.5+623.566.5 DOI 10.17223/19988621/47/6 А.И . Дульнев, Е.А. Неклюдова ЭКСПЕРИМЕНТАЛЬНО-РАСЧЕТНАЯ ОЦЕНКА ВЗРЫВОСОПРОТИВЛЯЕМОСТИ ОБРАЗЦОВ ИЗ СТЕКЛОПЛА...»

«Порше Центр Тольятти • 445024 • Тольятти • Революционная, 82 ООО "Премьер-Спорт"Получатель: PC Togliatty/Samara (Premier Sport), Революционная, 82 445024 Тольятти 445024 Тольятти Телефон: +...»

«ГОСУДАРСТВЕННЫЙ СТАНДАРТ СОЮЗА ССР МЕБЕЛЬ ОБЩИЕ ТЕХНИЧЕСКИЕ УСЛОВИЯ ГОСТ 16371—84 Издание официально" Цена fO коп. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО СТАНДАРТАМ Москва скачать ту УДК 684.4 : 006.354 Группа К25 ГОСУДАРСТВЕННЫЙ СТАНДАРТ СОЮЗА ССР ГОСТ МЕБЕЛЬ Общие технические условия 1 6 3 7 1 -8 4 Взамен Furniture. Gene...»

«ГОСТ Р 50541-93 (МЭК 127—5—89) ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОМ ФЕДЕРМЩИ МИНИАТЮРНЫЕ ПЛАВКИЕ ПРЕДОХРАНИТЕЛИ РУКОВОДСТВО ПО СЕРТИФИКАЦИИ МИНИАТЮРНЫХ ПЛАВКИХ ВСТАВОК Издание официальное ЬЗ 1-93/103 ГОССТАНДАРТ РОССИИ Маски стоимость дома УДК 62I.3I6.M3.001.4 ; 006.354 Группа Э29 го су д а рствен н ы й ста...»

«ВАЖНЫЕ ИНСТРУКЦИИ ПО ТЕХНИКЕ БЕЗОПАСНОСТИ ОБЕСПЕЧЕНИЕ СОБСТВЕННОЙ БЕЗОПАСНОСТИ И БЕЗОПАСНОСТИ ДРУГИХ ЛЮДЕЙ ЯВЛЯЕТСЯ КРАЙНЕ ВАЖНЫМ В настоящем руководстве и на самом приборе приведены важные указания по технике безопасности, которые не...»

«СОГЛАСОВАНО ГЦИ СИВНИИР '.П. Иванов 2006 г. Внесена в Государственный Установка поверочная реестр средств измерений для счетчиков газа и спирометров Регистрационный № ~ ~ УПС-16-С Изготовлена по технической документации ООО "Научно-внедренческое предприятие "Газометр" г. Казань, зав. номер 01. Назначение и область применения...»

«ДОПОЛНИТЕЛЬНАЯ ОБЩЕРАЗВИВАЮЩАЯ ПРОГРАММА технической направленности "Проектная деятельность. Техническое творчество" СОДЕРЖАНИЕ 1. Пояснительная записка 2. Учебно-тематический план 3.Содержание про...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.