Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 27
Текст из файла (страница 27)
4. а) преобразований являются проекторами? б. Пусть Т ~ Еш) (Р). Нулевым подпрострааством (ядром) Т называют мно:кестзо Л'(Т), определяемое соотпошепном Л'(Т) (х ж У: Тх=О). Доказать, что Л'(Т) является векторным подпространством У. Доказать также, что образ Т является векторным подпространством 1~. 7. Пусть Р— векторное пространство над 11 в Т <и ~ Епд(1'). Говорят, что Т имеет действительное собственное заачелие Х ю 11, если существует ненулевой вектор х <и р такой, что Тх =Хх; при этом х называют собствелньт вектором Т, соответ- ствующям собственному аначеппю Х. а) Докавать, что если Т~и Епд(Р) такое, что Т(х, р)=(х+ау, р), то любой вектор вида (р, 0) прн рФ 0 является собст- венным вектором Т. Какие у Т собственные значения? б) Пусть Т ю Епд( Р).
Обозначим через Р, множество собственных векторов Т, соответствугощит собственному значению ?. Показать, что Р,О (01 является векторным подпрострапстзом Р. Доказать аналогичное утверждение для Л'(Т). 8. Пайти собственные значения и собственные векто- ры преобразований Ть ТзжЕпд(йт): Т|(х, р) (-р, х), Тз(х, р)=(х, — р). 1"акой геометрический смысл имеют Т~ и Тз? 9. Доказать, ч7о а) если Я, Тж Епд(У), то Юе Т ~и Епд(Р); б) если при ТюЕпд(Р) существует преобразование Б: Р- 1" такое, что Я ° Т Т ° Я ?г, то 8ы Епд(Р)„' в) если Т~Лп1(Р), то М'(Т) (01.
10. Доказать, что если гп ти та е йз и Хюй, то а) г3 '(тз+тз) т1 ' тз+ г! 'Гз1 170 б) Х(г~ гг) (1г~) гз = г~ '(Хгз)! в) 1г~ гз1 К !!г~ ! !!гз!!! г) !!г~ — гзР !!г,!!т+ !!гз!Р— 2!!г~~ !!гз!! соз О, где 8 — угол между г~ и гз! д) 1!!г~!! — !!гз!!1 ( !!г~ + гз!! я.= !!г~!1+ !!гз!! (последнее неравенство известно как неравенство тре- раольникп). Дать геометрические иллюстрации зтим ре- зультатам.
В действительности вышесказанное имеет место для любого пространства со скалярным процзведенпем; в ча- стности, результаты справедливы для К" (я ~+ М) с обыч- ным внутренним (скалярным) произведением. 11. Вычислить единичные векторы, параллельные а) а=(т, 1, з)! б) Ь-((, р, О), р = К. Определить единичный вектор, ортогопальньтй а и Ь од- новременно. 42. Пусть а, Ь, с ~и К' и ) ыК. Доказать, что а) аХЬ -ЬХа; б) аХ(Ь+с)= аХЬ+аХс; в) (йа) Х Ь вЂ” а Х(ЛЬ) = й(а Х Ь); т) йХ) К,) Хй=~ !сХ! =)! д) аХ(ЬХе)-(а с)Ь-(а Ь)с; е) а (ЬХе) Ъ (сХа)- с (аХЬ) -а (с Х Ь) -Ь (аХс) -е.(ЬХа).
тЗ. Используя результаты 5.4, т2, доказать, что опе- рация Х: Кз Х К'- К' не ассоцяатпвна, т. е. в обтцем случае аХ(ЬХс)Ф(аХЬ)Хс. 14. Пусть т, и: К вЂ” К'. Доказать, что и ля л а) -,(( й) т —, + —, к! Л б) л, (( Х й) = ( Х У + —, Х й —,— „" Х ( — й Х у', в) если В(г)!! а для всех 8, где аыК вЂ” постоянная, то Л/й ортогонален к $ при всех й Провестп вычисле- ния при $(." — (а соз ~, а з1п ~, 0), д(~) =(О, 1, ~).
$?1 $5, Решетки и булавы алгебры Булеза алгебра является одним из математических объектов, с которыми мы уже сталкивалвсь во введении. 51ы покажем, что существует не одна булеза алгебра, а много. Следовательно, любое преждевременное использование этого объекта моягет привести к ведоразумению. Тем не менее мы качнем изучение с введения более общей структуры, пазываедшй решеткой. Некоторые из решеток имегог важное эначепие в абстрактной теории вычислений, возникшей из понятия аппроксимации. Одна программа аппроксимирует другую, если опа осуществляет те же самые вычисления на подмножестве данных, доступных той программе. Если же рассматривать результат работы программы как множество, то одна программа аппроксимирует другую, когда для некоторых входных данных она выдает в качестве результата подмножество В гэ А, где А — множество выходных данных второй программы.
Это достаточно простые и, вероятно, очевидные способы аппроксимации программ. При этом возникает мпон~ество злементов, связанных некоторым отношепием порядка. Вычпслепие является результатом выполнения программы (ва некоторых данных), которая написана на каком-либо языке (см. гл. 8). Для общности рассмотрений свойства вычислений пало выводить ие в терминах рассматриваемой про1раммы, а в терминах языка, используемого для записи про~рампы, В то же время мы должны быть в состоянии определить результат выполнения программы «язык Хз с помощью формального определения. Н сон<алевию, количество деталей, требующихся для описания даже простых примеров, достаточно велико и, следовательно, ничего ве определяет. Одпако в и. 5.1 мы дадим теоретические обоснования некоторых ключевых результатов.
Это будет следовать (п. 5.2) из формального использоиапзя булевой алгебры, а затем (п. 5.3)' пз краткого рассмотрения некоторых общих приложении. 5.1. Решетки. Напомним, что бинзрпое отиошеппе р на мпоягосгве 8 является частично упорядоченным огношением, если оно рефлексивно, транзитивпо и анти- симметрично. Следовательно, (Я, р) — частично упорядочепное мпожество, и, если ие возникает двусмысленности, р можно записать как -, а (Я, —.) обозначить просто через Я. '!эстичио упоридочгииоо миожсстэо называется лиисйио упорл0очелиьт (или целью), ес:ш для 172 любых х, уж Я или х < у, или у < х, или же выполнены оба зти отиошеиия.
На самом деле любой частичный порядок можно представить в виде объедияевпя линейиых порядков. Поатому вовлекает естествецпый и полезиый способ изображения отношений порядка. Замеп1м, что любое конечное, лввейпо упорядочевпое множество (А, ~) молшо представить следующим образом: а~ < а» < ... < а.; Г" Ф2 Ряс. 5.5 Рве. 5Л Докавательсгво етого факта оставляем в качестве упражвепия.
в" Используя этот результат, моя'по представить любой частичный порядок (конечкый вли бесковечпый„одиако бесковечпые отвошевпя сложно изобразить па конечных листах бумаги за коле шое время!) изображепием множества соответствующей цепей. Получецвая диаграмма называется диаграммой Хасса. Пример 5.1. Отношение р ((х, у): х — множитель р), определепноо па мнон~естве (1, 2, 3, 4, 6, 10, 12, 20), дает диаграмму Хасса (язобраясеппую па рис. 5.8) и»»ожет быть рзвбито ка лпвейпо упорядочепвые подмяоя<ества ((1, 2, 4, 12), (1, 3, 6, 12), (2, 6), (тц 20), (2, 10, 20)).
Зтому раэбпешпо эквивалентно следугощее 173 здесь рефлексивпость и травзитлвность не требугот доказательств. Легко видеть, что рве, 5.7 является »очевидным» представлеппем (А, <). Другими словами, мы записываем А как (ан аг, ..., а„). П р е д л о ж в п и е. Частичное упорядочение на конечном мнолсестее может быть представлено как объединение линейных порядков на некоторых подмножествах.
множество линейных порядков: ((2, 6, 12), (1, 3, 6), (1, 2, 10, 20), (2, 4, 20), (4, 12)), Заметим, что по сразнепп>о с отношениями, изображенными на диаграммах в $2 гл. 2, хотя 1рх для всех х >и (1, 2, 3, 4, 6, 10, 12, 20).
па этом рисунке отсутствуют восемь стрел, выходящих па 1. Это достигается неявным представленнем свойств рефлексявпоств и трапаптнвности. в Пусть дано (А, ~) н  — А. Разумно аадать вопрос: будет ли В ограничено сверху (свпзу) элементами множества А) Далее мы можем искать наименьшую верхнюю грань (наибольну>о нижнюю грань), которая обозначается зпр (!п1) (читается супремум (инфпмум)). Эти понятия были полностью определены в $5 гл.
2. Будем пх использовать для характеристики решетки. О п р е д е л е п и е. Рви>етяой называется частично упорядоченное лн>ожестзо (А, (), в котором каждая пара элементов имеет супремум н нпфимум. Для заданных х, у >и А зтп грани будем записывать следующим образохн х Л у = 1п1((х, у)), х ~/ у = зпр((х, у)), К Не всякое частично упорядоченное множество является решеткой. Например, частично упорядоченное множество пз примера 5,1 не является решеткой, поскольку 12 ~/20 не определено. Определив оперзнии Л и Ч между парами элементов в частично упорядоченном»пон>естзе, расширим это понятие естественным образом. Положим Л Х Лвнхх=1п1Хю 9 Х Чватх зпРХг Это обозначает зпр Х п 1п1Х конечного пепустого множества Х. Легко показать, что существует много специальных видов решеток, в которых можно производить рааличпыа операция.
Ограничимся рассмотрением трех тагих типов. Определепие. Решетка Ь, обозначаемая (йч Л, '»'), дисуибутивни, если она подчиняется дистрибутивным аакопам хЛ(уЧз) = (хЛуЫ(хЛх) хЧ(уЛ'з) -( Чу)Л( Лз) для всех х, у, з ы Г,. в" Не все решетки являются дистрибутивными. 171 Пример 5.2. Решетка, пзображеппая яа рис. 5.9, ве является дпстрпбутпвкой, поскольку Ь|~(с(~/с) = Ь/~в Ь, тогда как (Ь/~б)~/(Ь/~с) = а~/а = а.
в" Предложен ие. Пусть в дистрибутивной решетке (Б, /Х, )/) выполнены соотношения '/у = хЧг хЛу= хЛг Тогда у г. Доказательство. Сначала с ааметим, что из определепяя ш1 и бпр а) аДЬ Ь/~а, а~/Ь = Ы/а; б) а/~Ь~а(а~/Ь; Рис. 59 в) (а/~Ь)~/а = а, аИа~/Ь) = а. Позтому у уЦ(у~,х) уЦ(г/~ х) (у~/г)~,(у'/х) -(г'~/у)/,(гЦх) г'/(у/,х) = г')/(гДх) = г. в" Определепие. Предполояпи, что (Л, /~, 7)— решетка и О, 1ыХ такие, что 0<к<1 для всех хыу (об влемвптах 0 и 1 скажем немного позже), Тогда х~/1 1, х/~1= х, хДО О, х~/О =х для любого хвв,б.
Такая решетка яазывается решеткой з дополкеквями, воли для любого х ы Е существует Уж ° в.б такой, что х/~х О, х~/х — 1 (х казывают дополнением х), в Предложение. Если (Е, /~, ~/) — дистрибутивная решетка с двполпвниями, то дополнения единственны. До к а з ат ел ь с т в о. Предположим, что х, у, г ж Ь и х~/у х~/г( 1), х/1 у = х/ г(= 0). Тогда ив предыдущего предлоткепия следует, что у г. в" Третий, и яоследяий специальный тип решеток, который мы определим, необычен в том смысле, что оя не дает яам ничего нового для конечных решеток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
