Н.И. Ионкин - Электронные лекции (2010) (1135227), страница 2
Текст из файла (страница 2)
.. . ..⎟.⎠⎝. ...0 0 ··· 13 −действий3Крестиками отмечены в общем случае ненулевые элементы.∙(+1)действий2Преобразование правых частей:2. Обратный ход∙(−1)действий23. Всего33+ 2 −действий3Разложение матрицы на множителиЗададимся целью представить матрицув виде = · ,где⎛⎞11 0 · · ·0⎜ 21 22 · · ·0 ⎟⎜⎟ = ⎜ .... ⎟....⎝ .... ⎠1 2 · · · — нижнетреугольная матрица,⎛⎞1 12 · · · 1⎜0 1 · · · 2 ⎟⎜⎟ = ⎜ .. .. .
.. ⎟. ⎠⎝. ...0 0 ··· 1— верхнетреугольная матрица с единицами на главной диагонали.По формуле для элемента произведения матриц: =∑︁=1 (2)Разложение матрицы на множители. Связь этого разложения с методом ГауссаПерепишем предыдущее выражение, выделив слагаемое с =−1∑︁ + +=1Из вида матрицы7 :∑︁ =+1следует, что∑︁ = 0=+1Таким образом, предпологая, что ̸= 0,получим −−1∑︀=1 = ,<(3)Теперь из формулы элемента произведения матриц выделим слагаемое с =−1∑︁ + +=1Из вида матрицыследует, что∑︁ : =+1∑︁ = 0=+1Таким образом, можно записать: = −−1∑︁ ,≥(4)=1Легко видеть, что формулы (3) и (4) позволяют вычислить все элементы матрици.Докажем существование и единственность факторизации матрицы A.Утверждение. Пусть все главные миноры марицы А отличны от 0:1 = 11⃒⃒⃒1,1 1,2 ⃒⃒⃒≠ 0, 2 = ⃒≠ 0, · · · , ̸= 0, ∀ = 1, 2,1 2,2 ⃒Тогда разложение в форме (2) существует и единственно.Доказательство.
По свойству определителей:det = det · det Так как все элементы главной диагонали матрицы С равны 1, тоdet = 1, ∀ = 1, .det = 11 · 22 · . . . · ⇒ det = det Исходя из этого утверждения, а также из вида определителя =следует:, det 0 = 1 ⇒ 11 = 11−1А так как все главные миноры (1) отличны от нуля, то всепостроению.det ,существуют и единственны поРазложение матрицы на множители. Связь этого разложения с методом Гаусса8Связь метода Гаусса с разложением матрицы на множителиРассмотрим метод Гаусса для решения СЛАУ с применением факторизации. Пусть = · ,где B и C — матрицы в разложении в форме (2) (матрицы НПТФ и ВТФ соответственно).В этом случае исходная система будет выглядеть следующим образом:· ·=Обозначим · = .(5)Тогда система (5) распадается на две системы:· =(6) · = ,(7)Выпишем уравнения системы (6):1 1 + 2 2 + .
. . + = , ∀ = 1, Поскольку ̸= 0, , откуда получим:∑︀ − −1=1 =, = 1, мы можем разделить на(8)Посчитаем число операций умножения и деления, требуемых для реализации полученной формулы.Для каждого уравнения этой системы получаем (i – 1) операций умножения и 1 операциюделения. То есть при каждом фиксированном i получается i операций. А так как i можетменяться от 1 до m, получаем формулу:∑︁ · ( + 1)2 = 1 + 2 + . . . + ( − 1) + ==1Мы получили в точности число шагов, требуемых для преобразования правых частей системы(6) при прямом ходе.Для системы (7) оценка·(−1)получается аналогично.2Задача.
Показать, что факторизация матрицы А требует3 −операций умножения и3деления.Доказательство. Воспользуемся формулами для факторизации из предыдущего параграфа: = −−1∑︁ ,≥=1Для вычисления каждогопотребуется j-1 операция умножения. Отпустим индекс j:∑︁( − 1)( − 1) =2=1Теперь отпустим индекс i:∑︁( − 1)=121 ∑︁ 2 1 ∑︁= −2 =12 =1Обращение матриц методом Гаусса-Жордана9Вторая сумма вычисляется элементарно, значение первой суммы нам известно из школьного(+1)(2+1).курса –6( + 1)(2 + 1) ( + 1)( − 1)( + 1)−=1246Далее следующая формула: −−1∑︀ =1 =,<Для вычисления каждого потребуется j-1 операция умножения и 1 операция деления. Отпустиминдекс i:−1∑︁==1( − 1)2Отпустим индекс j:1 ∑︁1 ∑︁ 2 1 ∑︁( + 1)(2 + 1) ( + 1)−=( − 1) = −=2 =12 =12 =1124( − 1)( + 1)6Суммируя с предыдущем результатом, получаем окончательный ответ:2( − 1)( + 1)(3 − )=63Получается, что суммарная сложность метода совпадает со сложностью классического методаГаусса.Замечание.
Факторизация дает существенный выигрыш в том случае, если решается СЛАУс построяной матрицей§3и меняющимися правыми частями.Обращение матриц методом Гаусса-ЖорданаРассмотрим систему линейных алгебраических уравнений: = , ∈ × , || ≠ 0(1)Определение. Матрица −1 называется обратной к матрице , если выполнено: · −1 = −1 · = Обозначим = −1 : · = , = , ∈ 1, Запишем СЛАУ порядка m (c2неизвестными):· =(2)Обращение матриц методом Гаусса-Жордана10Для решения подобной системы классическим методом Гаусса потребуется порядка3Покажем, что число действий можно снизить до . Для этого обозначим:∑︁ = 6 операций.(3)=1 () = (1 , 2 , .
. . , ) , = 1, (4) () = (⏟ 0⏞ , 0, . . . , ⏟ 0⏞ , ⏟ 1⏞ , ⏟ 0⏞ , . . . , ⏟ 0⏞ )1−1+1(5)Теперь система (2) сводится к m системам с m уравнениями в каждой. При этом матрица Аодна и та же для всех систем: · () = () , = 1, (6)Факторизуем матрицу А и перепишем полученные системы (6):=· = {, , ≥ ; , ∈ 1, } (Нижняя почти треугольная форма)⎧⎫⎨ 1, = ; ⎬, , < ; (, ∈ , ) (Верхняя треугольная форма)=⎩⎭0, > ;Обозначим() = () .Система уравнений примет вид: () = ()(7)() = ()(8)Ещё раз отметим тот факт, что матрица A остается одинаковой для всех m систем. Соответственно,факторизацию матрицы А нужно проводить только один раз.
При фиксированном j для решения2формул (7) и (8) требуется операций. А поскольку общее количество систем равно m, общая3сложность решения составляет . Суммируя этот показатель с числом операций, требуемых43 −3 −для факторизации матрицы A () получаем общую сложность. Полученная оценка33— не предел. Для ее улучшения рассмотрим структуру матрицы B подробнее.Распишем систему (7):()()11 1 = 0 ⇒ 1 = 0()()()21 1 + 22 2 = 0 ⇒ 2 = 0...()−1 = 0() = 1Таким образом()() = 0, < ; =1, = .Оставшиеся уравнения:()()(), + ,+1 +1 + . . .
+ , = 0, ̸= 0 ⇒Метод квадратного корня11()∑︀−1(), , = + 1, .==−Оценим число операций для реализации указанного метода решения. Фиксируем индексы i иj: в этом случае нам потребуется = + 1, ( − )умножений и 1 деление. Сначала отпустим индекс i (), тогда число операций будет равно:( − + 1) + ( − ) + . . . + 2 + 1 =Далее отпустим индекс j ( = 1, ( − + 1)( − + 2)2):∑︁( − + 1)( − + 2)2=1Задача.
Показать, что сумма(+1)(+2).6(9) равнаДоказательство. Проведем замену: = − + 1:∑︁( + 1)=1(9)2=∑︁=1Откуда следует, что первая сумма равна2+∑︁2=12(+1)(+1)(2+1), а вторая –, что в сумме и дает412требуемую оценку.(−1)действий, а, поскольку таких систем m штук (т.к. = 1, ), то22 (−1)для их решения потребуетсяопераций. Таким образом, суммарное количество операций,2требуемых на решение (1) равно:Система (8) требует3 − ⏟ 3⏞факторизация (1)§4( + 1)( + 2) 2 ( − 1)++= 36⏞2⏞⏟⏟решение (7)решение (8)Метод квадратного корняРассмотрим систему линейных алгебраических уравнений: = , ∈ C× (R× ), || ≠ 0(1)Определение.
Матрица A называется эрмитовой (или самосопряженной) матрицей, если = * , = Пусть A - эрмитова матрица. Представим ее в виде: = * где: - диагональная матрица = ±1; = 1, , - верхняя треугольная матрица > 0, < , , = 1, ,(2)Метод квадратного корня*12- матрица, сопряженная к S. и на примере вещественных матриц второго порядка:)︂(︂)︂11 1211 12=, =21 220 22(︂)︂(︂)︂11 011 0* =, =12 220 22Рассмотрим метод нахождения матриц(︂Перемножим матрицы *и:(︂)︂11 11 11 12 =022 22,)︂(︂)︂ (︂)︂ (︂11 11 1211 011 11 11 1211 211 ==12 2211 11 12 11 212 + 22 222022 22*Из (2) и условия равенства матриц получаем соотношения:11 = 11 211(3)12 = 11 11 12(4)22 = 11 212 + 22 222(5)Из уравнения (3) имеем:11 = (11 )√︀11 = |11 |Из уравнения (4):12 =1211 11Из уравнения (5):22 = (22 − 11 212 )√︁22 = |22 − 11 212 |Таким образом, все элементы матрициоднозначно определены.Рассмотрим теперь невырожденную эрмитову (или симметрическую) матрицуистолбцами и найдем для нее разложение в виде (2).
Из того, чтоматрицей, получаем:() =∑︁ = , с строкамиявляется диагональной > 0=1Далее запишем выражение для : = ( * ) =∑︁ ,≤(6)=1Выделим из суммы-ыйэлемент:* = ( ) =−1∑︁=1 + +∑︁=+1 (7)Примеры и канонический вид итерационных методов решения СЛАУПри=13будем иметь:* = ( ) =−1∑︁ + +∑︁ =+1=1В силу вида матрицы = 0, > , поэтому последняя из сумм будет равна 0. Учитывая2равенство = | | , перепишем получившееся выражение в виде:2 = −−1∑︁| |2 =1Теперь можно записать формулы для элементов матриц = ( −−1∑︁и:| |2 )=1⎯⎸−1∑︁⎸⎷ = | −| |2 |=1Из (7) получим: = −∑︀−1=1 − ∑︀=+1 По данным формулам однозначно находятся все элементы матрици.Рассмотрим применение данного разложения к решению систем линейных алгебраическихуравнений: = * = Обозначим = ,получим две системы линейных алгебраических уравнений:{︂ * = , = ;Для решения этих двух систем потребуется порядка3умножений и делений, а также6извлечений квадратного корня.§5Примеры и канонический вид итерационных методов решенияСЛАУРассмотрим СЛАУ: = ,где— матрица размера( × ), || ≠ 0, = (1 , .
. . , ) ,(1)Примеры и канонический вид итерационных методов решения СЛАУ14 = (1 , . . . , ) .Из невырожденности матрицыследует, что решение системы (1) существует и единственно.Перепишем систему (1) в виде:∑︁ = , = 1, . . . , =1Выделим из суммы-оеслагаемое:−1∑︁ + +=1Пусть ̸= 0, -ую0компоненту-ой(2)итерации. Запишем метод Якоби (МЯ):−1∑︁∑︁ − − , =1 =+1 = 0, 1, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
