Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 7
Текст из файла (страница 7)
2 8. МЕТОД;йКОРДАНА (ГАУССА-'йКОРДАНА) Пусть требуется решить линейную систему Ах = Ь, А е М„вида (4.1). Первый шаг метода Жордана сопадает с первым шагом метода Гаусса: система (4.1) преобразуется к виду х1 + а1я х2 + ... + аг„х„= Ь, (') бй бй (1) (Ц бй 022 Х2 + ° ° ° + И2и Х~ = Ь2 (1) ачгхя + ... + а(ц х„= Ь(') по тем же формулам Ь, =Ь1/ам, у =2,...,п, (ц Ь; =Ь; — Ь, ап, з,,)'=2,...,п. а1 — — а1,/ам, (1) а1 =а1,— а1 ан, (й-ц (й-ц (й-ц хй 1 + ай, „хй +...
+ ай, „х„= Ь„, (й-ц (й-ц (й-ц ай й хй +... + ай „х„= Ь (2) а„й хй + ... + а(й„ЦХ„= Ь(" ') Предположим, что а й ~ О. Поделив й-е уравнение системы (2) на айй (й-ц (й — Ц перепишем его в виде (й) (й) (й) хй + ай й, 1хй.11+... + ай„х„= Ь„, К.Ю.Богачев Точные методы решения линейных систем После Й вЂ” 1, Й = 1,..., п шагов метода Жордана система (4.1) преобразована к виду (й-Ц (й-Ц (й-Ц Х1 +а1й хй+...+а„, х„=Ь, (й-ц (й-ц (й-ц хе + 11г,й хй + .. + ая х„= Ь2 ~8. МЕТОД ~КОРДАНА (ГАУССА-БОГДАНА) где (й — 1) (й) ~й) Ч (й — 1) айй (й — й) ь'") = ' айй (4) 3 = и+ 1, ° Умножим уравнение (3) на а;й и вычтем его из г-го уравнения системы (2), (й — 1) г = 1,..., п.
В результате система (2) примет вид (й) (й) (й) + а,й 1хй+1 +...+ а,„х„= 6, (й) (й) (й) + а~й,,хй~1 +...+ а2„х„= 62 х2 (й) +ай, й,,хй+г (й) хй+ ай й+,хйч.1 (й) ай„„, й„,хйч.1 +...+ай, „х„=бй, (й) (й) (й) (й) +...+ ай„х„= 6й (й) (й) + ° ° ° + а~~1,чх~ = ьй ~1 хй 1 (5) а„йч,хйч., +...+ а„„х„= й„ =й~) где (й) (й-1) (й-1) (й) а; = а," — а;й ай 5()=5( ) — ( )Ь~) "й г = 1,...,п, г ~ Й, ) = Й + 1,...,и. г=1,...,п, гфй. Метод Жордана удобно применять для нахождения обратной матрицы. При этом вместо правой части 6 используется набор правых частей, состоящий из и столбцов единичной матрицы, над которыми одновременно производятся преобразования, задаваемые соотношениями (4), (б).
После проведения п шагов метода джордана этот набор будет состоять из столбцов обратной матрицы А '. Поскольку на каждом шаге метода джордана подматрица А~й ') (а;, );, й „- та же, что на соответствующем шаге метода Гаусса, то метод (й — 1) джордана осуществим тогда и только тогда, когда осуществим метод Гаусса, т.е. когда все главные угловые миноры матрицы А отличны от нуля. Оценка количества арифметических операций в методе Жордана 1. На вычисление ай) при у' = й+ 1,...,и, й = 1,...,п по формулам (4) требуется Я,(п — й) = п(п — 1)/2 = О(п2) (и -+ со) операций деления. К.Ю.Богачев Точные методы решения линейных систем Выражения (4), (6) являются формулами перехода от системы (2) к системе (5).
Если обозначить а~") = а;„6) = 6;, г, у = 1,..., п, то переход от системы (4.1) <а) <о) к системе (1) будет осуществляться по тем же формулам при й = 1. После проведения вычислений по формулам (4), (б) при й = 1,..., и матрица системы (4.1) станет единичной матрицей. Следовательно, правая часть системы содержит искомое репгение: х; = 5;", 1 = 1,..., п. 39. ПОЛОЖИТЕЛЬНО ОПРЕДЕЛЕННЫЕ МАТРИЦЫ 33 2. На вычисление а~ ) при т' = 1,..., п, т' ф й, )' = й+ 1,..., и, й = 1,..., п по формулам (6) требуется Я,(п — Й)(п — 1) = (и — 1)~п/2 = пг/2+0(иа) (п — + сс) операций умножения и столько же операций вычитания.
3. На вычисление бь при й = 1,..., т~ по формулам (4) требуется п операций (й) деления. 4. На вычисление о) ) при т' = 1,..., п, т' ~ й, /с = 1,..., п по формулам (6) требуется ~ "„,(и — 1) = и(п — 1) = 0(п ) (и -+ сс) операций умножения и столько же операций вычитания.
Таким образом, метод 2Кордана требует 0(п~) + иг/2 + и+ 0(п ) = иг/2 + 0(п~) (и -+ сс) мультипликативных операций и столько же алдитивных операций. Всего: иг + 0(п~) (и -+ сс) арифметических операций. По аналогии с методом Гаусса можно строить метод Жордана с вибором главного элемента. Именно, в подматрице А = (а;, ),3 — ь,„,,„(совпадакт(ь О (ь-1) щей с подматрицей из метода Гаусса) той же процедурой, что и в методе Гаусса, выбирается главный элемент. 3 9. ПОЛО;ЖИТЕЛЬНО ОПРЕДЕЛЕННЫЕ МАТРИЦЫ Определение. Матрица А Е М„называется положительно определенной (обозначается А > О), если для всех х Е С" выражение (Ах,х) вещественно и (Ах,х) > О для всех х Е С", х ~ О (здесь (, ) означает обычное скалярное произведение в С", (х, у) = у*х, где у* = (дм..., д„), черта над символом обозначает, как обычно, знак комплексного сопряжения).
Если рассматриваемая матрица А вещественна, то часто положительно определенной называется матрица А, для которой (Ах, х) > О для всех х Е К", х ~ О. Замечание 1. Если матрица А Š̄— самосопряженная (т.е. А* = А), то выражение (Ах, х) вещественно для всех х е С".
Действительно, (Ах,х) = (х, А*х) = (х, Ах) = (Ах, х) и потому (Ах,х) вещественно. Лемма 1. Если матрица А полоэкительно определена, то она невыроэкде- Доказательство. Предположим противное, с)е$А = О. Тогда линейная система Ах = О имеет решение х е С", х ~ О. Для этого х выражение (Ах, х) = (О, х) = О, что противоречит положительной определенности матрицы А.
Лемма 2. Если льатрица А положительно определена, то для нее сущестпвует ЬЛ -раэлоэкение. К.Ю.Богачев Точные методы решения линейных систем ~9. ПОЛОЖИТЕЛЬНО ОПРЕДЕЛЕННЫЕ МАТРИЦЫ Доказательство. В соответствии с теоремой 4.1 нам надо проверить, что главные угловые миноры положительно определенной матрицы А отличны от нуля. Определим отображение хв,1 пространства С" -+ С", й ( и действующее по правилу: для всякого х = (х1,...,х„)' е С" хйй = (хы...,хь)' е С".
Это отображение есть отображение "на", т.е. для каждого элемента х = (хы..., хь)' е Сх найдется элемент х е С", являющийся прообразом х при этом отображении (например, х = (хм..., хг, О,..., О)' е С"). Поскольку матрица А положительно определена, то для всякого й = 1,..., и и всякого х Е С", такого, что х~г~ ~ О выражение (Ах~ь~,х~ь~) вещественно и положительно. По правилу перемножения матриц (Ахр,~,х~ь~) = (Агх~ь~,х~г~)ь, где ап а1г ... апс а21 а22 " агг Аь = аы аьг ...
аьь -главный угловая подматрица А, ( „)ь — обычное скалярное произведение в пространстве С", (х, у)г — — у"х, х, у е С". Следовательно, выражение (Агх, х)ь вещественно и положительно для всех х е С, т.е. матрицы Аь е Мь, Й = ь 1,..., и положительно определены. Пользуясь леммой 1, получаем, что матрицы Аь, й = 1,..., п невырождены. Из теоремы 4.1 теперь вытекает требуемый результат. Лемма 3. Самосопряженная матрица А Е М„, положительно определена тогда и только гпогда, когда все ее собственные значения вещественны и положитпельны. Доказательство. Пусть А Е М„самосопряженная положительно определеная матрица, Л вЂ” ее собственное значение, х ф Π— соответствующий собственный вектор: Ах = Лх. Умножим это равенство скалярно на х, получим (Ах, х) (Ах,х) = Л(х,х) и Л = ' .
Поскольку (Ах,х) вещественно и положитель- ~И' ' но, то Л > О. Пусть А Е М„самосопряженная матрица и Л; > О, 1 = 1,2,...,п— ее собственные значения. В курсе линейной алгебры было доказано, что всякая самосопряженная (симметричная в вещественном случае) матрица диагонализируема в евклидовом базисе, т.е. существует ортонормированный базис хыхг,...,х„, (х;,хэ) = бв, состоящий из собственных векторов матрицы А: Ах; = Л;х;. Пусть х ф Π— произвольный вектор, х = ~,", с;х; — его разложение по базису (хг), причем (/х)!г = ~,", )с;)г ф О.
Рассмотрим выражение (Ах,х) = (АЕ," д с;х;, Е"; 1с;х,) = ( ', с;Л;х;,~,", с;х;) = ~ "; 1Л;!с;/г. Следовательно, (Ах,х) вещественно. Поскольку Л; > О и не все с; равны О, то (Ах,х) положительно. Итак, для всякого вектора х ф О выражение (Ах, х) вещественно и положительно, что и означает положительную определенность матрицы А. К.Ю.Богачев Точные методы ретения линейных систем '31 О. МЕТОД ХОЛЕЦКОГО (КВАДРАТНОГО КОРНЯ) 35 3 10.
МЕТОД ХОЛЕЦКОГО (КВАДРАТНОГО КОРНЯ) Пусть требуется решить линейную систему Ах = о с самосопряженной (симметричной в вещественном случае) матрицей А Е М„, А* = А. 3 10.1. Разложение Холецкого Теорема 1. Пусть матрица А — самосопряженнал (А* = А) и все ее главные угловые миноры отличны от нуля. Тогда существуют матрица Л = (г;~) Е ВТ(п) с вещественными положительными элементами на главной диагонали (га ) О для всех 1 = 1,...,п) и диагональная матрица П с вещественными равными по модулю единице диагональными элементами (да Е ( — 1, 1) для всех 1 = 1,..., п) такие, что А = Я'0К . Доказательство. По теореме 4.1 для матрицы А осуществимо И7- разложение, т.е. существуют Ь Е 1Т(п) и Г Е ПТ(п) такие, что А = И1.
Поскольку матрица Ь = (1; ) невырождена, то 1н ф О, 1= 1,...,п и матрица й= д1аК(1„,...,1п„) обратима, й ' = йаи(1,,',...,1„"). Положим А = йй ' Е ЬТ(п). Тогда по правилам перемножения матриц 1н = 1, 1 = 1,..., п. Подставим это представление матрицы Б = йР в Иг-разложение матрицы А: А = К1Н~. Так как А = А*, то А = КШУ = А* = У*й*А*. Поэтому У = й — ] Т вЂ” ~ П ~ й~ Б~ П(А') " = й-'А-'У*й*. (2) Заметим, что Ь* е ВТ(п), причем главная диагональ этой матрицы состоит из единиц. Следовательно Ь* Е ПТ(п).
Поэтому в левой части равенства (2) стоит матрица Б'(А*) Е 11Т(п). В право же части равенства (2) стоит произведение нижних треугольных матриц, которое является опять нижней треугольной матрицей, т.е. принадлежит 1Т(п). Поэтому из (2) вытекает П1*) Е ПТ(п) О 1Т(п). Единственной матрицей, которая принадлежит одновременно подгруппам 11Т(п) и 1Т(п) является Т вЂ” единичная матрица. Следовательно, П(А*) ' = й-'А-'Н*й" = Т. (3) Таким образом, Б" = А' и А = У*йУ. Далее, из (3) 1 = й-'Ь-'и*й* = й-'Ь-'(Ь*)*й* = й-'Ь-'Ьй' = й-'й* К.Ю.Богачев Точные методы решения линейных систем Обозначим через ВТ(п) подгруппу невырожденных верхних треугольных матриц в М„, а через 11Т(п) -- подгруппу в ВТ(п) матриц с единицами на главной диагонали. ~1 О.
МЕТОД ХОЛЕЦКОГО (КВАДРАТНОГО КОРНЯ) т.е. Р = .Р*. В силу (1) получаем 1ьь = 1я, т.е. 1ьь — вещественные для всех й = 1,..., т~. Представив матрипу Р в виде .Р = ~Р~'~'Р ~Р~'1~, где Р=йая(з1ип1п ... а~п1 ) ф)'~'=йад(ф~п~ ... ф1 ~) получаем А = Н*~Р~'~~Р(Р)'~~У. Обозначим Л = )Р('~~Б' е КТ(п). Тогда А = К*РК, причем диагональные элементы тн матрицы К равны ф1„~ ) О. Следовательно, полученное разложение является требуемым. Замечание 1.
Если матрица А — вещественная, то все участвующие в теореме 1 матрицы вещественные. Замечание 2. Если в условиях теоремы 1 матрица А положительно определена, то матрица Р в теореме 1 — единичная, т.е. разложение, даваемое этой теоремой, имеет вид А = К,*К. Замечание 3. Если матрица А положительно определена, то для нее выполнены условия теоремы 1. Это вытекает из леммы 9.2. З 10.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
