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

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

В математике , особенно в линейной алгебре , умножение матриц - это бинарная операция, которая производит матрицу из двух матриц. Для умножения матриц количество столбцов в первой матрице должно быть равно количеству строк во второй матрице. Результирующая матрица, известная как матричное произведение , имеет количество строк первой и количество столбцов второй матрицы. Произведение матриц A и B обозначается AB . ^{[1] [2]}

Умножение матриц было впервые описано французским математик Жак Филипп Мари Бине в 1812 году, ^[3] , чтобы представить композицию из линейных отображений , представленных матрицами. Таким образом, умножение матриц является основным инструментом линейной алгебры и, как таковое, имеет многочисленные приложения во многих областях математики, а также в прикладной математике , статистике , физике , экономике и технике . ^{[4] [5]} Вычисление матричных произведений - центральная операция во всех вычислительных приложениях линейной алгебры.

Обозначение [ править ]

В этой статье будут использоваться следующие условные обозначения: матрицы представлены заглавными буквами жирным шрифтом, например A ; векторы, выделенные строчными полужирными буквами, например a ; а элементы векторов и матриц выделены курсивом (поскольку они являются числами из поля), например A и a . Индексная нотация часто является наиболее ясным способом выражения определений и используется в литературе как стандарт. Элемент i, j матрицы A обозначается ( A ) _ij , A _ij или a _ij, тогда как числовая метка (не элементы матрицы) на коллекции матриц указывается только в нижнем индексе, например, A ₁ , A ₂ и т. д.

Определение [ править ]

Если A - матрица размера m × n, а B - матрица размера n × p ,

${\displaystyle \mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\\\end{pmatrix}},\quad \mathbf {B} ={\begin{pmatrix}b_{11}&b_{12}&\cdots &b_{1p}\\b_{21}&b_{22}&\cdots &b_{2p}\\\vdots &\vdots &\ddots &\vdots \\b_{n1}&b_{n2}&\cdots &b_{np}\\\end{pmatrix}}}$

матричное произведение С = АВ (обозначается без умножения знаков или точек) определяется , чтобы быть м × р матрица ^{[6] [7] [8] [9]}

${\displaystyle \mathbf {C} ={\begin{pmatrix}c_{11}&c_{12}&\cdots &c_{1p}\\c_{21}&c_{22}&\cdots &c_{2p}\\\vdots &\vdots &\ddots &\vdots \\c_{m1}&c_{m2}&\cdots &c_{mp}\\\end{pmatrix}}}$

такой, что

${\displaystyle c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots +a_{in}b_{nj}=\sum _{k=1}^{n}a_{ik}b_{kj},}$

для i = 1, ..., m и j = 1, ..., p .

Таким образом, запись продукта получается путем поэтапного умножения записей i- й строки A и j- го столбца B и суммирования этих n произведений. Другими слова, это скалярное произведение из я - й строки A и J - м столбце B . ^[1]${\displaystyle c_{ij}}$${\displaystyle c_{ij}}$

Следовательно, AB можно также записать как

${\displaystyle \mathbf {C} ={\begin{pmatrix}a_{11}b_{11}+\cdots +a_{1n}b_{n1}&a_{11}b_{12}+\cdots +a_{1n}b_{n2}&\cdots &a_{11}b_{1p}+\cdots +a_{1n}b_{np}\\a_{21}b_{11}+\cdots +a_{2n}b_{n1}&a_{21}b_{12}+\cdots +a_{2n}b_{n2}&\cdots &a_{21}b_{1p}+\cdots +a_{2n}b_{np}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}b_{11}+\cdots +a_{mn}b_{n1}&a_{m1}b_{12}+\cdots +a_{mn}b_{n2}&\cdots &a_{m1}b_{1p}+\cdots +a_{mn}b_{np}\\\end{pmatrix}}}$

Таким образом, продукт AB определен тогда и только тогда, когда количество столбцов в A равно количеству строк в B , ^[2] в данном случае n .

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

Иллюстрация [ править ]

Рисунке справа схематично иллюстрирует произведение двух матриц A и B , показывающий , как каждое пересечение в матрице продукта соответствует ряду А и столбец B .

${\displaystyle {\overset {4\times 2{\text{ matrix}}}{\begin{bmatrix}{a_{11}}&{a_{12}}\\\cdot &\cdot \\{a_{31}}&{a_{32}}\\\cdot &\cdot \\\end{bmatrix}}}{\overset {2\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &{b_{12}}&{b_{13}}\\\cdot &{b_{22}}&{b_{23}}\\\end{bmatrix}}}={\overset {4\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &c_{12}&c_{13}\\\cdot &\cdot &\cdot \\\cdot &c_{32}&c_{33}\\\cdot &\cdot &\cdot \\\end{bmatrix}}}}$

Значения на пересечениях, отмеченных кружками:

${\displaystyle {\begin{aligned}c_{12}&={a_{11}}{b_{12}}+{a_{12}}{b_{22}}\\c_{33}&={a_{31}}{b_{13}}+{a_{32}}{b_{23}}\end{aligned}}}$

Основные приложения [ править ]

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

Линейные карты [ править ]

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

Линейное отображение из векторного пространства размерности п в векторном пространстве размерности м отображает вектор - столбец

${\displaystyle \mathbf {x} ={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}}}$

на вектор-столбец

${\displaystyle \mathbf {y} =A(\mathbf {x} )={\begin{pmatrix}a_{11}x_{1}+\cdots +a_{1n}x_{n}\\a_{21}x_{1}+\cdots +a_{2n}x_{n}\\\vdots \\a_{m1}x_{1}+\cdots +a_{mn}x_{n}\end{pmatrix}}.}$

Таким образом, линейное отображение A определяется матрицей

${\displaystyle \mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\\\end{pmatrix}},}$

и отображает вектор-столбец в матричное произведение ${\displaystyle \mathbf {x} }$

${\displaystyle \mathbf {y} =\mathbf {Ax} .}$

Если B - другая линейная карта из предыдущего векторного пространства размерности m в векторное пространство размерности p , она представлена матрицей . Прямое вычисление показывает, что матрица составной карты является матричным произведением (общая формула ), которая определяет композиция функций представлена ​​здесь как частный случай ассоциативности матричного произведения (см. § Ассоциативность ниже):${\displaystyle p\times m}$${\displaystyle \mathbf {B} .}$ ${\displaystyle B\circ A}$${\displaystyle \mathbf {BA} .}$${\displaystyle (B\circ A)(\mathbf {x} )=B(A(\mathbf {x} ))}$

${\displaystyle (\mathbf {BA} )\mathbf {x} =\mathbf {B} (\mathbf {Ax} )=\mathbf {BAx} .}$

Система линейных уравнений [ править ]

Общий вид системы линейных уравнений имеет вид

${\displaystyle {\begin{matrix}a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+\cdots +a_{2n}x_{n}=b_{2}\\\vdots \\a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m}\end{matrix}}.}$

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

${\displaystyle \mathbf {Ax} =\mathbf {b} .}$

Точечный продукт, билинейная форма и внутренний продукт [ править ]

Скалярное произведение двух векторов - столбцов является матрицей продукта

${\displaystyle \mathbf {x} ^{\mathsf {T}}\mathbf {y} ,}$

где - вектор-строка, полученный транспонированием, и результирующая матрица 1 × 1 отождествляется с ее уникальным элементом.${\displaystyle \mathbf {x} ^{\mathsf {T}}}$ ${\displaystyle \mathbf {x} }$

В более общем смысле, любая билинейная форма над векторным пространством конечной размерности может быть выражена как матричное произведение

${\displaystyle \mathbf {x} ^{\mathsf {T}}\mathbf {Ay} ,}$

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

${\displaystyle \mathbf {x} ^{\dagger }\mathbf {Ay} ,}$

где обозначает сопряженное транспонирование из (конъюгата транспонированной, или , что эквивалентно транспонированная конъюгата).${\displaystyle \mathbf {x} ^{\dagger }}$${\displaystyle \mathbf {x} }$

Общие свойства [ править ]

Умножение матриц разделяет некоторые свойства с обычным умножением . Тем не менее, умножение матриц не определенно , если число столбцов первого фактор отличается от числа строк второго фактора, и это некоммутативное , ^[10] , даже когда продукт остается определенным после изменения порядка факторов . ^{[11] [12]}

Некоммутативность [ править ]

Операция коммутативна, если для двух элементов A и B, таких, что продукт определен, также определено, и${\displaystyle \mathbf {A} \mathbf {B} }$${\displaystyle \mathbf {B} \mathbf {A} }$${\displaystyle \mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A} .}$

Если A и B - матрицы соответствующих размеров и , то определяется, если , и определяется, если . Следовательно, если один из продуктов определен, другой вообще не определен. Если два продукта определены, но имеют разные размеры; таким образом, они не могут быть равны. Только в том случае , если , то есть, если A и B являются квадратными матрицами одинакового размера, оба продукта определены и имеют одинаковый размер. Даже в этом случае в целом${\displaystyle m\times n}$${\displaystyle p\times q}$${\displaystyle \mathbf {A} \mathbf {B} }$${\displaystyle n=p}$${\displaystyle \mathbf {B} \mathbf {A} }$${\displaystyle m=q}$${\displaystyle m=q\neq n=p}$${\displaystyle m=q=n=p}$

${\displaystyle \mathbf {A} \mathbf {B} \neq \mathbf {B} \mathbf {A} .}$

Например

${\displaystyle {\begin{pmatrix}0&1\\0&0\end{pmatrix}}{\begin{pmatrix}0&0\\1&0\end{pmatrix}}={\begin{pmatrix}1&0\\0&0\end{pmatrix}},}$

но

${\displaystyle {\begin{pmatrix}0&0\\1&0\end{pmatrix}}{\begin{pmatrix}0&1\\0&0\end{pmatrix}}={\begin{pmatrix}0&0\\0&1\end{pmatrix}}.}$

Этот пример может быть расширен для показа , что, если является матрица с элементами в поле F , то для каждой матрицы B с элементами из F , тогда и только тогда , когда , и я это единичная матрица . Если вместо поля предполагается, что записи принадлежат кольцу , то нужно добавить условие, что c принадлежит центру кольца.${\displaystyle n\times n}$ ${\displaystyle \mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A} }$${\displaystyle n\times n}$ ${\displaystyle \mathbf {A} =c\,\mathbf {I} }$${\displaystyle c\in F}$${\displaystyle n\times n}$

Один частный случай, когда коммутативность действительно имеет место, - это когда D и E - две (квадратные) диагональные матрицы (одинакового размера); тогда DE = ED . ^[10] Опять же, если матрицы расположены над общим кольцом, а не над полем, соответствующие элементы в каждой должны также коммутировать друг с другом, чтобы это имело место.

Распределительность [ править ]

Матричное произведение является распределительным по отношению к матричному сложению . То есть, если A , B , C , D - матрицы соответствующих размеров m × n , n × p , n × p и p × q , одна имеет (левая дистрибутивность)

${\displaystyle \mathbf {A} (\mathbf {B} +\mathbf {C} )=\mathbf {AB} +\mathbf {AC} ,}$

и (правильная дистрибутивность)

${\displaystyle (\mathbf {B} +\mathbf {C} )\mathbf {D} =\mathbf {BD} +\mathbf {CD} .}$^[10]

Это происходит из-за распределенности коэффициентов по формуле

${\displaystyle \sum _{k}a_{ik}(b_{kj}+c_{kj})=\sum _{k}a_{ik}b_{kj}+\sum _{k}a_{ik}c_{kj}}$

${\displaystyle \sum _{k}(b_{ik}+c_{ik})d_{kj}=\sum _{k}b_{ik}d_{kj}+\sum _{k}c_{ik}d_{kj}.}$

Произведение со скаляром [ править ]

Если A - матрица, а c - скаляр, то матрицы и получаются умножением всех элементов A на c слева или справа . Если скаляры обладают коммутативным свойством , то${\displaystyle c\mathbf {A} }$${\displaystyle \mathbf {A} c}$${\displaystyle c\mathbf {A} =\mathbf {A} c.}$

Если продукт определен (то есть количество столбцов A равно количеству строк B ), то ${\displaystyle \mathbf {AB} }$

${\displaystyle c(\mathbf {AB} )=(c\mathbf {A} )\mathbf {B} }$ а также ${\displaystyle (\mathbf {A} \mathbf {B} )c=\mathbf {A} (\mathbf {B} c).}$

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

Эти свойства являются результатом билинейности произведения скаляров:

${\displaystyle c\left(\sum _{k}a_{ik}b_{kj}\right)=\sum _{k}(ca_{ik})b_{kj}}$

${\displaystyle \left(\sum _{k}a_{ik}b_{kj}\right)c=\sum _{k}a_{ik}(b_{kj}c).}$

Транспонировать [ править ]

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

${\displaystyle (\mathbf {AB} )^{\mathsf {T}}=\mathbf {B} ^{\mathsf {T}}\mathbf {A} ^{\mathsf {T}}}$

где ^T обозначает транспонирование, то есть чередование строк и столбцов.

Это тождество не выполняется для некоммутативных элементов, поскольку порядок между элементами A и B меняется на противоположный, когда расширяется определение матричного произведения.

Комплексное сопряжение [ править ]

Если A и B имеют сложные записи, то

${\displaystyle (\mathbf {AB} )^{*}=\mathbf {A} ^{*}\mathbf {B} ^{*}}$

где ^* обозначает комплексно сопряженное по элементам матрицу.

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

Транспонирование действует на индексы записей, в то время как конъюгация действует независимо на сами записи. Это приводит к тому, что, если A и B имеют сложные записи, один имеет

${\displaystyle (\mathbf {AB} )^{\dagger }=\mathbf {B} ^{\dagger }\mathbf {A} ^{\dagger },}$

где ^† обозначает сопряженное транспонирование (сопряжение транспонирования или эквивалентное транспонирование сопряженного элемента).

Ассоциативность [ править ]

Для трех матриц A , B и C произведения ( AB ) C и A ( BC ) определены тогда и только тогда, когда количество столбцов A равно количеству строк B , а количество столбцов B равно количеству строк C (в частности, если один из продуктов определен, то другой также определен). В этом случае имеется ассоциативное свойство

${\displaystyle (\mathbf {AB} )\mathbf {C} =\mathbf {A} (\mathbf {BC} ).}$

Что касается любой ассоциативной операции, это позволяет опустить круглые скобки и записать указанные выше продукты как ${\displaystyle \mathbf {ABC} .}$

Это естественно распространяется на произведение любого количества матриц при условии, что размеры совпадают. То есть, если A ₁ , A ₂ , ..., A _n - матрицы такие, что количество столбцов A _i равно количеству строк A _{i + 1} для i = 1, ..., n - 1 , тогда продукт

${\displaystyle \prod _{i=1}^{n}\mathbf {A} _{i}=\mathbf {A} _{1}\mathbf {A} _{2}\cdots \mathbf {A} _{n}}$

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

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

Сложность не ассоциативна [ править ]

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

Например, если A , B и C являются матрицами соответствующих размеров 10 × 30, 30 × 5, 5 × 60 , вычисление ( AB ) C требует 10 × 30 × 5 + 10 × 5 × 60 = 4500 умножений, при вычислении A ( BC ) нужно 30 × 5 × 60 + 10 × 30 × 60 = 27000 умножений.

Были разработаны алгоритмы для выбора наилучшего порядка продуктов, см. Умножение цепочки матриц . При увеличении числа матриц n было показано, что выбор наилучшего порядка имеет сложность${\displaystyle O(n\log n).}$

Применение к подобию [ править ]

Любая обратимая матрица определяет преобразование подобия (на квадратных матрицах того же размера, что и )${\displaystyle \mathbf {P} }$${\displaystyle \mathbf {P} }$

${\displaystyle S_{\mathbf {P} }(\mathbf {A} )=\mathbf {P} ^{-1}\mathbf {A} \mathbf {P} .}$

Преобразования подобия сопоставляют продукт с продуктами, то есть

${\displaystyle S_{\mathbf {P} }(\mathbf {AB} )=S_{\mathbf {P} }(\mathbf {A} )S_{\mathbf {P} }(\mathbf {B} ).}$

Фактически, есть

${\displaystyle \mathbf {P} ^{-1}(\mathbf {AB} )\mathbf {P} =\mathbf {P} ^{-1}\mathbf {A} (\mathbf {P} \mathbf {P} ^{-1})\mathbf {B} \mathbf {P} =(\mathbf {P} ^{-1}\mathbf {A} \mathbf {P} )(\mathbf {P} ^{-1}\mathbf {B} \mathbf {P} ).}$

Квадратные матрицы [ править ]

Обозначим множество квадратных матриц размера n × n с элементами кольца R , которое на практике часто является полем .${\displaystyle {\mathcal {M}}_{n}(R)}$

В , произведение определяется для каждой пары матриц. Это делает в кольцо , которое имеет единичную матрицу I в качестве единичного элемента (матрицы, диагональные элементы равны 1 , а все остальные элементы равны 0). Это кольцо также является ассоциативной R -алгеброй .${\displaystyle {\mathcal {M}}_{n}(R)}$${\displaystyle {\mathcal {M}}_{n}(R)}$

Если n > 1 , многие матрицы не имеют мультипликативного обратного . Например, матрица, в которой все элементы строки (или столбца) равны 0, не имеет инверсии. Если он существует, матрица, обратная матрице A , обозначается A ⁻¹ , и, таким образом, проверяется

${\displaystyle \mathbf {A} \mathbf {A} ^{-1}=\mathbf {A} ^{-1}\mathbf {A} =\mathbf {I} .}$

Матрица, имеющая обратную, является обратимой матрицей . В противном случае это особая матрица .

Произведение матриц обратимо тогда и только тогда, когда каждый фактор обратим. В этом случае

${\displaystyle (\mathbf {A} \mathbf {B} )^{-1}=\mathbf {B} ^{-1}\mathbf {A} ^{-1}.}$

Когда R является коммутативным , и, в частности, когда это поле, то определитель продукта является произведением определителей. Поскольку детерминанты являются скалярами, а скаляры коммутируют, таким образом

${\displaystyle \det(\mathbf {AB} )=\det(\mathbf {BA} )=\det(\mathbf {A} )\det(\mathbf {B} ).}$

Остальные матричные инварианты не так хорошо работают с произведениями. Тем не менее, если R коммутативно, AB и BA имеют один и тот же след , один и тот же характеристический многочлен и одинаковые собственные значения с одинаковой кратностью. Однако, как правило , собственные векторы разные, если AB ≠ BA .

Полномочия матрицы [ править ]

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

${\displaystyle \mathbf {A} ^{0}=\mathbf {I} ,}$

${\displaystyle \mathbf {A} ^{1}=\mathbf {A} ,}$

${\displaystyle \mathbf {A} ^{k}=\underbrace {\mathbf {A} \mathbf {A} \cdots \mathbf {A} } _{k{\text{ times}}}.}$

Для вычисления k- й степени матрицы требуется в k - 1 раз больше времени, чем на единичное умножение матриц, если это выполняется с помощью тривиального алгоритма (повторное умножение). Поскольку это может занять очень много времени, обычно предпочитают использовать возведение в степень возведением в квадрат , которое требует менее 2 log ₂ k умножений матриц и, следовательно, намного более эффективно.

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

${\displaystyle {\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}}^{k}={\begin{bmatrix}a_{11}^{k}&0&\cdots &0\\0&a_{22}^{k}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}^{k}\end{bmatrix}}.}$

Абстрактная алгебра [ править ]

Определение матричного произведения требует, чтобы элементы принадлежали полукольцу, и не требует, чтобы умножение элементов полукольца было коммутативным . Во многих приложениях матричные элементы принадлежат полю, хотя тропическое полукольцо также является обычным выбором для задач поиска кратчайшего пути в графах . ^[13] Даже в случае матриц над полями произведение, вообще говоря, не коммутативно, хотя оно ассоциативно и дистрибутивно над сложением матриц . Эти единичные матрицы (которые являются квадратные матрицы , чьи элементы равны нулю вне главной диагонали и 1 на главной диагонали) являютсяединичные элементы матричного произведения. Отсюда следует, что матрицы размера n × n над кольцом образуют кольцо, которое некоммутативно, за исключением случая, когда n = 1 и основное кольцо коммутативно.

Квадратная матрица может иметь мультипликативную обратную матрицу , называемую обратной матрицей . В общем случае, когда элементы принадлежат коммутативному кольцу r , матрица имеет обратную тогда и только тогда, когда ее определитель имеет мультипликативную обратную по r . Определитель произведения квадратных матриц - это произведение определителей факторов. П × п матрицы , которые имеют обратную форму в группу в соответствии с матричным умножением, то подгруппы из которых называются матричными группы . Многие классические группы (включая все конечные группы ) изоморфныматричным группам; это отправная точка теории представлений групп .

Вычислительная сложность [ править ]

Улучшение оценок показателя ω со временем для вычислительной сложности умножения матриц .${\displaystyle O(n^{\omega })}$

Алгоритм умножения матриц , который является результатом определения, требует, в худшем случае , умножения скаляров и сложений для вычисления произведения двух квадратных матриц размера n × n . Следовательно , его вычислительная сложность заключается в модели вычислений, для которой скалярные операции требуют постоянного времени (на практике это имеет место для чисел с плавающей запятой , но не для целых чисел).${\displaystyle n^{3}}$${\displaystyle (n-1)n^{2}}$${\displaystyle O(n^{3})}$

Довольно удивительно, что эта сложность не оптимальна, как показал в 1969 году Фолькер Штрассен , который предоставил алгоритм, теперь называемый алгоритмом Штрассена , со сложностью ^[14]. Показатель степени сложности умножения матриц был улучшен в несколько раз, ^{[ 15] [16] [17] [18] [19] [20], что} приводит к алгоритму Копперсмита – Винограда со сложностью O ( n ^2.3755 ) (1990). ^{[21] [22]} Этот алгоритм был немного улучшен в 2010 году Stothers до сложности O ( n ^2.3737${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.8074}).}$) , ^[23] в 2013 году Вирджинией Василевской Уильямс в O ( n ^2.3729 ) , ^{[22] [24]} и в 2014 году Франсуа Ле ^Галлем в O ( n ^2.3728639 ) . ^[25] Это было дополнительно уточнено в 2020 году Джошем Алманом и Вирджинией Василевской Уильямс до окончательной (актуальной) сложности O ( n ^2.3728596 ) . ^[26]

Наибольшее нижняя граница для экспоненты алгоритма умножения матриц обычно называется . Один имеет , потому что нужно читать элементы матрицы, чтобы умножить их на другую матрицу. Итак . Неизвестно . Наибольшая известная нижняя граница сложности умножения матриц равна Ω ( n ² log ( n )) для ограниченного типа арифметических схем и принадлежит Рану Разу . ^[27]${\displaystyle \omega }$${\displaystyle 2\leq \omega }$${\displaystyle n^{2}}$${\displaystyle 2\leq \omega <2.373}$${\displaystyle 2<\omega }$

Связанные сложности [ править ]

Важность вычислительной сложности матричного умножения основана на том факте, что многие алгоритмические проблемы могут быть решены с помощью матричных вычислений, и большинство проблем с матрицами имеют сложность, которая либо такая же, как у матричного умножения (с точностью до мультипликативной константы). ), или может быть выражено через сложность умножения матриц или ее показатель степени${\displaystyle \omega .}$

Есть несколько преимуществ выражения сложности в терминах экспоненты умножения матриц. Во-первых, если будет улучшено, это автоматически улучшит известную верхнюю границу сложности многих алгоритмов. Во-вторых, в практических реализациях никогда не используется алгоритм умножения матриц, который имеет лучшую асимптотическую сложность, потому что константа, скрытая за большой нотацией O, слишком велика для того, чтобы сделать алгоритм конкурентоспособным для размеров матриц, которыми можно манипулировать на компьютере. ^{[ необходима цитата ]} Таким образом, выражение сложности в терминах обеспечивает более реалистичную сложность, поскольку она остается действительной, какой бы алгоритм ни был выбран для вычисления матрицы.${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle \omega }$

Задачи, которые имеют ту же асимптотическую сложность, что и умножение матриц, включают определитель , обращение матриц , исключение Гаусса (см. Следующий раздел). Проблемы , связанные с сложностью, которая выражается в терминах включают характеристический полином, собственные значения (но не собственные векторы), Эрмита нормальную форму , и Смит нормальную форму . ^{[ необходима цитата ]}${\displaystyle \omega }$

Обращение матрицы, определитель и исключение Гаусса [ править ]

В своей статье 1969 года, где он доказал сложность вычисления матриц, Штрассен также доказал, что обращение матриц , определитель и исключение Гаусса имеют, с точностью до мультипликативной константы, ту же вычислительную сложность, что и умножение матриц. Доказательство не делает никаких предположений об используемом умножении матриц, за исключением того, что его сложность для некоторых${\displaystyle O(n^{2.807})}$${\displaystyle O(n^{\omega })}$${\displaystyle \omega \geq 2}$

Отправной точкой доказательства Штрассена является использование блочного умножения матриц . В частности, матрица четной размерности 2 n × 2 n может быть разделена на четыре блока n × n.

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}.}$

В этой форме его обратное

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}^{-1}={\begin{bmatrix}{A}^{-1}+{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&-{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}\\-({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&({D}-{CA}^{-1}{B})^{-1}\end{bmatrix}},}$

при условии, что A и обратимы.${\displaystyle {D}-{CA}^{-1}{B}}$

Таким образом, обратная матрица 2 n × 2 n может быть вычислена с помощью двух инверсий, шести умножений и четырех сложений или аддитивных обращений матриц n × n . Отсюда следует, что, обозначая соответственно I ( n ) , M ( n ) и A ( n ) = n ² количество операций, необходимых для инвертирования, умножения и сложения матриц размера n × n , мы получаем

${\displaystyle I(2n)\leq 2I(n)+6M(n)+4A(n).}$

Если можно применить эту формулу рекурсивно:${\displaystyle n=2^{k},}$

${\displaystyle {\begin{aligned}I(2^{k})&\leq 2I(2^{k-1})+6M(2^{k-1})+4A(2^{k-1})\\&\leq 2^{2}I(2^{k-2})+6(M(2^{k-1})+2M(2^{k-2}))+4(A(2^{k-1})+2A(2^{k-2}))\\&\ldots \end{aligned}}}$

Если и в конце концов получится ${\displaystyle M(n)\leq cn^{\omega },}$${\displaystyle \alpha =2^{\omega }\geq 4,}$

${\displaystyle {\begin{aligned}I(2^{k})&\leq 2^{k}I(1)+6c(\alpha ^{k-1}+2\alpha ^{k-2}+\cdots +2^{k-1}\alpha ^{0})+k2^{k+1}\\&\leq 2^{k}+6c{\frac {\alpha ^{k}-2^{k}}{\alpha -2}}+k2^{k+1}\\&\leq d(2^{k})^{\omega }.\end{aligned}}}$

для некоторой постоянной d .

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

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

Тот же аргумент применяется к разложению LU , так как, если матрица A обратима, равенство

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}={\begin{bmatrix}I&0\\CA^{-1}&I\end{bmatrix}}\,{\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}}}$

определяет блочное разложение LU, которое может быть применено рекурсивно к и для получения в конечном итоге истинного LU-разложения исходной матрицы.${\displaystyle A}$${\displaystyle D-CA^{-1}B,}$

Аргумент применим также к определителю, поскольку он является результатом разложения блочного LU, что

${\displaystyle \det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det(D-CA^{-1}B).}$

См. Также [ править ]

• Матричное исчисление , для взаимодействия умножения матриц с операциями из исчисления
• Другие виды изделий из матриц:
  • Блочное умножение матриц
  • Краковское произведение , определенное как A ∧ B = B ^T A
  • Внутреннее произведение Фробениуса , скалярное произведение матриц, рассматриваемых как векторы, или, что эквивалентно, сумма элементов произведения Адамара
  • Произведение Адамара двух матриц одинакового размера, в результате получается матрица одинакового размера, которая является произведением запись за записью.
  • Произведение Кронекера или тензорное произведение , обобщение на любой размер предыдущего
  • Продукт Khatri-Rao и продукт для разделения лиц
  • Внешний продукт , также называемый диадическим произведением или тензорным произведением матриц двух столбцов, который${\displaystyle \mathbf {a} \mathbf {b} ^{\mathsf {T}}}$
  • Скалярное умножение

Заметки [ править ]

Ссылки [ править ]

Викискладе есть медиафайлы, связанные с умножением матриц .

В Викиучебнике линейной алгебры есть страница по теме: Умножение матриц

В Викибуке Применимая математика есть страница по теме: Умножение матриц