1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 70
Текст из файла (страница 70)
Затембарьер понижается, процесс обнуления повторяется заново, и так дотех пор, пока не будет достигнута требуемая точность.К 70-м годам прошлого века, когда было разработано немало эффективных численных методов для решения симметричной проблемысобственных значений, стало казаться, что метод Якоби устарел и будет вытеснен из широкой вычислительной практики (см., к примеру,рассуждения в [79]).
Дальнейшее развитие не подтвердило эти пессимистичные прогнозы. Выяснилось, что метод Якоби почти не имеетконкурентов по точности нахождения малых собственных значений, тогда как методы, основанные на трёхдиагонализации исходной матрицы,4303. Численные методы линейной алгебрымогут терять точность (соответствующие примеры приведены в [13]).Кроме того, метод Якоби оказался хорошо распараллеливаемым, т. е.подходящим для расчётов на современных многопроцессорных ЭВМ.3.17бЧисленные методы сингулярного разложенияСингулярные числа зависят от элементов матрицы существенно более плавным образом, нежели собственные числа. Мы могли видеть этоиз следствия из теоремы Вейля (теорема 3.16.3). На эту тему существует ещё один известный результатТеорема 3.17.1 (теорема Виландта-Хофмана) Пусть A и B — эрмитовы n × n-матрицы, причём λ1 ≥ λ2 ≥ .
. . ≥ λn — собственныезначения матрицы A и λ̃1 ≥ λ̃2 ≥ . . . ≥ λ̃n — собственные значенияматрицы Ã = A + B. ТогдаnXi=1λ̃i − λi2!1/2≤ kBkF ,где k · kF — фробениусова норма матрицы.Доказательство можно найти в [41, 42]Простейшие методы нахождения сингулярных чисел матриц основаны на том, что они являются собственными числами матриц A⊤A иAA⊤ (A∗A и AA∗ в комплексном случае).3.18Численные методы несимметричнойпроблемы собственных значенийСуществует большое количество разнообразных численных методовдля решения общей несимметричной проблемы собственных значений.В нашем курсе рассматриваются лишь два основных и, пожалуй, наибоее популярных метода. Более подробную информацию о состоянииэтой области вычислительной математики читатель может получитьиз более полных и специальных книг [5, 11, 13, 42, 43, 44, 59, 64, 65, 67]и др., а также из обзоров и специальных статей.3.18.
Численные методы для несимметричной проблемысобственных значений3.18аСтепенной методЕсли для собственных значений λi , i = 1, 2, . . . , n, некоторой матрицы справедливо неравенство |λ1 | > |λ2 | ≥ |λ3 | ≥ . . . |λn |, то λ1 называютдоминирующим собственным значением, а соответствующий ему собственный вектор — доминирующим собственным вектором. Степенной метод, описанию которого посвящён этот пункт, предназначен длярешения частичной проблемы собственных значений — нахождения доминирующих собственного значения и собственного вектора матрицы.Лежащая в его основе идея чрезвычайно проста и состоит в том,что если у матрицы A имеется собственное значение λ1 , превосходящеепо модулю все остальные собственные значения, то при действии этойматрицей на произвольный вектор x ∈ Cn направление v1 , отвечающееэтому собственному значению λ1 будет растягиваться сильнее остальных (при λ1 > 1) или сжиматься меньше остальных (при λ1 ≤ 1).
Приповторном умножении A на результат Ax предшествующего умножения эта компонента ещё более удлинится в сравнении с остальными. Повторив рассмотренную процедуру умножения достаточное количествораз, мы получим вектор, в котором полностью преобладает направление v1 , т.
е. практически будет получен приближённый собственныйвектор.В качестве приближённого собственного значения матрицы A можно при этом взять «отношение» двух последовательных векторов, порождённых нашим процессом — x(k+1) = Ak+1 x(0) и x(k) = Ak x(0) ,k = 0, 1, 2, . . . . Слово «отношение» взято здесь в кавычки потому, чтоупотреблено не вполне строго: ясно, что векторы x(k+1) и x(k) могутоказаться неколлинеарными, и тогда их «отношение» смысла иметь небудет. Возможны следующие пути решения этого вопроса:1) рассматривать отношение каких-нибудь фиксированных компонент векторов x(k+1) и x(k) , т.
е.(k+1)xi(k)/xi(3.153)для некоторого i ∈ {1, 2, . . . , n};2) рассматривать отношение проекций последовательных приближений x(k+1) и x(k) на направление, задаваемое каким-нибудь вектором l(k) , т. е.hx(k+1) , l(k) i.(3.154)hx(k) , l(k) i4323. Численные методы линейной алгебрыВо втором случае мы обозначили направление проектирования черезl(k) , чтобы подчеркнуть его возможную зависимость от номера шага k.Ясно также, что это направление l(k) не должно быть ортогональнымвектору x(k) , чтобы не занулился знаменатель в (3.154).Последний способ кажется более предпочтительным в вычислительном отношении, поскольку позволяет избегать капризного поведения водной отдельно взятой компоненте вектора x(k) , когда она может сделаться очень малой по абсолютной величине или совсем занулиться,хотя в целом вектор x(k) будет иметь значительную длину.
Наконец, вкачестве вектора, задающего направление проектирования во второмварианте, естественно взять сам x(k) , вычисляя на каждом шаге отношениеhx(k+1) , x(k) i,(3.155)hx(k) , x(k) iгде x(k) = Ak x(0) . Нетрудно увидеть, что это выражение совпадает сотношением Рэлея для приближения x(k) к собственному вектору.Для организации вычислительного алгоритма степенного методатребуется разрешить ещё два тонких момента, связанных с реализацией на ЭВМ.Во-первых, это возможное неограниченное увеличение (при λ1 > 1)или неограниченное уменьшение (при λ1 < 1) норм векторов x(k) иx(k+1) , участвующих в нашем процессе. Разрядная сетка современныхцифровых ЭВМ, как известно, конечна и позволяет представлять числаиз ограниченного диапазона.
Чтобы избежать проблем, вызванных выходом за этот диапазон («переполнением» или «исчезновением порядка»), имеет смысл нормировать x(k) . При этом наиболее удобна нормировка в евклидовой норме k · k2 , так как тогда знаменатель отношения(3.155) сделается равным единице.Во-вторых, при выводе степенного метода мы неявно предполагали,что начальный вектор x(0) выбран так, что он имеет ненулевую проекцию на направление доминирующего собственного вектора v1 матрицыA. В противном случае произведения любых степеней матрицы A наx(0) будут также иметь нулевые проекции на v1 , и никакой дифференциации длины компонент Ak x(0) , на которой и основывается степенной метод, не произойдёт. Это затруднение может быть преодолено спомощью какой-нибудь априорной информации о доминирующем собственном векторе матрицы.
Кроме того, при практической реализациистепенного метода на цифровых ЭВМ неизбежные ошибки округления,3.18. Численные методы для несимметричной проблемысобственных значенийкак правило, приводят к появлению ненулевых компонент в направлении v1 , которые затем в процессе итерирования растянутся на нужнуювеличину. Но, строго говоря, это может не происходить в некоторыхисключительных случаях, и потому при ответственных вычисленияхрекомендуется многократный запуск степенного метода с различныминачальными векторами (так называемый мультистарт).Таблица 3.12. Степенной метод для нахождениядоминирующего собственного значения матрицыk ← 0;выбираем вектор x(0) 6= 0;нормируем x(0) ← x(0) /kx(0) k2 ;DO WHILE ( метод не сошёлся )y (k+1) ← Ax(k) ;λ̃ ← y (k+1) , x(k) ;x(k+1) ← y (k+1) /ky (k+1) k2 ;k ← k + 1;END DOВ псевдокоде, представленном в Табл.
3.12, λ̃ — это приближённоедоминирующее собственное значение матрицы A, а x(k) — текущее приближение к нормированному доминирующему собственному вектору.Теорема 3.18.1 Пусть n×n-матрица A является матрицей простойструктуры (т. е. диагонализуема) и у неё имеется простое доминирующее собственное значение, которому соответствует один линейный элементарный делитель. Если начальный вектор x(0) не лежитв линейной оболочке lin {v2 , . . . , vn } собственных векторов A, которыене являются доминирующими, то степенной метод сходится.Доказательство. При сделанных нами предположениях о матрице Aона может быть представлена в видеA = V DV −1 ,4343. Численные методы линейной алгебрыгде D = diag {λ1 , λ2 , . .
. , λn } — диагональная матрица с собственнымизначениями λ1 , λ2 , . . . , λn по диагонали, а V — матрица, осуществляющая преобразование подобия, причём без ограничения общности можносчитать, что λ1 — доминирующее собственное значение A. Матрица Vсоставлена из собственных векторов vi матрицы A как из столбцов:V = v1 v2 · · · vn(v1 )1(v2 )1...(vn )1 (v ) 1 2= .. .(v1 )n(v2 )2...(v2 )n......(vn )2 .. ,. (vn )n...где через (vi )j обозначена j-ая компонента i-го собственного вектораматрицы A. При этом можно считать, что kvi k2 = 1. Следовательно,Ak x(0) =kV DV −1 x(0) == VD V−1V DV −1 V DV −1 · · · V DV −1 x(0){z}|k разV D V −1 V · · · V −1 V DV −1 x(0)= V Dk V −1 x(0) = V Dk zλk1 z1 λk z 2 2= V .. = . λkn znλk1 z11 (λ /λ )k (z /z ) 2 1 2 1,V ...(λn /λ1 )k (zn /z1 )где обозначено z = V −1 x(0) . Необходимое условие последнего преобразования этой цепочки — z1 6= 0 — выполнено потому, что в условияхтеоремы вектор x(0) = V z должен иметь ненулевую первую компоненту при разложении по базису из собственных векторов A, т.
е. столбцовматрицы V .Коль скоро λ1 — доминирующее собственное значение матрицы A,т. е.|λ1 | > |λ2 | ≥ . . . ≥ |λn |,то все частные λ2 /λ1 , λ3 /λ1 , . . . , λn /λ1 по модулю меньше единицы, и3.18. Численные методы для несимметричной проблемысобственных значенийпотому при k → ∞ вектор1 (λ /λ )k (z /z )212 1...(λn /λ1 )k (zn /z1 )(3.156)сходится к вектору (1, 0, 0, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
