2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Перемножение матриц
Сообщение07.07.2016, 10:25 


02/07/16
16
Здравствуйте!
Почему перемножение матриц вычисляется по такой формуле, а никак иначе?
$c_{ij} = \sum_{r=1}^m a_{ir}b_{rj} $

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение07.07.2016, 10:30 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
любая матрица есть "матрица линейного отображения"
и умножение матриц таково, что матрица композиции отображений является произведением матриц отображений

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение07.07.2016, 18:46 
Заслуженный участник
Аватара пользователя


11/03/08
9904
Москва
Вообще-то есть разные способы ввести произведение матриц. Это, "строка на столбец", просто самое практически востребованное.

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение08.07.2016, 11:56 


02/07/16
16
Евгений Машеров в сообщении #1136374 писал(а):
Вообще-то есть разные способы ввести произведение матриц. Это, "строка на столбец", просто самое практически востребованное.

Можете, пожалуйста, рассказать подробнее. Не может же "строка на столбец" взяться с неба:)

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение08.07.2016, 13:27 
Заслуженный участник
Аватара пользователя


11/03/08
9904
Москва

(Оффтоп)

Командир древнегреческой фаланги решает сложную математическую задачу: k человек получают жалование по n оболов хлеба в день. Сколько всего надо? Ответ на этот вопрос - произведение k на n.
Однако военная наука усовершенствуется, в войске служат разные воины, конные и пешие, разного чина и т.п., а воинский паёк включает не один хлеб, а и мясо, и овощи, и вино, и деньгами "на соль" (saldarii), а конному ещё овёс и сено положено. И войско уже не монолитная фаланга, а разбито на отдельные подразделения.
Личный состав командир легиона записал в виде таблицы - сколько в каждом подразделении воинов каждого рода, а Сенат утвердил другую таблицу - сколько чего кому положено. А гражданский спец-интеллектуал при легионе, трибун латиклавариус, должен посчитать, что какому подразделению выдать. Как изучавший философию у лучших греческих философов, он догадывается, что умножать надо. Но уже не число на число, а таблицу на таблицу. Поэлементно умножил - непонятно что получил, попробовал для другого легиона - там вообще поэлементного умножения не получается, разные количества строк и столбцов в таблицах. Пока не догадался, что умножать надо число воинов определённой категории в подразделении на норму выдачи данного вида довольствия по этой категории, и все произведения по этому подразделению просуммировать. Тогда получится потребность этого подразделения в данном довольствии. Строка на столбец и просуммировать.

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение08.07.2016, 16:03 
Заслуженный участник
Аватара пользователя


11/03/08
9904
Москва
Теперь о разных произведениях.
По Адамару:
- перемножаются элементы, стоящие в одинаковых позициях и произведение записывается на ту же позицию $c_{i,j}=a_{i,j}b_{i.j}$ Часто реализовано во многих программных системах. Сомножители должны иметь одинаковые числа строк и столбцов.
По Фробениусу:
Сумма произведений элементов, стоящих на одинаковых позициях.
По Кронекеру:
Матрицы размерностей m на n одна и p на q вторая при умножении дадут матрицу $mp$ на $nq$, состоящую из клеток p на q, равных второй матрице, умноженной на соответствующий элемент первой. Обобщением умножения по Кронекеру является умножение по Трейси-Сингху и по Кхатри-Рао.
Краковское произведение:
Для матриц A и B оно равно $B^TA$, где перемножение транспонированной матрицы B на A делается по обычным правилам матричного умножения.

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

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение08.07.2016, 19:07 
Заслуженный участник


27/04/09
28128
Тут можно добавить, что, так же как обычное произведение — это следствие того, что используемые матрицы — матрицы каких-то линейных операторов, произведение Кронекера — это просто тензорное произведение двух тензоров второго ранга (не важно, сколько раз ковариантными и сколько контравариантными) с данными матрицами, хотя матрица после этого и «сплющена», а на самом деле она должна бы быть четырёхмерной. Произведение Фробениуса будет просто скалярным произведением, выраженным в базисе из матриц, у которых все элементы нулевые кроме одной единицы. Произведение Адамара — обычное поднятие произведения на $A$ в произведение на функциях $X\to A$. А вот краковское самому интересно чем мотивируется.

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение08.07.2016, 19:47 


02/07/16
16
Большое спасибо всем отписавшимся в теме)

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение08.07.2016, 21:30 
Заслуженный участник
Аватара пользователя


11/03/08
9904
Москва
Насколько я понял, "краковское произведение" ввёл известный польский астроном Банахевич для упрощения ручных расчётов (умножение получается "столбец на столбец", что должно снижать вероятность ошибки из-за путаницы в номерах строк), что в 1930-е представляло известную пользу. Позже, в 1950-е интерес возобновился, в связи с использованием внешней памяти последовательного доступа (лент и т.п.) и ограниченностью оперативной, поскольку такое умножение могло быть реализовано с более эффективным доступом (уменьшая количество перемоток ленты), но с развитием вычтехники он угас. Сейчас это скорее математический курьёз, упоминаемый, как пример практически полезного неассоциативного умножения.

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение09.07.2016, 00:57 
Заслуженный участник


04/05/09
4587
Евгений Машеров в сообщении #1136622 писал(а):
Насколько я понял, "краковское произведение" ввёл известный польский астроном Банахевич для упрощения ручных расчётов (умножение получается "столбец на столбец", что должно снижать вероятность ошибки из-за путаницы в номерах строк), что в 1930-е представляло известную пользу. Позже, в 1950-е интерес возобновился, в связи с использованием внешней памяти последовательного доступа (лент и т.п.) и ограниченностью оперативной, поскольку такое умножение могло быть реализовано с более эффективным доступом (уменьшая количество перемоток ленты), но с развитием вычтехники он угас. Сейчас это скорее математический курьёз, упоминаемый, как пример практически полезного неассоциативного умножения.
До сих пор используется, хотя может быть и неявно. Особенности организаций кеша памяти, а также всяческие SSE инструкции позволяют значительно быстрее умножать одинаково организованные массивы. Т.е. даже если транспонировать матрицу перед каждым умножением, уможение получится быстрее, чем по исходным матрицам.

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение09.07.2016, 08:15 
Заслуженный участник
Аватара пользователя


11/03/08
9904
Москва
Ну, под "интерес угас" я имел в виду, что уже не вводится, как самостоятельный объект, оптимизированная последовательность вычислений определяется через транспонирование и обычное умножение. Хотя вот даже монография недавняя есть:
Цитата:
Cracovian Algebra

Retail Price: $120.00

Cracovian Algebra

Authors: Kociñski, Jerzy

Book Description:
Cracovians are matrices with a redefined product, namely, the row-by-column product is replaced by the column-by-column product (or, alternatively by the row-by-row product). This alteration in the product definition implies that the multiplication of Cracovians is noncommutative and nonassociative. An exposition of cracovian algebra on “Cracovian Calculus”, and on the original papers of Banachiewics and his coworkers, together with applications to solutions of Systems of Linear Equations and to Spherical Polygonometry represents the main subjects of this book. The last three sections contain also new applications of cracovian algebra.

Table of Contents:
Preface; Chapter 1. Basic Definitions and Properties; Chapter 2. Division of Cracovians and Solutions of Systems of Linear Equations; Chapter 3. The Inverse Cracovian; Chapter 4. The Cracovian Square Root; Chapter 5. Cracovian and Matrix Expressions in Linear Algebra; Chapter 6. Rotation Cracovians; Chapter 7. An Outlook on Quasigroups; Index.

Binding: Hardcover
Pub. Date: 2004
ISBN: 1-59454-105-1

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

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение09.07.2016, 09:20 
Аватара пользователя


27/01/09
814
Уфа
Я так понимаю, что для программистов, транспонированием матрицы, лежащей в памяти (с произвольным доступом), может быть изменение порядка доступа к элементам матрицы (ячейкам), т.е. не обязательно транспонированную матрицу переписывать в другое место, т.е. такой операции как транспонирование матрицы не выполняется, а решается это изменением способа доступа, поэтому если это удобнее получается с т.з. количества операций или количества кода, то может быть скрыто в алгоритме умножения матриц.

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение09.07.2016, 10:18 
Заслуженный участник
Аватара пользователя


11/03/08
9904
Москва
В порядке гипотезы - отличие расположения элементов массива в памяти в Фортране (по столбцам) в отличие от последующих языков программирования могло быть связано с интересом к такому умножению.
А угасание интереса к нему могло быть обусловлено его неассоциативностью, что повышает вероятность ошибки не при вычислениях (которыми занимается машина), а при аналитических выкладках.
Сейчас оно осталось разве что, как пример квазигруппы. Тогда как "по Адамару" и "по Кронекеру" имеют практическое применение, хотя и меньшее, чем "обычное матричное умножение".

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение09.07.2016, 17:02 
Заслуженный участник


27/04/09
28128
Chifu в сообщении #1136686 писал(а):
поэтому если это удобнее получается с т.з. количества операций или количества кода, то может быть скрыто в алгоритме умножения матриц
Ни с той, ни с другой. Разумеется, операций будет столько же. venco ведь выше написал, с какой. :-) Менять порядок доступа как раз не очень осмысленно.

 Профиль  
                  
 
 Re: Перемножение матриц
Сообщение12.07.2016, 09:57 
Аватара пользователя


27/01/09
814
Уфа
arseniiv в сообщении #1136749 писал(а):
Chifu в сообщении #1136686 писал(а):
поэтому если это удобнее получается с т.з. количества операций или количества кода, то может быть скрыто в алгоритме умножения матриц
Ни с той, ни с другой. Разумеется, операций будет столько же. venco ведь выше написал, с какой. :-) Менять порядок доступа как раз не очень осмысленно.
Ну хорошо, для подготовки команд обработки массивов/потоков (с целью уменьшения скорости выполнения), но тогда операцию транспонирования придется выполнять (переписывать массив), а это организация доступа/записи, либо программист либо процессор это сделают, если такая специальная команда есть. Я просто хотел обратить внимание на то, что матрицу можно "взять" транспонированной (организовать так способ доступа).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group