Простейшие операции над матрицами.

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

Процедура переножает две матрицы A=(ai j) размера n*m и B=(bi j) размера m*k получая в итоге матрицу C=(ci j) размера n*k. Формула по которой получаем элементы матрицы C следующая:

	сij=ai1b1j+...+aimbmj для i=1..n;j=1..k

Наверх

Вероятностная проверка умножения матриц.

Алгоритм прислан riiki и мне этот алгоритм очень понравился, надеюсь, что многим он будет полезен.

Допустим нам надо проверить матричное равенство A*B=C, в котором матрицы A,B,C квадратные размера n*n. Для проверки "в лоб" с помощью простого перемножения матриц A,B и затем сравнения полученного результата с матрицей C, потребует выполнение O(n3) операций. Но есть другой вариант - использовать вероятностный алгоритм.

Выберем вектор Y=(y1,...,yn) у которого координаты равны 0 или 1, при этом появление 0 или 1 равновероятно. Сравним A*(B*Y) и C*Y, если равенства нет, то и исходное равенство не выполнено. Если же A*(B*Y)=C*Y, то вероятность того, что A*B < > C меньше 1/2. Таким образом мы можем проверить равенство с необходимой вероятностью.

На вход алгоритм получает матрицы A,B,C и вероятность с которой нам необходимо удостовериться в равенстве, на выходе получаем True или False, соответственно, если равенство выполнено с заданной вероятностью или нет.

Алгоритм использует уже имеющиеся для получения псевдослучайных чисел распределенных равномерно и перемножения матриц. Использование последнего алгоритма обусловлено желанием не перегружать блок-схему, хотя правильние было бы произвести перемножения матрицы на вектор на прямую, подразумевая тот факт, что компоненты вектора принимают значения только 0,1. Наверх

Обращение матрицы с помощью расширенной матрицы.

Процедура обращает квадратную матрицу M размером n*n с помощью элементарных операций, которые приводят матрицу M к единичной. Обозначим расширенную матрицу A:

К числу элементарных операций относятся:

Перестановка двух столбцов (строк) матрицы.

Умножение строки (столбца) на k не равное 0.

Сложение двух строк (столбцов).

Поскольку если матрица вырожденна, то у нее не существует обратной в алгоритме вводится дополнительная переменная S, по значению которой можно определить вырождена матрица (S=1) или нет (S=0) Наверх

Обращение матрицы методом Гаусса.

Процедура находит, обратную квадратной матрице A размером n*n, по методу Гаусса. Для несобственной матрицы A=(ai j) находится матрица A -1=(xi j) , такая, что

	A A -1=E,

где E- единичная матрица.

Уравнение представляет собой n систем n линейных уравнений для n2 неизвестных xi j. Каждая из систем имеет одну и ту же основную матрицу A и различные свободные члены. Все системы решаются одновременно методом Гаусса (см. метод Гаусса).

В процедуре введена переменная S, если матрица близка к вырожденной, то S=1 и обратная матрица не вычисляется, иначе S=0. Наверх

Вычисление определителя методом триангуляции.

Функция вычисляет определитель матрицы det (ai j). Матрица A имеет размер n*n. Триангуляция производится с выбором максимального элемента.

Алгоритм вычисления: а) первом столбце определяется максимальный элемент M1. Если он находится в j-й строке, то первая и j-я строки переставляются. При М1=0 определитель равен нулю; б) затем из элементов ai,j(j>1) вычитаются соответствующие элементы первого столбца, умноженные на a1 j1 1. В результате получим:

где a(1)i j = ai j - ai1 a1 j / a11

К определителю матрицы a(1)i j применяем тот же прием еще (n-2) раза. Окончательно получим:

При перестановке столбцов учитывается изменение знака определителя. Наверх