Подразделы

Другие разделы

Дата и время

01/04/2025 01:18:08

Авторизация

Матрицы

Представление матриц Операции над матрицами LU-разложение и вычисление обратной матрицы Умножение матриц Алгоритм умножения матриц Штрассена

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

Транспонированная матрица $A^T$ получается из матрицы $A$ путем обмена местами ее строк и столбцов.

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

Определим сложение матриц следующим образом. Если $A$ и $B$ матрицы размером $n xx m$ , то их суммой $A+B$ является матрица $C$ размером $n xx m$ , определяемая соотношением $c_{ij}=a_{ij}+b_{ij}$ .

Для разрежённых матриц можно применить слияние упорядоченных последовательностей:

class SparseMatrix {
  int n,m;
  vector<list<pair<int,double>>> data;
public:
  SparseMatrix(int n, int m):n(n),m(m),data(n) {}
  pair<int,int> size()const {return {n,m};}
  double get(int i,int j) const; // получение значения
  double set(int i,int j, double v); // установка значения
  SparseMatrix & SparseMatrix::operator+=(const SparseMatrix& b)
  { if(n!=b.n || m!=b.m) throw runtime_error("несоответствие размеров");
    for(int i=0; i<n; ++i)
    { // слияние за O(q), где q - количество ненулевых элементов в строке (общее количество во всей матрице K=q*n)
      auto it1=data[i].begin();
      auto it2=b.data[i].begin();
      while(it1!=data[i].end() && it2!=b.data[i].end())
      { if(it1->first==it2->first) { it1->second+=it2->second; ++it1; ++it2; }
        else if(it1->first<it2->first) ++it1;
        else { data[i].insert(it1,*it2); ++it2; }
      }
       while(it2!=b.data[i].end()) { data[i].insert(it1,*it2); ++it2; }
    }
   return *this;
  }
};
inline SparseMatrix operator+(SparseMatrix a, const SparseMatrix b) { return a+=b; }

Если $b$ – число, а $A$ – матрица, то $bA = (b*a_{ij})$ определяет скалярное произведение матрицы на число, которое также выполняется поэлементно. Частным случаем скалярного произведения является умножение на $-1$ , которое дает противоположную матрицу $-A$ , обладающую тем свойством, что $A+ (-A)=0$ .

Соответственно, можно определить вычитание матриц как сложение с противоположной матрицей: $A-B=A+(-B)$ .

Матричное умножение определяется следующим образом. Матрицы $A$ размером $n xx m$ и $B$ размером $m xx p$ могут быть перемножены, если число столбцов $A$ равно числу строк $B$ . Их произведение $C = AB$ представляет собой матрицу размером $n xx p$ , элементы которой определяются уравнением $c_{ij}=sum_{k=1}^{m} a_{ik}*b_{kj}$ . Для умножения матриц размером $n xx n$ требуется $n^3$ умножений и столько же сложений.

Умножение матриц ассоциативно. Умножение матриц дистрибутивно относительно сложения.

Матрицей, обратной к данной матрице $А$ размером $n xx n$ является матрица размером $n xx n$ , обозначаемая как $A^{-1}$ (если таковая существует), такая что $A*A^{-1}=A^{-1}*A=I_n$ .

Часто приходится иметь дело с квадратными матрицами размером $n xx n$ . Некоторые из квадратных матриц представляют особый интерес.