Начало
Учебные материалы
Матрицы
Представление матриц Операции над матрицами LU-разложение и вычисление обратной матрицы Умножение матриц Алгоритм умножения матриц Штрассена
Операции над матрицами
обмена местами ее строк и столбцов.
Элементами матриц и векторов служат элементы некоторой числовой системы,
такие как действительные числа, комплексные числа или, например, целые числа
по модулю простого числа. Числовая система определяет, каким образом должны
складываться и перемножаться числа. Эти определения можно распространить
и на матрицы.
Определим сложение матриц следующим образом. Если
`A` и `B` матрицы размером `n xx m`, то их суммой `A+B` является матрица `C`
размером `n xx m`, определяемая соотношением `c_{ij}=a_{ij}+b_{ij}`.
--
Для разрежённых матриц можно применить слияние упорядоченных последовательностей:
```c++
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`. Некоторые из квадратных матриц представляют особый интерес.
1. Диагональная матрица обладает тем свойством, что `a_{ij}=0` при `i!=j`.
2. Единичная матрица `I_n` размером `n xx n` представляет собой
диагональную матрицу, все диагональные элементы которой равны 1.
3. Верхне-треуголъной матрицей `U` называется матрица, у которой все элементы ниже диагонали равны 0 (`u_{ij} = 0` при `i > j`).
4. Нижне-треуголъной матрицей `L` называется матрица, у которой все элементы выше диагонали равны 0.
5. Матрица перестановки (permutation matrix) `P` имеет в каждой строке
и столбце ровно по одной единице, а на всех прочих местах располагаются нули.
6. Симметричная матрица `A` удовлетворяет условию `A=A^T`.
