Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 20
Текст из файла (страница 20)
получаем противоречие (так как нз равенства (щ(х) — ~Л(х)) о(х) = тз(х) — г1(х) следует с(ея((о1 — оз) и) = доя(г~ — тз) — Прим. перев.). Значит, д1(х) — оз(х) = О и т1(х) = тз(х). Чтобы определить о(х) н т(х), можно использовать алгоритм 4.3.1Р для деления чисел с многократной точностью, только без переносов. Алгоритм Р (Деление полииомов иад поле и). Даны полиномы и(х) =и х +" +и1х+ио, и(х) =о„х" +" +и1х+оо над полем Я, где иь ~ О н тп > и > О.
Алгоритм находит пояиномы т(х) = т„1х" + ° + то о(х) =о „х "+ ° ° +оэ, над полем Я, удовлетворяющие условиям (1). Ш. ]Итерация по й.] Выполнять шаг Р2 для х = т - и, ~п — п — 1, ..., 0; затем прекратить выполнение алгоритма с (т„м .,то) = (и -1 ио). Р2. (Цикл деления.] Ъстановить сначала оь +- и„~ь/и„, а затем — иу +- и1 — йьиу-э для,у = и + Й вЂ” 1, и, + й — 2, ... „к. (Действие последней операции состоит в замещении и(х) на и(х) — дьх"в(х), полипом степени ( п+ к.) 1 Пример использования алгоритма Р приводится ниже, в (5). Количество выполняемых арифметических операций, в сущности, пропорционально п(тп — и + 1).
Обратите внимание, что явное деление коэффициентов выполняется только в начале шага Р2 и знаменателем всегда является и„. Таким образом, если о(х)— нормированный полипом (с и„= 1), реальное деление не производитСя вовсе. Если умножение более предпочтительно, чем деление, имеет смысл предварительно вычислить значение 1/и„и на шаге Р2 выполнить умножение на эту величину.
Зачастую остаток т(х) из (1) будет записываться как и(х) ппк1 е(х). Области единственного разложения на множители. Если мы ограничимся рассмотрением полиномов над полем, то не охватим полипомы нвд множеством целых чисел и полиномы от нескольких переменных.
Поэтому будем рассматривать более общую ситуацию, когда алгебраическая система коэффициентов Я представляет собой областпь едиисвееииого раэлолсеиил иа миаяситлели и не обязана быть полем. Это означает, что Б — коммутативное кольцо с единицей и что 1) ив ф О, если и и и — ненулевые элементы Б; й) каждый ненулевой элемент и б Я либо обрагпим, либо имеет "единственное" представление в виде произведения просгпых рм ..., р~.' (2) и = р|„..
рг, 1 > 1. Обрапгиммй элемент в данном случае представляет собой элемент, который имеет обратную величину, а именно — элемент и, такой, что ие = 1 для некоторого и й 5. Простой элемент — зто не являющийся обратимым элемент р, такой, что уравнение р = дг истинно только тогда, когда либо д, либо г представляет собой обратимый элемент. Представление (2) единственно в том смысэе, что если р1...рг = 4г .. 4„ где все р и д просты, то з = 1 и имеется перестановка я1... хг множества (1,..., 1), такая, что рг = агу „..., рг = агр„, для некоторых обратимых ам ..., ао Другими словами, разложение на простые множители единственно с точностью до порядка множителей и до умножения на обратимые.
Любое поле представляет собой область единственного разложения на множители, в которой каждый ненулевой элемент обратим и в которой не существует простых элементов. Целые числа образуют область единственного разложения, в которой обратимые элементы — +1 н -1, а простые — х2, хЗ, хб, х7, х11 и т.
д, Случай, когда Ю содержит все целые числа, принципиален, поскольку зачастую предпочтительнее работать с целыми коэффициентами, а ие с произвольными рациональными. Одним из ключевых фактов, связанных с полиномами (см. упр. 10), является то, что полинами над областью единственного разлоэсенил обраэрюгп область единспгаенного разлоэгсенил. Полинам, который является простым в этой области, обычно называется непрнаадиммм.
Многократно используя теорему о единственности разложения, можно доказать, что полиномы от нескольких переменных над множеством целых чисел или нэд любым полем с любым числом переменных могут быть единственным образом разложены на непривцдимые полиномы. Например, полипом от трех переменных 90хэ — 120хэр+ 18хгрг — 24хрэг над целыми числами представляет собой произведение пяти неприводимых полиномов 2 3 х (Зх — 4р) . (Ьх + рг). Тот же полинам над рациональными числами является произведением трех неприводимых полиномов (бх) (Зх — 4р) (бх + рг). Это разложение может быть записано как х (90х — 120р) (х + ~~рг) и еще бесконечным числом способов, хотя разложение, по существу, единственно.
Как обычно, мы говорим, что и(х) ирапген полииому и(х), а о(х) является делишелам и(х), если и(х) = и(х)д(х) для некоторого полинома д(х). Если есть алгоритм, который определяет, является ли и кратным и для произвольных ненулевых элементов и и и некоторой области единственного разложения 5, и позволяет оцределнть ю, если и = и ю, то алгоритм Р дает метод для выяснения, является ли и(х) кратным и(х) для произвольных ненулевых полиномов и(х) и и(х) над Я.
Если и(х) кратно и(х), легко увидеть, что и„+э должно быть кратно и при переходе к шагу Р2; отсюда будет найдено частное и(х)/и(х). Применяя это наблюдение рекурснвно, получим алгоритм, который отв«чает иа вопрос, является ли данный полинам над Я от любого числа переменных кратным другому полипому нэд 5, а также алгоритм, который будет находить частное, если таковое существует. Множество элементов области единственного разложения называется взаимно проспгмм, если нет простого элемента этой области единственного разложения, который делит все остальные элементы.
Полинам над областью единственного разложения называется примишиенььи, если его коэффициенты взаимно просты (не путайте это понятие с совершенно другим понятием пр»»мвшивнмх полиножое по модулю р, которое обсуждалось в разделе 3,2.2). Следующий факт, представленный для полиномов над целыми числами К. Ф. Гауссом (С. г, Сапзэ) в 42 разделе его знаменитой книги РЬдшз1бопвз Аг1»)нпе»1сю (1л1рз18, 1801), имеет первостепенную важность.
Лемма О (Лемма Гаусса). Произведение примитивных полпномов нал областью единственного разложения примитивно, Доказатеяьсшео. Пусть и(х) = и х'"+ +не н о(х) = о„х" + +по — примитивные полиномы. Пусть р — любой просгой элемент области; тогда следует показать, что р не делит все коэффициенты и(х)о(х), По условию имеется такой индексу, что иу не делится на р, и такой индекс й, что с» не делится на р. Пусть у и й— наименьшие такие индексы; тогда коэффициент при х~+" в и(х)в(х) равен изв» + и +го», + ° ° + пу»»ео + и, гв»»» + ° + ион»+у Так как первый член этой суммы не делится на р, а все остальные делятся, иа р не делится и вся сумма.
$ Если ненулевой полипом и(х) над областью единственного разложения Я не примитивен, можно записать и(х) = р~ и»(х), где р» — простой злемеят из 5, делящий все коэффициенты в(х), а и»(х) — другой ненулевой полипом нал Я. Все коэффициенты и»(х) имеют на один простой множитель меньше соответствующих коэффициентов и(х). Теперь, если и»(х) не примитивен, можно записать и~(х) = рз нз(х) и т. д. Этот процесс безусловно прекратится при представлении ы(х) = с ° и»(х), где с е о н о»(х) — примитивен. Фактически пмеется соответствующая лемме С лемма Н.
Лемма Н. Любой ненулевой поляком и(х) над областью единственного разложения 5 можно разложить на множнтелп в вяде и(х) = с е(х), где с представляет собой элемент Я, а в(х) — примнгнвлый полинам. Кроме того, это представление единственно в том смысле, что еглп и = с» ° щ(х) = сз ° вз(х), то с» = асз я ез(х) = ав» (х), где а — обратимый элемент Я, Доказательсшво. Мы уже показали, что такое разложение существует, так что доказательства требует только единственность разложения.
Положим, что с» щ (х) = сз оз(х), где гч(х) и вз(х) — примитивные полиномы. Пусть р — некоторое простое нз 5. Если р» делит с», то оно делит и сз, в противном случае р» должно делить все коэффициенты сз . ез(х) и р должно делить все коэффициенты оз(х). Таким образом, получается противоречие с посылкой примитивности из(х). Точно так же р» делит сз только в том случае, если р» делит см Следовательно, в силу единственности разложения с» = асз, где а обратимо; поскольку 0 = асз ° щ(х) — сз оз(х) = сз ° (ащ(х) — ез(х)), получаем ощ(х) — оз(х) = О.
й Таким образом, можно записать любой ненулевой полипом и(х) в виде и(х) = сонг(и) рр(и(х)), (3) где сопт(и) — содерхсание (сопгеп6) и, представляющее собой элемент Я, а рр(и(х))— прямив»пенка часть (рг(ш111ое раг») п(х), являющаяся примитивным попиномом над Я. В случае, когда и(х) = О, удобно определить сонг(и) = рр(и(х)) = О. Комбинация лемм С и Н приводит к соотношениям сонг(и и) = а сепг(и) сопг(и), (4) рр( (х) и( )) = 5 РР(и(х)) Рр( ( )), где а и Ь вЂ” обратимые элементы, зависящие от пути вычисления содержимого, при- чем аЬ = 1. При работе с полиномами нзд целыми числами обратимыми элементами являются только +1 и -1, и поэтому удобно определить рр(и(х)) так, чтобы ее старший коэффициент был положителен; тогда (4) истинно при а = Ь = 1.
При Работе с полиномами над полем можно принять сопс(~) = с(и): так что РР(и(х)) будет нормированным полиномом; в этом случае (4) вновь выполняется при а = 5 = 1 для всех и(х) и и(х). Например, пусть мы работаем с полиномами над целыми числамн и пусть и(х) = -26хз + 39 и и(х) = 21х + 14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
