Файл qr.h

$QR$-разложение. Подробнее...


Функции

void qr_decomp (double **A, size_t m, size_t n, double *t)
 $QR$-разложение матрицы.
void qr_decomp_t (double **At, size_t m, size_t n, double *t)
 $QR$-разложение матрицы, в отличие от qr_decomp работает с транспонированной матрицей.
void qr_solve (double **QR, size_t n, double *t, double *b)
 Решение системы линейных уравнений.
void qr_solve_t (double **QRt, size_t n, double *t, double *b)
 Решение системы линейных уравнений, в отличие от qr_solve работает с транспонированной матрицей.
void qr_least_squares (double **QR, size_t m, size_t n, double *t, double *b, double *r)
 `Решение' переопределенной системы методом наименьших квадратов.
void qr_least_squares_t (double **QRt, size_t m, size_t n, double *t, double *b, double *r)
 `Решение' переопределенной системы методом наименьших квадратов, в отличие от qr_least_squares работает с транспонированной матрицей.
void qr_least_unpack (double **QR, size_t m, size_t n, double *t, double **Q, double **R)
 Полное представление $QR$-разложения.
void qr_least_unpack_t (double **QRt, size_t m, size_t n, double *t, double **Q, double **R)
 Полное представление $QR$-разложения, в отличие от qr_least_unpack работает с транспонированной матрицей.

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

$QR$-разложение.

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

Произвольная $m\times n$ матрица $A$ ранга $n$ допускает разложение вида $A=QR$, где $Q$ - $m\times n$ матрица с ортогональными столбцами, $R$ - верхнетреугольная $n\times n$ матрица. Такое разложение можно использовать для решения системы линейных уравнений $Ax=b$, сводя ее к треугольной системе $Rx=Q^{\rm T}b$. Данная треугольная система позволяет также найти псевдорешение (в смысле метода наименьших квадратов) переопределенной системы. $QR$-разложение используется также для нахождения ортонормированного базиса подпространства. Если $A$ имеет полный столбцовый ранг, то столбцы матрицы $Q$ составляют ортонормированный базис подпространства, натянутого на столбцы матрицы $A$.

Заметки:
Файл содержит два типа функций. К первому типу относятся функции в название которых отсутствует постфикс _t, ко второму типу относятся функции в которых есть постфикс _t. Функции второго типа используются, если исходная матрица была транспонирована. В силу особенностей современных процессоров, функции второго типа работают существенно быстрее, хотя алгоритмы не отличаются. Поэтому для решения больших систем линейных уравнений с помощью метода $QR$-разложения, предпочтительней сначала транспонировать матрицу, а затем использовать функции второго типа.

Функции

void qr_decomp ( double **  A,
size_t  m,
size_t  n,
double *  t 
)

$QR$-разложение матрицы.

Функция находит $QR$-разложение $m \times n$ матрицы A ранга $n$. На выходе диагональ и верхнетреугольная часть матрицы $A$ содержат элементы матрицы $R$. Матрица $Q$ представлена элементами ниже диагонали и вектором $t$. Вектор $t$ имеет длину $n$. Матрица $Q$ определяется произведением матриц отражений Хаусхолдера: $Q = Q_k\cdot\dots\cdot Q_2\cdot Q_1$, где $Q_i=E-t_i v_i v_i^{\rm T}$ и $v_i=(0,...,1,A_{i+1,i},A_{i+2,i},...,A_{m,i})$. Такая же схема используется в библиотеках LAPACK, GSL и др.

Для разложения используется алгоритм вращений Хаусхолдера (См. [GolubVanLoan], алгоритм 5.2.1).

Трудоемкость: $2n^2m-(2/3)n^3+O(mn)$

Примеры:
xqr.c и xqrls.c.

void qr_decomp_t ( double **  At,
size_t  m,
size_t  n,
double *  t 
)

$QR$-разложение матрицы, в отличие от qr_decomp работает с транспонированной матрицей.

Трудоемкость: $2n^2m-(2/3)n^3+O(mn)$

void qr_least_squares ( double **  QR,
size_t  m,
size_t  n,
double *  t,
double *  b,
double *  r 
)

`Решение' переопределенной системы методом наименьших квадратов.

Функция находит псевдорешение переопределенной $m \times n$ системы линейных уравнений $Ax=b$ ранга $n$, используя предварительно найденное $QR$-разложение матрицы $A$. $QR$-разложение должно быть представлено матрицей $QR$ и вектором $t$, возвращаемыми функцией qr_decomp. Псевдорешение минимизирует евклидову норму невязки $\|Ax-b\|_2$. Псевдорешение $x$ записывается на месте вектора правой части $b$. Невязка $Ax-b$ возвращается в векторе $r$.

Трудоемкость: $mn+n^2$

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

void qr_least_squares_t ( double **  QRt,
size_t  m,
size_t  n,
double *  t,
double *  b,
double *  r 
)

`Решение' переопределенной системы методом наименьших квадратов, в отличие от qr_least_squares работает с транспонированной матрицей.

Функция находит псевдорешение переопределенной $m \times n$ системы линейных уравнений $A^{\rm T}x=b$, используя предварительно найденное $QR$-разложение матрицы $A^T$. $QR$-разложение должно быть представлено матрицей $QR$ и вектором $t$, возвращаемыми функцией qr_decomp_t. Псевдорешение минимизирует евклидову норму невязки $\|A^{\rm T}x-b\|_2$. Псевдорешение $x$ записывается на месте вектора правой части $b$. Невязка $A^{\rm T}x-b$ возвращается в векторе $r$.

Трудоемкость: $mn+n^2$

void qr_least_unpack ( double **  QR,
size_t  m,
size_t  n,
double *  t,
double **  Q,
double **  R 
)

Полное представление $QR$-разложения.

Функция находит матрицы $Q$, $R$ размеров $m \times n$ и $n\times n$ соответственно, представленные в запакованном формате $QR$, $t$.

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

void qr_least_unpack_t ( double **  QRt,
size_t  m,
size_t  n,
double *  t,
double **  Q,
double **  R 
)

Полное представление $QR$-разложения, в отличие от qr_least_unpack работает с транспонированной матрицей.

Функция находит матрицы Q, R размеров $m \times n$ и $m\times m$ соответственно, представленные в запакованном формате $QR$, $t$.

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

void qr_solve ( double **  QR,
size_t  n,
double *  t,
double *  b 
)

Решение системы линейных уравнений.

Функция находит решение квадратной системы линейных уравнений $Ax=b$ порядка $n$. Функция использует предварительно найденное $QR$-разложение матрицы $A$, представленное матрицей $QR$ и вектором $t$, которые возвращаются функцией qr_decomp. Решение $x$ записывается на месте вектора правой части $b$. Матрица $QR$ и вектор $t$ не меняются данной функцией и могут быть использованы для решения системы с другой правой частью.

Используется алгоритм прямой и обратной подстановки.

Трудоемкость: $n^2+O(n)$

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

void qr_solve_t ( double **  QRt,
size_t  n,
double *  t,
double *  b 
)

Решение системы линейных уравнений, в отличие от qr_solve работает с транспонированной матрицей.

Функция находит решение квадратной системы линейных уравнений $A^Tx=b$ порядка $n$. Функция использует предварительно найденное $QR$-разложение матрицы $A$, представленное матрицей $QR$ и вектором $t$, которые возвращаются функцией qr_decomp_t. Решение $x$ записывается на месте вектора правой части $b$. Матрица $QR$ и вектор $t$ не меняются данной функцией и могут быть использованы для решения системы с другой правой частью.

Используется алгоритм прямой и обратной подстановки.

Трудоемкость: $n^2+O(n)$

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