Свойства транспонированной матрицы

Вопрос 40

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

В массиве X из 20 вещественных чисел поменять местами наибольшие и наименьшие элементы.

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

Эту задачу нужно решать с помощью двух последовательных просмотров массива X. Целью первого просмотра является вычисление наибольшего МАХ и наименьшего МIN значений элементов массива X. В начале просмотра значение первого элемента Х[1] считается одновременно наибольшим и наименьшим, что справедливо в том случае, если в массиве всего один элемент. Далее со второго элемента Х[2] и до последнего Х[20] сравниваются значение текущего элемента с MIN. Если значение текущего элемента меньше, то оно с этого момента считается минимальным. По окончании цикла в рабочей ячейке MIN окажется число, равное значению наименьшего элемента. Аналогично поступаем для нахождения МАХ.
Далее нужно сравнить между собой MIN и МАХ. Если эти величины равны между собой, то массив состоит из 20 равнозначных элементов. Следовательно, переставлять их местами нет необходимости. Если MIN?МАХ, то нужно наименьшим элементам присвоить значение МАХ, а наибольшим элементам присвоить значение MIN. Эти действия являются основой для второго просмотра массива X.

PROGRAM PR31;
VAR
X: ARRAY [ 1.. 20] OF REAL;
I: INTEGER;
MIN, MAX: REAL;
BEGIN
WRITELN('Введитемассив X, из 20 вещественныхчисел');
FOR I := 1 ТО 20 DO READ(X[I]);
MIN :=Х[1];
МАХ :=Х[1];
FOR I := 2 ТО 20
DO BEGIN
IF MIN>X[I]
THEN MIN := X[I];
IF MAX<X[I]
THEN MAX := X[I];
END;
IF MIN <> MAX
THEN FOR I := 1 TO 20
DO BEGIN
IF MAX = X[I]
THEN X[I] := MIN
ELSE IF MIN = X[I]
THEN X[I]:=MAX;
END;
WRITELN('Элементымассива X имеютзначения:');
FOR I := 1 TO 20 DO WRITE(X[I]: 4:1,' ');
WRITELN
END.

Метод "пузырька"

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

• если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;
• при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .

В результате наибольший элемент оказывается в самом верху массива.

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

Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j.

Теперь можно привести текст программы упорядочения массива M[1..N]:

Стандартная процедураswapбудет использоваться и в остальных алгоритмах сортировки для перестановки элементов (их тип мы уточнять не будем) местами:

Заметим, что если массив M — глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.

Вопрос 41

В системе MatLab достаточно просто выполняются математические операции над матрицами и векторами. Рассмотрим сначала простые операции сложения и умножения матриц и векторов. Пусть даны два вектора

a = [1 2 3 4 5]; % вектор-строка
b = [1; 1; 1; 1; 1]; % вектор-столбец

тогда умножение этих двух векторов можно записать так

c = a*b; % c=1+2+3+4+5=16
d = b*a; % d – матрица 5х5 элементов

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

Сложение и вычитание двух векторов записывается так

a1 = [1 2 3 4 5];
a2 = [5 4 3 2 1];
c = a1+a2; % c = [1+5, 2+4, 3+3, 4+2, 5+1];
с = a2-a1; % c = [5-1, 4-2, 3-3, 2-4, 1-5];

Следует обратить внимание, что операции сложения и вычитания можно выполнять между двумя векторами-столбцами или двумя векторами-строками. Иначе MatLab выдаст сообщение об ошибке, т.к. разнотипные векторы складывать нельзя. Так обстоит дело со всеми недопустимыми арифметическими операциями: в случае невозможности их вычисления система MatLab сообщит об ошибке и выполнение программы будет завершено на соответствующей строке.

Аналогичным образом выполняются операции умножения и сложения между матрицами:

A = [1 2 3; 4 5 6; 7 8 9];
B = ones(3);
C = A+B; % сложение двух матриц одинакового размера
D = A+5; % сложение матрицы и числа
E = A*B; % умножение матрицы А на В
F = B*A; % умножение матрицы В на А
G = 5*A; % умножение матрицы на число

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

a = [1 1 1]; % вектор-строка
b = a’; % вектор-столбец, образованный
% транспонированием вектора-строки а.
A = [1 2 3; 4 5 6; 7 8 9]; % матрица 3х3 элемента
B = a*A; % B = [12 15 18] – вектор-строка
C = A*b; % C = [6; 15; 24] – вектор-столбец
D = a*A*a’; % D = 45 – число, сумма эл-ов матрицы А
E = A’; % E – транспонированная матрица А
F = inv(A); % F – обратная матрица А
G = A^-1; % G – обратная матрица А

Из приведенного примера видно, что операция транспонирования матриц и векторов обозначается символом ‘ (апостроф), который ставится после имени вектора или матрицы. Вычисление обратной матрицы можно делать путем вызова функции inv() или возводя матрицу в степень -1. Результат в обоих случаях будет одинаковым, а два способа вычисления сделано для удобства использования при реализации различных алгоритмов.

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

.* - поэлементное умножение;
./ и .\ - поэлементные деления;
.^ - поэлементное возведение в степень.

Рассмотрим работу данных операторов на следующем примере.

a = [1 2 3]; % вектор-строка
b = [3 2 1]; % вектор-строка
c = a.*b; % c = [3 4 3]
A = ones(3); % матрица 3х3, состоящая из единиц
B = [1 2 3;4 5 6; 7 8 9]; % матрица 3х3
C = A.*B; % матрица 3х3, состоящая из
D = A./B; % матрица 3х3, состоящая из
E = A.\B; % матрица 3х3, состоящая из
F = A.^2; % возведение элементов матрицы А в квадрат

В заключении данного параграфа рассмотрим несколько функций полезных при работе с векторами и матрицами.

Для поиска максимального значения элемента вектора используется стандартная функция max(), которая возвращает найденное максимальное значение элемента и его позицию (индекс):

a = [1 6 3 4];
[v, i] = max(a); % v = 6, i = 2;

или

v = max(a); % v = 6;

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

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

A = [4 3 5; 6 7 2; 3 1 8];
[V, I] = max(A); % V=[6 7 8], I = [2 2 3]
V = max(A); % V=[6 7 8]

Полный синтаксис функции max() можно узнать, набрав в командном окне MatLab команду

help<название функции>

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

Другой полезной функцией работы с матрицами и векторами является функция sum(), которая вычисляет сумму значений элементов вектора или столбцов матрицы:

a = [3 5 4 2 1];
s = sum(a); % s = 3+5+4+2+1=15
A = [4 3 5; 6 7 2; 3 1 8];
S1 = sum(A); % S1=[13 11 15]
S2 = sum(sum(A)); % S2=39

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

Для сортировки значений элементов вектора или матрицы по возрастанию или убыванию используется функция sort() следующим образом:

a = [3 5 4 2 1];

b1 = sort(a); % b1=[1 2 3 4 5]
b2 = sort(a, ‘descend’); % b2=[5 4 3 2 1]
b3 = sort(a, ‘ascend’); % b3=[1 2 3 4 5]

дляматриц

A = [4 3 5; 6 7 2; 3 1 8];
B1 = sort(A); % B1=[3 1 2
% 4 3 5
% 6 7 8]
B2 = sort(A, ‘descend’); % B2=[6 7 8
% 4 3 5
% 3 1 2]

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

a = [3 5 4 2 1];
b1 = find(a == 2); % b1 = 4 – индексэлемента 2
b2 = find(a ~= 2); % b2 = [1 2 3 5] – индексыбез 2
b3 = find(a > 3); % b3 = [2 3]

В приведенном примере символ ‘==’ означает проверку на равенство, а символ ‘~=’ выполняет проверку на неравенство значений элементов вектора а. Более подробно об этих операторах будет описано в разделе условные операторы.

Еще одной полезной функцией работы с векторами и матрицами является функция mean() для вычисления среднего арифметического значения, которая работает следующим образом:

a = [3 5 4 2 1];
m = mean(a); % m = 3
A = [4 3 5; 6 7 2; 3 1 8];
M1 = mean(A); % M1 = [4.333 3.667 5.000]
M2 = mean(mean(A)); % M2 = 4.333

Определение.

Транспонирование матрицы - это операция над матрицей, при которой ее строки и столбцы меняются местами:

a^T_ij = a_ji

Свойства транспонированной матрицы

• Если матрица A имеет размер n×m, то транспонированная матрица A^T имеет размер m×n;
• (A^T)^T = A;
• (k · A)^T = k · A^T;
• (A + B)^T = A^T + B^T;
• (A · B)^T = B^T · A^T.