Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 9
Текст из файла (страница 9)
Г-0 3'-0 Компоненты векторов ч н У принадлежат полю 6Р (б), и вся арифметнна ивляется арифметикой паля 6Р (5). Если 13 47 2Л. Оек оо и Ро Р яа Гз 2. В д не зшрш тм шгюзу та одномерное преобразование Фурье вектора т равно Определение 2.3.2. Пусть Š— поле. Подмножества в Е называется падлояем, если она является полем относительно насле. дуеимх операций ело;кепи» и умвоження, исходное поле Е в этом случае называется расширением подпола.
Поле рациональных чисел является подполем поля вещественнык чисел, «оторое в свою очередь является подпалем поля ком. плексных чисел. Поле комплексных рациональных чисел ве яв. ляется цодполем поля вещественных чисел, но является подпалем поля комплексньш чисел Легко видеть, что конечное поле бЕ (2) является подполем поля бр (4), так как элементы О и 1 склалываются и умно зются в и ле ОЕ (4) ак же, кап з поле ОЕ (2). Однако бЕ (2) не являетсн подполем ни поля бЕ (3), ви поля бр (5). Чтобы доказать, что некоторое подмножество поля является оадполем, веобхадимо докззать только то, что оно содержит ненулевой элемент н замкнуто относительно сложения и умножения.
Все остальные необходимые свойства наследуютсн иэ поля Е Обращение по сложению илн уивожение на элемент Р входят в порождаемую элемеатом р циклическую группу соответственно относительно операций сложения или умножения. Каждое поле содержит в качестве подмножества множество своих целых , †(1 + 1 -1- 1), †(! -1- 1), — 1, О, 1, 1 .1. 1, 1Ф) 1. 1, Целые поля обычно запнсывнются просто как О, ж1, ~2, ~3, .... Поле может содержать только конечное число целых, и в этом случае такое число называется хприкшериаиикай поля. (Оно всегда просюе.) Все элененты палей бр (3) н ПЕ (5) являются целыми, так что характеристики полей равны соответственно 3 и 5. Так как в поле ПЕ (4) пелмми являююя только О н 1, то характе.
рнсгнка этага поля равна 2. Характеристика н паля веществен. ных чисел, и поля комплексных чисел равна . Каждое пале харантеристики оз содержит пале рацнональнмх чисел (илв его изомарфную копию). Вел» пале имеет конечную характеристику р, то целые этого поля образуют циклическую группу па сложению; следовательно, сложение целых паля представляет собой сложение па модулю р, где р — число иелых паля. Сумму и копий единицм поля будем записывать в «иде Кл)), где двойные скобки обозначают вычисление по модулю р. Конечное поле задает групау двуми путями: все элементы поля образуют группу относительно сложения и все ненулевые элементы поля образуют груоиу относительно умйожения.
На самон деле па умножению ненулевые элементы паля образуют циклическую группу Доказать зто утаерждениег трудна, и мы отложим доказательства до гл. 5, но пользоваться цикличностью этоЙ структуры будем раньше Так как по умножению множество ненулевых элементов группы образует цикличккую группу, то она порождается одним элементом определение 2.3.2. Примипшвямм элементам поля Галуа ОЕ (4) называется элемент порядка (4 .. 1) относительно умно.
жения Он порождает мультипликативную группу поля. Например, в поле ПЕ (5) степени элемента 3 ривны 3' .. 3, 3' — 4, 3' — 2, 3' — 1. Следовательно, 3 — примитивный элш и т ол«бЕ (5) 2дК Векторные врострвиствв Для заданного поля Е я-последовательность (ом и, „, о„,) элементов поля называется ееюпором длины я пад нолем Е.
Мне. жество всек таких векторов длины и вместе с двумя заданными иа «ем операциями — с,яожеижм шкшороа и ум озгенжм яо око. Яяр =называется шшнариым проспграшпеом вад полем Е. При рассмотрении эекторвмх прострааств элементы паля Е, над которыми страются векторы, называются сколлроми. Умножение на скаляр — зто операция, связывающая вектор т с элементам юля с по правилу с (и, иг, ..., о„г) =(ю. сот,, мг„т).
Векюрвое сложение является операцией сложения двух веитарав, т = ч' -1- т", выполняемо~о по следующему правилу: (46, ой..., а.'..б 4-(аа, ио. ойп) = — (по+по ог-) о( о м 1 о -1)' Векюрвое пространство я-носледоват*лшкютей представляет собой один пример векторных пространств.
Векторное пространство вад полем Е можно определить абстрактно нак множество у элене~язов (именуемых векторами) с двумя заданными на нем операцияив. Первая операция оаределеиа на парах элементов из У, называется сложением егюлорое и абозначашся плюсом. Вторая операция определена на элементе из У и элементе из Е, дает в результате элемент из !' и называется умножением яа око. Яяр; для обозначения такай операция зтн элементы записываются И Гк Х Оосх е зс !маг гю * ысот т Ь В к «огне про тра с'в рядом.
Для того чтобы У было векторным пространством, эги операции должны удовлетворять следующим аксиомам. !. У представлвет собой абелеву группу относительно авера. ции сложения лекторов. 2. (Двстрнбутнвиый закон.) Для любых векторов чм ч„ и лю. бого сквляра с с (ч, .(- ч,) = сч, -(- т е 3 (Дистрибутивный заяои.) Дла любого вектора ч н любых скаляров с, н с, выполняется !.т = ч и (с, -(- с,) ч = с,ч + сщ . 4. (Ассоциативный закал.) Для любого нектара ч и любых скаляров с, и с, (с,с,) ч = с, (с,ч) Ну евой элемент из У называетса и ч см оордикат н обозна.
чается через О. Отметим, что мы использовали символ (- двумя разлвчиыми спасабамн: для некторнога слаженна н хля слажена а оле. Огмегим ~акме, что мы использовали символ О длн обозначения нулевого элемента поля и символ О пля обозначения начала координат векторного пространства. Это неопределенность практически не приводит к недоразумениям Подмножество вектарнога пространства называется ееюпоркым кодлростракстеом. если ано само является векторным простраяством относнтелыю исходных операций слаженна векторов и умложення вектора на скаляр. Огиосительно счожеииа векторов векторное пространство янляетсз группой, а векторное продпрастранстеа — подгруппой. Для того чтобы проверить, пвляется лн непустое подмножество венторнога пространства подпросгран. сгвом, нн«О»адика праверигь тельно замкнутость падмгюжестеа относительно сложения венторов и умножения векторов на скаляр. Замкнутость относительно умножения на скаляр гараяти.
руст принадлежность подмножеству нулевого вектора. Все остальные требуемые свойства маследуются из исходного пространства. Векторное простравство л-последовательностей над Р обозначается через Рц В этом пространстие сложение векторов и умножение вектора на скаляр определены покомпонентпо В Р" имеется еще одна операция. называемая локоллокекткым лроиюсдекисм двух векторов. Если и == (ам аь ..., а„ Н н ч = (Ьм Ьь Ь„,), то нокоыповевгное произведение определяется равенствам пг = (а,Ьм о,бо ..., а„,Ь„,).
Оно представляет собой вектор, компоненты которого получаются в результате перемножения компонент векторов и и ч Скаларкмм ироизтде ием двух л последовательностей иа Р„ называетсн скаляр, определяемый равенстооы и ч =(ам,.., о,,) (Ье..., Ь,,) =а,Ь, (- ... +а„,Ь» о Ненедленна проверяется, что и.ч = ч и, (си).ч = с (и.ч) и что также и.(п -(- ч) = (м.и) -)- (нач). Если скалярное произведение двух векторов равно нулю, та векторы называются ортагокальными. Над некоторыми полями возможна орюгональность кенулевых векторов самим себе, ео зто невозмаж*о над полем вещественных чисел. Вентор, ортагаиальиый я каждому вектору нэ данного множества, называетси ортогональрым к этому множеству.
Теорема 2.4.!. Пусть У вЂ” мкторкт прттракгтю л-послед еотгльксстсй кад лелем Р, ссдержаигге лсдпрттракстло В'. Мкожестзо ескторое, ортагокзльиы» к ОУ, само образует лод. пространство. Докаэательстзо. Пусть У обозначает множество всек венторав, ортогональных к В' У не пусто, так как О принадлежит У. Пусть м — произвольный вектор из В', а п, и е, — некоторые векторы нз У. Тогда м. и„= м. п, — О н м.и,-(-к и, =О == тч (н,+ из), так что и, —, п, также вектор из У.
Далее, м.(сид =- с (м.е,) = О, так что си, также вектор нз У Следовательно, У является подпространством. (2 Множество всех нектаров, ортогональных к надпространству ОГ, называется орттакильиыр дола»некием надпространства В' и обазвачается через В'« В векторном пространстве и всех л-последовательностей над полем вещественных чисел пересечение надпространств Ог и йг«содержит только нулевой велюр; но в векторном прострзнстве над ПР (у) подпростраиство В'«может иметь яегриннальнае пересеченве с йг нли может даже лежать в В', свдержать Ог и совпадать с В' Например, надпространства из двух векюров (ОО) и (! !) пространства ПР* (2) является своим ортогональным дополнением. В векторном прострапстве У суммз вида п =- аП, В а,ч, -)- ... + аьчь, где а, — скаляры, называется зокецкол комбинацией векторов то , чь.
Говорит, что множество векторов порождает линейное пространство, если каждый вектор этого пространства представим в виде некая линейной комбинации векторов нз этага множестна. Тогдн говорят также, что такое линейное пространство натянуто на зто множество векторов Линейное пространство, которое на. тянута на конечное множество векторов, иазываетск кокечкомгр. км,и зсюпоркым пространством. Число векторов в наименьшем множестве, порождающем некое пространство, называется размерностью этого пространства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
