Конспект лекций - 3ий поток, лектор - Ионкин (1113828), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

b11 = a11 , c1j =a1jb11=a1j,ja11= 2, m, то есть нашли все элементы c1j .2. bi1 = ai1 ⇒ нашли все элементы bi1 .3. Исходя из первых двух пунктов найдем диагональный элемент b22 .4. И так далее.Утверждение 1. Пусть все главные угловые миноры матрицы A отличны от нуля. Тогда факторизация матрицы A, представленная в виде (2), возможна единственным образом.Доказательство: Введем ∆0 = 1. В силу того, что Ai = Bi Ci ⇒ |Ai | = |Bi ||Ci |. Таккак главная диагональ матрицы C состоит из единиц, то |Ai | = ∆i = b11 b22 . .

. bii ⇒ibii = ∆∆i−1, i = 1, m ⇒ bii 6= 0.Связь метода Гаусса с разложением матрицы A на множителиРассматриваем систему (1) порядка m и факторизацию матрицы A (2):(BY = f(5)BCx = f ⇒Cx = Y(6)где Y = Cx.Задача. Доказать, что нахождение матриц B и C требуетделений.m3 −m3умножений и7Решение: Воспользуемся формулами для факторизации матрицы:bij = aij +j−1Xbil clj , i > jl=1Для вычисления каждого bij потребуется j − 1 умножение. Тогда зафиксировав индекс i, получим:iXi(i − 1)(j − 1) =2j=1Далее посчитаем для индекса i:mXi(i − 1)i=12mm1X 2 1X=i −i2 i=12 i=1Нетрудно получить значение первой суммы:щая будет равна:m(m + 1)(2m + 1).

Тогда результирую6m(m + 1)(2m + 1) m(m + 1)m(m + 1)(m − 1)−=1246Далее для вычисления элементов cij воспользуемся формулойaij −cij =i−1Pl=1biibil clj, i<jДля каждого cij потребуется j − 1 умножений и одно деление. Зафиксируем индексj:j−1Xj(j − 1)j=2i=1И для индекса j получаем аналогичную формулу:mXj(j − 1)j=12mm1X 2 1Xm(m + 1)(2m + 1) m(m + 1)m(m + 1)(m − 1)=j −j=−=2 j=12 j=11246Просуммируем два полученных результата для окончательно ответа:m(m + 1)(m − 1) m(m + 1)(m − 1)m3 − m+=663В прямом методе Гаусса при сведении матрицы к верхнетреугольному виду с едиm3 − mницами на главной диагонали требуетсядействий, то есть в точности такое3число, что и для факторизации матрицы A.8Распишем покоординатно системы (5) и (6):bi1 y1 + bi2 y2 + · · · + bii yi = fi , i = 1, mxi + cii+1 xi+1 + · · · + cim xm = yi , i = 1, mСчитая, что bii 6= 0, выразим yi и xi :fi −i−1Pbil yll=1yi =(5∗)biixi = yi −mXcil xl(6∗)l=i+1m(m + 1) m(m − 1)+действий.

Для преобразования22m(m + 1)правых частей в методе Гаусса требуется, что совпадает с числом действий2m(m − 1)в системе (5*). Для обратного хода метода Гаусса требуетсядействий, что2совпадает с числом действий в системе (6*). Тогда общее количество действия дляметода Гаусса равно:m3 − m+ m2 .3Эти две формулы требуют§3 Обращение матриц методом Гаусса-ЖорданаРассмотрим матричное уравнение видаAx = f,(1)где A — матрица размера (m × m), |A| =6 0Так как определитель матрицы A не равен нулю, то существует обратная к нейматрица и, по определениюA−1 A = AA−1 = EОбозначим A−1 = X, тогда получим уравнениеAX = E,где X = xij , i, j = 1, m.Для решения системыAX = Eметодом Гаусса требуется число операций порядка m6 .

Покажем, что число действийможно снизить до m3 .9Распишем покоординатно:mXail xlj = δij– в этой системе m2 неизвестныхl=1Введем вектор-столбецx(j) = (x1j , x2j , . . . , xmj )T ,i = 1, m.Введем вектор правых частей единичной матрицы и обозначим егоδ (j) = (0, 0, . . . , 0, 1, 0, . . . , 0, 0),где на j позиции стоит единица.Тогда видно, что для того чтобы обратить матрицу, необходимо решить m системAx(j) = δ (j) ,j = 1, m(2)Таким образом, решение системы с m2 неизвестными сведено к решению m систем с m неизвестными и фиксированной матрицей A.

Теперь применим факторизацию (предполагая, что необходимое условие выполнено, т.е. все угловые минорыотличны от нуля): A = BC.Вновь расписав уравнение, получимBCx(j) = δ (j) .Обозначая вектор Cx(j) = Y (j) , видим, что для решения системы (2) нужнорешить две системы:BY (j) = δ (j) , j = 1, m(3)Cx(j) = Y (j) ,j = 1, m(4)Эти системы имеют треугольные матрицы, поэтому все неизвестные находятсяпо явным формулам.

Следовательно,по совокупности эти две системы требуют m2действий. А так как необходимо решить m систем, то на решение всех систем понадоm3 − mбится m3 действий. Факторизация, проведенная один раз, требуетдействий.34mОткуда получаем, что общее количество действий равно m3 − .33Однако, если воспользоваться спецификой видов матриц, то число действийможно уменьшить до m3 . Докажем данное утверждение.Рассмотрим систему (3).

Учитывая нижнетреугольную форму матрицы B, получим:(j)b11 y1 = 0y1 = 0b21 y1 + b22 y2 = 0 =⇒···y2 = 0(j)(j)(j)(j)=⇒(j)jbj−1,1 y1 + bj−1,2 y2 + · · · + bj−1,j−1 yj−1=0=⇒(j)(j)yj−1 = 010(j)Откуда получаем, что yi = 0, где i 6 j − 1Следующее j-ое уравнение даст нам (учитывая, что bjj 6= 0):(j)bjj yj = 1=⇒(j)yj =1bjj(∗)Оставшиеся уравнения системы имеют вид:−(j)bi,j yi+(j)bi,j+1 yi+1+ ··· +bi,i yij= 0, i = j + 1, m, bii 6= 0=⇒(i)yj=i−1Pbil yljl=jbiiФиксируем все индексы, т.е. i и j и считаем число действий:1 деление+(i − j) умножений.Теперь отпускаем один из индексов, например, i. Тогда получим(m − j) + (m − j − 1) + · · · + 2 + 1 =(m − j + 1)(m − j)2умножении при фиксированном j.Вдобавок к этому (m − j) делений + 1 деление от (*), откуда получаем, что прификсированном j всего(m − j + 1)(m − j + 2)⇒2умножений и делений.Теперь, отпустив j, получимmX(m − j + 1)(m − j + 2)j=12(5)делений и умножений при решении системы вида B · Y = f .m(m + 1)(m + 2)Задача.

Доказать, что для реализации (5) необходимоопераций.6m m2 − mj + 2m − mj + j 2 − 2j + m − j + 2m (m − j + 1)(m − j + 2)PPРешение:==22j=1j=1mmm2 3m 2m + 3 P1Pm2 + 3m (2m + 3)m(m + 1)=+−j+j2 + 1 =−+2222 j=124j=1m(m + 1)(2m + 1)m(m + 1)(m + 2)++1=.126m(m − 1)Для реализации (4) необходимодействий (обратный ход метода Гаус2m2 (m − 1)са), а учитывая, что нам надо решить m уравнений, получимумножений2и делений.Таким образом, весь процесс Гаусса-Жордана обращения матрицы требует m3действий (факторизация + решение системы (3) + решение системы (4)):m3 − m m(m + 1)(m + 2) m3 − m2++= m3 .36211§4 Метод квадратного корняРассмотрим матричное уравнение видаAx = f,(1)где A — матрица размера (m × m), |A| =6 0, A = A∗Представим матрицу A в виде A = S ∗ DS, гдеd11 0 . . .

0 0 d22 . . . 0D =  ...... .. ... .00...s11 s21 . . . 0 s22 . . .S =  ...... ...00 ...(эрмитова, т.е. aij = aji ).00...,0 dmms1ms2m ..  ,. smmгде sii > 0, dii = ±1, i = 1, m.Следовательно S ∗ будет нижнетреугольная.Покажем для симметричной матрицы второго порядка, что такое разложениевозможно. Для простоты потребуем, чтобы она была вещественной.d11 0s11 0s11 s12a11 a12∗T, D=, S =S =, S=A=0 s220 d22s12 s22a21 a22Найдем в начале произведение DS.

d11 0s11 s12d11 s11 d11 s12DS =·=0 d220 s220d22 s22Теперь домножим на S ∗ слева. s11 0d11 s11 d11 s12d11 s211s11 d11 s12∗S DS =·==As12 s220d22 s22s11 d11 s12 d22 s222 + s212 d11Откуда получим, чтоa11a12a21a22= d11 s211= s11 d11 s12= a12= d22 s222 + s212 d11Для того чтобы факторизация была возможна, необходимо, чтобы система была12разрешима. Ее решение находится по формулам:d11 = sign(a11 )ps=|a11 |11a12s12 =s11 d11d22 = sign(a22 − s212 d11 )q s22 = |a22 − s2 d11 |12Таким образом показано, что для матрицы A (вещественной и симметричной)возможна факторизация и все находится по явным формулам. Рассмотрим общийслучай.

Элементы матрицы DS находятся по формуле:(DS)ij =mXnodil slj = с учетом свойств матриц = dii sijl=1Заметим, что(S ∗ )ij = S jiУмножим слева матрицу S ∗ на DS:∗(S DS)ij =mXsli dll sljl=1Распишем сумму, приравняв ее к aij элементуi−1XmXsli dll slj + sii dii sij +l=1sli dll slj = aij ,i, j = 1, ml=i+1Учтем специфику матрицы S: sli = 0,mXl > i. Следовательно,sli dll slj = 0l=i+1Тогда получимsii dii sij = aij −i−1Xsli dll slj ,i6jl=1Рассмотрим два случая (i = j и i < j).Положим i = j.

Получим:sii sii dii = aii −i−1Xl=1sll sli dll(3)13Так как zz = |z|2 , то|sii |2 dii = aii −i−1X|sli |2 dlll=1Таким образом, мы получили формулы, из которых можем найти диагональныеэлементы матрицы D:i−1Xdii = sign(aii −|sli |2 dll )l=1Далее понятно, чтоvui−1Xut|sli |2 dll aii −sii =l=1Осталось вновь вернуться к исходной формуле, частный случай которой мырассмотрели. Из формулы (3) можно найти элементы sij , считая, что dii sii 6= 0:sij =aij −Pi−1l=1slj dll sljsii dii,i < j.Система перепишется в виде:S ∗ DSx = fОбозначая DSx = Y , получим:(S ∗Y = fDSx = Y(4)(5)Матрица S ∗ нижнетреугольная и из (4) легко находится вектор Y .

Затем, решаяуравнение (5), находим вектор x.Был рассмотрен метод квадратного корня. Этот метод имеет преимущество поколичеству арифметических действий (умножений и делений) перед методом Гаусса,m3m3который пропорционалендействий, а рассмотренный нами способ , так как36расчеты проводились только для части матрицы (но здесь есть еще m извлеченийкорня).Следовательно, если матрица эрмитова или самосопряженная, то один из наиболее эффективных прямых методов - метод квадратного корня.§5 Примеры и канонический вид итерационных методов решения СЛАУРассмотрим матричное уравнение видаAx = f,(1)14где A — матрица размера (m × m), |A| =6 0,x = (x1 , x2 , . .

. , xm )T ,f = (f1 , f2 , . . . , fm )T .Когда решается линейная система (1), то в правой части, как правило, стоитфункция наблюдения. Ясно, что прямой метод дает точное (числовое) решение, абстрагируясь от округления - в силу конечной разрядной сетки.Также, если m достаточно велико, то количество действий даже для суперкомпьютера может оказаться очень большим. А использование итерационных методовпозволит решить систему (1) быстрее. Более того, в некоторых случаях возможнооценить число итераций, необходимых для достижения заданной точности.В качестве примера рассмотрим методы Якоби и Зейделя. Запишем систему (1)покоординатно:mX(2)aij xj = fi , i = 1, mj=1Рассмотрим метод Якоби (МЯ).

Характеристики

Список файлов лекций