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

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

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

. . +emλ2c1 λ mПолучим, чтоxn −→ e1 ,n→∞38Задача. Доказать, что(n)λ1− λ1 = Oλ1λ2(i)n(n), где λ1 =(i)xn(i), i = 1, mxn+1(i)Решение: Выпишем выражения для xn и xn+1 :(i)(i)−n−n−n (i)x(i)n = c1 λ1 e1 + c2 λ2 e2 + · · · + cm λm em(i)(i)(i)xn+1 = c1 λ−n−1e1 + c2 λ2−n−1 e2 + · · · + cm λ−n−1e(i)1mm(1)(2)Теперь поделим (1) на (2):−n−n !(i) λ2cm em λm1++ ··· +(i)(i)λ1λ1c1 e 1c1 e1−n−1−n−1 ! =(i) (i) c2 e 2λ2cm e m λ m1++ ··· +(i)(i)λ1λ1c1 e 1c1 e 1(i)(i)(i)xn(i)xn+1c1 λ−n1 e1=(i)c1 λ−n−1e11c2 e 2= λ1 + Oλ1λ2n= λn1Что и требовалось показать.Задача. Пусть A = A∗ , существует A−1 ,(n)λ1 =(xn , xn )(xn+1 , xn )Доказать, что(n)λ1− λ1 = Oλ1λ22n(n)Решение: Найдем λ1 , учитывая ортонормированность базиса из собственных векторов:−2n(xn , xn )c21 λ−2n+ c22 λ2−2n + · · · + c2m λm(n)1λ1 == 2 −2n−1=−2n−1(xn+1 , xn )c1 λ 1+ c22 λ2−2n−1 + · · · + c2m λm 2 −2n 2 −2n !cλcmλm22−2nc21 λ11++ ··· +c1λ1c1λ1= 2 −2n−1 ! = 2 −2n−1cmc2λ2λmc21 λ−2n−11++ ··· +1c1λ1c1λ1 2nλ1= λ1 + Oλ2Что и требовалось показать.39Метод обратных итераций со сдвигомРассмотрим метод обратных итераций со сдвигом:(A − αE)xn+1 = xn ,где n = 0, 1, .

. . ,(6)x0 — задано и α такое число, что∃(A − αE)−1Тогда ясно, чтоxn+1 = (A − αE)−1 xn(7)Обозначим B = (A − αE)−1 .Так как для этой матрицы B метод стал степенным, то мы можем сделать выводо том, куда сходятся итерации.xn → e l11max=16k6m |λk − α||λl − α|Здесь точно так же, как и в степенном методе, можно найти собственное значение(i)λl = lim α +n→∞xn(i)xn+1Казалось бы, что тогда этим методом можно найти все собственные значенияматрицы A, но он для этого не применяется. Метод обратных итераций со сдвигомприменяется при уточнении собственных векторов и собственных значений.§10 Приведение матрицы к верхней почти треугольной формеБерем произвольную матрицу A порядка m.

Задача поиска всего спектра —очень важная и сложная задача. Очевидно, что лучше всего матрицу A свести к матрице C, называемой предельной, у которой все собственные значения сразу можнонайти (это матрица треугольного вида, относительно главной диагонали или диагональная). Для этого можно было бы воспользоваться методом Гаусса, однако приведение матрицы A к треугольной форме методом Гаусса не сохраняет спектр матрицы.Поэтому лучше воспользоваться преобразованием подобия.

ЕслиC = Q−1 AQтогда у матриц C и A совпадают собственные значения.(1)40Под верхней почти треугольной матрицей (ВПТМ) понимается матрица вида× × ... × ×× × ... × × 0 × ... × ×(∗) 0 0 ... × ×,. . . . . . . . . . . . . . . 0 0 ... × ×где под × подразумевается, вообще говоря, ненулевой элемент.Первым делом покажем, что любую матрицу с помощью преобразований элементарных отражений можно привести к виду (∗).

А далее можно организовать итерационный процесс, приводящий матрицу к трехдиагональной структуре.Напомним, что ортогональная матрица — это такая матрица S, для которойвыполнено:S −1 = S TРассмотрим вектор V T = (V1 , V2 , . . . , Vm )TОпределение. Элементарным отражением, который соответствует векторустолбцу V , называется преобразование, задаваемое матрицейH=E−2V V TkV k2(2)У этого преобразования есть три очень важных свойства. Во-первых, оно симметричное, во-вторых, ортогональное и, наконец, имеет совершенно уникальное свойство заключающееся в том, что действуя на произвольный вектор, преобразованиеобнуляет все его координаты, кроме первой.Во-первых,kV k2 = V T V = V12 + V22 + · · · + Vm2VVTV12V1 V2 V2 V1V22= ......Vm V1 Vm V2.

. . V 1 Vm. . . V 2 Vm ...2. . . VmВидно, что полученная матрица симметричная. Так как второе слагаемое E вравенстве (2) тоже симметричное, то:HT = HТеперь докажем второе свойство, утверждающее, что матрица H является ортогональной:H T = H −1Для этого посчитаем произведение H T H. Если мы покажем, что это единичнаяматрица, то тогда, по определению обратной матрицы, H T будет совпадать с H −1 .41T2H H=H =VVTE−2kV k2 VVT· E−2=kV k2noVVTV V TV V TT2=E−4+4= в силу ассоциативности V V = kV k = EkV k2kV k4Утверждение 4. Пусть задан произвольный вектор x = (x1 , x2 , . .

. , xm )T , тогдаможно выбрать вектор V так, чтоHx = (−σ, 0, 0, . . . , 0)T ,σ = kxk =mX! 21x2i.i=1Доказательство: Возьмем векторV = x + σz,где z = (1, 0, 0, . . . , 0)T .Тогда образ вектора x будет равенHx = x −2(x + σz)(x + σz)T2(x + σz)T xx=x−(x+σz)(x + σz)T (x + σz)(x + σz)T (x + σz)Посчитаем числитель и знаменатель дроби по отдельности.Числитель:2 (x + σz)T x = 2 kxk2 + σx1Знаменатель:(x + σz)T (x + σz) = kxk2 + σx1 + σx1 + σ 2Достаточно убедиться, что, если мы положим σ равной1σ = kxk = (x, x) 2 ,то получим, что числитель равен2 (x + σz)T x = 2 kxk2 + σx1 = 2σ 2 + 2σx1 ,а знаменатель(x + σz)T (x + σz) = 2σ 2 + 2σx1Получаем, что числитель совпадает со знаменателем, а значит вся дробь обращается в единицу.ТогдаHx = x − x − σz = (−σ, 0, 0, .

. . , 0)TПоследнее свойство позволяет привести совершенно произвольную матрицу кверхней почти треугольной форме.42Запишем матрицу A блочно..a11 . ym−1A = . . . . . . . . . . . . . . ,.xm−1 .. Am−1гдеym−1 = (a12 , a13 , . . . , a1m ),xm−1 = (a21 , a31 , . . . , am1 )T .По доказанному утверждению, для вектора xm−1 выбираем вектор V :V = xm−1 + σzm−1 ,kxk = σ,zm−1 = (1, 0, . . . , 0){z}|m−1Выбрав вектор V таким образом, построим матрицу элементарных отражений:Hm−1 xm−1 = −σzm−1 = (−σ, 0, 0, .

. . , 0)TНо матрица H имеет порядок (m − 1). Её умножать на матрицу A порядка mмы не можем. Поэтому построим матрицу U1 :1o12,U1 =o21 Hm−1гдеo12 = (0, . . . , 0),o21 = (0, . . . , 0)T .Проверим, сохранила ли матрица U1 те три свойства, которыми обладало преобразование элементарного отражения.Очевидно, чтоU1 = U1T .Проверим, является ли она ортогональной.

1o121o121o122U1 = U1 U1 =·=2o21 Hm−1o21 Hm−1o21 Hm−1Так как матрица Hm−1 ортогональная, то тогда понятно, что полученная матрица является единичной, откуда получим, чтоU1−1 = U1T = U1 .Докажем, что умножение этой матрицы на матрицу A слева позволит обнулитьв первом столбце все элементы, кроме первых двух. Домножим матрицу A слева наматрицу U1−1 : 1o12a11 ym−1a11ym−1−1U1 A = U1 A =·=o21 Hm−1xm−1 Am−1Hm−1 xm−1 Hm−1 Am−143Далее домножим справа на U1 : 1o12=·=o21 Hm−1 noym−1 Hm−1−1= из-за ортогональности Hm−1 = Hm−1 =Hm−1 Am−1 Hm−1× × × ...

× no × × × . . . ×ym−1 Hm−1= σ1 = kxm−1 k = −1 0 × × . . . ×Hm−1Am−1 Hm−1. . . . . . . . . . . . . . . . .0 × × ... ×U1−1 AU1a11−σ1 zm−1a11−σ1 zm−1==a11ym−1Hm−1 xm−1 Hm−1 Am−1Итак, мы получили матрицу C1 , такую чтоC1 = U1−1 AU1или, другими словами, подобную матрице A, причем матрица подобия U1 ортогональна.Далее возьмем другой вектор размерности (m − 2):(1)(1)(1)xm−2 = (c32 , c42 , .

. . , cm2 )Tпо которому можно так же выбрать вектор V и построить преобразование Hm−2 :Hm−2 xm−2 = −σ2 zm−2 ,где σ2 = kxm−2 kТеперь можно сказать, что вновь по Hm−2 восстановим матрицу порядка m,добавив элементы:.E2 .. o12U2 = . . . . . . . . . . . . . ,.o21 .. Hm−2где1 0E2 =.0 1Легко убедиться, матрица U2 симметрична и ортогональна.После всего этого, применим U2 к C1 :× × ...

×× × . . . × 0 × . . . ×−1 −1C2 = U2 U1 AU1 U2 =  0 0 . . . ×. . . . . . . . . . . . . .0 0 ... ×Спустя (m − 2) шага, аналогично выстраивая Uk , получим матрицу C:−1C = Um−2. . . U2−1 U1−1 AU1 U2 . . . Um−3 Um−2 ,44которая будет верхней почти треугольной формы:Cji = 0,∀i > j + 2.ОбозначимU = U1 U2 . . . Um−2Найдем U−1:−1−1U −1 = (U1 , U2 , . . . , Um−2 )−1 = Um−2Um−3.

. . U2−1 U1−1 =noT= каждый множитель ортогонален = Um−1. . . U2T U1T = U TПолучили, чтоU −1 = U T .А значит, итоговое произведение будет иметь видC = U −1 AU.Показано, что любую матрицу можно свести к верхней почти треугольной формес помощью преобразования подобия с преобразующей ортогональной матрицей.Замечание. Собственные значения матрицы C равны собственным значениямматрицы A:AλCk = 1, mk = λk ,Доказательство: Запишем задачу на собственные значения для одной из матриц:Ax = λx,x 6= 0.Домножим слева на U −1 :U −1 Ax = λU −1 x.Обозначим U −1 x = y или x = U y, тогда−1U| {zAU} y = λy,y 6= 0C⇓Cy = λy,y 6= 0Замечание.

Если матрица A симметрична (вещественный случай), то C тожебудет симметричной:A = AT ⇒ C = C TДоказательство:C = U −1 AUНайдем транспонированную:C T = (U −1 AU )T = U T AT (U −1 )T = U −1 AU = C45§11 Понятие QR–алгоритма. Решение полной проблемы собственных значенийРассмотрим произвольную квадратную матрицу A порядка m. Поставим передсобой задачу: факторизовать матрицу A в виде произведения:A = QR,(1)где Q−1 = QT (ортогональная), R — верхнетреугольной формы.Обозначимx = (a11 , a21 , .

. . , am1 )T .Согласно доказанному свойству выше, возьмем вектор V :V = x + kxkz.По этому вектору построим матрицу H1H1 = E −2V V T,kV k2H1−1 = H1 = H1T .Тогда получим× × ... × 0 × . . . ×0×...×H1 A =  . . . . . . . . . . . . .

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

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