Разряженные матрицы. Р. Тьюарсон (984138), страница 20
Текст из файла (страница 20)
Доказательство. Если в матрице Аао (р,д+й— — 1)-й элемент равен нулю, но (йд+Й вЂ” 1)-й в (р,)'+й — 1)-й элементы — оба ненулевые, то из формул (5.4.1), (5.4.2), (5.2.2) и (5.4.3) следует, что (р,4+ й — 1)-й элемент матрицы А(ь+П будет ненулевым. Начиная с этого места, ход доказательстве настоящей теоремы совпадает с доказательствок теоремы 2.5.5 при условии, что СеЕ заменено 6)Е и матрица М является матрицей размеров и Х (и— — й + !), все элементы которой равны единице.
Эт) часть доказательства поэтому мы здесь не приводим. Приводимое ниже следствие непосредственно вы текает из теоремы 5.4.5, и на этом основании его до. казательство опущено. Следствие 5.4.7. Если на я-м шаге метода бЗЕ элемент а~,",~ выбран в качестве главного элемента, причем з ~ й, 1= 5+й — 1, а з и 5 определяются формулой уф= тт еЯе, (5.
4,8) для всех ~а<я1 ~я, ~ > г, с)й (г — некоторое подхс. дящим образом выбранное допустимое значение глав' ного элемента, а е! — 1-й столбец матрицы 1, к+1), гс локальное заполнение будет минимальным. Так как элементы всех матриц Тк вычисляются ас элементам всех матриц А~">, то минимизация локаль' ного заполнения всех матриц Аао будет минимизк' ровать число ненулевых элементов формы РР! пР" ,минимизация числа ненулевых элементов в форме РР! 13! уел топни, что обеспечение локальных минимумов приво„ит к глобальному минимуму. Это может быть рным для некоторых матриц, но не является таковым для произвольных матриц. Волее простой, хотя и менее точный метод выбора званого элемента, при котором локальное заполнение мало, основан на следующей теореме (Марко.
вич (1957)). Теорема 5.4.9. Если элемент а!с'!!+ „гдг ! > й, аз!бран в качестве главного элемента на й-м шаге метода 6!Е, то максимально возможное заполнение (нг обязательно совпадающее с реальным) дается формулой д!!в!! = (гссл! — 1) (с!м! — 1), (5.4.10) гдв )с, и )с — соответственно (и — 1+ 1)-мгрный и и-мерный векторьс-столбцы, всг элементы которьсх единицы, а г; — !'-й столбец матрицы !„ь+!.
Доказательство, Из формулы (5,4.11) видно, что слм и с!м обозначают общее число ненулевых элементов соответственно в 1-й строке и в (!'+я — 1)-м столбце матрицы А91, Поэтому максимум возможного заполнения, который может иметь место, когда (й!+ Й вЂ” 1)-й элемент матрицы Ам! выбран в качестве главного элемента, будет равен (г<м — 1)(см! — 1), что завершает доказательство, Легко показать, что у!се!! является (1, !)-м элементом матрицы 0в: из формул (5.4.10), (5.4.11) и на основании равенства в',.(х= )с'е =1 имеем л! а!сл! = (г',Вь'тс — 1) ()с'Вде —. 1) = = г', (В, )С, — )х) ()с' — )х') г, поэтому бл — — (В,7л — 1') Я'Ву — $'л).
(5.4.12) Дла того чтобы воспользоваться теоремой 5.4.9 в" есто формулы (5.4.8), будем производить выбор 13х . Гл. Б. Исключение Гаусса — Жердина главного элемента на й-м шаге с помощью уравнения ~ф>=ш!пе'/6 е (5.4.1 3) для всех )а//е>/+ь >(> е. Заметим, что главный элемент а',е> + о выбранный в соответствии с формулой (5,4.13), не обязательно приводит к наименьшему локальному заполнению. Приведенные в равд. 3.2 методы минимизации объема памяти для хранения формы ЕР1, основанные на априорной перестановке столбцов, могут быть также применены и для формы РР1.
Такая возможность вытекает из следующих соображений. При й = 1 уравнения (3.2.2) и (5.4.11.) одинаковы, н поэтому все с/и, уш и Хп> будут идентичными для ме/ ' / / годов СЕ и СЛЕ. Более того, в обоих методах СЕ н СЗЕ на (й+1)-м шаге главный элемент может быть выбран только нз последних л — й строк а столбцов.
Поэтому только последние и — и из вели. чин т/">, связанных с методом СйЕ, должны быть изменены на к-м шаге. Это вместе с тем обстоятельством что Вн — это матрица размеров и,>/',(и — й+ 1) (а не размеров (и — й+ 1) Х(п — Й+ 1), как в ме. тоде СЕ), позволяет нам иначе сформулировать тео. рему 3.2.12. Теорема 5.4.14. Если ненулевые элементы послед. них и — й+ 1 строк и столбцов матрицы ла> распре.
делены в этих строках и столбцах случайным абра. зом и г//и> есть число ненулевь/х элементов в!-й стра. ке матрицы А/н> для > ) й, тогда г//е+н — ожидаемое число ненулевых элементов >-й строки матрицы Л<"+» для» й — дается формулами г',""> = Г//е>, й>/ее> = О, (5.4. 15) та+и= Г/е>+ г'е' — 2— е — аич Ф О, (5.4,16) и — Ф /Ф д.5. Лодяодящие формы для метода 01Н 133 5.5. Подходящие формы для метода П.)Е Если главные элементьг последовательно берутся на диагонали матрицы А, начиная с верхнего левого угла, следующие формы, описанные в гл. 3, являются также желательными и для метода ОЛЕ: ВОР, 5ВВ(лР, ОВВЭР, транспонированная форма ВТР (нижняя треугольная блочная форма), транспонированная форма ВВТР (окаймленная нижняя треугольная блочная форма).
В гл. 3 уже были приведены методы, позволяющие преобразовать матрицу А к одной из этих форм, Подходящая форма для матрицы А, которая включена в некоторые программы для ЭВМ (Орчард-Хейс, 1968), определяется матрицами перестановок Р и Я, такими, что ! Ам А~з Ая О А„О О О Азг Агг О О Аяг Аяг Аяя РА11= А = 'де Агг и А44 — нижние тРеУгольные матРицы, а Ам— квадратная матрица.
Главные элементы выбираются последовательно из матриц 1, Агг, Агг и Ам. За исключением матРицы Аеь главные элементы выби- доказательство. Такое же, что и для теоремы 3,2.12. Итак, мы видим, что столбцы матрицы А могут быть априорно упорядочены в соответствии с возрастающими значениями всех со1, у'," или я)п и главные элементы выбираются согласно формуле (3.2.11), но значение део изменяется с помощью формул (5,4.15) и (5.4.16) вместо фоРмУл (3.2.13) и (3.2.14) (Тьюарсон (1966), (1967а); Орчард-Хейс (1968)). Как и в равд. 3.3, можно преобразовать матрицуА с помощью матриц перестановок строк (Р) и столбцов (Я) так, чтобы матрица А = РА(г имела одну нз форм, желательных для метода ОЗЕ.
Мы перейдем к рассмотренйю этого вопроса. 134 Гл. Д Исключение Гаусса — Жердина раются на диагонали. Заполнение имеет место толька в областях Ам, А„и А4з, когда главные элементы выбираются из матрицы Азз Это заполнение может быть минимизировано любым из методов, изложен. ных в равд. 5.4. 5.6. Библиография и комментарии Метод О3Е описан во многих руководствах по численному анализу, например Хильдебранда (1956), Фаддеева и Фаддеевой (1960), Фокса (1965), Рэлстона (1965), Уэстлейка (!968).
Форма РН описана у Данцига и Орчард-Хейса (1954), Гасса (1958), Хедли (!962) и Данцига (!963а). Примеры вычислений с применением формэя РГ! и способов сохранения разреженности даны Ларсоном (1962), Смитом и Орчард-Хейсом (1963), Вулфом и Катлером (1963), Диксоном (1965), Бауманном (1965), Тьюарсоном (1966, 1967а), Орчард-Хейсом (1968), Данцигом и др. (!969), Брейтоном н др. (1969), Билом (1971) и Де Бюше (1971). Сравнение форм ЕН и РН с точки зрения заполнения для разреженных матриц со случайным рас. пределением ненулевых элементов дано Брейтонои и др. (1969). Глава 6 МЕТОДЫ ОРТОГОНАЛИЗАЦИИ 6.1. Введение Во многих практических приложениях требуется преобразовать заданную разреженную матрицу в другую матрицу с ортонормипованными столбцами. Применение программ ортонормирования хорошо известно (Дэвис (1962)). В этой главе мы рассмотрим задачу определения оптимального порядка, в котором столбцы заданной разреженной матрицы должны быть ортонормированы, чтобы результирующаяся матрица была как можно более разреженной.
Нас будут интересовать методы ортонормирования Грима — Шмидта, Хаусхолдера и Гиеенса (Тьюарсон (1968а), (1970а) ). 6.2. Метод Грама — Шмидта Пусть А обозначает матрицу размеров т)~п, где т ) и, ранг которой равен п. Метод Грима — Шмидта заключается в определении такой верхней треугольнон матрицы О, что столбцы матрицы АО ортоиормнрованы (Дэвис (1962); Райс (1966)). Если матрица А разреженная, то, вообще говоря, предпочтителы<ей найти такую матрицу перестановок Я, чтобы я матрица АЯО, и матрица О были разреженными. Методы для осуществления этого будут рассмотрены в следующем разделе. В настоящем разделе мы рассмотрим слегка измененный вариант метода Грана — Шмидта, более точный по сравнению с обычным методом с точки зрения ошибок округления (Райс (1966); Тыоарсон (1968а)).
Он называется модифийированным методом Грима — Шмидта (ЙОБ) и состоит из п шагов. Если А1м обозначает матрицу к на- Гл. и. Методы ортогоналаааяии Х-й сноннец д-н сюрака Рис. 6.2.1. Элементарная матрица 1га на Э.м шаге. столбец и (1,1)-й элемент матрицы А1а1, то метод может быть в математической форме описан следующим образом: А +О=А1 ~У„, й=1, 2, ..., и, (6.2.1) где элементарная верхняя треугольная матрица 0г (см. рис.
6.2.1) дается формулой У» — — Гя+ еа(~~ — ег), (6.2.2) причем элементы вектора-строки С1а1 определяютса так: ИМ=0, 1< Ф; чалу й-го шага, й = 1, 2, ..., и, а Ап> =— А, то после „ шагов все столбцы матрицы А1н+и будут ортонормн. 'рованными. В матрице Аан первые й — 1 столбцов ор.
тонормированы, а й-й столбец ортогонален к ним. 1(а й-м шаге й-й столбец матрицы А нормируется, а по. следние 'и — й столбцов делаются ортогональными к нему. Результирующая матрица обозначается через А<а+'>. Если о1м и а<," ,обозначают соответственно 1хй дд Минимизация ненулевых элементов в методе нб$137 а<»/ / т <»/ а» /(й, 1 й, (6.2. 4) < (а<»т а<»/)» а<м — /, ' а<»>, / <»т <м» 1 » а<»"и = / 1) й. 6 такой форме метод К»зЬ обычно приводится в учебниках. Если А — квадратная матрица л-го порядка (и< = н), то из формулы (6.2.1) и из того факта, что обратная к матрице с ортонормированными столбцами равна транспонированной к ней матрице, следует, что ~<я+<у (6.2.6) Таким образом, метод КС<Ь может быть использован для вычисления матрицы А-'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
