Файл svd.h

Сингулярное разложение. Подробнее...


Функции

void svd_decomp (double **A, size_t m, size_t n, double *w, int matu, double **U, int matv, double **V, size_t *ierr)
 Сингулярное разложение матрицы.
void svd_correct (double *w, size_t n, double rel_err)
 Автоматическое корректирование вычисленных сингулярных чисел.
double svd_cond (double *w, size_t n)
 Вычисление спектрального числа обусловленности на основе сингулярного разложения.
void svd_least_squares (double **U, double *w, double **V, size_t m, size_t n, double *b, double *x)
 Нахождение нормального псевдорешения системы линейных уравнений на основе сингулярного разложения.

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

Сингулярное разложение.

Файл содержит функции, строящие и использующие сингулярное разложение матрицы.

Cингулярным разложением прямоугольной матрицы $A$ размера $m\times n$, $m \ge n$ называется ее представление $A = U S V^{\rm T}$, где

Отношение максимального сингулярного числа к минимальному есть спектральное число обусловленности квадратной матрицы. Число $r$ ненулевых сингулярных чисел указывает ранг матрицы. При вычислениях на компьютере вместо нулевых сингулярных чисел могут быть получены ненулевые, поэтому вычисленные сингулярные числа необходимо отредактировать с учетом погрешности вычислений.

Сингулярное разложение используется для нахождения нормального псевдорешения прямоугольной системы $Ax = b$. Вектор x называется псевдорешением системы $Ax=b$, если на нем достигается минимум $\|Ax-b\|_2$. Псевдорешение $x$ называется нормальным, если среди всех псевдорешений оно имеет минимальную длину. Для любой системы нормальное псевдорешение единственно.

Пусть $S={\rm diag}(\sigma_1,\dots,\sigma_r,0,\dots,0)$, $U=(U_1, U_2)$, $V=(V_1, V_2)$, где $U_1$, $V_1$ имеют по $r$ столбцов каждая. Нормальное псевдорешение можно найти по формуле $x = V_1 S_1^{-1} U_1^{\rm T} b$.

Функции

double svd_cond ( double *  w,
size_t  n 
)

Вычисление спектрального числа обусловленности на основе сингулярного разложения.

Функция вычисляет спектральное число обусловленности матрицы $A$ на основе найденного функцией svd_decomp сингулярного разложения $A = USV^{\rm T}$. Матрица A имеет размеры $m\times n$, $m \ge n$. Спектральное число обусловленности равно отношению максимального сингулярного значения к минимальному.

Трудоемкость:

void svd_correct ( double *  w,
size_t  n,
double  rel_err 
)

Автоматическое корректирование вычисленных сингулярных чисел.

Функция зануляет близкие к нулю сингулярные числа матрицы $A$, вычисленные функцией svd_decomp, с учетом задаваемой относительной погрешности $rel\_err$. Матрица A имеет размеры $m\times n$, $m \ge n$. Величина $rel\_err$ должна отражать ошибку в исходных данных (в матрице $A$). Если данные рассматриваются как точные, то необходимо задать $rel\_err = 0$. В этом случае функция установит значение $rel\_err$, отражающее ошибку при вычислениях в самой функции svd_decomp, а именно, $\varepsilon\cdot n$, где $\varepsilon \approx 10^{16}$ - расстояние между $1$ и следующим за ним числом в арифметике двойной точности. Зануляются сингулярные значения, не превосходящие $rell\_err \cdot \sigma_{\max}$, где $\sigma_{\max}$ - максимальное сингулярное значение.

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

void svd_decomp ( double **  A,
size_t  m,
size_t  n,
double *  w,
int  matu,
double **  U,
int  matv,
double **  V,
size_t *  ierr 
)

Сингулярное разложение матрицы.

Функция находит сингулярное разложение $A = U\cdot S\cdot V^{\rm T}$ вещественной матрицы A размера $m\times n$, $m \ge n$.

Алгоритм состоит из двух частей. На первом этапе отражениями Хаусхолдера матрица $A$ приводится к двухдиагональному виду. На втором этапе вариантом $QR$-алгоритма двухдиагональная матрица приводится к диагональному виду $S$.

Функция является переводом фортрановской программы svd из книги [FMM].

Трудоемкость:

Дополнительная память: O(n)

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

void svd_least_squares ( double **  U,
double *  w,
double **  V,
size_t  m,
size_t  n,
double *  b,
double *  x 
)

Нахождение нормального псевдорешения системы линейных уравнений на основе сингулярного разложения.

Функция находит нормальное псевдорешение системы линейных уравнений $Ax = b$ на основе вычисленного функцией svd_decomp сингулярного разложения $A = USV^{\rm T}$. Матрица A имеет размеры $m\times n$, $m \ge n$. При вычислении псевдорешения используются только ненулевые сингулярные значения. Перед вызовом функции рекомендуется занулить близкие к нулю сингулярные значения (например, с помощью функции svd_correct).

Трудоемкость:

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

Документация по NL. Последние изменения: Mon Oct 9 12:25:55 2006. Создано системой  doxygen 1.4.7