Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 21
Текст из файла (страница 21)
Предположим, что задан алгоритм вычисления з = Нд, :1 "1 причем ранг по столбцам матрицы Н равен 1 Без потери общности можно предположить, что последний столбец матрицы Н счщержнт па крайней мере одна ненуяевой элемент (в противном случае ега можно удалить нз Н). Сеедавзтельно, переменная 4 содержится в некотором члене-произведении, скажем, последнем таком члеие. Эта означает, что для некстарога множества скаляров а, гумма ~ а,4 является множителем в некотором умножении, причем о, чь О.
Так как на скаляры не наложена никаких ограничений, то можно гюлагать и~ равным 1, так что член М -1- ! -1 д,' аг4 Явлнетса ыножителем внекотоРам члене-аРонэведенни. =е Чтобы завершить доказательство, нам надо при любом данном алгоритме решения исходной задачи построить, котя и искусственную, новую задачу ь' = Н'д ранга 1 — 1, которую можно решить данным алгоритмам, удаляя ез нега адно умножение. Тогда, согласно предпочожению нндук- икн, любой алгоритм решения новой задачи содержит по меньшей мере 1 — 1 умножение, н, следовательно, походная задача данным алгоритмом решается па меньшей мере с ! умножениями. Чтобы это сделать, заменим в исходной задаче переменную 4 г — 1 на — ~ а,до Тогда последний член-произведение, содержащий г=е г — 1 множителем сумму 4 -~- л) и,до будет представлять собой евое умаожение на нуль и, сггедавательно, может быть удален из алго- ритма.
Алгоритм теперь решает некоторую новую задачу, а именно, з' = Н'дй где д' представляет собой вектор ллины ! — 1, формируемый из вектора д удалением последней компоненты, а матрица Н' получается из матрицы Н заменой !.го столбца И, на столбец Вг — адо Таким образом, ЗЗ С р Окг гэ! Сз = (11 Р)8 = СН4. где ы Сэ = (1)РН, з = (А',' А")8, !Ха Г.З И стр с»атр н Гт и сэрюк и данный алгоритм вычисляет Н'й', что и завершает донаэатель.
ство О Теорема 3.8.3. Каждый аггоритм еычисггння лагсйяой сгсртка з (х) .= й (х) й (х), где бей у (х) = 1. — 1 и бейб (х) = Аà — 1, содержит ло мень. шсй марг 1. -1- У( — 1 умножений. Дохажтнгьстга. Рассматрннаемое вычисление можно а матрич. иом вчае записать равенством з=-Нй, является ДС -1- И вЂ” 1) х Дг)-матрнцей Как элементы ыножестэа Е (у,, йн ..,, 3,,), строки матрицм Н, очевидно, линейно нева виснмы, следовательно, применение теоремы 3.8.1 показывает, что число умножений равно по меньшей мере Е -1- У вЂ” !. О Теорема 3.8.4. Пусто р (х) гмллстся простым млоючгглом стс. лени л.
Каждый алгоритм гычисгсяая яроиэггдгяла млоюч смог г (х) = у(х) й(х) (шоб р (х)) содержит ло меньшей мере 2л — 1 умножений. Доказотсюстео. Предположим, по «лгоритм содержит умножений. Тогда на вмходе алгоритма получим линейную комбинацию этих ! членов-произведений з = АВ, где А является (л х !)-матряпей над полем Е, а 3 — вентор длины 1, гюмпанейтамн к!порога являются зтя члены-произведения. Ясно, что многочлены й (х) и й (х) «сегда можно выбрать так, чтобы сделать некоторую одну компоненту многочлеиа з (х) ненулевой, а остальные нулевыми.
Следовательно, а строк матрицы А должны быть линейно независиммми, так что А должна содержать н л линейно независимых столбцов. Без потери общности можно полагать, что первые л столбцов матрниы А являютса линейно независимыми, так что матрица А может быть разбита иа блоки аида где А' — обратимая (л х л)-матрица. Униатам на обратную к А' матрицу С: Так кап мнагочлеи р (х) неприводим, то можно показать, что нсе элементы любой строки матрицы Н линейно независимы, равно как и все элементы любой линейной комбинации строк матрины Н.
Это утверждение является стандартным результатам теории катрин н будет доказано отдельно в виде теоремы 3 8.6 з конце наставшего раздела Следовательно, все элементы первой строки матрицы СН линейно независимы, так что спгласно тео. реме 3.8.2 для вычисления нерпой компояснты вектора СНй требуется по меньшей мере о умножений. С другой стороны, первая строка вычисления содержат самое большое 1+ (г — л) умножений, так как ыатрица Р содержит 1 — и столбцаэ, а вектор 8 длины ! содержит все члены-произведения.
Слеловательно, ! -1- (! — л) )~ л, так что 1) 2я — 1, чта н доказывает теорему. О , В начестае приложения этой теоремм рассмотрим комплексное умножение как залечу умножения по модулю многачлена х' -1- 1. Согласно теореме 3.8.4, для выполнения одного комплексного умножения необходимо по меньшей мере три вещественных умнажсния. . Хотя мы н не будем этого делать, теорему 3.8 4 можно доказать и Лля умножения многочленов по модулю миогочлена р' (х), где р (х) — простой многочлен.
Вместо этого мы рассмотрим слу. чяй, когда р (х) распадается в произведение й простых ыногочленов. В этом случае ннтзйсная теорема об остатках псаволяег разбить задачу на й подзадач, каждая длины ла где ~ л, =- л. Дополнительных умножений при этом не вааникзег. Следовательно, используя для наждай из подзадач теорему 3.8.4, с помощью китайской теоремы об остатках длв полной задачи вычисления произведения многочленов па составному модулю получаем по меньшей мере ~'„ (2пг — 1) = 2л — У ! ! З.В Сг Р сэр э 122 .! о о -р, Го о о с, — !о н С-ь = (1!Р)5 з = (А' , 'А")5 122 Г.э.вн ри птртммистнз рок умножений Следующая те рема утверждает, что нг од н ал1оритм решения этой задачи не может быть лучше такого непользования кнтайцкой теореыы об остатках. Теорема 3.8.5. Пусть много«гсп р (х) степени л р сподсг пся е прсшггдсппс й различных пра тмс множителей.
Каждый алгоритм вычисления проигггдспия мпогочгспоэ г(х) = й(х) й(х) (шай р (х)) пюсржит по меньшей мере уп — й умножении. Доказатстстго, Так кан китайская теореыа об остатках задает не требующее умножений обратимое преобразование, то достаточно рассмотреть вычпслеане з = Нй, в катарам ьгатряца Н блочна.диагональная, т.
е н соответствую1цая китайской теореме об остатках 1-я подзадача задаегся вычислением з, — — Н,дь Теперь вовторнм доказательство теоремы 3 8.4. Предположим, что алгоритм содержит 1 умножеянй. Тогда ь = А5, где 5 — вектор длины 1, содержащий все члены-пронзведення„' н А представляет собой (и х 1)-матрицу над полем Е. Так как! А «одержнт п линейно независимых с~рок, то она содержит н и линейно везависпмых столбцов, в «ачесгве которых можно еыч брать первые и столбцов.
Тогда где С обозначает матрицу, обратную к матрице А'. Следовательно, для вычисления первой компоненты вектора Сг требуется самое больпюе ! — (1 — п) умножений. Но, кроме того, выпол- настоя равенство Се=С~ "'. й, Рассмотрим теперь некоторую лннейнуго комбинацию строк матрицы Н. Любая линейная «омбннация строк каждой из матриц Н, содержит лишь линейно незавнснмые столбцы. Слеловатедьно, дюбвя лннейно независимая комбвиацня строк матрицы Н со.
держит по меньшей мере и — (й — !) .чннейно неаавнснмых столбцов, Следовательно, по теореме 3.8.2 вычисаение гервой коыпонегны вектора СНй требует па меньшей мере л — (й — !) умножений. Эгн верхняя н ннжвяя границы числа умможеняй, необходнмых для вычнслення первой компоненты вектора Се, приводят к неравенству ! -(- Н вЂ” а) ) л — (й — 1), так что 1) 2п — й, что доказывает теорему. П Теперь мы должны завершить незаконченное доказательство теоремы 3.8ХС Теорема 3.8.5. Лусть э = Нй лредапааллст собой мотричпую запись произведения миогочггпсе г (х) = й (х) й (х) (шой р (х)), гдг р (х) — неприоодимый лиогочлсщ и мшприца Н составлена из коэффицшитог мпогочтпа й(х).
Тогда осе глсм пты любой строки матрицы Н, тая жс «ок и есс злсмсипгьг любой линейной комбинации строк матрицы Н, лопсйио пюаешимы Дотют1ыгьслыо. Шш 1. Обозначим через С Р сапрстждпюитую матрацу мпашчлепа р (х), определяемую следуюгцей (» х а).матрнцей: Тогда 1-й столбец матрицы Н раве» Сгй, н через свои векторстолбпы матрица Н записмвается в ваде Н вЂ” — [8 Сгй С,й .. Сг 8). Пусть тч — произвольная ненулеван нектар-строка, а мН соответствующая линейная комбинация строк матрквы Н. Надо показать, что никанан линейная комбинация столбцов мН не равна нулю.
Предположнм, что / ".г б = ~ а,(нСгй) = [м й' огбг~й 1-О 1-С гы Гл 3 Б р ырнмм«р с р Так кбк зто равенство должна выполнятьсн для любого й, то и а(С«) =О, где — 1 а(С«) = ~ агСог г-о цредставляст собой матрацу размера л х и, вычнслснную по матраце Сг. Поскольку страда и отлична от нулевой, то матрнца а (Ср) должна быть выражценнай, так нак в протнвном случае и а(Ср) не может равняться нулю Слеловательна, нам нала показать, 'гго едннственныы многочленом сгепенн не более л — 1, таким что подстановка в него матрацы Сэ прнвоюи к вырожденной матрице, является нулевой многочлен. Шаг 2.
Легко цравернть, чта любой простой многочлен р (х) обращается в нуль прн подстановке в нега его сопровождающей матрацы. Таким образом, р (Ср) = О, где О обозначает нулевую (и х л).матрнцу. Пусть а (х) обозначает многочлен степени не более — 1, такой то этрнца а (Ср) аыражденна, н пусть обозначает ненулевой вектор нз нулевого пространства матрицы а (Ср). Тогда, тан как р (х) является непрнводнмым мнагочленом степени л, то существуют мнагочлены А (х) н Р (х), такие что А (х) а (х) -1- Р (х) р (х) = !. Следовательно.
(А(Ср)а(Сэ)-(-Р(Ср) р(С»))ч =1ч. Но р (Сэ) = О, так что мы змеем Д (Гр) а (Ср) ч = ч, что про' тнворечнт выбору т: а (Сэ) ч = О. Следовательно, за нсключеннем нулевого многачлена, не существует многочленв а (х) степенг~ л — ! нля меньше, таггого что матрица а (Ср) является вырождсн.
ной. Эю завершает доказательство теоремй. () Задачн 3.1. в. Ко лс«сны умномю 1 +Ш= ( +ге)( + )Л)» о вмчвыиь У ямн эя рэт у с=- (о — Ыд.г- ( — 4, 1= (с--ь)44- ь( -1-а) Р У Пал. с Л форме гл д В р д а ой р ц родс»мин«й «посоле»е й, б. 2-ычы и юм««с рты г(*)=3()л(*) 1 л ' — и юми Г ! ~ ~1 Г пртлп о, мниочлюн л(*) э а() о влек «е фр- тв«в рыл«чуется сбмюмм ынчы м б 7 е.Прдсавньтнрь олнмеввхд д м юл ве гю гннэм р «вмпкыгь сб д й юр менял«н Спмько вемсс«еенмы сн й оде ми иог го 7 3.2. ПР звдюнон ус розою зл» В . ейной вер кн дву«пылел — 1 в чылення вы«ный «орры г «*й фуыц А' л, Иг и«пг лг=о д льнымй. З.З.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
