Численные методы. Ионкин (2012) (неоффициальные) (косяки есть) (1160437), страница 6

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

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

Пусть 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 −2ncmλλmc22+ ··· +c21 λ−2n1+1c1λ1c1λ1= 2 −2n−1 ! = 2 −2n−1λ2cmλmc2c21 λ−2n−1+ ··· +1+1c1λ1c1λ1 2nλ1= λ1 + Oλ2Что и требовалось показать.Метод обратных итераций со сдвигомРассмотрим метод обратных итераций со сдвигом:(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 − α|40Здесь точно так же, как и в степенном методе, можно найти собственное значение(i)λl = α + limn→∞xn(i)xn+1Казалось бы, что тогда этим методом можно найти все собственные значенияматрицы A, но он для этого не применяется. Метод обратных итераций со сдвигомприменяется при уточнении собственных векторов и собственных значений.§10 Приведение матрицы к верхней почти треугольной формеБерем произвольную матрицу A порядка m. Задача поиска всего спектра —очень важная и сложная задача.

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

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

Элементарным отражением, который соответствует векторстолбцу V , называется преобразование, задаваемое матрицейH=E−2V V TkV k2(2)41У этого преобразования есть три очень важных свойства. Во-первых, оно симметричное, во-вторых, ортогональное и, наконец, имеет совершенно уникальное свойство заключающееся в том, что действуя на произвольный вектор, преобразованиеобнуляет все его координаты, кроме первой.Во-первых,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 .T2H H=H ==E−4VVTE−2kV k2 VVT· E−2=kV k2noV V TV V TVVTT2+4=всилуассоциативностиVV=kVk=EkV k2kV k4Утверждение.

Пусть задан произвольный вектор 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)Посчитаем числитель и знаменатель дроби по отдельности.42Числитель: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Последнее свойство позволяет привести совершенно произвольную матрицу кверхней почти треугольной форме.Запишем матрицу 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)T{z}|m−1Выбрав вектор V таким образом, построим матрицу элементарных отражений:Hm−1 xm−1 = −σzm−1 = (−σ, 0, 0, .

. . , 0)TНо матрица H имеет порядок (m − 1). Её умножать на матрицу A порядка mмы не можем. Поэтому построим матрицу U1 :43U1 =1o12,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−1Далее домножим справа на U1 : a11ym−11o12=·=Hm−1 xm−1 Hm−1 Am−1o21 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−1==a11−σ1 zm−1Итак, мы получили матрицу C1 , такую чтоC1 = U1−1 AU1или, другими словами, подобную матрице A, причем матрица подобия U1 ортогональна.44Далее возьмем другой вектор размерности (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 ,которая будет верхней почти треугольной формы: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−2. . . U2T U1T = U TПолучили, чтоU −1 = U T .А значит, итоговое произведение будет иметь видC = U −1 AU.Показано, что любую матрицу можно свести к верхней почти треугольной формес помощью преобразования подобия с преобразующей ортогональной матрицей.45Замечание. Собственные значения матрицы C равны собственным значениямматрицы A:Ak = 1, mλCk = λ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 = C§11 Понятие QR–алгоритма. Решение полной проблемы собственных значенийРассмотрим произвольную квадратную матрицу A порядка m. Поставим передсобой задачу: факторизовать матрицу A в виде произведения:A = QR,где Q−1 = QT (ортогональная), R — верхнетреугольной формы.Обозначимx = (a11 , a21 , . . . , am1 )T .Согласно доказанному свойству выше, возьмем вектор V :V = x + kxkz.(1)46По этому вектору построим матрицу H1H1 = E −2V V T,kV k2H1−1 = H1 = H1T .Тогда получим× × ...

× 0 × . . . ×H1 A =  0 × . . . × . . . . . . . . . . . . . .0 × ... ×Ясно, что проделав (m − 1) аналогичных шагов, можно получить верхнетреугольную матрицу.В итоге получаем матрицу R:R = Hm−1 Hm−2 · . . . · H2 H1 AОбозначимQ = H1 H2 · . . . · Hm−1Найдем обратную−1TQ−1 = (H1 · . . . · Hm−1 )−1 = Hm−1· . . . · H1−1 = Hm−1· . . .

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

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