Решение систем линейных уравнений методом двойной фактори-

Зации

Решение ищем в виде:

Двойная факторизация - представление обратной матрицы в виде про-изведения элементарных верхних и нижних треугольных матриц, в которых не равны нулю элементы только одной строки или одного столбца. Такие матрицы называются факторными.

Произведение факторных матриц дает обратную матрицу.

Рассмотрим структуру факторных матриц:

1) Левая факторная матрица на к-м шаге факторизации L_k.

J

k

n

i

1
	1
		Lkk
		…	1
		Lnk		1

k

Элементарная нижняя треугольная матри-ца, в которой диагональные элементы рав-ны 1, в к-ом столбце диагональные и все поддиагональные элементы не равны ну-лю. Все остальные элементы матрицы рав-ны нулю. Таких матриц может быть n.

n

Элементы этой матрицы определяются по формулам:

2) Правая факторная матрица R_к.

		k		n

1
	1
		1	rr,k+1	...rk,n
			1
				1

Это элементарная верхняя треугольная матрица с единичной диагональю.

В к-ой строке элементы, лежащие правее диаго-нали, не равны нулю. Все остальные элементы матрицы

k

равны нулю.

Таких матриц может быть n-1. Элементы мат-рицы R вычисляются по формуле:

n

k=1…n, j=k+1…n, i=k+1…n.

n

Теорема:

Для квадратной матрицы А размерностью существует n левых и (n-1) правых факторных матриц, таких, что их произведение дает обратную мат-рицу:

Здесь: А – исходная матрица; L – левые факторные матрицы, полученные на 1, 2, …, n шагах факторизации; R – правые факторные матрицы.

Существует эффективные алгоритмы перемножения факторных матриц, в которых нулевые элементы и единицы на диагонали не хранятся, а подразу-меваются в ходе вычислений. В памяти хранятся и участвуют в вычислениях только значащие элементы матриц.

Алгоритм факторизации:

1) Выбор очередного ведущего элемента а_кк, определяющего опорную

строку и опорный столбец;

2) На основе элементов опорной строки и опорного столбца

пересчитываются все остальные элементы матрицы по формуле:

				R2 R1
к

R1

(5)

3) Пересчитываем элементы опорного столбца

по формуле (1);

4) Пересчитываем элементы опорной строки по

формуле (3);

5) Пересчитываем ведущий элемент по формуле (2)

L₁ … L_к … L_n

L1

В результате этого получаем очередные (к-е) L_k и R_k факторные матрицы. Их значащие элементы расположены в опорном столбце (L_k) и в опорной строке (R_к). Единицы на главной диагонали и нулевые элементы этих матриц подра-зумеваются;

6) Если таким образом получены n левых и (n-1) правая факторная мат-рица, то переходим к пункту 7, иначе - возврат к пункту 1;

В результате все поле матрицы будет заполнено элементами факторных мат-риц L и R. Полученная матрица называется факторизованной;

7) Расчет обратной матрицы А^-1 перемножением факторных матриц по формуле (4);

8) Решение системы уравнений по формуле: .

Примечания:

1. Метод использует простые преобразования;

1.2. Объем занимаемой памяти ЭВМ зависит от степени разрежен-ности матрицы и последовательности выбора ведущих элемен-тов;

1.3. Возможность реализации серии расчётов режимов при меняющихся значениях элементов вектора І и неизменной матрице проводимостей Y.

Примеры:

Решение системы:

Решаем СЛАУ методом Гаусса. Прямой ход – 2 шага исключения неиз-вестных:

1-й шаг

Умножаем 2-е уравнение на -2 и складываем его с 1-м. При этом исключается х₁ из 2-го уравнения.

Умножаем 1-е уравнение на 5, а 3-е на -2 и складываем их. Исключается х₁ из 3-го уравнения.

2-й шаг

Умножаем 2-е уравнение на -2 и складываем его

с 3-м. При этом исключается х₂ из 3-го уравне- ния.

Получили эквивалентную систему уравнений с треугольной матрицей коэффициентов.

Обратный ход:

Из последнего уравнения находим х₃. Подставляем его во 2-е уравнение и из него находим х₂. Подставляем х₂ и х₃ в 1-е уравнение и определяем х₁.

Для проверки подставляем х_{1 ,}х_2, х₃ в исходную систему.

Решаем СЛАУ методом Жордана

Нужно выполнить 3 шага исключения неизвестных.

В результате их исходная прямоугольная матрица коэффициентов преоб-разуется в единичную.

1-й шаг. Делим 1-е уравнение на коэффициент при х₁, т.е. 2. и исключаем х₁ из уравнений 2 и 3. Получаем эквивалентную СЛАУ:

=>

2-й шаг. Делим 2-е уравнение на коэффициент при х₂ , т.е. 7 и исключаем х₂ из уравнений 1 и 3. Получаем эквивалентную систему:

=>

3-й шаг. Делим 3-е уравнение на коэффициент при х₃ , т.е. -5.7 и исклю-чаем неизвестную х₃ из уравнений 1 и 2. Получаем эквивалентную систе-му уравнений с единичной матрицей коэффициентов:

=> Результат решения СЛАУ очевиден: х₁ = х₂ = х₃ =1.

Т.е. искомые значения неизвестных равны правым частям уравнений сис-темы, полученным после n-го шага исключения неизвестных.

Решаем СЛАУ методом LU - факторизации

Для разложения матрицы коэффициентов на две треугольные – реализуем алгоритм Краута.

Выбираем опорный элемент. Он равен 2. Делим на него элементы опорной (1-й) строки. Опорный столбец (1-й) оставляем без изменений. Пересчитываем остальные элементы матрицы. Это 1-й шаг факторизации.

Снова выбираем опорный элемент. Он равен -7. Делим на него элемент опорной (2-й) строки. Опорный столбец (2-й) оставляем без изменений. Пересчитываем остальные элементы матрицы. Это 2-й шаг факторизации.

Из полученной матрицы выделяем нижнюю треугольную матрицу L (включающую и диагональные элементы) и верхнюю треугольную матрицу U (с единицами на диагонали). Их перемножение дает исходную матрицу коэффициентов.

	L		U

Составляем 2 вспомогательные системы уравнений с использованием этих треугольных матриц:

LY=B ; Ux=Y , или

Y₁=2.5; Решаем эту систему и находим

Y₁-7Y₂=1; значения Y .

Y₂=

5Y₁-14Y₂-5.49Y₃=4

Подставляем их значения во вторую систему, решаем её и определяем искомые значения Х :

X₃=1.0025; X₂=1.0009; X₁=1.00087

Для проверки – подставляем их исходную систему уравнений.

Решаем СЛАУ методом двойной факторизации

Определяем обратную матрицу коэффициентов. 1-й шаг факторизации:

Выбираем ведущий элемент – он равен 2. Ведущие строка и

столбец – 1-я строка и 1-й столбец.

Выбираем

ведущий элемент он равен 2. Ведущие строки и столбец -1-я строка и 1-й столбе

Пересчитываем элементы, не входящие в опорную строку и столбец по формуле (1) (- аналогично алгоритму Краута):

Пересчитываем по формулам (1) и (3) элементы ведущего столбца и строки, т.е. делим их на ведущий элемент:

Пересчитываем ведущий элемент по формуле (2):

В полученной матрице выделяем элементы первой левой (L₁) и первой правой (R₁) факторных матриц.

2-й шаг факторизации:

Выбираем очередной ведущий элемент. Он равен -7. Ведущая строка и столбец – 2-й.

Пересчитываем элем6енты, не входящие входивший в ведущие строки и столбцы:

Пересчитываем элементы ведущего столбца и строки:

Пересчитываем ведущий элемент:

В полученной матрице выделяем элементы очередных левой (L₂) и правой (R₂) факторных матриц.

3-й шаг факторизации:

Выбираем ведущий элемент. Это -5,5. Пересчитываем его по формуле (2). Получаем факторизованную матрицу: .

Её элементы – это элементы всех факторных матриц. Выделяем факторные матрицы.

Обратная матрица определяется:

R1 R2 L3 L2 L1

R1∙R2 L3 L2 L1 R1∙R2∙L3 L2

L1 R1∙R2∙L3∙L2 L1 A^-1

Для проверки – перемножим исходную и обратную матрицы: А∙А^-1

Решаем систему уравнений:

X=A^-1∙B