4.3. Метод вращений.
Наиболее эффективный подход к проблеме собственных значений основан на использовании преобразований подобия, позволяющих привести исходную матрицу к треугольному, диагональному или блочно-диагональному виду. Поскольку преобразование подобия не меняет спектр матрицы, то применение такого рода преобразований во многих случаях приводит к решению полной проблемы собственных значений. Наиболее эффективны преобразования подобия в случае симметричных матриц.
Однако во многих случаях достаточно предположить, что среди собственных значений матрицы отсутствуют кратные. В этом случае существует преобразование подобие, приводящее матрицу к диагональному виду.
Один из способов
построения искомого преобразования
подобия состоит в использовании
элементарных матриц плоских вращений
:
(4.10)
Матрица
(для определенности пусть
)
отличается от единичной матрицы только
элементами
и
.
Несложно убедиться, что матрицы
являются ортогональными. В силу этого
преобразования
,
называемое преобразованием плоских
вращений, или преобразованием Гивенса,
является преобразованием подобия. При
умножении произвольной матрицы слева
(или справа) на матрицу
результирующая матрица отличается от
исходной лишь элементами строк с номерами
и
(или столбцами с соответствующими
номерами).
Полагая
,
рассмотрим произведения:
:
,
:
.
Определим угол
вращения таким образом, чтобы
.
С учетом последнего равенства данное
условие приводит к выражению для угла
:
.
Используя тригонометрические тождества, имеем:
,
. (4.11)
При выбранном угле
поворота преобразование
в отношении симметричной матрицы
обладает замечательным свойством. В
результате данного преобразования
уменьшается общая сумма квадратов
недиагональных элементов результирующей
матрицы. Многократное применение такого
рода преобразования с матрицами вращения
такими, что на текущем шаге
приводит к сходимости последовательности
матриц
,
к матрице диагонального вида, при этом
на диагонали результирующей матрицы
будут находиться приближенные значения
собственных чисел исходной матрицы
.
Пример реализации метода вращений в
среде Matlab
приведен в Приложении.
Упражнения.
1. Показать, что при умножении имеет место тождество
.
Литература
1. А.А.Самарский, А.В.Гулин. Численные методы. М., Наука, 1989.
2. В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М., Наука, 1984.
3. Д.К.Фадеев, В.Н.Фадеева. Вычислительные методы линейной алгебры. СПт. 2002.
П.1. Реализация итерационного метода вращений для расчета собственных значений симметричной матрицы
% Проблема собственных значений
% Метод Вращений
N=22; % Задание Размерности матрицы
A=rand(N); %Формирование матрицы случайных значений
A=A*A'; %Формирование симметричной матрицы
Err=1; %Инициация начального значения погрешности
kk=0; %Инициация счетчика итераций
while Err>1.e-9 % Начало цикла итерационного процесса (пока Err>1/e9)
kk=kk+1; % Прирощение счетчика итераций
for k=2:N % Вниз по столбцам
%Выбор максимального по модулю элемента к-ой строки слева
%от главной диагонали для исключения поддиагональных элементов
[mm,m]=find((abs(A(k,1:k-1))-max(abs(A(k,1:k-1))))==0);
w=2*A(k,m)/(A(k,k)-A(m,m)); %Тангенс дв-го угла вращения
ss=sqrt(1+w^2);
s=sign(w)*sqrt((ss-1)/(2*ss));%Синус угла вращения
c=sqrt((ss+1)/(2*ss)); %Косинус угла вращения
T=eye(N); %%%%%%%%%%%%%%%%%%%%%%
T(m,m)=c; %Формирование матрицы
T(k,k)=c; %вращения
T(k,m)=-s; %T_km
T(m,k)=s; %%%%%%%%%%%%%%%%%%%%%%
A=T'*A*T; % Преобразование Гивенса (плоских вращений)
end
AA=A-diag(diag(A)); % Выделение НЕдиагональных элементов матрицы
Err=sum(sum(AA.^2)); % Выч. суммы квадратов недиагональных элементов
end % Конец цикла итерационного процесса
S=sparse(A); %Формат разреженной матрицы
spy(abs(S)>1e-5) %Визуализация структуры разреженной матрицы (|a_ij|>1.e-5)
{'Iterations' kk} % Вывод числа итераций
'eigenvalues'
Labdf=sort(diag(A),'descend') % Спектр матрицы в порядке убывания
Содержание
Введение………………………………………………………………………………………..3
Задачи линейной алгебры…………………………………………………………………4
1.1 Основные понятия ………………………………………………………………..4
1.2 Нормы векторов и матриц………………………………………………………...5
1.3. Системы линейных алгебраических уравнений. Разрешимость
и устойчивость………………………………………………………………………….6
2. Прямые методы решения систем ЛАУ……………………………………………………..7
2.1 Метод Гаусса………………………………………………………………………..8
2.2 Метод Гаусса с выбором ведущего элемента…………………………………….9
2.3 LU-факторизация………………………………………………………………….10
2.4 Разложение Холецкого (метод квадратного корня)…………………………….12
2.5 Число обусловленности матрицы и оценки погрешности решения систем линейных алгебраических уравнений………………………………………………..13
2.6 Геометрический смысл и примеры плохой обусловленности матриц………...14
3. Итерационные методы решения систем ЛАУ
3.1 Общая схема двухслойного итерационного метода. Сходимость………………16
3.2 Вычислительная сложность итерационных методов. Число итераций………..18
3.3 Метод простой итерации………………………………………………………….19
3.4 Оптимальный выбор параметра нестационарного итерационного метода…...20
3.5 Градиентные методы. Методы наискорейшего спуска………………………….21
3.6 Методы сопряженных градиентов………………………………………….…….23
3.7 Неявные итерационные методы и выбор переобусловливателя…………….….26
4. Проблема собственных значений и собственных векторов.
4.1 Свойства собственных значений и собственных векторов матриц……………..27
4.2 Степенной метод……………………………………………………………………29
4.3 Метод вращений……………………………………………………………………30
Литература ……………………………………………………………………………...31
Приложение
1 Скалярное произведение может быть определено также другими способами в соответствии с аксиомами скалярного умножения.
1 Программная реализация перестановок строк матрицы с помощью современных возможностей объектно- ориентированного программирования может быть реализована более эффективно, нежели непосредственное умножение с матрицей перестановок.