1. Алгоритм Штрассена

Использование правил блочного произведения матриц позволяет уменьшить общее количество операций, а значит, и время выполнения работы программы. Допустим, требуется умножить квадратные матрицы A и B порядка . При перемножении матриц, по формулам, приведённым в определении произведения, потребуется умножений и сложений. Разобьём матрицы A и B на блоки порядка n. Вычисление произведения блочных матриц проведём по формулам Штрассена

1. потребуется умножений и сложений

2. потребуется умножений и сложений

3. потребуется умножений и сложений

4. потребуется умножений и сложений

5. потребуется умножений и сложений

6. потребуется умножений и сложений

7. потребуется умножений и сложений

8. потребуется сложений

9. потребуется сложений

10. потребуется сложений

11. потребуется сложений.

Всего, для вычисления произведения матриц по формулам Штрассена, потребуется операций сложения и умножения. При выполнении неравенства (n>7) формулы Штрассена приводят к меньшему объёму вычислений. Выигрыш в числе операций будет увеличиваться, если при вычислении произведения матриц (шаги1-7) использовать ту же схему.

Обозначим через число операций сложения и умножения, используемых при умножении матриц n-го порядка по формулам Штрассена. Справедлива рекуррентная формула . Положим . Тогда , далее, свернём сумму по формуле суммы членов геометрической прогрессии и заметим. В результате получим . Подставив вместо k его выражение через n () получим ( ).

2. Кронекерово произведение

Определение 6.22Пусть и - прямоугольные матрицы соответственно размеров и . Кронекеровым произведением называется матрица размеров следующего блочного строения .

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

Свойство 6.16. Пусть и , тогда .

Доказательство следует из правила блочного произведения матриц.

Свойство 6.17. Пусть существуют и , тогда .

Доказательство. По доказанному ранее (Свойство 6 .16), имеем . Из полученного равенства вытекает требуемое утверждение.

Свойство 6.18. .

Доказательство следует из определения операций кронекерова произведения и транспонирования матриц.

Свойство 6.19. Пусть - квадратная матрица порядка , а - квадратная матрица порядка , тогда .

Доказательство. Если матрица A имеет верхний треугольный вид, то утверждение получается последовательным разложением определителя по теореме Лапласа по первым m столбцам. Если матрица A имеет нижний треугольный вид, то утверждение получается последовательным разложением определителя по теореме Лапласа по первым m строкам. Рассмотрим случай, когда матрица A не треугольная. Элементарными преобразованиями со строками (а именно, перестановкой строк и прибавлением к одной строки, другой строки умноженной на число) приведём матрицу A к треугольному виду T. Тогда , где - матрица элементарных преобразований. Имеет место равенство , из которого выводим . Поскольку T – треугольная матрица, то . Матрица элементарного преобразования , если она соответствует прибавлению к некоторой строке другой строки, умноженной на число, имеет треугольный вид, и, значит . Если матрица элементарного преобразования соответствует перестановке двух строк, то . Таким образом, . Для доказательства утверждения осталось заметить равенство .

Следствие 6.14. .

Доказательство проведём индукцией по n. Положим и . При n=2 имеем , т.е. утверждение верно. Пусть оно справедливо при n-1. Тогда , что и требовалось доказать.