П.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

1. Задачи линейной алгебры…………………………………………………………………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

Приложение

[*] Скалярное произведение может быть определено также другими способами.

[†] Программная реализация перестановок строк матрицы с помощью современных возможностей объектно- ориентированного программирования может быть реализована более эффективно, нежели непосредственное умножение с матрицей перестановок.