-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathreadme_08_04.txt
121 lines (105 loc) · 8.57 KB
/
readme_08_04.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
Запуск программы
evc [входной файл] [выходной файл] [опции]
Входной файл должен следовать за evc. Выходной файл должен следовать за входным файлом.
Доступны следующие опции:
-d вывод отладочной информации [по умолчанию ВЫКЛ]
-e вывод информации информации об ошибках [по умолчанию ВЫКЛ]
-p вывод входной матрицы до и после преобразований [по умолчанию ВЫКЛ]
-t вывод времени работы алгоритма [по умолчанию ВЫКЛ]
-prec=<num> точность локализации нуля [по умолчанию -- 1e-14]
-eps=<num> точность решения [по умолчанию -- 1e-10]
-max_iter=<num> ограничивает число итераций алгоритма [по умолчанию -- 0, т.е. нет ограничений на итерации]
-h, -? вывод подсказки и завершение программы
/**
* Функция приведения исходной матрицы к трехдиагональному виду унитарным подобием методом вращений.
* Результат упрощения матрицы будет записан вместо исходной матрицы по указателю A.
* Дополнительной памяти не требуется, т.к. текующее преобразование матрицы
* не зависит от прошлых преобразований.
* @param n размерность матрицы
* @param A указатель на исходную матрицу
* @param tmp указатель на дополнительный вектор
* @param precision определяет числа, меньше какого считать нулем
* @return 0 - работа завершена успешно,
* -1 - метод упрощения не применим к данной матрице
*/
Алгоритм заключается в следуюущем:
1. Построить матрицу вращения T_ij такую, что на позиции (i, i) находится
число alpha, на позиции (i, j) -- -betta, на позиции (j, i) -- betta, на позиции (j, j) -- alpha,
на главной диагонали -- единицы, в остальных позициях -- нули.
alpha = A[i*n+i-1] / sqrt(A[i*n+i-1] * A[i*n+i-1] + A[j*n+i-1] * A[j*n+i-1])
betta = -A[j*n+i-1] / sqrt(A[i*n+i-1] * A[i*n+i-1] + A[j*n+i-1] * A[j*n+i-1])
2. Умножить матрицу A слева на матрицу T_ij. При этом меняются только строки под номерами i, j
3. Построить транспонированную матрицу вращения (T_ij)^t
4. Умножить матрицу A справа на матрицу(T_ij)^t. При этом меняются только столбцы под номерами i, j
В силу ассоциативности умножения матриц, умножение слева и справа производится в одной итериции
int sim_08_04(int n, double* A, double* tmp, double precision)
/**
* Функция, определяющая размер дополнительной памяти.
* Для данного метода решений дополнительной памяти не требуется.
* @param n размерность матрицы
* @return размер выделяемой дополнительной памяти
*/
int sim_memsize_08_04(int n)
/**
* Функция, проверяющая входную матрицу на симметричность
* @param n размерность матрицы
* @param A указатель на матрицу
* @return 0 - матрица не симметрична
* 1 - матрица симметрична
*/
int is_simmetric(int n, double* A)
/**
* Функция построения собственных значений матрицы LR методом для симметричных матриц.
* Дополнительной памяти не требуется, т.к. текующее преобразование матрицы
* не зависит от прошлых преобразований.
* @param n размерность матрицы
* @param max_iterations ограничение на число итераций алгоритма
* @param epsilon точность
* @param A указатель на матрицу
* @param E указатель на полученные собственные значения
* @param tmp указатель на дополнительный вектор
* @param precision определяет числа, меньше какого считать нулем
* @return 0 - работа завершена успешно,
* 1 - метод не сходится за указанное число итераций,
* -1 - метод поиска собственных значений не применим к данной матрице
*/
Алгоритм заключается в следуюущем:
1. Разложить трехдиагональную матрицу, полученную после применения функции sim_08_04,
на матрицу L(k) и R(k) при помощи функции LR_decomposition.
2. Вычислить матрицу A(k+1) = R(k) * L(k).
Данные действия будут повторяться до тех пор, пока диагональные элементы не сойдутся, то есть
будут меняться не более, чем на epsilon, либо заданное число итераций (но может сойтись и раньше).
int evc_08_04(int n, int max_iterations, double epsilon, double* A, double* E, double* tmp, double precision)
/**
* Функция, определяющая размер дополнительной памяти.
* Для данного метода решений дополнительной памяти не требуется.
* @param n размерность матрицы
* @return размер выделяемой дополнительной памяти
*/
int evc_memsize_08_04(int n)
/**
* Функция LR разложения трехдиагональной матрицы по формулам для данного вида матрицы.
* Матрицы L и R двухдиагональны, при этом у матрицы L на главной диагонали единицы.
* Матрица L хранится под главной диагональю исходной матрицы.
* Матрица R хранится на главной диагонали и над главной диагональю исходной матрицы.
* @param n размерность матрицы
* @param A указатель на матрицу
* @param precision "точность локализации нуля"
*/
void LR_decomposition(int n, double* A, double precision)
/**
* Функция, вычисляющая произведение матриц R на L, получившихся в результате LR разложения.
* Диагональные элементы, получившиеся в результате данного произведения, будут приближениями
* к собственным значениям матрицы
* @param n размерность матрицы
* @param A указатель на матрицу
*/
void compute_next_A(int n, double* A)
/**
* Функция, определяющая, достигла ли точность вычисления собственных значений указанного epsilon.
* Под точностью подразумевается сходимость матрицы L к единичной матрице.
* @param n размерность матрицы
* @param epsilon точность вычисления
* @param A указатель на матрицу
*/
int is_epsilon_reached(int n, double epsilon, double* A)