Каждый вектор можно рассматривать как одностолбцовую или однострочную матрицу. Одностолбцовую матрицу будем называть вектор-столбцом, а однострочную матрицу - вектор-строкой.
Если A-матрица размера m*n, то вектор столбец b имеет размер n, а вектор строка b имеет размер m.
Таким образом, что бы умножить матрицу на вектор, надо рассматривать вектор как вектор-столбец. При умножении вектора на матрицу, его нужно рассматривать как вектор -строку.
Умножить матрицу
на комплексный вектор
Получаем результат
Как видите при неизменной размерности вектора, у нас могут существовать два решения.
Хотелось бы обратить Ваше внимание на то что матрица в первом и втором варианте, несмотря на одинаковые значения, совершенно разные (имеют различную размерность)
В первом случае вектор считается как столбец и тогда необходимо умножать матрицу на вектор , а во втором случае у нас вектор-строка и тогда у нас произведение вектора на матрицу.
Данный бот умножает в том числе вектора и матрицы которые имею комплексные значения. Создан на основе более полного калькулятора Умножение матриц с комплексными значениями онлайн
Свойства умножения матрицы на вектор
Матрица
Вектор столбец
Вектор-строка
Произвольное число
1. Произведение матрицы на сумму векторов-столбцов равна сумме произведений матрицы на каждый из векторов
2. Произведение суммы векторов-строк на матрицу равна сумме произведений векторов на матрицу
3. Общий множитель вектора можно вынести за пределы произведения матрицы на вектор/вектора на матрицу
4.Произведение вектора-строки на произведение матрицы и вектора столбца, равноценно произведению произведения вектора-строки на матрицу и вектора-столбца.
Определение 1Произведение матриц (С= АВ) - операция только для согласованных матриц А и В, у которых число столбцов матрицы А равно числу строк матрицы В:
C ⏟ m × n = A ⏟ m × p × B ⏟ p × n
Пример 1
Даны матрицы:
- A = a (i j) размеров m × n ;
- B = b (i j) размеров p × n
Матрицу C , элементы c i j которой вычисляются по следующей формуле:
c i j = a i 1 × b 1 j + a i 2 × b 2 j + . . . + a i p × b p j , i = 1 , . . . m , j = 1 , . . . m
Пример 2
Вычислим произведения АВ=ВА:
А = 1 2 1 0 1 2 , В = 1 0 0 1 1 1
Решение, используя правило умножения матриц:
А ⏟ 2 × 3 × В ⏟ 3 × 2 = 1 2 1 0 1 2 × 1 0 0 1 1 1 = 1 × 1 + 2 × 0 + 1 × 1 1 × 0 + 2 × 1 + 1 × 1 0 × 1 + 1 × 0 + 2 × 1 0 × 0 + 1 × 1 + 2 × 1 = = 2 3 2 3 ⏟ 2 × 2
В ⏟ 3 × 2 × А ⏟ 2 × 3 = 1 0 0 1 1 1 × 1 2 1 0 1 2 = 1 × 1 + 0 × 0 1 × 2 + 0 × 1 1 × 1 + 0 × 2 0 × 1 + 1 × 0 0 × 2 + 1 × 1 0 × 1 + 1 × 2 1 × 1 + 1 × 0 1 × 2 + 1 × 1 1 × 1 + 1 × 2 = 1 2 1 0 1 2 1 3 3 ⏟ 3 × 3
Произведение А В и В А найдены, но являются матрицами разных размеров: А В не равна В А.
Свойства умножения матриц
Свойства умножения матриц:
- (А В) С = А (В С) - ассоциативность умножения матриц;
- А (В + С) = А В + А С - дистрибутивность умножения;
- (А + В) С = А С + В С - дистрибутивность умножения;
- λ (А В) = (λ А) В
Проверяем свойство №1: (А В) С = А (В С) :
(А × В) × А = 1 2 3 4 × 5 6 7 8 × 1 0 0 2 = 19 22 43 50 × 1 0 0 2 = 19 44 43 100 ,
А (В × С) = 1 2 3 4 × 5 6 7 8 1 0 0 2 = 1 2 3 4 × 5 12 7 16 = 19 44 43 100 .
Пример 2
Проверяем свойство №2: А (В + С) = А В + А С:
А × (В + С) = 1 2 3 4 × 5 6 7 8 + 1 0 0 2 = 1 2 3 4 × 6 6 7 10 = 20 26 46 58 ,
А В + А С = 1 2 3 4 × 5 6 7 8 + 1 2 3 4 × 1 0 0 2 = 19 22 43 50 + 1 4 3 8 = 20 26 46 58 .
Произведение трех матриц
Произведение трех матриц А В С вычисляют 2-мя способами:
- найти А В и умножить на С: (А В) С;
- либо найти сначала В С, а затем умножить А (В С) .
Перемножить матрицы 2-мя способами:
4 3 7 5 × - 28 93 38 - 126 × 7 3 2 1
Алгоритм действий:
- найти произведение 2-х матриц;
- затем снова найти произведение 2-х матриц.
1). А В = 4 3 7 5 × - 28 93 38 - 126 = 4 (- 28) + 3 × 38 4 × 93 + 3 (- 126) 7 (- 28) + 5 × 38 7 × 93 + 5 (- 126) = 2 - 6 - 6 21
2). А В С = (А В) С = 2 - 6 - 6 21 7 3 2 1 = 2 × 7 - 6 × 2 2 × 3 - 6 × 1 - 6 × 7 + 21 × 2 - 6 × 3 + 21 × 1 = 2 0 0 3 .
Используем формулу А В С = (А В) С:
1). В С = - 28 93 38 - 126 7 3 2 1 = - 28 × 7 + 93 × 2 - 28 × 3 + 93 × 1 38 × 7 - 126 × 2 38 × 3 - 126 × 1 = - 10 9 14 - 12
2). А В С = (А В) С = 7 3 2 1 - 10 9 14 - 12 = 4 (- 10) + 3 × 14 4 × 9 + 3 (- 12) 7 (- 10) + 5 × 14 7 × 9 + 5 (- 12) = 2 0 0 3
Ответ: 4 3 7 5 - 28 93 38 - 126 7 3 2 1 = 2 0 0 3
Умножение матрицы на число
Определение 2Произведение матрицы А на число k - это матрица В = А k того же размера, которая получена из исходной умножением на заданное число всех ее элементов:
b i , j = k × a i , j
Свойства умножения матрицы на число:
- 1 × А = А
- 0 × А = нулевая матрица
- k (A + B) = k A + k B
- (k + n) A = k A + n A
- (k × n) × A = k (n × A)
Найдем произведение матрицы А = 4 2 9 0 на 5.
5 А = 5 4 2 9 0 5 × 4 5 × 2 5 × 9 5 × 0 = 20 10 45 0
Умножение матрицы на вектор
Определение 3Чтобы найти произведение матрицы и вектора, необходимо умножать по правилу «строка на столбец»:
- если умножить матрицу на вектор-столбец число столбцов в матрице должно совпадать с числом строк в векторе-столбце;
- результатом умножения вектора-столбца является только вектор-столбец:
А В = а 11 а 12 ⋯ а 1 n а 21 а 22 ⋯ а 2 n ⋯ ⋯ ⋯ ⋯ а m 1 а m 2 ⋯ а m n b 1 b 2 ⋯ b 1 n = a 11 × b 1 + a 12 × b 2 + ⋯ + a 1 n × b n a 21 × b 1 + a 22 × b 2 + ⋯ + a 2 n × b n ⋯ ⋯ ⋯ ⋯ a m 1 × b 1 + a m 2 × b 2 + ⋯ + a m n × b n = c 1 c 2 ⋯ c 1 m
- если умножить матрицу на вектор-строку, то умножаемая матрица должна быть исключительно вектором-столбцом, причем количество столбцов должно совпадать с количеством столбцов в векторе-строке:
А В = а а ⋯ а b b ⋯ b = a 1 × b 1 a 1 × b 2 ⋯ a 1 × b n a 2 × b 1 a 2 × b 2 ⋯ a 2 × b n ⋯ ⋯ ⋯ ⋯ a n × b 1 a n × b 2 ⋯ a n × b n = c 11 c 12 ⋯ c 1 n c 21 c 22 ⋯ c 2 n ⋯ ⋯ ⋯ ⋯ c n 1 c n 2 ⋯ c n n
Пример 5
Найдем произведение матрицы А и вектора-столбца В:
А В = 2 4 0 - 2 1 3 - 1 0 1 1 2 - 1 = 2 × 1 + 4 × 2 + 0 × (- 1) - 2 × 1 + 1 × 2 + 3 × (- 1) - 1 × 1 + 0 × 2 + 1 × (- 1) = 2 + 8 + 0 - 2 + 2 - 3 - 1 + 0 - 1 = 10 - 3 - 2
Пример 6
Найдем произведение матрицы А и вектора-строку В:
А = 3 2 0 - 1 , В = - 1 1 0 2
А В = 3 2 0 1 × - 1 1 0 2 = 3 × (- 1) 3 × 1 3 × 0 3 × 2 2 × (- 1) 2 × 1 2 × 0 2 × 2 0 × (- 1) 0 × 1 0 × 0 0 × 2 1 × (- 1) 1 × 1 1 × 0 1 × 2 = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2
Ответ: А В = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2
Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
В системе MatLab достаточно просто выполняются математические операции над матрицами и векторами. Рассмотрим сначала простые операции сложения и умножения матриц и векторов. Пусть даны два вектора
a = ; %
вектор-строка
b = ; %
вектор-столбец
тогда умножение этих двух векторов можно записать так
c = a*b; % c=1+2+3+4+5=16
d = b*a; % d – матрица 5х5 элементов
В соответствии с операциями над векторами, умножение вектор-строки на вектор-столбец дает число, а умножение вектор-столбца на вектор-строку дает двумерную матрицу, что и является результатом вычислений в приведенном примере, т.е.
Сложение и вычитание двух векторов записывается так
a1 = ;
a2 = ;
c = a1+a2; % c
= ;
с = a2-a1; % c = ;
Следует обратить внимание, что операции сложения и вычитания можно выполнять между двумя векторами-столбцами или двумя векторами-строками. Иначе MatLab выдаст сообщение об ошибке, т.к. разнотипные векторы складывать нельзя. Так обстоит дело со всеми недопустимыми арифметическими операциями: в случае невозможности их вычисления система MatLab сообщит об ошибке и выполнение программы будет завершено на соответствующей строке.
Аналогичным образом выполняются операции умножения и сложения между матрицами:
A = ;
B = ones(3);
C = A+B; % сложение двух
матриц одинакового размера
D = A+5; % сложение
матрицы и числа
E = A*B; % умножение
матрицы А на В
F = B*A; % умножение
матрицы В на А
G = 5*A; % умножение
матрицы на число
Операции вычисления обратной матрицы, а также транспонирования матриц и векторов, записываются следующим образом:
a = ; %
вектор-строка
b = a’; %
вектор-столбец, образованный
%
транспонированием вектора-строки а.
A = ; %
матрица 3х3 элемента
B = a*A; % B = – вектор-строка
C = A*b; % C = –
вектор-столбец
D = a*A*a’; % D = 45 – число, сумма эл-ов
матрицы А
E = A’; % E – транспонированная матрица
А
F = inv(A); % F – обратная матрица А
G = A^-1; % G – обратная матрица А
Из приведенного примера видно, что операция транспонирования матриц и векторов обозначается символом ‘ (апостроф), который ставится после имени вектора или матрицы. Вычисление обратной матрицы можно делать путем вызова функции inv() или возводя матрицу в степень -1. Результат в обоих случаях будет одинаковым, а два способа вычисления сделано для удобства использования при реализации различных алгоритмов.
Если в процессе вычислений требуется поэлементно умножить, разделить или возвести в степень элементы вектора или матрицы, то для этого используются операторы:
.* - поэлементное умножение;
./ и.\ - поэлементные деления;
.^ - поэлементное возведение в степень.
Рассмотрим работу данных операторов на следующем примере.
a = ; %
вектор-строка
b = ; % вектор-строка
c = a.*b; % c =
A = ones(3); % матрица 3х3,
состоящая из единиц
B = ; %
матрица 3х3
C = A.*B; % матрица 3х3,
состоящая из 
D = A./B; % матрица 3х3,
состоящая из 
E = A.\B; % матрица 3х3,
состоящая из 
F = A.^2; % возведение
элементов матрицы А в квадрат
В заключении данного параграфа рассмотрим несколько функций полезных при работе с векторами и матрицами.
Для поиска максимального значения элемента вектора используется стандартная функция max(), которая возвращает найденное максимальное значение элемента и его позицию (индекс):
a = ;
= max(a); %
v = 6, i = 2;
v = max(a); % v = 6;
Приведенный пример показывает два разных способа вызова функции max(). В первом случае определяется и максимальное значение элемента и его индекс в векторе, а во втором – только максимальное значение элемента.
В случае с матрицами, данная функция определяет максимальные значения, стоящие в столбцах, как показано ниже в примере:
A = ;
= max(A); %
V=, I =
V = max(A); %
V=
Полный синтаксис функции max() можно узнать, набрав в командном окне MatLab команду
help <название функции>
Аналогичным образом работает функция min(), которая определяет минимальное значение элемента вектора или матрицы и его индекс.
Другой полезной функцией работы с матрицами и векторами является функция sum(), которая вычисляет сумму значений элементов вектора или столбцов матрицы:
a = ;
s = sum(a); %
s = 3+5+4+2+1=15
A = ;
S1 = sum(A); %
S1=
S2 = sum(sum(A)); % S2=39
При вычислении суммы S2 сначала вычисляется сумма значений элементов матрицы А по столбцам, а затем, по строкам. В результате, переменная S2 содержит сумму значений всех элементов матрицы А.
Для сортировки значений элементов вектора или матрицы по возрастанию или убыванию используется функция sort() следующим образом:
a = ;
b1 = sort(a); %
b1=
b2 = sort(a, ‘descend’); %
b2=
b3 = sort(a, ‘ascend’); %
b3=
для матриц
A = ;
B1 = sort(A); %
B1=
B2 = sort(A, ‘descend’); %
B2=
Во многих практических задачах часто требуется найти определенный элемент в векторе или матрице. Это можно выполнить с помощью стандартной функции find(), которая в качестве аргумента принимает условие, в соответствии с которым и находятся требуемые элементы, например:
a = ;
b1 = find(a == 2); %
b1 = 4 – индекс элемента 2
b2 = find(a ~= 2); %
b2 = – индексы без 2
b3 = find(a > 3); % b3 =
В приведенном примере символ ‘==’ означает проверку на равенство, а символ ‘~=’ выполняет проверку на неравенство значений элементов вектора а. Более подробно об этих операторах будет описано в разделе условные операторы.
Еще одной полезной функцией работы с векторами и матрицами является функция mean() для вычисления среднего арифметического значения, которая работает следующим образом:
a = ;
m = mean(a); %
m = 3
A = ;
M1 = mean(A); %
M1 =
M2 = mean(mean(A)); %
M2 = 4.333
Лекция 6. Параллельные численные алгоритмы для решения типовых задач вычислительной математики: умножение матриц.
Умножение матрицы на вектор. Достижение максимально возможного быстродействия. Использование параллелизма среднего уровня. Организация параллельных вычислений при p = n. Использование ограниченного набора процессоров. Матричное умножение. Макрооперационный анализ алгоритмов решения задач. Организация параллелизма на основе разделения данных.
Умножение матрицы на вектор
Задача умножения матрицы на вектор определяется соотношениями
Тем самым, получение результирующего вектора предполагает повторения однотипных операций по умножению строк матрицы и вектора . Получение каждой такой операции включает поэлементное умножение элементов строки матрицы и вектора и последующее суммирование полученных произведений. Общее количество необходимых скалярных операций оценивается величиной
Как следует из выполняемых действий при умножении матрицы и вектора, параллельные способы решения задачи могут быть получены на основе параллельных алгоритмов суммирования (см. параграф 4.1). В данном разделе анализ способов распараллеливания будет дополнен рассмотрением вопросов организации параллельных вычислений в зависимости от количества доступных для использования процессоров. Кроме того, на примере задачи умножения матрицы на вектор будут обращено внимание на необходимость выбора наиболее подходящей топологии вычислительной системы (существующих коммуникационных каналов между процессорами) для снижения затрат для организации межпроцессорного взаимодействия.
Достижение максимально возможного быстродействия ()
Выполним анализ информационных зависимостей в алгоритме умножения матрицы на вектор для выбора возможных способов распараллеливания. Как можно заметить, выполняемые при проведении вычислений операции умножения отдельных строк матрицы на вектор являются независимыми и могут быть выполнены параллельно;
Умножение каждой строки на вектор включает независимые операции поэлементного умножения и тоже могут быть выполнены параллельно;
Суммирование получаемых произведений в каждой операции умножения строки матрицы на вектор могут быть выполнены по одному из ранее рассмотренных вариантов алгоритма суммирования (последовательный алгоритм, обычная и модифицированная каскадные схемы).
Таким образом, максимально необходимое количество процессоров определяется величиной
Использование такого количества процессоров может быть представлено следующим образом. Множество процессоров разбивается на групп
,
каждая из которых представляет набор процессоров для выполнения операции умножения отдельной строки матрицы на вектор. В начале вычислений на каждый процессор группы пересылаются элемент строки матрицы и соответствующий элемент вектора . Далее каждый процессор выполняет операцию умножения. Последующие затем вычисления выполняются по каскадной схеме суммирования. Для иллюстрации на рис. 6.1 приведена вычислительная схема для процессоров группы при размерности матрицы .
Рис. 6.1. Вычислительная схема операции умножения строки матрицы на вектор
Время выполнения параллельного алгоритма при использовании процессоров определяется временем выполнения параллельной операции умножения и временем выполнения каскадной схемы
Как результат, показатели эффективности алгоритма определяются следующими соотношениями:
Для рассматриваемой задачи умножения матрицы на вектор наиболее подходящими топологиями являются структуры, в которых обеспечивается быстрая передача данных (пути единичной длины) в каскадной схеме суммирования (см. рис. 4.5). Таковыми топологиями являются структура с полной системой связей (полный граф ) и гиперкуб . Другие топологии приводят к возрастанию коммуникационного времени из-за удлинения маршрутов передачи данных. Так, при линейном упорядочивании процессоров с системой связей только с ближайшими соседями слева и справа (линейка или кольцо ) для каскадной схемы длина пути передачи каждой получаемой частичной суммы на итерации , , является равной . Если принять, что передача данных по маршруту длины в топологиях с линейной структурой требует выполнения операций передачи данных, общее количество параллельных операций (суммарной длительности путей) передачи данных определяется величиной
(без учета передач данных для начальной загрузки процессоров).
Применение вычислительной системы с топологией в виде прямоугольной двумерной решетки размера приводит к простой и наглядной интерпретации выполняемых вычислений (структура сети соответствует структуре обрабатываемых данных). Для такой топологии строки матрицы наиболее целесообразно разместить по горизонталям решетки; в этом случае элементы вектора должны быть разосланы по вертикалям вычислительной системы. Выполнение вычислений при таком размещении данных может осуществляться параллельно по строкам решетки; как результат, общее количество передач данных совпадает с результатами для линейки ().
Коммуникационные действия, выполняемые при решении поставленной задачи, состоят в передаче данных между парами процессоров МВС. Подробный анализ длительности реализации таких операций проведен в п. 3.3.
4. Рекомендации по реализации параллельного алгоритма . При реализации параллельного алгоритма целесообразно выделить начальный этап по загрузке используемых процессоров исходными данными. Наиболее просто такая инициализация обеспечивается при топологии вычислительной системы с топологией в виде полного графа (загрузка обеспечивается при помощи одной параллельной операции пересылки данных). При организации множества процессоров в виде гиперкуба может оказаться полезной двухуровневое управление процессом начальной загрузки, при которой центральный управляющий процессор обеспечивает рассылку строк матрицы и вектора к управляющим процессорам процессорных групп , , которые, в свою очередь, рассылают элементы строк матрицы и вектора по исполнительным процессорам. Для топологий в виде линейки или кольца требуется последовательных операций передачи данных с последовательно убывающим объемом пересылаемых данных от до элементов.
Использование параллелизма среднего уровня ()
1. Выбор параллельного способа вычислений . При уменьшении доступного количества используемых процессоров () обычная каскадная схема суммирования при выполнении операций умножения строк матрицы на вектор становится не применимой. Для простоты изложения материала положим и воспользуется модифицированной каскадной схемой. Начальная нагрузка каждого процессора в этом случае увеличивается и процессор загружается () частями строк матрицы и вектора . Время выполнения операции умножения матрицы на вектор может быть оценено как величина
При использовании количества процессоров, необходимого для реализации модифицированной каскадной схемы, т.е. при 
, данное выражение дает оценку времени исполнения 
(при ).
При количестве процессоров , когда время выполнения алгоритма оценивается как , может быть предложена новая схема параллельного выполнения вычислений, при которой для каждой итерации каскадного суммирования используются неперекрывающиеся наборы процессоров . При таком походе имеющегося количества процессоров оказывается достаточным для реализации только одной операции умножения строки матрицы и вектора . Кроме того, при выполнении очередной итерации каскадного суммирования процессоры, ответственные за исполнение всех предшествующих итераций, являются свободными. Однако этот недостаток предлагаемого подхода можно обратить в достоинство, задействовав простаивающие процессоры для обработки следующих строк матрицы . В результате может быть сформирована следующая схема конвейерного выполнения умножения матрицы и вектора:
Множество процессоров разбивается на непересекающиеся процессорные группы
,
при этом группа , , состоит из процессоров и используется для выполнения итерации каскадного алгоритма (группа применяется для реализации поэлементного умножения); общее количество процессоров ;
Инициализация вычислений состоит в поэлементной загрузке процессоров группы значениями 1 строки матрицы и вектора ; после начальной загрузки выполняется параллельная операция поэлементного умножения и последующей реализации обычной каскадной схемы суммирования;
При выполнении вычислений каждый раз после завершения операции поэлементного умножения осуществляется загрузка процессоров группы элементами очередной строки матрицы и инициируется процесс вычислений для вновь загруженных данных.
В результате применения описанного алгоритма множество процессоров реализует конвейер для выполнения операции умножения строки матрицы на вектор. На подобном конвейере одновременно могут находиться несколько отдельных строк матрицы на разных стадиях обработки. Так, например, после поэлементного умножения элементов первой строки и вектора процессоры группы будут выполнять первую итерацию каскадного алгоритма для первой строки матрицы, а процессоры группы будут исполнять поэлементное умножение значений второй строки матрицы и т.д. Для иллюстрации на рис. 6.2 приведена ситуация процесса вычислений после 2 итераций конвейера при .
Рис. 6.2. Состояние конвейера для операции умножения строки матрицы на вектор после выполнения 2 итераций
2. Оценка показателей эффективности алгоритма . Умножение первой строки на вектор в соответствии с каскадной схемой будет завершено, как и обычно, после выполнения () параллельных операций. Для других же строк – в соответствии с конвейерной схемой организации вычислений - появление результатов умножения каждой очередной строки будет происходить после завершения каждой последующей итерации конвейера. Как результат, общее время выполнения операции умножения матрицы на вектор может быть выражено величиной
Данная оценка является несколько большей, чем время выполнения параллельного алгоритма, описанного в предыдущем пункте (), однако вновь предлагаемый способ требует меньшего количества передаваемых данных (вектор пересылается только однократно). Кроме того, использование конвейерной схемы приводит к более раннему появлению части результатов вычислений (что может быть полезным в ряде ситуаций обработки данных).
Как результат, показатели эффективности алгоритма определяются соотношениями следующего вида:
3. Выбор топологии вычислительной системы . Целесообразная топология вычислительной системы полностью определяется вычислительной схемой – это полное бинарное дерево высотой . Количество передач данных при такой топологии сети определяется общим количеством итераций, выполняемых конвейером, т.е.
Инициализация вычислений начинается с листьев дерева, результаты суммирования накапливаются в корневом процессоре.
Анализ трудоемкости выполняемых коммуникационных действий для вычислительных систем с другими топологиями межпроцессорных связей предполагается осуществить в качестве самостоятельного задания (см. также п. 3.4).
Организация параллельных вычислений при
1. Выбор параллельного способа вычислений . При использовании процессоров для умножения матрицы на вектор может быть использован ранее уже рассмотренный в пособии параллельный алгоритм построчного умножения, при котором строки матрицы распределяются по процессорам построчно и каждый процессор реализует операцию умножения какой-либо отдельной строки матрицы на вектор . Другой возможный способ организации параллельных вычислений может состоять в построении конвейерной схемы для операции умножения строки матрицы на вектор (скалярного произведения векторов ) путем расположения всех имеющихся процессоров в виде линейной последовательности (линейки ).
Подобная схема вычислений может быть определена следующим образом. Представим множество процессоров в виде линейной последовательности (см. рис. 4.7):
каждый процессор , , используется для умножения элементов столбца матрицы и элемента вектора . Выполнение вычислений на каждом процессоре , , состоит в следующем:
Запрашивается очередной элемент столбца матрицы;
Выполняется умножение элементов и ;
Запрашивается результат вычислений предшествующего процессора;
Выполняется сложение значений ;
Полученный результат пересылается следующему процессору.
Рис. 6.3. Состояние линейного конвейера для операции умножения строки матрицы на вектор после выполнения двух итераций
При инициализации описанной схемы необходимо выполнить ряд дополнительных действий:
При выполнении первой итерации каждый процессор дополнительно запрашивает элемент вектора ;
Для синхронизации вычислений (при выполнении очередной итерации схемы запрашивается результат вычисления предшествующего процессора) на этапе инициализации процессор , , выполняет () цикл ожидания.
Кроме того, для однородности описанной схемы для первого процессора , у которого нет предшествующего процессора, целесообразно ввести пустую операцию сложения (
).
Для иллюстрации на рис. 6.3 показано состояние процесса вычислений после второй итерации конвейера при .
2. Оценка показателей эффективности алгоритма . Умножение первой строки на вектор в соответствии с описанной конвейерной схемой будет завершено после выполнения () параллельных операций. Результат умножения следующих строк будет происходить после завершения каждой очередной итерации конвейера (напомним, итерация каждого процессора включает выполнение операций умножения и сложения). Как результат, общее время выполнения операции умножения матрицы на вектор может быть выражено соотношением:
Данная оценка также является большей, чем минимально возможное время выполнения параллельного алгоритма при . Полезность использования конвейерной вычислительной схемы состоит, как отмечалось в предыдущем пункте, в уменьшении количества передаваемых данных и в более раннем появлении части результатов вычислений.
Показатели эффективности данной вычислительной схемы определяются соотношениями:
, 
,
3. Выбор топологии вычислительной системы . Необходимая топология вычислительной системы для выполнения описанного алгоритма однозначно определяется предлагаемой вычислительной схемой – это линейно упорядоченное множество процессоров (линейка ).
Использование ограниченного набора процессоров ()
1. Выбор параллельного способа вычислений . При уменьшении количества процессоров до величины параллельная вычислительная схема умножения матрицы на вектор может быть получена в результате адаптации алгоритма построчного умножения. В этом случае каскадная схема суммирования результатов поэлементного умножения вырождается и операция умножения строки матрицы на вектор полностью выполняется на единственном процессоре. Получаемая при таком подходе вычислительная схема может быть конкретизирована следующим образом:
На каждый из имеющихся процессоров пересылается вектор и строк матрицы;
Выполнение операции умножения строк матрица на вектор выполняется при помощи обычного последовательного алгоритма.
Следует отметить, что размер матрицы может оказаться не кратным количеству процессоров и тогда строки матрицы не могут быть разделены поровну между процессорами. В этих ситуациях можно отступить от требования равномерности загрузки процессоров и для получения более простой вычислительной схемы принять правило, что размещение данных на процессорах осуществляется только построчно (т.е. элементы одной строки матрицы не могут быть разделены между несколькими процессорами). Неодинаковое количество строк приводит к разной вычислительной нагрузке процессоров; тем самым, завершение вычислений (общая длительность решения задачи) будет определяться временем работы наиболее загруженного процессора (при этом часть от этого общего времени отдельные процессоры могут простаивать из-за исчерпания своей доли вычислений). Неравномерность загрузки процессоров снижает эффективность использования МВС и, как результат рассмотрения данного примера можно заключить, что проблема балансировки
3. Выбор топологии вычислительной системы . В соответствии с характером выполняемых межпроцессорных взаимодействий в предложенной вычислительной схеме в качестве возможной топологии МВС может служить организация процессоров в виде звезды (см. рис. 1.1). Управляющий процессор подобной топологии может использоваться для загрузки вычислительных процессоров исходными данными и для приема результатов выполненных вычислений.
Матричное умножение
Задача умножения матрицы на матрицу определяется соотношениями
.
(для простоты изложения материала будем предполагать, что перемножаемые матрицы и являются квадратными и имеют порядок ).
Анализ возможных способов параллельного выполнения данной задачи может быть проведен по аналогии с рассмотрением задачи умножения матрицы на вектор. Оставив подобный анализ для самостоятельного изучения, покажем на примере задачи матричного умножения использование нескольких общих подходов, позволяющих формировать параллельные способы решения сложных задач.
Итак, в предыдущем уроке мы разобрали правила сложения и вычитания матриц. Это настолько простые операции, что большинство студентов понимают их буквально с ходу.
Однако вы рано радуетесь. Халява закончилась — переходим к умножению. Сразу предупрежу: умножить две матрицы — это вовсе не перемножить числа, стоящие в клеточках с одинаковыми координатами, как бы вы могли подумать. Тут всё намного веселее. И начать придётся с предварительных определений.
Согласованные матрицы
Одна из важнейших характеристик матрицы — это её размер. Мы уже сто раз говорили об этом: запись $A=\left[ m\times n \right]$ означает, что в матрице ровно $m$ строк и $n$ столбцов. Как не путать строки со столбцами, мы тоже уже обсуждали. Сейчас важно другое.
Определение. Матрицы вида $A=\left[ m\times n \right]$ и $B=\left[ n\times k \right]$, в которых количество столбцов в первой матрице совпадает с количеством строк во второй, называются согласованными.
Ещё раз: количество столбцов в первой матрице равно количеству строк во второй! Отсюда получаем сразу два вывода:
- Нам важен порядок матриц. Например, матрицы $A=\left[ 3\times 2 \right]$ и $B=\left[ 2\times 5 \right]$ являются согласованными (2 столбца в первой матрице и 2 строки во второй), а вот наоборот — матрицы $B=\left[ 2\times 5 \right]$ и $A=\left[ 3\times 2 \right]$ — уже не согласованы (5 столбцов в первой матрице — это как бы не 3 строки во второй).
- Согласованность легко проверить, если выписать все размеры друг за другом. На примере из предыдущего пункта: «3 2 2 5» — посередине одинаковые числа, поэтому матрицы согласованы. А вот «2 5 3 2» — не согласованы, поскольку посередине разные числа.
Кроме того, капитан очевидность как бы намекает, что квадратные матрицы одинакового размера $\left[ n\times n \right]$ согласованы всегда.
В математике, когда важен порядок перечисления объектов (например, в рассмотренном выше определении важен порядок матриц), часто говорят об упорядоченных парах. Мы встречались с ними ещё в школе: думаю, и ежу понятно, что координаты $\left(1;0 \right)$ и $\left(0;1 \right)$ задают разные точки на плоскости.
Так вот: координаты — это тоже упорядоченные пары, которые составляются из чисел. Но ничто не мешает составить такую пару из матриц. Тогда можно будет сказать: «Упорядоченная пара матриц $\left(A;B \right)$ является согласованной, если количество столбцов в первой матрице совпадает с количеством строк во второй».
Ну и что с того?
Определение умножения
Рассмотрим две согласованные матрицы: $A=\left[ m\times n \right]$ и $B=\left[ n\times k \right]$. И определим для них операцию умножения.
Определение. Произведение двух согласованных матриц $A=\left[ m\times n \right]$ и $B=\left[ n\times k \right]$ — это новая матрица $C=\left[ m\times k \right]$, элементы которой считаются по формуле:
\[\begin{align} & {{c}_{i;j}}={{a}_{i;1}}\cdot {{b}_{1;j}}+{{a}_{i;2}}\cdot {{b}_{2;j}}+\ldots +{{a}_{i;n}}\cdot {{b}_{n;j}}= \\ & =\sum\limits_{t=1}^{n}{{{a}_{i;t}}\cdot {{b}_{t;j}}} \end{align}\]
Обозначается такое произведение стандартно: $C=A\cdot B$.
У тех, кто впервые видит это определение, сразу возникает два вопроса:
- Что это за лютая дичь?
- А почему так сложно?
Что ж, обо всём по порядку. Начнём с первого вопроса. Что означают все эти индексы? И как не ошибиться при работе с реальными матрицами?
Прежде всего заметим, что длинная строчка для расчёта ${{c}_{i;j}}$ (специально поставил точку с запятой между индексами, чтобы не запутаться, но вообще их ставить не надо — я сам задолбался набирать формулу в определении) на самом деле сводится к простому правилу:
- Берём $i$-ю строку в первой матрице;
- Берём $j$-й столбец во второй матрице;
- Получаем две последовательности чисел. Перемножаем элементы этих последовательностей с одинаковыми номерами, а затем складываем полученные произведения.
Данный процесс легко понять по картинке:
Схема перемножения двух матрицЕщё раз: фиксируем строку $i$ в первой матрице, столбец $j$ во второй матрице, перемножаем элементы с одинаковыми номерами, а затем полученные произведения складываем — получаем ${{c}_{ij}}$. И так для всех $1\le i\le m$ и $1\le j\le k$. Т.е. всего будет $m\times k$ таких «извращений».
На самом деле мы уже встречались с перемножением матриц в школьной программе, только в сильно урезанном виде. Пусть даны вектора:
\[\begin{align} & \vec{a}=\left({{x}_{a}};{{y}_{a}};{{z}_{a}} \right); \\ & \overrightarrow{b}=\left({{x}_{b}};{{y}_{b}};{{z}_{b}} \right). \\ \end{align}\]
Тогда их скалярным произведением будет именно сумма попарных произведений:
\[\overrightarrow{a}\times \overrightarrow{b}={{x}_{a}}\cdot {{x}_{b}}+{{y}_{a}}\cdot {{y}_{b}}+{{z}_{a}}\cdot {{z}_{b}}\]
По сути, в те далёкие годы, когда деревья были зеленее, а небо ярче, мы просто умножали вектор-строку $\overrightarrow{a}$ на вектор-столбец $\overrightarrow{b}$.
Сегодня ничего не поменялось. Просто теперь этих векторов-строк и столбцов стало больше.
Но хватит теории! Давайте посмотрим на реальные примеры. И начнём с самого простого случая — квадратных матриц.
Умножение квадратных матриц
Задача 1. Выполните умножение:
\[\left[ \begin{array}{*{35}{r}} 1 & 2 \\ -3 & 4 \\\end{array} \right]\cdot \left[ \begin{array}{*{35}{r}} -2 & 4 \\ 3 & 1 \\\end{array} \right]\]
Решение. Итак, у нас две матрицы: $A=\left[ 2\times 2 \right]$ и $B=\left[ 2\times 2 \right]$. Понятно, что они согласованы (квадратные матрицы одинакового размера всегда согласованы). Поэтому выполняем умножение:
\[\begin{align} & \left[ \begin{array}{*{35}{r}} 1 & 2 \\ -3 & 4 \\\end{array} \right]\cdot \left[ \begin{array}{*{35}{r}} -2 & 4 \\ 3 & 1 \\\end{array} \right]=\left[ \begin{array}{*{35}{r}} 1\cdot \left(-2 \right)+2\cdot 3 & 1\cdot 4+2\cdot 1 \\ -3\cdot \left(-2 \right)+4\cdot 3 & -3\cdot 4+4\cdot 1 \\\end{array} \right]= \\ & =\left[ \begin{array}{*{35}{r}} 4 & 6 \\ 18 & -8 \\\end{array} \right]. \end{align}\]
Вот и всё!
Ответ: $\left[ \begin{array}{*{35}{r}}4 & 6 \\ 18 & -8 \\\end{array} \right]$.
Задача 2. Выполните умножение:
\[\left[ \begin{matrix} 1 & 3 \\ 2 & 6 \\\end{matrix} \right]\cdot \left[ \begin{array}{*{35}{r}}9 & 6 \\ -3 & -2 \\\end{array} \right]\]
Решение. Опять согласованные матрицы, поэтому выполняем действия:\[\]
\[\begin{align} & \left[ \begin{matrix} 1 & 3 \\ 2 & 6 \\\end{matrix} \right]\cdot \left[ \begin{array}{*{35}{r}} 9 & 6 \\ -3 & -2 \\\end{array} \right]=\left[ \begin{array}{*{35}{r}} 1\cdot 9+3\cdot \left(-3 \right) & 1\cdot 6+3\cdot \left(-2 \right) \\ 2\cdot 9+6\cdot \left(-3 \right) & 2\cdot 6+6\cdot \left(-2 \right) \\\end{array} \right]= \\ & =\left[ \begin{matrix} 0 & 0 \\ 0 & 0 \\\end{matrix} \right]. \end{align}\]
Как видим, получилась матрица, заполненная нулями
Ответ: $\left[ \begin{matrix} 0 & 0 \\ 0 & 0 \\\end{matrix} \right]$.
Из приведённых примеров очевидно, что умножение матриц — не такая уж и сложная операция. По крайней мере для квадратных матриц размера 2 на 2.
В процессе вычислений мы составили промежуточную матрицу, где прямо расписали, какие числа входят в ту или иную ячейку. Именно так и следует делать при решении настоящих задач.
Основные свойства матричного произведения
В двух словах. Умножение матриц:
- Некоммутативно: $A\cdot B\ne B\cdot A$ в общем случае. Бывают, конечно, особые матрицы, для которых равенство $A\cdot B=B\cdot A$ (например, если $B=E$ — единичной матрице), но в абсолютном большинстве случаев это не работает;
- Ассоциативно: $\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)$. Тут без вариантов: стоящие рядом матрицы можно перемножать, не переживая за то, что стоит левее и правее этих двух матриц.
- Дистрибутивно: $A\cdot \left(B+C \right)=A\cdot B+A\cdot C$ и $\left(A+B \right)\cdot C=A\cdot C+B\cdot C$ (в силу некоммутативности произведения приходится отдельно прописывать дистрибутивность справа и слева.
А теперь — всё то же самое, но более подробно.
Умножение матриц во многом напоминает классическое умножение чисел. Но есть отличия, важнейшее из которых состоит в том, что умножение матриц, вообще говоря, некоммутативно .
Рассмотрим ещё раз матрицы из задачи 1. Прямое их произведение мы уже знаем:
\[\left[ \begin{array}{*{35}{r}} 1 & 2 \\ -3 & 4 \\\end{array} \right]\cdot \left[ \begin{array}{*{35}{r}} -2 & 4 \\ 3 & 1 \\\end{array} \right]=\left[ \begin{array}{*{35}{r}}4 & 6 \\ 18 & -8 \\\end{array} \right]\]
Но если поменять матрицы местами, то получим совсем другой результат:
\[\left[ \begin{array}{*{35}{r}} -2 & 4 \\ 3 & 1 \\\end{array} \right]\cdot \left[ \begin{array}{*{35}{r}} 1 & 2 \\ -3 & 4 \\\end{array} \right]=\left[ \begin{matrix} -14 & 4 \\ 0 & 10 \\\end{matrix} \right]\]
Получается, что $A\cdot B\ne B\cdot A$. Кроме того, операция умножения определена только для согласованных матриц $A=\left[ m\times n \right]$ и $B=\left[ n\times k \right]$, но никто не гарантировал, что они останутся согласованными, если их поменять местами. Например, матрицы $\left[ 2\times 3 \right]$ и $\left[ 3\times 5 \right]$ вполне себе согласованы в указанном порядке, но те же матрицы $\left[ 3\times 5 \right]$ и $\left[ 2\times 3 \right]$, записанные в обратном порядке, уже не согласованы. Печаль.:(
Среди квадратных матриц заданного размера $n$ всегда найдутся такие, которые дают одинаковый результат как при перемножении в прямом, так и в обратном порядке. Как описать все подобные матрицы (и сколько их вообще) — тема для отдельного урока. Сегодня не будем об этом.:)
Тем не менее, умножение матриц ассоциативно:
\[\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)\]
Следовательно, когда вам надо перемножить сразу несколько матриц подряд, совсем необязательно делать это напролом: вполне возможно, что некоторые рядом стоящие матрицы при перемножении дают интересный результат. Например, нулевую матрицу, как в Задаче 2, рассмотренной выше.
В реальных задачах чаще всего приходится перемножать квадратные матрицы размера $\left[ n\times n \right]$. Множество всех таких матриц обозначается ${{M}^{n}}$ (т.е. записи $A=\left[ n\times n \right]$ и \ означают одно и то же), и в нём обязательно найдётся матрица $E$, которую называют единичной.
Определение. Единичная матрица размера $n$ — это такая матрица $E$, что для любой квадратной матрицы $A=\left[ n\times n \right]$ выполняется равенство:
Такая матрица всегда выглядит одинаково: на главной диагонали её стоят единицы, а во всех остальных клетках — нули.
\[\begin{align} & A\cdot \left(B+C \right)=A\cdot B+A\cdot C; \\ & \left(A+B \right)\cdot C=A\cdot C+B\cdot C. \\ \end{align}\]
Другими словами, если нужно умножить одну матрицу на сумму двух других, то можно умножить её на каждую из этих «двух других», а затем результаты сложить. На практике обычно приходится выполнять обратную операцию: замечаем одинаковую матрицу, выносим её за скобку, выполняем сложение и тем самым упрощаем себе жизнь.:)
Заметьте: для описания дистрибутивности нам пришлось прописать две формулы: где сумма стоит во втором множителе и где сумма стоит в первом. Это происходит как раз из-за того, что умножение матриц некоммутативно (и вообще, в некоммутативной алгебре куча всяких приколов, которые при работе с обычными числами даже не приходят в голову). И если, допустим, вам на экзамене нужно будет расписать это свойство, то обязательно пишите обе формулы, иначе препод может немного разозлиться.
Ладно, всё это были сказки о квадратных матрицах. А что насчёт прямоугольных?
Случай прямоугольных матриц
А ничего — всё то же самое, что и с квадратными.
Задача 3. Выполните умножение:
\[\left[ \begin{matrix} \begin{matrix} 5 \\ 2 \\ 3 \\\end{matrix} & \begin{matrix} 4 \\ 5 \\ 1 \\\end{matrix} \\\end{matrix} \right]\cdot \left[ \begin{array}{*{35}{r}} -2 & 5 \\ 3 & 4 \\\end{array} \right]\]
Решение. Имеем две матрицы: $A=\left[ 3\times 2 \right]$ и $B=\left[ 2\times 2 \right]$. Выпишем числа, обозначающие размеры, в ряд:
Как видим, центральные два числа совпадают. Значит, матрицы согласованы, и их можно перемножить. Причём на выходе мы получим матрицу $C=\left[ 3\times 2 \right]$:
\[\begin{align} & \left[ \begin{matrix} \begin{matrix} 5 \\ 2 \\ 3 \\\end{matrix} & \begin{matrix} 4 \\ 5 \\ 1 \\\end{matrix} \\\end{matrix} \right]\cdot \left[ \begin{array}{*{35}{r}} -2 & 5 \\ 3 & 4 \\\end{array} \right]=\left[ \begin{array}{*{35}{r}} 5\cdot \left(-2 \right)+4\cdot 3 & 5\cdot 5+4\cdot 4 \\ 2\cdot \left(-2 \right)+5\cdot 3 & 2\cdot 5+5\cdot 4 \\ 3\cdot \left(-2 \right)+1\cdot 3 & 3\cdot 5+1\cdot 4 \\\end{array} \right]= \\ & =\left[ \begin{array}{*{35}{r}} 2 & 41 \\ 11 & 30 \\ -3 & 19 \\\end{array} \right]. \end{align}\]
Всё чётко: в итоговой матрице 3 строки и 2 столбца. Вполне себе $=\left[ 3\times 2 \right]$.
Ответ: $\left[ \begin{array}{*{35}{r}} \begin{array}{*{35}{r}} 2 \\ 11 \\ -3 \\\end{array} & \begin{matrix} 41 \\ 30 \\ 19 \\\end{matrix} \\\end{array} \right]$.
Сейчас рассмотрим одно из лучших тренировочных заданий для тех, кто только начинает работать с матрицами. В нём нужно не просто перемножить какие-то две таблички, а сначала определить: допустимо ли такое умножение?
Задача 4. Найдите все возможные попарные произведения матриц:
\\]; $B=\left[ \begin{matrix} \begin{matrix} 0 \\ 2 \\ 0 \\ 4 \\\end{matrix} & \begin{matrix} 1 \\ 0 \\ 3 \\ 0 \\\end{matrix} \\\end{matrix} \right]$; $C=\left[ \begin{matrix}0 & 1 \\ 1 & 0 \\\end{matrix} \right]$.
Решение. Для начала запишем размеры матриц:
\;\ B=\left[ 4\times 2 \right];\ C=\left[ 2\times 2 \right]\]
Получаем, что матрицу $A$ можно согласовать лишь с матрицей $B$, поскольку количество столбцов у $A$ равно 4, а такое количество строк только у $B$. Следовательно, можем найти произведение:
\\cdot \left[ \begin{array}{*{35}{r}} 0 & 1 \\ 2 & 0 \\ 0 & 3 \\ 4 & 0 \\\end{array} \right]=\left[ \begin{array}{*{35}{r}}-10 & 7 \\ 10 & 7 \\\end{array} \right]\]
Промежуточные шаги предлагаю выполнить читателю самостоятельно. Замечу лишь, что размер результирующей матрицы лучше определять заранее, ещё до каких-либо вычислений:
\\cdot \left[ 4\times 2 \right]=\left[ 2\times 2 \right]\]
Другими словами, мы просто убираем «транзитные» коэффициенты, которые обеспечивали согласованность матриц.
Какие ещё возможны варианты? Безусловно, можно найти $B\cdot A$, поскольку $B=\left[ 4\times 2 \right]$, $A=\left[ 2\times 4 \right]$, поэтому упорядоченная пара $\left(B;A \right)$ является согласованной, а размерность произведения будет:
\\cdot \left[ 2\times 4 \right]=\left[ 4\times 4 \right]\]
Короче говоря, на выходе будет матрица $\left[ 4\times 4 \right]$, коэффициенты которой легко считаются:
\\cdot \left[ \begin{array}{*{35}{r}} 1 & -1 & 2 & -2 \\ 1 & 1 & 2 & 2 \\\end{array} \right]=\left[ \begin{array}{*{35}{r}}1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end{array} \right]\]
Очевидно, можно согласовать ещё $C\cdot A$ и $B\cdot C$ — и всё. Поэтому просто запишем полученные произведения:
Это было легко.:)
Ответ: $AB=\left[ \begin{array}{*{35}{r}} -10 & 7 \\ 10 & 7 \\\end{array} \right]$; $BA=\left[ \begin{array}{*{35}{r}} 1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end{array} \right]$; $CA=\left[ \begin{array}{*{35}{r}} 1 & 1 & 2 & 2 \\ 1 & -1 & 2 & -2 \\\end{array} \right]$; $BC=\left[ \begin{array}{*{35}{r}}1 & 0 \\ 0 & 2 \\ 3 & 0 \\ 0 & 4 \\\end{array} \right]$.
Вообще, очень рекомендую выполнить это задание самостоятельно. И ещё одно аналогичное задание, которое есть в домашней работе. Эти простые на первый взгляд размышления помогут вам отработать все ключевые этапы умножения матриц.
Но на этом история не заканчивается. Переходим к частным случаям умножения.:)
Вектор-строки и вектор-столбцы
Одной из самых распространённых матричных операций является умножение на матрицу, в которой одна строка или один столбец.
Определение. Вектор-столбец — это матрица размера $\left[ m\times 1 \right]$, т.е. состоящая из нескольких строк и только одного столбца.
Вектор-строка — это матрица размера $\left[ 1\times n \right]$, т.е. состоящая из одной строки и нескольких столбцов.
На самом деле мы уже встречались с этими объектами. Например, обычный трёхмерный вектор из стереометрии $\overrightarrow{a}=\left(x;y;z \right)$ — это не что иное как вектор-строка. С точки зрения теории разницы между строками и столбцами почти нет. Внимательными надо быть разве что при согласовании с окружающими матрицами-множителями.
Задача 5. Выполните умножение:
\[\left[ \begin{array}{*{35}{r}} 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end{array} \right]\cdot \left[ \begin{array}{*{35}{r}} 1 \\ 2 \\ -1 \\\end{array} \right]\]
Решение. Перед нами произведение согласованных матриц: $\left[ 3\times 3 \right]\cdot \left[ 3\times 1 \right]=\left[ 3\times 1 \right]$. Найдём это произведение:
\[\left[ \begin{array}{*{35}{r}} 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end{array} \right]\cdot \left[ \begin{array}{*{35}{r}} 1 \\ 2 \\ -1 \\\end{array} \right]=\left[ \begin{array}{*{35}{r}} 2\cdot 1+\left(-1 \right)\cdot 2+3\cdot \left(-1 \right) \\ 4\cdot 1+2\cdot 2+0\cdot 2 \\ -1\cdot 1+1\cdot 2+1\cdot \left(-1 \right) \\\end{array} \right]=\left[ \begin{array}{*{35}{r}} -3 \\ 8 \\ 0 \\\end{array} \right]\]
Ответ: $\left[ \begin{array}{*{35}{r}}-3 \\ 8 \\ 0 \\\end{array} \right]$.
Задача 6. Выполните умножение:
\[\left[ \begin{array}{*{35}{r}} 1 & 2 & -3 \\\end{array} \right]\cdot \left[ \begin{array}{*{35}{r}} 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end{array} \right]\]
Решение. Опять всё согласовано: $\left[ 1\times 3 \right]\cdot \left[ 3\times 3 \right]=\left[ 1\times 3 \right]$. Считаем произведение:
\[\left[ \begin{array}{*{35}{r}} 1 & 2 & -3 \\\end{array} \right]\cdot \left[ \begin{array}{*{35}{r}} 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end{array} \right]=\left[ \begin{array}{*{35}{r}}5 & -19 & 5 \\\end{array} \right]\]
Ответ: $\left[ \begin{matrix} 5 & -19 & 5 \\\end{matrix} \right]$.
Как видите, при умножении вектор-строки и вектор-столбца на квадратную матрицу на выходе мы всегда получаем строку или столбец того же размера. Этот факт имеет множество приложений — от решения линейных уравнений до всевозможных преобразований координат (которые в итоге тоже сводятся к системам уравнений, но давайте не будем о грустном).
Думаю, здесь всё было очевидно. Переходим к заключительной части сегодняшнего урока.
Возведение матрицы в степень
Среди всех операций умножения отдельного внимания заслуживает возведение в степень — это когда мы несколько раз умножаем один и тот же объект на самого себя. Матрицы — не исключение, их тоже можно возводить в различные степени.
Такие произведения всегда согласованы:
\\cdot \left[ n\times n \right]=\left[ n\times n \right]\]
И обозначаются точно так же, как и обычные степени:
\[\begin{align} & A\cdot A={{A}^{2}}; \\ & A\cdot A\cdot A={{A}^{3}}; \\ & \underbrace{A\cdot A\cdot \ldots \cdot A}_{n}={{A}^{n}}. \\ \end{align}\]
На первый взгляд, всё просто. Посмотрим, как это выглядит на практике:
Задача 7. Возведите матрицу в указанную степень:
${{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{3}}$
Решение. Ну ОК, давайте возводить. Сначала возведём в квадрат:
\[\begin{align} & {{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{2}}=\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]\cdot \left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]= \\ & =\left[ \begin{array}{*{35}{r}} 1\cdot 1+1\cdot 0 & 1\cdot 1+1\cdot 1 \\ 0\cdot 1+1\cdot 0 & 0\cdot 1+1\cdot 1 \\\end{array} \right]= \\ & =\left[ \begin{array}{*{35}{r}} 1 & 2 \\ 0 & 1 \\\end{array} \right] \end{align}\]
\[\begin{align} & {{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{3}}={{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{3}}\cdot \left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]= \\ & =\left[ \begin{array}{*{35}{r}} 1 & 2 \\ 0 & 1 \\\end{array} \right]\cdot \left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]= \\ & =\left[ \begin{array}{*{35}{r}} 1 & 3 \\ 0 & 1 \\\end{array} \right] \end{align}\]
Вот и всё.:)
Ответ: $\left[ \begin{matrix}1 & 3 \\ 0 & 1 \\\end{matrix} \right]$.
Задача 8. Возведите матрицу в указанную степень:
\[{{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{10}}\]
Решение. Вот только не надо сейчас плакать по поводу того, что «степень слишком большая», «мир не справедлив» и «преподы совсем берега потеряли». На самом деле всё легко:
\[\begin{align} & {{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{10}}={{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{3}}\cdot {{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{3}}\cdot {{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{3}}\cdot \left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]= \\ & =\left(\left[ \begin{matrix} 1 & 3 \\ 0 & 1 \\\end{matrix} \right]\cdot \left[ \begin{matrix} 1 & 3 \\ 0 & 1 \\\end{matrix} \right] \right)\cdot \left(\left[ \begin{matrix} 1 & 3 \\ 0 & 1 \\\end{matrix} \right]\cdot \left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right] \right)= \\ & =\left[ \begin{matrix} 1 & 6 \\ 0 & 1 \\\end{matrix} \right]\cdot \left[ \begin{matrix} 1 & 4 \\ 0 & 1 \\\end{matrix} \right]= \\ & =\left[ \begin{matrix} 1 & 10 \\ 0 & 1 \\\end{matrix} \right] \end{align}\]
Заметьте: во второй строчке мы использовали ассоциативность умножения. Собственно, мы использовали её и в предыдущем задании, но там это было неявно.
Ответ: $\left[ \begin{matrix} 1 & 10 \\ 0 & 1 \\\end{matrix} \right]$.
Как видите, ничего сложного в возведении матрицы в степень нет. Последний пример можно обобщить:
\[{{\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \\\end{matrix} \right]}^{n}}=\left[ \begin{array}{*{35}{r}} 1 & n \\ 0 & 1 \\\end{array} \right]\]
Этот факт легко доказать через математическую индукцию или прямым перемножением. Однако далеко не всегда при возведении в степень можно выловить подобные закономерности. Поэтому будьте внимательны: зачастую перемножить несколько матриц «напролом» оказывается проще и быстрее, нежели искать какие-то там закономерности.
В общем, не ищите высший смысл там, где его нет. В заключение рассмотрим возведение в степень матрицы большего размера — аж $\left[ 3\times 3 \right]$.
Задача 9. Возведите матрицу в указанную степень:
\[{{\left[ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{matrix} \right]}^{3}}\]
Решение. Не будем искать закономерности. Работаем «напролом»:
\[{{\left[ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{matrix} \right]}^{3}}={{\left[ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{matrix} \right]}^{2}}\cdot \left[ \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{matrix} \right]\]
Для начала возведём эту матрицу в квадрат:
\[\begin{align} & {{\left[ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{matrix} \right]}^{2}}=\left[ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{matrix} \right]\cdot \left[ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{matrix} \right]= \\ & =\left[ \begin{array}{*{35}{r}} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end{array} \right] \end{align}\]
Теперь возведём в куб:
\[\begin{align} & {{\left[ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{matrix} \right]}^{3}}=\left[ \begin{array}{*{35}{r}} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end{array} \right]\cdot \left[ \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end{matrix} \right]= \\ & =\left[ \begin{array}{*{35}{r}} 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end{array} \right] \end{align}\]
Вот и всё. Задача решена.
Ответ: $\left[ \begin{matrix} 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end{matrix} \right]$.
Как видите, объём вычислений стал больше, но смысл от этого нисколько не поменялся.:)
На этом урок можно заканчивать. В следующий раз мы рассмотрим обратную операцию: по имеющемуся произведению будем искать исходные множители.
Как вы уже, наверное, догадались, речь пойдёт об обратной матрице и методах её нахождения.
