Матричный метод

Пример решения неоднородной СЛАУ

{3x+2y−z=4,2x−y+5z=23,x+7y−z=5;{\displaystyle {\begin{cases}3x+2y-z=4,\\2x-y+5z=23,\\x+7y-z=5;\end{cases}}}

Сначала убедимся в том, что определитель матрицы из коэффициентов при неизвестных СЛАУ не равен нулю.

|32−12−1517−1|=3−14+10−1−105+4=−103;{\displaystyle {\begin{vmatrix}3&2&-1\\2&-1&5\\1&7&-1\end{vmatrix}}=3-14+10-1-105+4=-103;}

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

A11=(−1)1+1⋅|−157−1|=−34;{\displaystyle A_{11}=(-1)^{1+1}\cdot {\begin{vmatrix}-1&5\\7&-1\end{vmatrix}}=-34;}

A12=(−1)1+2⋅|251−1|=7;{\displaystyle A_{12}=(-1)^{1+2}\cdot {\begin{vmatrix}2&5\\1&-1\end{vmatrix}}=7;}

A13=(−1)1+3⋅|2−117|=15;{\displaystyle A_{13}=(-1)^{1+3}\cdot {\begin{vmatrix}2&-1\\1&7\end{vmatrix}}=15;}

A21=(−1)2+1⋅|2−17−1|=−5;{\displaystyle A_{21}=(-1)^{2+1}\cdot {\begin{vmatrix}2&-1\\7&-1\end{vmatrix}}=-5;}

A22=(−1)2+2⋅|3−11−1|=−2;{\displaystyle A_{22}=(-1)^{2+2}\cdot {\begin{vmatrix}3&-1\\1&-1\end{vmatrix}}=-2;}

A23=(−1)2+3⋅|3217|=−19;{\displaystyle A_{23}=(-1)^{2+3}\cdot {\begin{vmatrix}3&2\\1&7\end{vmatrix}}=-19;}

A31=(−1)3+1⋅|2−1−15|=9;{\displaystyle A_{31}=(-1)^{3+1}\cdot {\begin{vmatrix}2&-1\\-1&5\end{vmatrix}}=9;}

A32=(−1)3+2⋅|3−125|=−17;{\displaystyle A_{32}=(-1)^{3+2}\cdot {\begin{vmatrix}3&-1\\2&5\end{vmatrix}}=-17;}

A33=(−1)3+3⋅|322−1|=−7;{\displaystyle A_{33}=(-1)^{3+3}\cdot {\begin{vmatrix}3&2\\2&-1\end{vmatrix}}=-7;}

Далее найдём союзную матрицу, транспонируем её и подставим в формулу для нахождения обратной матрицы.

C∗=(−34715−5−2−199−17−7);{\displaystyle C^{*}={\begin{pmatrix}-34&7&15\\-5&-2&-19\\9&-17&-7\end{pmatrix}};}

(C∗)T=(−34−597−2−1715−19−7);{\displaystyle (C^{*})^{T}={\begin{pmatrix}-34&-5&9\\7&-2&-17\\15&-19&-7\end{pmatrix}};}

A−1=1detA⋅(C∗)T{\displaystyle A^{-1}={\frac {1}{\det A}}\cdot (C^{*})^{T}}

Подставляя переменные в формулу, получаем:

A−1=1−103⋅(−34−597−2−1715−19−7)=(341035103−9103−7103210317103−15103191037103);{\displaystyle A^{-1}={\frac {1}{-103}}\cdot {\begin{pmatrix}-34&-5&9\\7&-2&-17\\15&-19&-7\end{pmatrix}}={\begin{pmatrix}{\frac {34}{103}}&{\frac {5}{103}}&-{\frac {9}{103}}\\-{\frac {7}{103}}&{\frac {2}{103}}&{\frac {17}{103}}\\-{\frac {15}{103}}&{\frac {19}{103}}&{\frac {7}{103}}\end{pmatrix}};}

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

X=A−1⋅B;{\displaystyle X=A^{-1}\cdot B;}

X=(341035103−9103−7103210317103−15103191037103)⋅(4235)=(214){\displaystyle X={\begin{pmatrix}{\frac {34}{103}}&{\frac {5}{103}}&-{\frac {9}{103}}\\-{\frac {7}{103}}&{\frac {2}{103}}&{\frac {17}{103}}\\-{\frac {15}{103}}&{\frac {19}{103}}&{\frac {7}{103}}\end{pmatrix}}\cdot {\begin{pmatrix}4\\23\\5\end{pmatrix}}={\begin{pmatrix}2\\1\\4\end{pmatrix}}}

Итак, x = 2; y = 1; z = 4.

Пример матрицы решений

Производитель продуктов питания нуждается новом поставщике основных ингредиентов для своих продуктов. У него есть четыре варианта выбора поставщика.

Факторами, которые он хочет учесть при принятии решения, являются:

• Стоимость
• Качество
• Местоположение
• Надежность
• Отсрочка

Вначале он заполняет таблицу, показанную на слайде 2 и оценивает, насколько хорошо поставщики удовлетворяют каждому фактору:

Слайд 1. Пример матрицы решений, показывающий не взвешенные оценки и то, , насколько каждый поставщик удовлетворяет каждому фактору.

Далее он решает, какие относительные веса имеет каждый фактор (первая строка таблицы). Он умножает их на уже введенные в таблицу оценки и подсчитывает итоговую сумму (в правом столбце), как показано на слайде 3.

Слайд 2. Пример матрицы решений, показывающий взвешенные оценки и то, насколько каждый поставщик удовлетворяет каждому фактору

В результате становится понятным, что наилучшим вариантом решения будут выбор поставщика 4, несмотря на отсутствие гибкости в отсрочке.

Что такое массив перестановок

Последние несколько строк вывода на рис. 1 указывают, что матрицы L и U можно перемножить так, чтобы получить исходную матрицу. Знание того, как это делается, не поможет вам в решении практических задач операций над матрицами, но позволит разобраться, что представляет собой часть P в разложении LUP. Восстановление исходной матрицы из ее компонентов L и U также пригодится для тестирования ваших библиотечных методов работы с матрицами на согласованность.

Один из способов восстановления исходной матрицы после разложения LUP — перемножение L и U с последующей перестановкой строк результата на основе массива P:

Метод UnPermute можно закодировать так:

Второй подход — преобразование массива perm в матрицу perm с последующим перемножением матрицы perm и комбинированной матрицы LU:

Матрица perm является квадратной с одним значением 1.0 в каждой строке и каждом столбце. Метод, который создает матрицу perm из массива perm, можно написать следующим образом:

Методы решения

Прямые методы дают алгоритм, по которому можно найти точное решение систем линейных алгебраических уравнений. Итерационные методы основаны на использовании повторяющегося процесса и позволяют получить решение в результате последовательных приближений.

Некоторые прямые методы:

• Метод Гаусса
• Метод Гаусса — Жордана
• Метод Крамера
• Матричный метод
• Метод прогонки (для трёхдиагональных матриц)
• Разложение Холецкого или метод квадратных корней (для положительно-определённых симметричных и эрмитовых матриц)

Итерационные методы устанавливают процедуру уточнения определённого начального приближения к решению. При выполнении условий сходимости они позволяют достичь любой точности просто повторением итераций. Преимущество этих методов в том, что часто они позволяют достичь решения с заранее заданной точностью быстрее, а также позволяют решать большие системы уравнений. Суть этих методов состоит в том, чтобы найти неподвижную точку матричного уравнения

x=A′x+b′{\displaystyle \mathbf {x} =A^{\prime }\mathbf {x} +\mathbf {b} ^{\prime }},

эквивалентного начальной системе линейных алгебраических уравнений. При итерации x{\displaystyle \mathbf {x} } в правой части уравнения заменяется, например, в методе Якоби (метод простой итерации) приближение, найденное на предыдущем шаге:

xn+1=A′xn+b′{\displaystyle \mathbf {x} _{n+1}=A^{\prime }\mathbf {x} _{n}+\mathbf {b} ^{\prime }}.

Итерационные методы делятся на несколько типов, в зависимости от применяемого подхода:

• Основанные на расщеплении: (M−N)x=b⇔Mx=Nx+b⇒Mxn+1=Nxn+b{\displaystyle (M-N)\mathbf {x} =\mathbf {b} \Leftrightarrow M\mathbf {x} =N\mathbf {x} +\mathbf {b} \Rightarrow M\mathbf {x} ^{n+1}=N\mathbf {x} ^{n}+\mathbf {b} }
• Вариационного типа: Ax=b⇒‖Ax−b‖→min{\displaystyle A\mathbf {x} =\mathbf {b} \Rightarrow \|A\mathbf {x} -\mathbf {b} \|\rightarrow \min }
• Проекционного типа: Ax=b⇒(Ax,m)=(b,m)∀m{\displaystyle A\mathbf {x} =\mathbf {b} \Rightarrow (A\mathbf {x} ,\mathbf {m} )=(\mathbf {b} ,\mathbf {m} )\forall \mathbf {m} }

Среди итерационных методов:

• Метод Якоби (метод простой итерации)
• Метод Гаусса — Зейделя
• Метод релаксации
• Многосеточный метод
• Метод Монтанте
• Метод Абрамова (пригоден для решения небольших СЛАУ)
• Метод обобщённых минимальных невязок (англ.)
• Метод бисопряжённых градиентов
• Стабилизированный метод бисопряжённых градиентов
• Квадратичный метод бисопряжённых градиентов (англ.)
• Метод квази-минимальных невязок (QMR)
• Метод вращений

Основные понятия

Под матрицей в линейной алгебре понимается прямоугольный массив элементов (таблица). Ниже представлены наборы элементов, заключенные в круглые скобки. Это и есть матрицы. Из приведенного примера видно, что элементами в прямоугольных массивах являются не только числа. Матрица может состоять из математических функций, алгебраических символов.

Для того чтобы разобраться с некоторыми понятиями, составим матрицу A из элементов a_ij. Индексы являются не просто буквами: i – это номер строки в таблице, а j – это номер столбца, в области пересечения которых располагается элемент a_ij. Итак, мы видим, что у нас получилась матрица из таких элементов, как a₁₁, a₂₁, a₁₂, a₂₂ и т. д. Буквой n мы обозначили число столбцов, а буквой m – число строк. Символ m × n обозначает размерность матрицы. Это то понятие, которое определяет число строк и столбцов в прямоугольном массиве элементов.

Необязательно в матрице должно быть несколько столбцов и строк. При размерности 1 × n массив элементов является однострочным, а при размерности m × 1 – одностолбцовым. При равенстве числа строчек и числа столбцов матрицу именуют квадратной. У каждой квадратной матрицы есть определитель (det A). Под этим термином понимается число, которое ставится в соответствие матрице A.

Еще несколько важных понятий, которые нужно запомнить для успешного решения матриц, – это главная и побочная диагонали. Под главной диагональю матрицы понимается та диагональ, которая идет вниз в правый угол таблицы из левого угла сверху. Побочная диагональ идет в правый угол вверх из левого угла снизу.

Обратная матрица

Прежде чем переходить к понятию обратного выражения матрицы, следует рассмотреть алгоритм её транспонирования. Во время операции строки и столбцы переставляются местами. На рисунке представлен метод решения:

По аналогии обратная матрица сходна с обратными числами. Например, противоположной цифре 5 будет дробь 1/5 = 5 (-1) степени. Произведение этих чисел равно 1, выглядит оно так: 5*5 (-1) = 1. Умножение обычной матричной таблицы на обратную даст в итоге единичную: А* А (-1) = Е. Это аналог числовой единицы.

Но для начала нужно понять алгоритм вычисления обратной матрицы. Для этого находят её определитель. Разработано два метода решения: с помощью элементарных преобразований или алгебраических дополнений.

Более простой способ решения — путём алгебраических дополнений. Рассмотрим матричную таблицу А, обратная ей А (-1) степени находится по формуле:

Матрица обратного вида возможна только для квадратного размера таблиц 2*2, 3*3 и т. д. Обозначается она надстроенным индексом (-1). Задачу легче рассмотреть на более простом примере, когда размер таблицы равен 2*2. На первом этапе выполняют действия:

Обратного выражения матрицы не может быть, если определитель равен нулю. В рассматриваемом случае он равен -2, поэтому всё в порядке.

2 этап: рассчитывают матрицу миноров, которая имеет те же значения, что и первоначальная. Под минором k-того порядка понимается определитель квадратной матрицы порядка k*k, составленный из её элементов, которые располагаются в выбранных k- столбцах и k-строках.

При этом расположение элементов таблицы не меняется. Чтобы найти минор верхнего левого числа, вычёркивают строчку и столбец, в которых прописан этот элемент. Оставшееся число и будет являться минором. На выходе должна получиться таблица:

3 этап: находят алгебраические дополнения.

4 этап: определяют транспонированную матрицу.

Итогом будет:

Проверка решения: чтобы удостовериться, что обратная таблица чисел найдена верно, следует выполнить проверочную операцию.

Методы вычисления обратной матрицы

Вычисление обратной матрицы с помощью присоединённой матрицы

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

Замечание. Если при преобразованиях в левой части матрицы образуется нулевая строка (столбец), то исходная матрица не имеет обратной матрицы.

Пример 1. Найти обратную матрицу матрицы A

A =		2	4	1
2	1
2	1	1

Решение: Приписываем к матрице A справа единичную матрицу третьего порядка:

A|E =		2	4	1	1		~
2	1	1
2	1	1	1

Преобразуем левую часть полученной матрицы в единичную. Для этого от 3-тей строки отнимем 1-ую строку:

~		2	4	1	1		~
2	1	1
2 — 2	1 — 4	1 — 1	0 — 1	0 — 0	1 — 0

~		2	4	1	1		~
2	1	1
-3	-1	1

Третью строку поделим на (-3) и поменяем местами со второй строкой:

~		2	4	1	1		~
2	1	1
1	1/3	-1/3

~		2	4	1	1		~
1	1/3	-1/3
2	1	1

Отнимем он 1-ой строки 2-ую умноженную на 4; от 3-тей строки 2-ую умноженную на 2:

~		2 — 4·0	4 — 4·1	1 — 4·0	1 — 4·(1/3)	0 — 4·0	0 — 4·(-1/3)		~
1	1/3	-1/3
0 — 2·0	2 — 2·1	1 — 2·0	0 — 2·1/3	1 — 2·0	0 — 2·(-1/3)

~		2	1	-1/3	4/3		~
1	1/3	-1/3
1	-2/3	1	2/3

Отнимем он 1-ой строки 3-ую строку:

~		2 — 0	0 — 0	1 — 1	-1/3 — (-2/3)	0 — 1	4/3 — 2/3		~
1	1/3	-1/3
1	-2/3	1	2/3

~		2	1/3	-1	2/3		~
1	1/3	-1/3
1	-2/3	1	2/3

Разделим 1-ую строку на 2:

~		1	1/6	-1/2	1/3
1	1/3	-1/3
1	-2/3	1	2/3

Ответ: A-1 =		1/6	-1/2	1/3
1/3	-1/3
-2/3	1	2/3

Вычисление обратной матрицы с помощью союзной матрицы

Определение. Матрица Ã, элементы которой равны алгебраическим дополнениям соответствующих элементов матрицы A называется союзной матрицей.

A-1 =	1	ÃT
det(A)

Пример 1. Найти обратную матрицу матрицы A

A =		2	4	1
2	1
2	1	1

Решение: Найдем определитель матрицы A:

det(A) =	2	4	1	=
2	1
2	1	1

= 2·2·1 + 4·1·2 + 1·0·1 — 1·2·2 — 2·1·1 — 4·0·1 = 4 + 8 + 0 — 4 — 2 — 0 = 6

Найдем алгебраические дополнения матрицы A:

A11 = (-1)1 + 1·	2	1	= 2·1 — 1·1 = 1
1	1

A12 = (-1)1 + 2·	1	= -(0·1 — 1·2) = 2
2	1

A13 = (-1)1 + 3·	2	= 0·1 — 2·2 = -4
2	1

A21 = (-1)2 + 1·	4	1	= -(4·1 — 1·1) = -3
1	1

A22 = (-1)2 + 2·	2	1	= 2·1 — 1·2 = 0
2	1

A23 = (-1)2 + 3·	2	4	= -(2·1 — 4·2) = 6
2	1

A31 = (-1)3 + 1·	4	1	= 4·1 — 1·2 = 2
2	1

A32 = (-1)3 + 2·	2	1	= -(2·1 — 1·0) = -2
1

A33 = (-1)3 + 3·	2	4	= 2·2 — 4·0 = 4
2

Запишем союзную матрицу:

à =		1	2	-4
-3	6
2	-2	4

Найдем обратную матрицу:

A-1 = 1 ÃT  = 1 det(A) 6

1 -3 2 2 -2 -4 6 4

=

1/6 -1/2 1/3 1/3 -1/3 -2/3 1 2/3

Ответ: A-1 =		1/6	-1/2	1/3
1/3	-1/3
-2/3	1	2/3

Матрицы. вступление и оглавлениеМатрицы: определение и основные понятия.Сведение системы линейных уравнений к матрице.Виды матрицУмножение матрицы на число.Сложение и вычитание матриц.Умножение матриц.Транспонирование матрицы.Элементарные преобразования матрицы.Определитель матрицы.Минор и алгебраическое дополнение матрицы.Обратная матрица.Линейно зависимые и независимые строки.Ранг матрицы.

Как использовать матричный анализ

Метод матрицы решений работает так: вы составляете таблицу, где заголовками строк будет список вариантов из которых нужно сделать выбор, а заголовками столбцов будут факторы, которые нужно учесть. Далее вы оцениваете каждую комбинацию вариант/фактор, используя для этой оценки весовой коэффициент.. Затем полученные оценки суммируются для каждого варианта решения и вы получаете общую оценку.

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

Шаг 1

Запишите все ваши варианты решений в первой колонке таблицы в качестве названий строк таблицы, и перечислите факторы, которые нужно рассмотреть, в качестве названий столбцов. Например, если вы покупаете новый ноутбук, факторами для рассмотрения могут быть стоимость, размеры и емкость жесткого диска, вес, размер экрана и т.п.

Шаг 2

Теперь заполняйте ячейки вашей таблицы, оценивая каждый вариант выбора решения  для каждого фактора. Оценка варианта может находиться в пределах от 0 (плохо) до 5 (отлично). Заметим, что вы не обязаны проставлять разные оценки для каждого варианта – если ни один из них не подходит для конкретного фактора в вашем решении, то все они могут получить оценку 0.

Шаг 3

Следующим шагом является определение относительной важности факторов в принятии решения. Обозначьте ее числами, скажем от 0 до 5, где 0 означает, что данный фактор совершенно неважен для окончательного решения, а 5 означает, что он весьма важен

(Вполне допустимо иметь факторы с одинаковой важностью.)

Шаг 4

Теперь нужно перемножить полученные на шаге 2 оценки с относительной важностью фактора, которую вы определили на шаге 3. Это даст вам взвешенные оценки для каждой комбинации вариант/фактор

Шаг 5

Наконец, сложите все взвешенные оценки для каждого из ваших вариантов решения. Тот вариант, который получит наибольшую сумму, выигрывает!

Параметры сверточного слоя

Размеры входного и выходного изображения

• srcC / dstC — число каналов во входном и выходном изображении. Альтернативные обозначения: C / D.
• srcH / dstH — высота входного и выходного изображения. Альтернативное обозначение: H.
• srcW / dstW — ширина входного и выходного изображения. Альтернативное обозначение: W.
• batch — число входных (выходных) изображений — слой за раз может обработать целую партию изображений. Альтернативное обозначение: N.

Размеры ядра свертки

• kernelY — высота ядра свертки. Альтернативное обозначение: Y.
• kernelX — ширина ядра свертки. Альтернативное обозначение: X.

1×13×35×57×7

• strideY — вертикальный шаг свертки.
• strideX — горизонтальный шаг свертки.

1×12×2

• dilationY — вертикальное растяжение свертки.
• dilationX — горизонтальное растяжение свертки.

1×1

Паддинг входного изображения

kernel — 1

• padY / padX — передние вертикальный и горизонтальный отступы.
• padH / padW — задние вертикальный и горизонтальный отступы.

Достоинства и недостатки метода

• Данный метод имеет очень простую реализацию. Не даром он применяется практически во всех известных мне библиотеках.
• Эффективность метода для многих случаев очень велика: от единиц процентов в базовой версии мы достигаем более 80% от теоретического максимума.
• Подход универсальный — у нас один код для всех возможных параметров сверточного слоя (а их не мало!). Поэтому данный метод часто работает в случаях, когда более эффективные (и потому более специализированные) подходы имеют ограничения.
• Подход работает для основных форматов тензоров изображений — NCHW и NHWC .

• К сожалению стандартное матричное умножение эффективно при условии, что значениях параметров M, N, K достаточно велики и кроме того это величины приблизительно одного порядка (эффективность базируется на том обстоятельстве, что требуемое число вычислений ~O(N^3), при этом требуемая пропускная способность памяти ~O(N^2)). Поэтому, если какой-то из параметров M, N, K мал, эффективность метода резко падает.
• Метод требует преобразования входных данных. А это далеко не бесплатная операция. Ей можно принебречь только при условии достаточно большого K. А если еще учесть, что внутри стандартного матричного умножения существует еще внутренне преобразование входных данных, то ситуация становится еще печальней.
• Исходя из того, что K = srcC * kernelY * kernelX / group, эффективность метода особенно низка для входных сверточных слоев. А для depthwise convolution матричный метод вообще проигрывает тривиальной реализации.
• Метод требует дополнительной обработки выходных данных для операции сдвига и вычисления активационной функции.
• Существуют более эффективные математические методы вычисления свертки, которые требую меньшего числа операций.

Понятие выражения

Определение гласит, что матрица — это прямоугольная таблица с заключёнными в ней числами. Её название обозначается латинскими прописными буквами (А, В). Таблицы бывают разной размерности — прямоугольной, квадратной, а также в виде строк и столбцов.

От количества строк и столбцов будет зависеть величина таблицы. Матрица размера m*n означает, что в таблице содержится m строк и n столбцов. Допустим, первая строка включает элементы а11, а12, а13, вторая — а21, а22, а23. Тогда элементы, где i = j (а11, а22) образовывают диагональ и называются диагональными.

Различают комплексные матрицы, у которых хотя бы один элемент равен комплексному числу, и действительные, когда все её элементы являются действительными числами. В математике комплексные числа представлены в виде a+b*i, где:

• a — действительная часть числа;
• b — мнимая часть;
• i — мнимая единица (квадратный корень из -1).

На приведенном примере показаны варианты.

Простейшие действия с матрицами могут быть разными. К их числу относятся:

• умножение;
• вычитание;
• умножение на число;
• перемножение между собой;
• транспортирование матриц.

C#

• 09/27/2016
• Чтение занимает 19 мин

В этой статье

Разложение матрицы

Продукты и технологии:

C#, Microsoft .NET Framework

В статье рассматриваются:

• реализация матрицы на C#;
• распараллеливание перемножения матриц;
• подходы к разложению матрицы;
• использование разложения матрицы для обращения матрицы (matrix inversion);
• вычисление определителя матрицы (determinant of a matrix).

Разложение матрицы — это метод разбиения квадратной числовой матрицы на две разные квадратные матрицы, лежащий в основе эффективного решения системы уравнений, которое в свою очередь является основой для обращения матрицы. Обращение матрицы — часть многих важных алгоритмов. В этой статье представлен и поясняется код на C#, выполняющий разложение матрицы, обращение матрицы, решение системы уравнений и связанные операции.

Следует отметить, что важным пополнением вашей персональной библиотеки кода является не само по себе разложение матрицы, а набор матричных методов. Я объясняю эти методы, поэтому вы сможете модифицировать исходный код под свои потребности. Кроме того, некоторые приемы, используемые в матричных методах, можно повторно задействовать в других сценариях кодирования.

Лучший способ прочувствовать то, о чем пойдет речь в этой статье, — взглянуть на экранный снимок на рис. 1. Демонстрационная программа начинает с создания квадратной матрицы 4 × 4 и отображения ее значений. Затем матрица раскладывается в так называемую матрицу LUP (lower, upper, permutation) (нижняя часть, верхняя часть и часть, относящаяся к перестановке). Последняя часть представляет собой массив со значениями {3,1,2,0} и указывает, что строки 0 и 3 поменялись местами в процессе разложения. В этом процессе также было сгенерировано значение-переключатель (toggle value), равное –1, сообщающее, что выполнено нечетное количество перестановок строк. Эта программа демонстрирует разложение двумя способами: сначала в комбинированную матрицу LU, а затем в отдельные матрицы L и U. Далее программа вычисляет и отображает обращенную по отношению к исходной матрицу, используя «за кулисами» матрицу LUP. Демонстрационная программа вычисляет определитель исходной матрицы, вновь применяя разложение. Далее она использует обратную матрицу для решения системы линейных уравнений и завершает свою работу объединением матриц L и U в исходную матрицу.

Рис. 1. Демонстрация разложения матрицы

К чему все эти сложности с созданием собственного метода разложения матрицы и библиотеки связанных методов? Хотя существует множество автономных матричных инструментов, их иногда очень трудно интегрировать в приложение или систему

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

Расчёт определителя

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

Произведения могут отличаться друг от друга составом элементов. Со знаком плюс будут включаться в сумму числа, если их индексы составляют чётную подстановку, в противоположном случае их значение меняется на минус. Определитель обозначается символом det A. Круглые скобки матричной таблицы, обрамляющие её элементы, заменяются на квадратные. Формула определителя:

Определитель первого порядка, состоящий из одного элемента, равен самому этому элементу. Детерминант матричной таблицы размером 2*2 второго порядка вычисляется путём перемножения её элементов, расположенных на главной диагонали, и вычитания из них произведения элементов, находящихся в побочной диагонали. Наглядный пример:

Для матрицы также можно найти дискриминант многочлена, отвечающий формуле:

Когда у многочлена имеются кратные корни, тогда дискриминант равен нулю.

Проверка согласованности

Интересный аспект связанных друг с другом библиотечных методов заключается в том, что зачастую их можно протестировать, проверяя, дают ли они согласованные результаты. Допустим, у вас есть метод, создающий случайную матрицу:

В дополнение предположим, что ваша матрица создает матрицу тождественности, или единичную матрицу (identity matrix), т. е. квадратную матрицу со значениями 1.0 по основной диагонали и значениями 0.0 в остальных ячейках:

И у вас есть метод, сравнивающий две матрицы на тождественность:

Заметьте, что метод MatrixAreEqual не сравнивает значения ячеек на точное равенство, так как эти значения имеют тип double. Вместо этого метод проверяет, очень ли близки друг к другу значения ячеек (в пределах epsilon).

Поскольку произведение любой квадратной матрицы m и единичной матрицы той же размерности равно исходной матрице m, вы можете протестировать метод MatrixProduct наряду со следующими строками кода:

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

Пример 1. Решить следующую систему линейных уравнений матричным методом:

Матричный вид записи системы линейных уравнений: Ax=b, где

Найдем обратную к матрице A методом Жордана-Гаусса. С правой стороны матрицы A запишем единичную матрицу:

Выбираем самый большой по модулю ведущий элемент столбца 1. Для этого заменяем местами строки 1 и 2:

Исключим элементы 1-го столбца матрицы ниже главной диагонали. Для этого сложим строки 2,3 со строкой 1, умноженной на -1/3,-1/3 соответственно:

Выбираем самый большой по модулю ведущий элемент столбца 2. Для этого заменяем местами строки 2 и 3:

Исключим элементы 2-го столбца матрицы ниже главной диагонали. Для этого сложим строку 3 со строкой 2, умноженной на -24/51:

Исключим элементы 3-го столбца матрицы выше главной диагонали. Для этого сложим строки 1, 2 со строкой 3, умноженной на 17/53, 85/159 соответственно:

Исключим элементы 2-го столбца матрицы выше главной диагонали. Для этого сложим строку 1 со строкой 2, умноженной на -3/17:

Делим каждую строку матрицы на ведущий элемент соответствующей строки:

Отделяем правую часть матрицы. Полученная матрица является обратной матрицей к A :

Обратная матрица найдена. Решение системы линейных уравнений имеет вид x=A−1b. Тогда

Ответ:

Пример 2. Решить следующую систему линейных уравнений матричным методом:

Матричный вид записи системы линейных уравнений: Ax=b, где

Найдем обратную к матрице A методом алгебраических дополнений. Вычислим определитель матрицы A :

Вычислим все алгебраические дополнения матрицы A:

Обратная матрица вычисляется из следующего выражения:

где A_ij − алгебраическое дополнение элемента матрицы A, находящиеся на пересечении i-ой строки и j-ого столбца, а Δ − определитель матрицы A.

Используя формулу обратной матрицы, получим:

Обратная матрица найдена. Решение системы линейных уравнений имеет вид x=A−1b. Тогда

Ответ:

Нахождение обратной матрицы с помощью элементарных преобразований (метод Гаусса)

Пример 3. Методом элементарных преобразований вычислить -1 если = .

Решение. Приписываем к исходной справа единичную того же порядка: . С помощью элементарных преобразований столбцов приведём левую “половину” к единичной, совершая одновременно точно такие преобразования над правой «половиной».
Поменяем местами 1 со 2 столбцы: ~. К третьему прибавим первый, ко второму — первый, × на -2: . Из первого вычтем удвоенный второй, из третьего — × на 6 второй; . Прибавим третий к первому и второму: . Умножим последний на минус один: . Справа от вертикальной черты квадратная таблица размером 3х3 .

Обращение матрицы

Чтобы использовать разложение для обращения матрицы, крайне важно написать вспомогательный метод, решающий систему уравнений. Этот метод представлен на рис. 4

Рис. 4. Метод HelperSolve

Метод HelperSolve находит массив x, который при умножении на матрицу LU дает массив b. Этот метод весьма непрост, и вы можете полностью понять его, только проследив его работу на нескольких примерах. В нем два цикла. Первый цикл использует прямую подстановку (forward substitution) в нижней части матрицы LU, а второй цикл — обратную подстановку (backward substitution) в верхней части той же матрицы. В некоторых других реализациях разложения матрицы аналогичный метод называют, например, luBackSub.

Хотя этот код короткий, он весьма сложен, но никаких сценариев, где вам могло бы понадобиться его изменение, нет. Заметьте, что HelperSolve принимает матрицу LU от MatrixDecompose, но не использует выходной параметр perm. Это подразумевает, что HelperSolve, по сути, является вспомогательным методом и нуждается в дополнительной оболочке кода для решения системы уравнений. При рефакторинге кода из этой статьи под объектно-ориентированное программирование вы, вероятно, предпочтете сделать метод HelperSolve закрытым.

Создав метод HelperSolve, можно реализовать метод обращения матрицы, как показано на рис. 5.

Рис. 5. Метод MatrixInverse

И вновь сложный код. Алгоритм обращения основан на том, что результат перемножения матрицы M и ее обращения является единичной матрицей. Метод MatrixInverse в основном отвечает за решение системы уравнений Ax = b, где A — матрица разложения LU , а константы b равны либо 1.0, либо 0.0 и соответствуют единичной матрице. Заметьте, что MatrixInverse использует массив perm, возвращаемый после вызова MatrixDecompose.

Вызов метода MatrixInverse мог бы выглядеть так:

Подведем итог

Важной матричной операцией является обращение матрицы, которое весьма сложно. Один из подходов — разложение исходной матрицы, написание вспомогательного метода, выполняющего прямую и обратную подстановки, и последующее использование разложения совместно с массивом перестановок LU и вспомогательного метода для поиска обращенной матрицы

Этот подход может показаться слишком сложным, но обычно он эффективнее и проще, чем прямое вычисление обращенной матрицы.