П 3.4 Метод квадратного корня для решения систем линейных алгебраических уравнений

Рассмотрим алгоритм метода квадратного корня.

Метод предназначен для решения СЛАУ с симметрическими матрицами.

Пусть надо решить систему

, (1)

где матрица A – вещественная, симметрическая; X – искомый вектор решения; f – вектор правой части системы.

Матрицу A можно представить в виде , где S – верхняя треугольная матрица, S^T – транспонированная к ней матрица (нижняя треугольная), D – диагональная матрица с элементами, равными +1 или –1.

Значения коэффициентов матрицы S и D находятся по формулам (2), описанным в п 2.2.

Исходную систему (1) заменяем двумя эквивалентными ей системами с треугольными матрицами: .

Решая их, получаем [19; 8]:

(2)

Если матрица А является симметричной и положительно определенной, то ее можно представить в виде произведения , S – верхняя треугольная матрица, S^T – транспонированная к ней матрица (нижняя треугольная).

Значения коэффициентов матрицы S находятся по формулам (3), описанным в п 2.2.

В этом случае решение системы линейных алгебраических уравнений (1) сводится к последовательному решению двух систем с треугольными матрицами [19; 8]:

(3)

SX = Y. (4)

Т.к. матрица системы (3) является нижней треугольной, то можно сразу выписать ее решение:

(5)

i = 2, 3, …, n. (6)

Определив таким образом вектор Y, можем найти из системы (4) искомое решение. Это решение находим обратным ходом метода Гаусса, т.к. матрица S – верхняя треугольная.Имеем:

, (7)

i = n-1, n-2, …, 1. (8)

Пример 1. Решить систему линейных уравнений методом квадратного корня.

Решение:

Матрица системы является симметрической и положительно определенной. Вычислим коэффициенты матрицы S:

Получим матрицу .

Вычислим вектор Y:

Находим искомый вектор решения X:

Пример 2. Для системы уравнений с симметрической матрицей описать алгоритм метода квадратного корня, используя S^TS-разложение.

При описании алгоритма используются объекты и методы классов «SquareMatrix», «Vector» и «FactorizationAlgorithms».

Реализация примера на языке программирования С++ может иметь следующий вид:

void DirectMethodsFactorization::squareMethod(SquareMatrix A, Vector f){

/*Создание матриц S, вектора X, вектора Y */

int n = A.getRowCount();

SquareMatrix S = SquareMatrix(n);

Vector X = Vector(n);

Vector Y = Vector(n);

/* S^TS – разложение. В результате факторизации имеем матрицу S – верхнюю треугольную матрицу */

FactorizationAlgorithms FA;

FA. STS_decomposition (A, S);

/* Решение системы S^TY = f. */

/* Решение системы SX = Y. Матрица S – верхняя треугольная матрица, следовательно искомый вектор решения находим обратным ходом метода Гаусса.*/

X.setElement(n-1,(Y.getElement(n-1)/S.getElement(n-1,n-1)));

for (int i = n-2; i >= 0; i--){

double sum = 0;

for (int j = n-1; j > i; j--){

sum += X.getElement(j) * S.getElement(i, j);

}

X.setElement(i, (Y.getElement(i)-sum)/S.getElement(i, i));

}

// вывод вектора решений

}

Поиск по сайту: