С какого элемента считаются матрицы c
Перейти к содержимому

С какого элемента считаются матрицы c

  • автор:

С какого элемента считаются матрицы c

Сложение определено для матриц одного типа, т.е. для матриц, у которых число строк и столбцов совпадает. Сумма матриц \(A=\\>\) и \(B=\\>\), матрица \(A+B\), определяется следующим образом: \((A+B)_=A_+B_\), \(1 \leq i \leq m, 1 \leq k \leq n\). Иными словами: складываются элементы матриц \(A\) и \(B\), стоящие на одинаковом месте (т.е. на пересечении одинаковых строк и столбцов) и записываются в то же место.

Пусть \[ A=\left( \begin 1 &4 & -1 \\ 3 & -6 & 7 \end \right) , \] \[ B=\left( \begin 2 &1 & 0 \\ 1 & 3 & 4 \end \right) , \] тогда \[ A+B=\left( \begin 3 & 5 & -1 \\ 4 & -3 & 11 \end \right) . \]

Умножение матрицы на число

Пусть \(A=\\>\) — матрица типа \((m,n)\), \(\lambda\) — произвольное число. Тогда матрица \(\<\lambda a_\>\) называется произведением числа \(\lambda \) на матрицу \(A\) и обозначается \(\lambda \cdot A\).

Пусть \[ A=\left( \begin 1 &4 & -1 \\ 7 & 5 & 2 \\ 3 & -6 & 7 \end \right) , \] тогда \[ 5A=\left( \begin 5 &20 & -5 \\ 35 & 25 & 10 \\ 15 & -30 & 35 \end \right) . \]

Как и в обычной, в матричной арифметике знак умножения иногда не указывают, так что выражения \(c\cdot A\) и \(cA\) равноправны.

Пусть \[ A=\left( \begin 2 & 3 \\ 4 & 5 \end \right), B=\left( \begin 1 & -2 \\ 3 & 4 \end \right). \]

Проверить ответ

\[3A-2B=\left( \begin 4 & 13 \\ 6 & 7 \end \right)\]

Транспонирование матриц

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

Пусть \[ A=\left( \begin 1 &4 & -1 & 4 \\ 7 & 5 & 2 & 2\\ 3 & -6 & 7 & 8 \end \right), \] тогда \[ A^T=\left( \begin 1 &7 & 3 \\ 4 & 5 & -6 \\ -1 & 2 & 7 \\ 4 &2 &8 \end \right) . \]

Подчеркнем, если матрица \(A\) имеет тип (\(m,n)\), то \(A^T\) имеет тип \((n,m)\), так что эта операция, вообще говоря, меняет тип матрицы. В частности, если \(A\) была матрицей-столбцом, \(A^T\) будет матрицей-строкой той же длины. Поэтому из типографских соображений матрицу-столбец часто представляют в виде \((a_1,a_2,a_3. a_n)^T\) (это выражение занимает меньше места).

Элементарные свойства операций с матрицами

Введенные операции обладают многими естественными арифметическими свойствами. Перечислим ряд из них.

1. Для любых матриц \(A,B,C\) одного типа \((A+B)+C=A+(B+C)\)(ассоциативность сложения).

2. Для любых матриц \(A,B\) одного типа \(A+B=B+A\) (коммутативность сложения).

3. Пусть \((m,n)\)-матрица \(O\) состоит из нулей. Такая матрица играет роль нуля при сложении матриц типа \((m,n)\), \(A+O=A\), \(0\cdot A=O\) для любой матрицы \(A\) того же типа.

4. Для любых чисел \(c_1,c_2\) и любой матрицы \(A\) верно \((c_1+c_2)A=c_1A+c_2A\).

5. Для любых матриц \(A,B\) одного типа и любого числа \(c\) верно \(c(A+B)=cA+cB\).

6. Для любых чисел \(c_1,c_2\) и любой матрицы \(A\) верно \((c_1c_2)A=c_1(c_2A)\).

7. Для любой матрицы \(A\) верно \(1\cdot A=A\).

8. Для любых матриц \(A,B\) одного типа \((A+B)^T=A^T+B^T\).

9. Для любого числа \(c\) и любой матрицы \(A\) верно: \((cA)^T=cA^T\).

10. Для любой квадратной матрицы \(detA=detA^T\).

11. Для любой матрицы \((A^T)^T=A\).

Умножение матриц

Рассмотрим сначала умножение матрицы-строки на матрицу столбец. Пусть \(A=(a_1,a_2. a_n)\), \(B=(b_1,b_2. b_n)^T\). Тогда

\[ AB=a_1b_1+a_2b_2+. +a_nb_n=\sum _^na_mb_m. \quad \quad(9) \]

Для того, чтобы было определено умножение между \(A\) и \(B\), необходимо, чтобы длина строки была равна длине столбца. Это условие называют условием согласования типов. Формулу (9) называют правилом умножения строчки на столбец.

Теперь обсудим общий случай. Пусть матрица \(A\) имеет тип \((m,n)\), а матрица \(B\) имеет тип \((n,p)\) (так что длина строки матрицы \(A\) совпадает с длиной столбца матрицы \(B\)). Тогда можно определить их произведение, матрицу \(C\), следующим образом: матрица \(C\) будет иметь тип \((m,p)\), причем для вычисления ее элемента \(C_\), \(1 \leq i \leq m, 1 \leq k \leq p\), следует взять строку с номером \(i\) матрицы \(A\) и умножить на столбец с номером \(k\) матрицы \(B\), \[ c_=a_b_+a_b_+. +a_b_=\sum _^na_b_. \] Таким образом следует вычислить все \(mp\) элементов матрицы \(C\). Еще раз подчеркнем, что для того, чтобы можно было перемножать матрицы \(A\) и \(B\), их типы должны быть согласованы!

Пусть \[ A=\left( \begin 1 &4 & -1 \\ 3 & -6 & 7 \end \right) , B=\left( \begin 2 &1 \\ 1 & 3 \\ -3 &5 \end \right) . \]

В данном случае матрица \(A\) имеет тип (2,3), матрица \(B\) имеет тип (3,2), так что типы матриц согласнованы и в результате умножения \(A\) на \(B\) получим матрицу типа \((2,2)\). Получаем: \[ AB=\left ( \begin 1\cdot 2 +4 \cdot 1+(-1)\cdot (-3) & 1\cdot 1 +4 \cdot 3+(-1)\cdot 5\\ 3\cdot 2 +(-6) \cdot 1+7\cdot (-3) &3\cdot 1 +(-6) \cdot 3+7\cdot 5 \end \right )= \left( \begin 9 & 8\\ -21 & 20 \end \right). \]

Для приведенных матриц произведение \(BA\) не определено — типы матриц \(B\) и \(A\)не согласованы. Это отражает общую ситуацию: результат произведения матриц зависит от порядка сомножителей (в отличие от обычной арифметики) — и даже может не существовать для одного выбора порядка сомножителей, существуя для другого.

Элементарные свойства операций с матрицами (продолжение)

Операция умножения матриц также обладает рядом естественных свойств. (Ниже считается, что типы матриц \(A,B\) согласованы, так что их можно перемножать).

6. Для квадратных матриц \(A,B\) одного типа \(det(AB)=detA \cdot detB\).

7. Рассмотрим квадратную матрицу порядка \(n\), \(E=diag\\). Такая матрица играет выделенную роль в умножении матриц: для любых матриц \(A,B\) имеем \(EA=A\), \(BE=B\). Матрица \(E\) называется единичной матрицей порядка \(n\). Согласно описанным выше результатам, \(detE=1\).

1. Умножить матрицы:

а) \[ \left( \begin 2 & 1 \\ 3 & 4 \end \right)\cdot \left( \begin 1 & -1 \\ 2 & 1 \end \right). \]

б) \[ \left( \begin 3 & 1 & 1 \\ 2 & 1 & 2 \\ 1 & 2 & 1 \end \right)\cdot \left( \begin 1 &1 & -1 \\ 2 & -1 & 1 \\ -1 & 2 & 1 \end \right). \]

2. Вычислить \[ \left( \begin 3 & 2 \\ -4 & -2 \end \right)^5. \]

3. Вычислить \(AB-BA\), если

а) \[ A=\left( \begin 1 &2 & 3 \\ 1 & -1 & 0 \\ -1 & 2 & 1 \end \right), B=\left( \begin 4 & 2 & 3 \\ — 1 & 1 & 3 \\ 1 & 2 & 1 \end \right). \]

б) \[ A=\left( \begin 2 &1 & 0 \\ 1 & 1 & 2 \\ 1 & 2 & 1 \end \right), B=\left( \begin 3 & 1 & -2 \\ 1 & -1 & 3 \\3 & 5 & 1 \end \right). \]

а) \(f(A)\), если \(f(x)=x^2-3x+3\), \[ A=\left( \begin -1 & 3 & 2 \\ 1 & -1 & 3 \\ -1 & 2 & 1 \end \right). \]

б) \(f(A)\), если \(f(x)=x^2+4x-2\), \[ A=\left( \begin 2 & 1 & 1 \\ 3 & -1 & 2 \\ -1 & 2 & 0 \end \right). \]

5. Показать, что каждая матрица второго порядка \[ A=\left( \begin a & b \\ c & d \end \right) \]

удовлетворяет уравнению \[ x^2-(a+d)x+(ad-bc)=0. \]

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

В рамках обычной арифметики обсуждается решение числового уравнения \[ ax=1, \] где \(a\) — заданное число. Если \(a \neq 0\), это уравнение имеет единственное решение, которое обозначается \(x=a^\) и называется обратным к \(a\) числом.

Пусть \(A\) — заданная квадратная матрица порядка \(n\), можно рассмотреть матричное уравнение \[ AX=E. \quad \quad(10) \]

Решение уравнения (\ref) называется матрицей, обратной \(A\).

Для того, чтобы существовала обратная \(A\) матрица, небходимо и достаточно, чтобы матрица \(A\) была невырожденной.

Обратную матрицу обозначают \(A^\).

Основные свойства обратной матрицы.

3. Если квадратные матрицы порядка \(n\) \(A\) и \(B\) невырождены, то \(AB\) тоже невырождена, у нее существует обратная матрица, причем \((AB)^=B^A^\).

4. Для невырожденной квадратной матрицы \(A\) верно: \((A^)^=A\).

5. Для невырожденной квадратной матрицы \(A\) верно: \((A^T)^=(A^)^T\).

Докажите эти свойства обратной матрицы.

Для вычисления эелементов обратной матрицы существуют явные формулы.

Пусть \(A\) — квадратная невырожденная матрица порядка \(n\). Вычислим матрицу \(D\) — матрицу алгебраических дополнений, согласно соотношениям

Пусть \(n=2\), \[ A=\left( \begin a & b \\ c & d \end \right), \] \(detA=ad-bc \neq 0\). Следуя (11), получаем: \[ D=\left( \begin d & -c \\ -b & a \end \right), \] так что \[ A^=\frac\left( \begin d & -b \\ -c & a \end \right). \]

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

Найти обратную матрицу для матрицы

1. \[ A=\left( \begin 2 &2 & 3 \\ 1 & -1 & 0 \\ -1 & 2 & 1 \end \right). \]

2. \[ A=\left( \begin 2 &-1 & 0 \\ 0 & 2 & -1 \\ -1 & -1 & 1 \end \right). \]

3. \[ A=\left( \begin 1 &1 & 1 \\ 1 & 2 & 2 \\ 2 & 3 & 4 \end \right). \]

Матричные уравнения

Матричными уравнениями называются уравнения вида \[ AX=G, \quad \quad(12)\] \[ XB=G, \quad \quad(13)\] \[ AXB=G, \quad \quad(14)\] где матрицы \(A,B,G\) заданы и требуется построить матрицу \(X\). Мы будем здесь считать, что матрицы \(A,B,G\) — квадратные одного порядка. Решение этих уравнений нетрудно построить, если матрицы \(A,B\) невырождены, так что существуют их обратные \(A^, B^\). Умножая, например, уравнение (12) слева на матрицу \(A^\), получаем: \[ A^(AX)=(A^A)X=EX=X=A^G. \] Умножая уравнение (13) справа на \(B^\), получаем: \[ (XB)B^=X(BB^)=XE=X=GB^. \] Аналогично, умножая (14) слева на \(A^\) и справа на \(B^\), получим: \[ X=A^GB^. \]

1. Найти решение матричного уравнения (12), если \[ A=\left( \begin 2 & 6 \\ -9 & 3 \end \right) , G=\left( \begin -26 & -50 \\ 27 & -15 \end \right) . \]

2. Найти решение матричного уравнения (12), если \[ A=\left( \begin 8 & -7 \\ -5 & 4 \end \right) , G=\left( \begin 25 & -34 \\ -16 & 22 \end \right) . \]

3. Найти решение матричного уравнения (13), если \[ B=\left( \begin -8 & -5 \\ -9 & 5 \end \right) , G=\left( \begin -20 & 30 \\ -19 & 20 \end \right) . \]

4. Найти решение матричного уравнения (13), если \[ B=\left( \begin 9 & 8 \\ -3 & 7 \end \right) , G=\left( \begin -72 & 23 \\ 0 & 58 \end \right) . \]

5. Найти решение матричного уравнения (14), если \[ A=\left( \begin 4 & 2 \\ 3 & -4 \end \right) , B=\left( \begin -1 & 2 \\ -2 & -1 \end \right) , G=\left( \begin 20 & -50 \\ 26 & 23 \end \right) . \]

6. Найти решение матричного уравнения (14), если \[ A=\left( \begin -4 & -2 \\ -3 & 3 \end \right) , B=\left( \begin 3 & 4 \\ 4 & 3 \end \right) , G=\left( \begin 132 & 134 \\ 18 & 24 \end \right) . \]

С какого элемента считаются матрицы c

3.3. Понятие матрицы. Основные матричные операции

Если выражений расставлены в прямоугольной таблице из строк и столбцов:

то говорят о матрице размера , или сокращенно об — матрице. Выражения называются элементами матрицы. Положение элемента в таб­лице характеризуется двойным индексом; первый индекс означает номер строки, второй- номер столбца, на пересечении которых стоит элемент (нумерация строк производится сверху вниз, а столбцов — слева направо). Элементами матрицы, как правило, являются числа, но иногда и другие математические объекты, например, векторы, многочлены, дифференциалы и даже матрицы. Матрица обозначается следующими способами :

Матрица размера называется квадратной матрицей порядка п.

Определитель квадратной матрицы.
Каждой квадратной матрице порядка с действительными или комплексными элементами можно однозначно поставить в соответствие действительное или комплексное число , которое называется определителем матрицы .

причем сумма должна быть распространена на все подстановки набора чисел

Если — определитель порядка , то минором элемента называют определитель порядка , получающийся из “вычеркиванием” i — й строки и j -го столбца.

Вычисление определителей.

Рассмотрим какую-либо четверку чисел, записанных в виде матрицы по два в строках и по два столбцах. Определителем или детерминантом, составленным из чисел этой таблицы, называется число ad bc , обозначаемое так: . Такой определитель называется определителем второго порядка, поскольку для его составления взята таблица из двух строк и двух столбцов. Числа, из которых составлен определитель, называются его элементами; при этом говорят, что элементы a и d составляют главную диагональ определителя, а элементы b и c его побочную диагональ. Видно, что определитель равен разности произведений пар элементов, стоящих на его главной и побочной диагоналях. Определитель третьего и любого другого порядка находится примерно также, а именно: Допустим, что у нас есть квадратная матрица . Определителем матрицы является выражение: + + – – – . С положительным знаком идут главная диагональ и образующиеся из элементов треугольники, имеющие параллельную главной диагонали сторону, в данном случае это треугольники , . С отрицательным знаком идут побочная диагональ и треугольники ей параллельные, т.е. , .

Основные операции над матрицами.

Основными арифметическими операциями над матрицами являются умножение матрицы на число, сложение и умножение матриц.

Матрицы равны, если они имеют одинаковые порядки и все их соответствующие элементы совпадают.

Перейдем к определению основных операций над матрицами.

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

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

Итак по определению имеем:

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

1) переместительным свойством:

2) сочетательным свойством:

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

Умножение матрицы на число:

Произведением матрицы на вещественное число называется матрица , элементы которой равны .

Для обозначения произведения матрицы на число используется запись C = A или C = A . Операция составления произведения матрицы на число называется умножением матрицы на это число.

Умножение матрицы на число обладает следующими свойствами:

1) распределительным свойством относительно суммы матриц:

2) сочетательным свойством относительно числового множителя:

3) распределительным свойством относительно суммы чисел:

( + ) A = A + A .

Перемножение матриц:

Произведением матрицы , имеющей порядки соответственно равные m и n , на матрицу , имеющую порядки соответственно равные n и p , называется матрица , имеющая порядки, соответственно равные m и p , и элементы c ij , определяемые формулой

Для обозначения произведения матрицы A на матрицу B используют запись C = AB . Операция составления произведения матрицы A на матрицу B называется перемножением этих матриц. Из сформулированного выше определения вытекает, что матрицу A можно умножить не на всякую матрицу B : необходимо чтобы число столбцов матрицы A было равно числу строк матрицы B . Для того чтобы оба произведения AB и BA не только были определены, но и имели одинаковый порядок, необходимо и достаточно, чтобы обе матрицы A и B были квадратными матрицами одного и того же порядка.

Это правило можно сформулировать и словесно: Элемент c ij , стоящий на пересечении i — й строки и j -го столбца матрицы C = AB , равен сумме попарных произведений соответствующих элементов i — й строки матрицы A и j -го столбца матрицы B . В качестве примера применения указанного правила приведем формулу перемножения квадратных матриц второго порядка

Свойства произведения матрицы A на матрицу B :

1) сочетательное свойство: ( AB ) C = A ( BC ) ;

2) распределительное относительно суммы матриц свойство:

(A + B) C = AC + BC или A (B + C) = AB + AC.

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

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

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

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

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

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

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

В этой статье предполагается, что вы владеете программированием на C# хотя бы на среднем уровне и по крайней мере на базовом уровне понимаете матричные операции и сопутствующую терминологию. Все ключевые части кода на C# приведены в самой статье. Полный исходный код можно скачать по ссылке archive.msdn.microsoft.com/mag201207matrix.

Определение матрицы

Существует несколько способов реализации матрицы на C#. Традиционный подход (он используется в этой статье) — применение массива массивов, который иногда называют массивом с неровными границами (jagged array). Например, следующий код определяет матрицу с тремя строками и двумя столбцами:

double[][] m = new double[3][]; m[0] = new double[2]; m[1] = new double[2]; m[2] = new double[2]; m[2][1] = 5.0; // присваиваем значение строке 2, столбцу 1 

В отличие от большинства языков программирования в C# есть встроенный тип многомерного массива, который предоставляет альтернативный подход к матрицам, например:

double[,] m = new double[3,2]; m[2,1] = 5.0; 

Третий подход к реализации матриц на C# — использование одного массива в сочетании с манипуляциями над индексами массива:

int rows = 3; int cols = 2; double[] m = new double[rows * cols]; int i = 2; int j = 1; m[i * cols + j] = 5.0; 

Независимо от примененной схемы хранения матрицы можно реализовать, используя либо ООП (объектно-ориентированное программирование), либо подход со статическими методами. Так, подход с ООП мог бы быть примерно таким:

public class MyMatrix < int m; // количество строк int n; // количество столбцов data[][]; // значения . >

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

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

static double[][] MatrixCreate(int rows, int cols) < // Создаем матрицу, полностью инициализированную // значениями 0.0. Проверка входных параметров опущена. double[][] result = new double[rows][]; for (int i = 0; i < rows; ++i) result[i] = new double[cols]; // автоинициализация в 0.0 return result; >

Этот метод можно вызывать так:

double[][] m = MatrixCreate(3,2); m[2][1] = 5.0; 

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

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

static string MatrixAsString(double[][] matrix) < string s = ""; for (int i = 0; i < matrix.Length; ++i) < for (int j = 0; j < matrix[i].Length; ++j) s += matrix[i][j].ToString("F3").PadLeft(8) + " "; s += Environment.NewLine; >return s; > 

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

Перемножение матриц

Microsoft .NET Framework 4 и более поздние версии предоставляют хороший способ значительно повысить производительность метода перемножения матриц. Перемножение матриц иллюстрируется на рис. 2.

Перемножение матриц

Рис. 2. Перемножение матриц

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

static double[][] MatrixProduct(double[][] matrixA, double[][] matrixB) < int aRows = matrixA.Length; int aCols = matrixA[0].Length; int bRows = matrixB.Length; int bCols = matrixB[0].Length; if (aCols != bRows) throw new Exception("Non-conformable matrices in MatrixProduct"); double[][] result = MatrixCreate(aRows, bCols); for (int i = 0; i < aRows; ++i) // каждая строка A for (int j = 0; j < bCols; ++j) // каждый столбец B for (int k = 0; k

Task Parallel Library упрощает кодирование простой распараллеленной версии перемножения матриц.

Поскольку перемножение матриц является операцией порядка O(n^3), производительность может быть проблемой. Так, если размер матрицы A равен 300 × 200, а матрицы B — 200 × 400, вычисление результата произведения A и B требует 300 * 200 * 400 = 24 000 000 операций умножения. Task Parallel Library (TPL) в пространстве имен System.Threading.Tasks в .NET Framework 4 и более поздних версиях упрощает кодирование простой распараллеленной версии перемножения матриц. Один из возможных вариантов выглядит так:

static double[][] MatrixProduct(double[][] matrixA, double[][] matrixB) < // Проверка ошибок, вычисление aRows, aCols, bCols double[][] result = MatrixCreate(aRows, bCols); Parallel.For(0, aRows, i => < for (int j = 0; j < bCols; ++j) for (int k = 0; k < aCols; ++k) result[i][j] += matrixA[i][k] * matrixB[k][j]; >); return result; > 

В этой версии вычисления делятся по строкам. «За кулисами» TPL генерирует весь сложный код инфраструктуры синхронизации для параллельных вычислений на нескольких процессорах.

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

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

static double[][] MatrixRandom(int rows, int cols, double minVal, double maxVal, int seed) < // Возвращаем матрицу со значениями // в диапазоне от minVal до maxVal Random ran = new Random(seed); double[][] result = MatrixCreate(rows, cols); for (int i = 0; i

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

static double[][] MatrixIdentity(int n)

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

static bool MatrixAreEqual(double[][] matrixA, double[][] matrixB, double epsilon) < // True, если все значения в A равны // соответствующим значениям в B int aRows = matrixA.Length; int bCols = matrixB[0].Length; for (int i = 0; i < aRows; ++i) // каждая строка A и B for (int j = 0; j < aCols; ++j) // каждый столбец A и B if (Math.Abs(matrixA[i][j] - matrixB[i][j]) >epsilon) return false; return true; > 

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

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

double[][] m = MatrixRandom(4, 4, -9.0, 9.0, 0); double[][] i = MatrixIdentity(4); double[][] mi = MatrixProduct(m, i); if (MatrixAreEqual(m, mi, 0.00000001) == true) Console.WriteLine("Consistent result"); else Console.WriteLine("Something is wrong"); Проверка согласованности хорошо поддается тестированию случайным вводом. 

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

При разложении берется квадратная матрица M и вычисляются две новые квадратные матрицы, которые при перемножении дают исходную матрицу M. Идея аналогичная обычному разложению чисел на множители: число 6 можно разложить на множители 2 и 3, потому что 2 * 3 = 6. Поначалу может показаться, что в разложении матриц нет особого смысла, но оказывается, что такое разложение существенно упрощает очень трудную задачу обращения матрицы. Если много видов разложения матриц, и каждый из них может вычисляться по нескольким алгоритмам. Методика, представленная в этой статье, называется разложением LUP и использует метод Дулитла (Doolittle's method) с выбором ведущего элемента столбца (partial pivoting).

Чтобы понять разложение LUP, полезно сначала разобраться в простом разложении LU, которое было введено знаменитым математиком Аланом Тьюрингом (Alan Turing). Допустим, у вам имеется вот такая матрица M размером 4 × 4:

9.000 5.000 3.000 4.000 4.000 8.000 2.000 5.000 3.000 5.000 7.000 1.000 2.000 6.000 0.000 8.000 

Одно из возможных разложений LU для M — это L, равная:

1.000 0.000 0.000 0.000 0.444 1.000 0.000 0.000 0.333 0.577 1.000 0.000 0.222 0.846 -0.219 1.000 
9.000 5.000 3.000 4.000 0.000 5.778 0.667 3.222 0.000 0.000 5.615 -2.192 0.000 0.000 0.000 3.904 

Это работает, так как L * U = M. Заметьте, что нижняя матрица L имеет значения 1.0 по диагонали и 0.0 вверху справа. Иначе говоря, значимые значения ячеек нижней матрицы находятся внизу слева. Аналогично значимые значения ячеек верхней матрицы расположены на основной диагонали и вверху справа.

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

Разложение LUP матрицы — небольшая, но важная вариация разложения LU. При разложении LUP берется матрица matrix M и создаются матрицы L и U, а также массив P. Произведение L и U в LUP не точно соответствует исходной матрице M, а является версией M, где некоторые строки переупорядочены. Информация о том, как эти строки были переупорядочены, хранится в массиве P; эту информацию можно использовать для реконструкции исходной матрицы M.

Близкий вариант разложения Дулитла, представленного в этой статье, называется разложением Краута (Crout). Главное различие между методами Дулитла и Краута в том, что Дулитл помещает значения 1.0 на основную диагональ матрицы L, а Краут — на основную диагональ матрицы U.

Причина, по которой разложение LUP используется чаще, чем разложение LU, весьма тонкая. Как вы вскоре увидите, разложение используется для обращения матрицы. Однако, когда разложение матрицы применяется как вспомогательный метод для ее обращения, оказывается, что инверсия заканчивается неудачей, если по основной диагонали матрицы LU имеется значение 0.0. Поэтому в разложении LUP, когда на основной диагонали появляется значение 0.0, алгоритм меняет местами две строки, чтобы сместить значение 0.0 с диагонали, и отслеживает, какие строки были переставлены, в массиве P.

Метод разложения матрицы показан на рис. 3.

Рис. 3. Метод разложения матрицы

static double[][] MatrixDecompose(double[][] matrix, out int[] perm, out int toggle) < // Разложение LUP Дулитла. Предполагается, // что матрица квадратная. int n = matrix.Length; // для удобства double[][] result = MatrixDuplicate(matrix); perm = new int[n]; for (int i = 0; i < n; ++i) < perm[i] = i; >toggle = 1; for (int j = 0; j < n - 1; ++j) // каждый столбец < double colMax = Math.Abs(result[j][j]); // Наибольшее значение в столбце j int pRow = j; for (int i = j + 1; i < n; ++i) < if (result[i][j] >colMax) < colMax = result[i][j]; pRow = i; >> if (pRow != j) // перестановка строк < double[] rowPtr = result[pRow]; result[pRow] = result[j]; result[j] = rowPtr; int tmp = perm[pRow]; // Меняем информацию о перестановке perm[pRow] = perm[j]; perm[j] = tmp; toggle = -toggle; // переключатель перестановки строк >if (Math.Abs(result[j][j]) < 1.0E-20) return null; for (int i = j + 1; i < n; ++i) < result[i][j] /= result[j][j]; for (int k = j + 1; k < n; ++k) result[i][k] -= result[i][j] * result[j][k]; >> // основной цикл по столбцу j return result; > 

Этот метод можно было бы вызвать так:

double[][] m = MatrixRandom(4, 4, -9.0, 9.0, 0); int[] perm; int toggle; double luMatrix = MatrixDecompose(m, out perm, out toggle); 

Метод MatrixDecompose принимает квадратную матрицу и возвращает три значения. Явно возвращается переставленная матрица LU. Остальные два значения возвращаются через выходные параметры. Один из них является массивом перестановки (permutation array), где хранится информация о том, как переставлены строки. Второй выходной параметр — переключатель, принимающий значение либо +1, либо –1 в зависимости от того, было количество перестановок четным (+1) или нечетным (–1). Значение переключателя не используется для обращения матрицы, но необходимо, если разложение применяется для вычисления определителя матрицы.

Метод MatrixDecompose весьма замысловатый, но на самом деле для модификации кода достаточно понимать в нем лишь несколько деталей. Версия, представленная здесь, выделяет новую память под возвращаемую матрицу LU через вспомогательный метод MatrixDuplicate:

static double[][] MatrixDuplicate(double[][] matrix) < // Предполагается, что матрица не нулевая double[][] result = MatrixCreate(matrix.Length, matrix[0].Length); for (int i = 0; i < matrix.Length; ++i) // Копирование значений for (int j = 0; j

Альтернативный подход — помещение результата во входную матрицу для экономии памяти. Семантика C# требует сделать параметр matrix передаваемым по ссылке (ref), потому что он используется и для ввода, и для вывода. При таком подходе сигнатура метода выглядела бы следующим образом:

static void MatrixDecompose(ref double[][] matrix, out int[] perm, out int toggle) 

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

static int[] MatrixDecompose(ref double[][] matrix, out int toggle) 

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

Другая часть MatrixDecompose, которую вам, может быть, захочется изменить, — это выражение:

if (Math.Abs(result[j][j]) < 1.0E-20) return null; 

Этот код означает следующее: если даже после обмена двух строк из-за того, что на основной диагонали было значение 0.0, там все равно остается 0.0, то вернуть null». Возможно, вы захотите сменить произвольное значение epsilon с 1.0E-20 на какое-то другое значение в зависимости от уровня точности, используемого в вашей системе. И вместо возврата null можно генерировать исключение; если бы этот метод вызывался в процессе обращения матрицы, данный процесс заканчивался бы неудачей. Наконец, если вы используете разложение матрицы для целей, отличных от ее обращения, то можно вообще исключить это выражение.

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

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

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

static double[] HelperSolve(double[][] luMatrix, double[] b) < // Решаем luMatrix * x = b int n = luMatrix.Length; double[] x = new double[n]; b.CopyTo(x, 0); for (int i = 1; i < n; ++i) < double sum = x[i]; for (int j = 0; j < i; ++j) sum -= luMatrix[i][j] * x[j]; x[i] = sum; >x[n - 1] /= luMatrix[n - 1][n - 1]; for (int i = n - 2; i >= 0; --i) < double sum = x[i]; for (int j = i + 1; j < n; ++j) sum -= luMatrix[i][j] * x[j]; x[i] = sum / luMatrix[i][i]; >return x; > 

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

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

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

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

static double[][] MatrixInverse(double[][] matrix) < int n = matrix.Length; double[][] result = MatrixDuplicate(matrix); int[] perm; int toggle; double[][] lum = MatrixDecompose(matrix, out perm, out toggle); if (lum == null) throw new Exception("Unable to compute inverse"); double[] b = new double[n]; for (int i = 0; i < n; ++i) < for (int j = 0; j < n; ++j) < if (i == perm[j]) b[j] = 1.0; else b[j] = 0.0; >double[] x = HelperSolve(lum, b); for (int j = 0; j < n; ++j) result[j][i] = x[j]; >return result; > 

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

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

double[][] m = MatrixRandom(4, 4, -9.0, 9.0, 0); double[][] inverse = MatrixInverse(m); Console.WriteLine(MatrixAsString(inverse)); 

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

Определитель матрицы

Когда у вас есть метод разложения матрицы, написать метод для вычисления определителя матрицы нетрудно:

static double MatrixDeterminant(double[][] matrix)

Как это ни удивительно, оказывается, что определитель матрицы — это просто результат перемножения значений на основной диагонали матрицы разложения LUP со знаком «плюс» или «минус» в зависимости от значения toggle. Обратите внимание на неявное преобразование типа значения toggle из int в double. Помимо добавления проверки ошибок в MatrixDeterminant, вы должны добавить прямой возврат в ситуациях, где размер входной матрицы равен 1 (возвращается единственное значение) или 2 × 2 (возвращается a*d – b*c). Вызов этого метода мог бы выглядеть так:

double[][] m = MatrixRandom(4, 4, -9.0, 9.0, 0); double det = MatrixDeterminant(m); Console.WriteLine("Determinant = " + det.ToString("F2")); 

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

Метод HelperSolve можно легко адаптировать для решения системы линейных уравнений:

static double[] SystemSolve(double[][] A, double[] b) < // Решаем Ax = b int n = A.Length; int[] perm; int toggle; double[][] luMatrix = MatrixDecompose( A, out perm, out toggle); if (luMatrix == null) return null; // или исключение double[] bp = new double[b.Length]; for (int i = 0; i

Вот код, который дал вывод, показанный на рис. 1, для решения следующей системы:

3x0 + 7x1 + 2x2 + 5x3 = 49 x0 + 8x1 + 4x2 + 2x3 = 30 2x0 + x1 + 9x2 + 3x3 = 43 5x0 + 4x1 + 7x2 + x3 = 52 double[][] m = MatrixCreate(4, 4); m[0][0] = 3.0; m[0][1] = 7.0; m[0][2] = 2.0; m[0][3] = 5.0; m[1][0] = 1.0; m[1][1] = 8.0; m[1][2] = 4.0; m[1][3] = 2.0; m[2][0] = 2.0; m[2][1] = 1.0; m[2][2] = 9.0; m[2][3] = 3.0; m[3][0] = 5.0; m[3][1] = 4.0; m[3][2] = 7.0; m[3][3] = 1.0; double[] b = new double[] < 49.0, 30.0, 43.0, 52.0 >; double[] x = SystemSolve(m, b); Console.WriteLine("\nSolution is x = \n" + VectorAsString(x)); 

Заметьте, что SystemSolve переупорядочивает свой входной параметр b, используя массив perm из MatrixDecompose до вызова HelperSolve.

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

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

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

// Создаем матрицу m. // Вызываем MatrixDecompose, возвращаем lu и perm. // Извлекаем нижнюю часть lu как матрицу 'lower'. // Извлекаем верхнюю часть lu как матрицу 'upper'. double[][] lu = MatrixProduct(lower, upper); double[][] orig = UnPermute(lu, perm); if (MatrixAreEqual(orig, m, 0.000000001) == true) Console.WriteLine("L and U unpermuted using perm array"); 

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

static double[][] UnPermute(double[][] luProduct, int[] perm) < double[][] result = MatrixDuplicate(luProduct); int[] unperm = new int[perm.Length]; for (int i = 0; i < perm.Length; ++i) unperm[perm[i]] = i; // создаем массив unperm for (int r = 0; r < luProduct.Length; ++r) //по каждой строке result[r] = luProduct[unperm[r]]; return result; >

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

// Создаем матрицу m. // Вызываем MatrixDecompose, возвращаем lu и perm. // Извлекаем нижнюю часть lu как матрицу 'lower'. // Извлекаем верхнюю часть lu как матрицу 'upper'. double[][] permMatrix = PermArrayToMatrix(perm); double[][] orig = MatrixProduct(permMatrix, lu); if (MatrixAreEqual(orig, m, 0.000000001) == true) Console.WriteLine("L and U unpermuted using perm matrix"); 

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

static double[][] PermArrayToMatrix(int[] perm) < // Массив perm преобразуем // в соответствующую матрицу по Дулитлу int n = perm.Length; double[][] result = MatrixCreate(n, n); for (int i = 0; i

Заключение

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

Джеймс Маккафри (Dr. James McCaffrey) — руководит в компании Volt Information Sciences Inc. повышением квалификации инженеров ПО из Microsoft, работающих в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и MSN Search. Автор книги «.NET Test Automation Recipes» (Apress, 2006). С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Полу Коху (Paul Koch) и Дэну Либлингу (Dan Liebling).

Как определить количество различных элементов матрицы в C++

Всем доброго времени суток! Хотел бы попросить вас о помощи. Не могу понять, как сделать следующее задание. Нужно сделать следующее задание: "Задана символьная матрица размером NxM. Определить количество различных элементов матрицы (т.е. повторяющиеся элементы считать один раз)." Тело следующее:

#include #include #include #include #include #include using namespace std; int main()< using std::setlocale; // следующие 2 строчки - РУССК ЯЗ setlocale(LC_ALL,""); int i,n,m,k,j; printf ("Введите кол-во строк массива не более 15 элементов, n = "); scanf("%d",&n); printf ("Введите кол-во столбцов массива не более 15 элементов, m = "); scanf("%d",&m); int **mas; mas=new int *[n]; for(i=0;i0)&&(k <=2)) < printf("Массив mas \n"); switch(k) < case 2: for (i=0; iprintf("\n"); > break; case 1: for (i=0; i > bool p= true; while (p==true) < p=false; for(i=0;iif(sum1>sum2) < for(j=0;jp=true; > // > > printf("Результат: \n"); for(i=0;i printf("\n"); > return 0; > 

Отслеживать

задан 16 дек 2018 в 16:46

Anton Zhahalkovich Anton Zhahalkovich

11 1 1 серебряный знак 5 5 бронзовых знаков

"символьная матрица" - ??

– user176262

16 дек 2018 в 16:47

да, символьная.

16 дек 2018 в 16:51

что это значит?

– user176262

16 дек 2018 в 16:52

вот и я особо не понял

16 дек 2018 в 17:01

"символьная матрица" Скорее всего имелось ввиду матрица из символов, то есть матрица из букв, то есть из переменных типа char в которые записаны буквы, а не управляющие символы. Ну, или матрица из wchar_t, для эстетов.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *