Функции | |
double | lu_decomp (double **A, size_t n, size_t *p, int *sgn) |
![]() | |
void | lu_solve (double **LU, size_t n, size_t *p, double *b) |
Решение системы линейных уравнений. | |
void | lu_improve (double **LU, size_t n, size_t *p, double *b, double *x, double *r) |
Один шаг итерационного уточнения решения системы линейных уравнений. | |
double | lu_det (double **LU, size_t n, int sgn) |
Определитель матрицы. | |
void | lu_invert (double **LU, size_t n, size_t *p, double **B) |
Обращение матрицы. | |
void | lu_mult_col (double **LU, size_t n, size_t *p, double *v, double *res) |
Умножение матрицы ![]() ![]() ![]() ![]() |
Файл содержит функции, реализующие и использующие -разложение квадратной матрицы.
Произвольная квадратная матрица порядка
допускает разложение вида
, где
- матрица перестановок,
- нижнетреугольная матрица с единичной диагональю,
- верхнетреугольная матрица. Такое разложение используют для решения систем линейных уравнений
, заменяя данную систему на пару систем
и
.
double lu_decomp | ( | double ** | A, | |
size_t | n, | |||
size_t * | p, | |||
int * | sgn | |||
) |
-разложение матрицы.
Функция находит -разложение и оценку числа обусловленности квадратной матрицы
порядка
. На выходе диагональ и верхнетреугольная часть матрицы
содержат элементы матрицы
. Нижнетреугольная часть матрицы
содержит поддиагональные элементы матрицы
. Диагональные элементы матрицы
равны
. Матрица перестановок
представлена вектором перестановок
, в котором
- индекс ведущей строки на
-ой итерации. На выходе
- определитель матрицы
. Функция возвращает нижнюю оценку числа обусловленности матрицы
порядка
. Как правило, данная оценка отличается от настоящего числа обусловленности не более чем в
раз.
Для разложения используется алгоритм Гаусса с выбором главного элемента по столбцу. Для оценки числа обусловленности используется алгоритм, описанный в [FMM, KMN].
Трудоемкость: операций с плавающей запятой
double lu_det | ( | double ** | LU, | |
size_t | n, | |||
int | sgn | |||
) |
Определитель матрицы.
Функция возвращает определитель квадратной матрицы порядка
. Ииспользуется предварительно найденное
-разложение матрицы A, представленное матрицей
и определителем
матрицы перестановок
(сам вектор перестановок не нужен), возвращаемыми функцией lu_decomp.
Трудоемкость: операций с плавающей запятой
void lu_improve | ( | double ** | LU, | |
size_t | n, | |||
size_t * | p, | |||
double * | b, | |||
double * | x, | |||
double * | r | |||
) |
Один шаг итерационного уточнения решения системы линейных уравнений.
Функция выполняет один шаг итерационного уточнения решения системы линейных уравнений
. Используется предварительно найденное
-разложение матрицы
, представленное матрицей
и вектором перестановок
, возвращаемыми функцией lu_decomp. Возвращается улучшенное решение
и вектор невязки
.
Используется следующий алгоритм: вначале вычисляется вектор , после этого с помощью функции lu_solve решается система
и, наконец, определяется улучшенное решение
и вектор невязки
.
Трудоемкость: операций с плавающей запятой
void lu_invert | ( | double ** | LU, | |
size_t | n, | |||
size_t * | p, | |||
double ** | B | |||
) |
Обращение матрицы.
Функция находит матрицу , обратную к матрице
. Используется предварительно найденное
-разложение матрицы
, представленное матрицей
и вектором перестановок
, возвращаемыми функцией lu_decomp.
Трудоемкость: операций с плавающей запятой
void lu_mult_col | ( | double ** | LU, | |
size_t | n, | |||
size_t * | p, | |||
double * | v, | |||
double * | res | |||
) |
Умножение матрицы , представленной массивами
и
, на вектор
.
Функция находит произведение . Используется предварительно найденное
-разложение матрицы
, представленное матрицей
и вектором перестановок
, возвращаемыми функцией lu_decomp. Результат возвращается в векторе
.
Трудоемкость: операций с плавающей запятой
void lu_solve | ( | double ** | LU, | |
size_t | n, | |||
size_t * | p, | |||
double * | b | |||
) |
Решение системы линейных уравнений.
Функция находит решение квадратной системы линейных уравнений порядка
, используя предварительно найденное
-разложение матрицы
, представленное матрицей
и вектором перестановок
, возвращаемыми функцией lu_decomp. Решение
записывается на месте вектора правой части
. Матрица
U и вектор
не меняются данной функцией и могут быть использованы для решения системы с другой правой частью.
Используется алгоритм прямой и обратной подстановки.
Трудоемкость: операций с плавающей запятой