NL: Файл band.h


Функции
void	band_tridiag (double a, double d, double c, double b, double *x, size_t n)
	Решение трехдиагональной системы методом прогонки.
void	band_mult_col (double *A, size_t n, size_t m1, size_t m2, double b, double *c)
	Умножение ленточной матрицы на плотный столбец.
void	band_decomp (double A, size_t n, size_t m1, size_t m2, double L, size_t p, int sgn)
	-разложение ленточной системы.
void	band_solve (double A, size_t n, size_t m1, size_t m2, double L, size_t p, double b)
	Решение ленточной системы на основе ее -разложения.

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

Файл содержит функции для работы с ленточными матрицами.

Матрица

с элементами $a_{ij} = 0$ при $i > j + m_1$

или

называется ленточной. Величина $m_1 + m_2 + 1$

называется шириной ленты, а $m_1$

- шириной нижней полуленты и шириной верхней полуленты соответственно. При $m_1 = m_2 = 1$

получаем трехдиагональную матрицу. Элементы $a_{k1}, a_{k+1,2},\dots,a_{n,n-k+1}$ называются $(k-1)$

-й поддиагональю, а $a_{1k}, a_{2,k+1},\dots,a_{n-k+1,n}$ - $(k-1)$

-й наддиагональю.

Для хранения элементов ленточной матрицы используется компактная схема. Ленточной матрице $A$

поставим в соответствие матрицу $C$

размера $n \times (m_1 + m_2 + 1)$ с элементами $c_{ij} = a_{i,\,i+j-m_1-1}$ , которую и будем хранить в двумерном массиве. Итак, каждому столбцу матрицы $C$

соответствует (под/над)диагональ матрицы $A$

Функции

void band_decomp	(	double **	A,
		size_t	n,
		size_t	m1,
		size_t	m2,
		double **	L,
		size_t *	p,
		int *	sgn
	)

$LU$ -разложение ленточной системы.

Функция находит $LU$ -разложение $PA=LU$ ленточной квадратной матрицы $A$ порядка $n$ с шириной нижней полуленты $m1$ и шириной верхней полуленты $m2$ . Для хранения матрицы используется компактная схема. Элементы матрицы хранятся в массиве $A$ размера $n \times (m1+m2+1)$ . Используется схема выбора главного элемента по столбцу. Элементы множителя $U$ возвращаются в компактной форме в массиве $A$ . Поддиагональные элементы множителя $L$ в компактной форме возвращаются в массиве $L$ размера $n \times m1$ . Диагональные элементы матрицы $L$ равны $1$ . Матрица перестановок $P$ представлена вектором перестановок $p$ : на $j$ -й итерации $j$ -я строка была переставлена с $p[j]$ -й. На выходе $sgn$ - определитель матрицы $P$ .

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

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

void band_mult_col	(	double **	A,
		size_t	n,
		size_t	m1,
		size_t	m2,
		double *	b,
		double *	c
	)

Умножение ленточной матрицы на плотный столбец.

Ленточная матрица $A$ , представленная схемой, описанной в описании band_decomp, умножается на вектор-столбец $b$ . Результат возвращается в массиве $c$ .

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

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

void band_solve	(	double **	A,
		size_t	n,
		size_t	m1,
		size_t	m2,
		double **	L,
		size_t *	p,
		double *	b
	)

Решение ленточной системы на основе ее $LU$ -разложения.

Функция находит решение ленточной системы $Ax = $ b на основе полученного функцией band_decomp $LU$ -разложения матрицы $A$ . На входе:

, , - массивы, возвращаемые функцией band_decomp,
, , - порядок системы, ширина нижней и ширина верхней полулент соответственно.
- правая часит системы уравнений.

Решение записывается на месте вектора $b$ , остальные массивы не меняются и могут использоваться в дальнейшем для решения системы с другой правой частью.

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

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

void band_tridiag	(	double *	a,
		double *	d,
		double *	c,
		double *	b,
		double *	x,
		size_t	n
	)

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

Решается трехдиагональная система порядка $n$ . Массивы $a$ , $d$ , $c$ содержат коэффициенты системы, расположенные соответственно под главной диагональю, на ней и над ней. Элементы $a[0]$ и $c[n-1]$ не используются. Массив $b$ содержит правую часть системы. Решение возвращается в массиве $x$ .

Трудоемкость: $8n - 7$

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