lopt10 (1013506)
Текст из файла
Лекция 102. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ О СОБСТВЕННЫХ ЗНАЧЕНИЯХ ИСОБСТВЕННЫХ ВЕКТОРАХ МАТРИЦПОСТАНОВКА ЗАДАЧИПусть A – действительная числовая квадратная матрица размеров (n × n) . Ненулевой вектор X = ( x1 ,..., x n )T размеров (n × 1) , удовлетворяющий условиюAX = λX ,называется собственным вектором матрицы A . Число λ называется собственным значением. Говорят, что собственный вектор X соответствует (принадлежит) собственномузначению λ .Равенство равносильно однородной относительно X системе:( A − λE )X = 0, ( X ≠ 0) .Система имеет ненулевое решение для вектора X (при известном λ ) при условииA − λE = 0 . Это равенство есть характеристическое уравнение:A − λE = Pn (λ) = 0 ,где Pn (λ) – характеристический многочлен n -й степени.
Корни λ1 , λ 2 ,..., λ n характеристического уравнения являются собственными (характеристическими) значениямиматрицы A , а соответствующие каждому собственному значению λ i , i = 1,..., n , ненулевые векторы X i , удовлетворяющие системеAX i = λ i X i(A − λ i E ) X iили= 0, i = 1,2,..., n ,являются собственными векторами.Требуется найти собственные значения и собственные векторы заданной матрицы.Различают полную и частичную проблему собственных значений, когда необходимо найти весь спектр (все собственные значения) и собственные векторы либо частьспектра, например: ρ( A ) = max λ i ( A ) и min λ i ( A ) .
Величина ρ(A ) называется спекiiтральным радиусом.З а м е ч а н и я.1. Если для собственного значения λ i найден собственный вектор X i , то векторμX i , где μ – произвольное число, также является собственным вектором, соответствующим этому же собственному значению λ i .2. Симметрическая матрица имеет полный спектр λ i , i = 1, n , действительных собственных значений; k-кратному корню характеристического уравнения симметрическойматрицы соответствует ровно k линейно независимых собственных векторов.82А. МЕТОД ИТЕРАЦИЙДля решения частичной проблемы собственных значений и собственных векторовв практических расчетах часто используется метод итераций (степенной метод).
На егооснове можно определить приближенно собственные значения матрицы A и спектральный радиус ρ( A ) = max λ i ( A ) .Пусть матрица A имеет n линейно независимых собственных векторовiX , i = 1, n ,исобственныезначенияматрицыAтаковы,чтоρ( A ) = λ1 ( A ) > λ 2 ( A ) ≥ ... ≥ λ n ( A ) .Методика решения задачиШаг 1. Выбрать произвольное начальное (нулевое) приближение собственноговектора X 1(0 ) (второй индекс в скобках здесь и ниже указывает номер приближения, апервый индекс без скобок соответствует номеру собственного значения). Положитьk = 0.x i1(1)(1)1(1)1(0)= AX, λ1 =, где i – любой номер 1 ≤ i ≤ n , и поШаг 2. Найти Xx i1(0)ложить k = 1.Шаг 3. Вычислить X 1(k +1) = AX 1(k ) .Шаг 4. Найти λ(1k +1) =x i1(k +1)x i1(k ), где x i1(k +1) , x i1(k ) – соответствующие координатывекторов X 1(k +1) и X 1(k ) .
При этом может быть использована любая координата с номером i, i = 1, n.Шаг 5. Если Δ = λ(1k +1) − λ(1k ) ≤ ε, процесс завершить и положить λ1 ≅ λ(1k +1) .Если Δ > ε , положить k = k + 1 и перейти к п.3.З а м е ч а н и я.1. Процесс последовательных приближенийX 1(1) = AX 1(0) , X 1(2) = AX 1(1) = A 2 X 1(0) ,...,X 1(k ) = AX 1(k −1) = A ⋅ A k −1 X 1(0) = A k X 1(0) ,...сходится, т.е. при k → ∞ вектор X 1( k ) стремится к собственному вектору X 1 .2. Используя λ1 , можно определить следующее значение λ 2 по формулеλ2 =x i1(k +1) − λ1 x i1(k )x i1(k ) − λ1 x i1(k −1)(i = 1,2,..., n) .Эта формула дает грубые значения для λ 2 , так как значение λ1 является приближенным. Если модули всех собственных значений различны, то на основе последнейформулы можно вычислять и остальные λ j ( j = 3,4,..., n) .833.
После проведения некоторого числа итераций рекомендуется «гасить» растущиекомпоненты получающегося собственного вектора. Это осуществляется нормировкойX 1(k ).вектора, например, по формулеX 1(k )1⎛5 1 2⎞⎜⎟Пример 1. Для матрицы A = ⎜ 1 4 1 ⎟ найти спектральный радиус методом ите⎜2 1 3⎟⎝⎠раций с точностью ε = 0,1 . 1. Выбирается начальное приближение собственного вектора X (0) = (1; 1; 1)T .Положим k = 0.2. НайдемX1(1)= AX1(0)⎛ 5 1 2 ⎞ ⎛1 ⎞ ⎛ 8 ⎞⎜⎟ ⎜ ⎟ ⎜ ⎟= ⎜ 1 4 1 ⎟ ⋅ ⎜1 ⎟ = ⎜ 6 ⎟ ;⎜ 2 1 3 ⎟ ⎜1 ⎟ ⎜ 6 ⎟⎝⎠ ⎝ ⎠ ⎝ ⎠λ(11)=x11(1)x11(0)=8= 8,1положим k = 1.3. ВычислимX1(2)= AX1(1)⎛ 5 1 2 ⎞ ⎛ 8 ⎞ ⎛ 58 ⎞⎜⎟ ⎜ ⎟ ⎜ ⎟= ⎜ 1 4 1 ⎟ ⋅ ⎜ 6 ⎟ = ⎜ 38 ⎟ .⎜ 2 1 3 ⎟ ⎜ 6 ⎟ ⎜ 40 ⎟⎝⎠ ⎝ ⎠ ⎝ ⎠4.
Найдемλ(12)5.=x11(2)x11(1)=58= 7,25.8Так как λ(12) − λ(11) = 0,75 > ε , то процесс необходимо продолжить.Результаты вычислений удобно представить в виде табл. 1.Таблица 1kx11(k )x 21(k )x 31(k )λ(1k )λ(1k ) − λ(1k −1)0123418584082838163825016821640274188887,257,0346,95590,750,1160,078 < εТочность по λ(1k ) достигнута на четвертой итерации. Таким образом, в качествеприближенного значения λ1 берется 6,9559 , а в качестве собственного вектора принима-84ется X 1 = (2838, 1682, 1888)T . Так как собственный векторопределяется с точно-стью до постоянного множителя, то X 1 лучше пронормировать, т.е.
поделить все егокомпоненты на величину нормы, например X 1 = max X i1 . Для рассматриваемого приi⎛ 2838 ⎞ ⎛ 1,000 ⎞⎟⎟ ⎜1 ⎜мера получим X =⎜ 1682 ⎟ = ⎜ 0,5927 ⎟ .2838 ⎜⎟⎟ ⎜⎝ 1888 ⎠ ⎝ 0,6652 ⎠В качестве собственного значения λ11x11(4)x11(3)x 21(4)x 12(3)2838== 6,9559 , но и408среднее арифметическоеможно взять не только отношениеx 31(4) 18881682== 6,7280 ;== 6,8905 , а также их250274x 31(3)6,9559 + 6,728 + 6,8905= 6,8581 . 3Б. МЕТОД ВРАЩЕНИЙМетод используется для решения полной проблемы собственных значений симметрической матрицы и основан на преобразовании подобия исходной матрицыA ∈ R n × n с помощью ортогональной матрицы H .Две матрицы A и A (i ) называются подобными ( A ∼ A (i ) или A (i ) ∼ A ), еслиA (i ) = H −1 AH или A = HA (i ) H −1 , где H – невырожденная матрица.В методе вращений в качестве H берется ортогональная матрица, такая, чтоTHH = H T H = E , т.е.
H T = H −1 . В силу свойства ортогонального преобразованияевклидова норма исходной матрицы A не меняется. Для преобразованной матрицы A (i )сохраняется ее след и собственные значения λ i :tr A =n∑ aii =i =1n∑ λ i ( A) = tr A (i ) .i =1При реализации метода вращений преобразование подобия применяется к исходной матрице A многократно:(A (k +1) = H (k ))−1(A ( k ) H ( k ) = H (k ))TA (k ) H (k ) ,k = 0,1,... .Формула определяет итерационный процесс, где начальное приближениеA= A .
На каждой k -й итерации для некоторого выбираемого при решении задачи недиагонального элемента aij(k ) , i ≠ j , определяется ортогональная матрица H (k ) , приво(0 )дящая этот элемент aij(k +1) (а также и a (jik +1) ) к нулю. При этом на каждой итерации в качестве aij(k ) выбирается наибольший по модулю. Матрица H (k ) , называемая матрицейвращения Якоби, зависит от угла ϕ(k ) и имеет вид85H (k )⎛1⎜⎜#⎜0⎜⎜0⎜⎜0= ⎜#⎜⎜0⎜0⎜⎜0⎜#⎜⎜⎝0"%"""%"""%"00##100 cos ϕ(k )00##000 sin ϕ(k )00##000#001#000#0i -й столбец"%"""%"""%"00##000 − sin ϕ(k )00##100 cos ϕ(k )00##000#000#001#0"%"""%"""%"0⎞⎟#⎟0⎟⎟0⎟⎟0⎟#⎟.⎟0⎟0⎟⎟0⎟#⎟⎟1 ⎟⎠i -я строкаj -я строкаj -й столбецВ данной ортогональной матрице элементы на главной диагонали единичные, кроме hii(k ) = cos ϕ(k ) и h (jjk ) = cos ϕ(k ) , а hij(k ) = − sin ϕ(k ) , h (jik ) = sin ϕ(k ) ( hij – элементыматрицы H ).Угол поворота ϕ(k ) определяется по формулеtg 2ϕ(k )=2aij(k )aii(k ) − a (jjk )= Pk ;ϕ (k ) =1arctg Pk ,2π, i < j (элемент a ij( k ) выбирается в верхней треугольной наддиагональной2πчасти матрицы A ) .
Заметим, что при aii( k ) = a (jjk ) получается ϕ( k ) = .4В процессе итераций сумма квадратов всех недиагональных элементов σ( A (k ) )где 2ϕ(k ) ≤при возрастании k уменьшается, так что σ( A (k +1) ) < σ( A (k ) ) . Элементы aij(k ) , приведенные к нулю на k -й итерации, на последующей итерации немного возрастают. Приk → ∞ получается монотонно убывающая ограниченная снизу нулем последовательность σ( A (1) ) > σ( A (2) ) > " > σ( A (k ) ) " . Поэтому σ( A (k ) ) → 0 при k → ∞ .
Это и озна0 ⎞⎛ λ1⎜⎟(k )чает сходимость метода. При этом A%→Λ=⎜⎟.⎜0λ n ⎟⎠⎝Методика решения задачиШаг 1. Положить k = 0, A (0) = A и задать ε > 0.86Шаг 2. Выделить в верхней треугольной наддиагональной части матрицы A (k )максимальный по модулю элемент aij(k ) , i < j .Если aij(k ) ≤ ε для всех i ≠ j , процесс завершить. Собственные значения опреде-()ляются по формуле λ i A (k ) = aii(k ) , i = 1, n.Собственные векторы X i находятся как i -е столбцы матрицы, получающейся врезультате перемножения:()ν k = H (0) H (1) H (2) " H (k −1) = X 1 , X 2 , X 3 ,..., X n .Если aij(k ) > ε , процесс продолжается.Шаг 3.
Найти угол поворота по формуле(k )(k )ϕ2aij1= arctg2aii( k ) − a (jjk )(при aii( k ) = a (jjk ) получается ϕ( k ) =π).4Шаг 4. Составить матрицу вращения H (k ) .Шаг 5. Вычислить очередное приближение(A (k +1) = H (k ))TA (k ) H (k ) .Положить k = k + 1 и перейти к п.2.З а м е ч а н и я.1. Контроль правильности выполнения действий на каждой итерации осуществляется путем проверки сохранения следа преобразуемой матрицы.2.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.