NL: Файл eig.h


Функции
void	eig_tridiag_reduction (double *A, size_t n, int matq, double d, double *a)
	Приведение симметричной матрицы к трехдиагональному виду.
void	eig_tridiag (double d, double a, size_t n, int matq, double *Q, size_t rc)
	Собственные числа симметричной трехдиагональной системы.
void	eig_jacobi (double *A, size_t n, double w, int matq, double *Q, int nrot, int *rc)
	Метод Якоби решения симметричной проблемы собственных значений.
void	eig_balance (double *A, size_t n, size_t low, size_t high, double scal)
	Балансирование вещественной матрицы.
void	eig_hess_reduction (double *A, size_t n, size_t low, size_t high, size_t perm)
	Приведение матрицы к верхней форме Хессенберга.
void	eig_hess_transform_matrix (double *A, size_t n, size_t low, size_t high, size_t perm, double **Q)
	Трансформирующая матрица к верхней форме Хессенберга.
void	eig_hess (double *A, size_t n, size_t low, size_t high, double wr, double wi, int matq, double Q, size_t iter, size_t *rc)
	Собственные числа и векторы матрицы Хессенберга.
void	eig_balance_inverse (double *Q, size_t n, size_t low, size_t high, double scal)
	Обратное балансирование.
void	eig_norm_Inf (double *Q, size_t n, double wi)
	Нормирование собственных векторов.
void	eig_vectors (double *A, size_t n, size_t low, size_t high, double wr, double wi, double *Q)
	Вычисление собственных векторов по методу обратной итерации.

Подробное описание

Пусть

--- квадратная матрица. Собственным вектором называется такой ненулевой вектор $x$

, что $Ax=\lambda x$ для некоторого числа $\lambda$ . При этом $\lambda$ называется собственным значением (или собственным числом). Проблема собственных значений заключается в нахождении части (или всех) собственных значений и (если требуется) соответствующих им собственных векторов.

В библиотеке реализованы следующие алгоритмы решения проблемы собственных значений:

Функции

void eig_balance	(	double **	A,
		size_t	n,
		size_t *	low,
		size_t *	high,
		double *	scal
	)

Балансирование вещественной матрицы.

Балансирование вещественной матрицы $A$ перед приведением ее к форме Хессенберга для дальнейшего нахождения собственных чисел. Собственные числа исходной и сбалансированной матрицы одни и те же. Определяются строки с нулями вне диагонали. Остальные строки и столбцы домножаются на скаляры с тем, чтобы их норма была близка к $1$ . Строки с нулями вне диагонали имеют номера с $0$ по $low - 1$ и $hight+1$ по $n-1$ . Элементы вектора $scal$ на этих позициях равны соответствующим собственным векторам, на остальных позициях --- соответствующим масштабным множителям.

Примеры:: xeig.c.

void eig_balance_inverse	(	double **	Q,
		size_t	n,
		size_t	low,
		size_t	high,
		double *	scal
	)

Обратное балансирование.

По собственным векторам $Q$ , найденным для сбалансированной матрицы $A$ , находит собственные векторы исходной матрицы.

Примеры:: xeig.c.

void eig_hess	(	double **	A,
		size_t	n,
		size_t	low,
		size_t	high,
		double *	wr,
		double *	wi,
		int	matq,
		double **	Q,
		size_t *	iter,
		size_t *	rc
	)

Собственные числа и векторы матрицы Хессенберга.

Для матрицы Хессенберга $A$ находит собственные числа и, если $matq \ne 0$ , - собственные векторы. Действительные части собственных чисел возвращаются в векторе $wr$ , мнимые --- $wi$ . Для вещественных собственных чисел ( $wi[j]=0$ ) столбец $j$ содержит соответствующий собственный вектор. Для пары комплексно сопряженных собственных чисел ( $wr[j]=wr[j+1]$ , $wi[j]=-wi[j+1]$ ) $j\f$ -й столбец матрицы $Q\f$ содержит действительную часть $j$ -го собственного вектора, а $(j+1)$ -й - его мнимую часть. $(j+1)$ -й собственный вектор комплексно сопряжен к нему. В векторе $iter$ возвращается число итераций, используемых для нахождения каждого собственного числа.

Если $matq = 0$ , то на место матрицы $Q$ ничего не записывается и можно задать $Q = NULL$ .

На выходе, если все прошло успешно, то $rc = 0$ . В противном случае число итераций превысило 30 и в $rc$ возвращается количество верно найденных собственных чисел.

Примеры:: xeig.c.

void eig_hess_reduction	(	double **	A,
		size_t	n,
		size_t	low,
		size_t	high,
		size_t *	perm
	)

Приведение матрицы к верхней форме Хессенберга.

Квадратная вещественная матрица $A$ порядка $n$ методом вращений Хаусхолдера приводится к верхней форме Хессенберга. На выходе элементы верхнего треугольника и поддиагонали матрицы $A$ хранят соответствующие элементы матрицы Хессенберга. Остальные элементы хранят дополнительную информацию. На выходе $perm$ --- вектор перестановок --- в дальнейшем используется функцией elmtrans

Примеры:: xeig.c.

void eig_hess_transform_matrix	(	double **	A,
		size_t	n,
		size_t	low,
		size_t	high,
		size_t *	perm,
		double **	Q
	)

Трансформирующая матрица к верхней форме Хессенберга.

Для квадратной вещественной матрицы $A$ порядка $n$ строит трансформирующую матрицу $Q$ , приводящую к верхней форме Хессенберга. На входе параметры $low$ , $high$ --- из функции eig_balance, $A$ , $perm$ --- из eig_hess

Примеры:: xeig.c.

void eig_jacobi	(	double **	A,
		size_t	n,
		double *	w,
		int	matq,
		double **	Q,
		int *	nrot,
		int *	rc
	)

Метод Якоби решения симметричной проблемы собственных значений.

Функция вычисляет все собственные числа и собственные векторы вещественной симметричной матрицы $A$ , элементы верхнетреугольной части которой хранятся в соответствующих позициях в массиве $A$ . На выходе элемены выше диагонали испорчены. В векторе $w$ возвращаются собственные числа. Если на входе $matq \ne 0$ , то на выходе $Q$ содержит нормализованные собственные векторы. $nrot$ возвращает число использованных вращений Якоби.

Если $matq = 0$ , то на место матрицы $Q$ ничего не записывается и можно задать $Q = NULL$ .

На выходе, если все прошло успешно, то $rc = 0$ . В противном случае число итераций превысило 50 и в $rc$ возвращается $1$ .

Примеры:: xjacobi.c.

void eig_norm_Inf	(	double **	Q,
		size_t	n,
		double *	wi
	)

Нормирование собственных векторов.

Нормировка собственных векторов по их чебышевой (Inf) норме.

Примеры:: xeig.c.

void eig_tridiag	(	double *	d,
		double *	a,
		size_t	n,
		int	matq,
		double **	Q,
		size_t *	rc
	)

Собственные числа симметричной трехдиагональной системы.

$QL$ -алгоритм с неявными сдвигами для нахождения собственных векторов и собственных чисел действительной симметричной трехдиагональной матрицы $A$ . Матрица $A$ может быть получена с помощью функции eig_tridiag_reduction. На входе $d$ содержит диагональ матрицы $A$ , на выходе - собственные числа Вектор $e$ на входе содержит поддиагональ матрицы $A$ , на выходе вектор теряет свои значения.

Если $matq \ne 0$ , то ищутся также собственные векторы. Если необходимы собственные векторы трехдиагональной матрицы, то матрица $Q$ на входе должна быть единичной. Если нужно найти собственные векторы матрицы, к которой уже применяли функцию eig_tridiag_reduction, то $Z$ должна быть матрицей, возвращаемой функцией eig_tridiag_reduction. В обоих случаях $k$ -й столбец возвращаемой матрицы $Z$ есть нормированный собственный вектор, соответствующий собственному числу $d[k]$ . Если собственные векторы не нужны, то нужно положить $matq = 0$ . В этом случае $Q$ не используется и может быть равной $NULL$ .

Если $rc=0$ , то вычисление успешное, иначе на вычисление одного из собственных чисел было потрачено более $30$ итераций. В этом случае $rc$ возвращает количество верно найденных собственных чисел (и векторов).

Примеры:: xeigsym.c.

void eig_tridiag_reduction	(	double **	A,
		size_t	n,
		int	matq,
		double *	d,
		double *	a
	)

Приведение симметричной матрицы к трехдиагональному виду.

Приведение преобразованиями Хаусхолдера вещественной симметричной матрицы $A$ к трехдиагональному виду $B=Q^{\rm T}AQ$ . $d$ возвращает диагональные элементы, $a$ --- поддиагональные элементы, $a[0] = 0$ . Если $matq \ne 0$ , то на выходе матрица $A$ заменяется на ортогональную матрицу $Q$ , в противном случае в $A$ - ``случайные'' значения.

Примеры:: xeigsym.c.

void eig_vectors	(	double **	A,
		size_t	n,
		size_t	low,
		size_t	high,
		double *	wr,
		double *	wi,
		double **	Q
	)

Вычисление собственных векторов по методу обратной итерации.

Вычисление собственных векторов матрицы Хессенберга по собственным числам. Автоматически вызывается функцией eig_hess, если vec == 1