lopt10 (Лекционный курс)
Описание файла
Файл "lopt10" внутри архива находится в папке "Лекционный курс". PDF-файл из архива "Лекционный курс", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Лекция 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.