УМК (1013374), страница 14
Текст из файла (страница 14)
Продолжая вычисления, получаемx 2(1)x1(2)=+1 =x 2(1)x1(2)1319( 2)=−+ 1 = − + 1 = , x2 =+1 = = +1 =и т.д. В результате имеем488242T⎛2 6⎞процесс, сходящийся к точке x ∗ = ⎜ ; ⎟ .⎝5 5⎠80x2x262 x1 + x 2 = 22x1 − 2 x 2 = −212x1 − 2 x 2 = −2x (0 )0−211x1−20 x (0 )x12 x1 + x 2 = 2абРис.
1Переставим уравнения в системе:x1 − 2 x 2 = −2 ,2 x1 + x 2 = 2 .В полученной системе диагональные элементы не преобладают. Уравнения методаЗейделя имеют видx1(k +1) = 2 x 2(k ) − 2 ,x 2(k +1) = −2 x1(k +1) + 2 .При x (0) = (0 ; 0)T получаем x1(1) = −2 , x 2(1) = 6 и т.д. В результате имеем расходящийся процесс (рис. 1,б).2. Условие преобладания диагональных элементов является достаточным для сходимости, но не является необходимым.3. Процесс (1.1) называется последовательным итерированием, так как на каждойитерации полученные из предыдущих уравнений значения подставляются в последующие.
Как правило, метод Зейделя обеспечивает лучшую сходимость, чем метод простыхитераций (за счет накопления информации). Метод Зейделя может сходиться, если расходится метод простых итераций, и наоборот.4. При расчетах на компьютере удобнее пользоваться формулой (1.3).5. Преимуществом метода Зейделя, как и метода простых итераций, является егосамоисправляемость.6. Метод Зейделя имеет преимущества перед методом простых итераций, так какон всегда сходится для нормальных систем линейных алгебраических уравнений, т.е.
таких систем, в которых матрица A является симметрической и положительно определенной. Систему линейных алгебраических уравнений с невырожденной матрицей A всегдаможно преобразовать к нормальной, если ее умножить слева на матрицу AT . Таким образом, система AT A x = AT b является нормальной, а матрица AT A - симметрической.81Лекция 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 ) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
