Алгоритам за множење матрица-вектор. Множење на матрици: примери, алгоритам на дејства, својства на производот

Во системот MatLab, прилично е едноставно да се извршат математички операции на матрици и вектори. Прво да разгледаме едноставни операции на собирање и множење на матрици и вектори. Нека се дадени два вектори

a = ; % вектор на ред
b = ; % колона вектор

тогаш множењето на овие два вектори може да се запише на следниов начин

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

Во согласност со операциите на вектори, со множење на вектор на ред со вектор на колона се добива број, а со множење на вектор на колона со вектор на ред се добива дводимензионална матрица, која е резултат на пресметките во горниот пример, т.е.

Собирањето и одземањето на два вектори се пишува на следниов начин:

a1 = ;
a2 = ;
c = a1+a2; % c = ;
c = a2-a1; % c = ;

Забележете дека операциите за собирање и одземање може да се изведат помеѓу два вектори на колони или вектори на два реда. Во спротивно, MatLab ќе прикаже порака за грешка, бидејќи Не може да се додадат вектори од различни типови. Ова е случај со сите нелегални аритметички операции: ако не можат да се пресметаат, MatLab ќе пријави грешка и програмата ќе заврши на соодветната линија.

Операциите за множење и собирање помеѓу матриците се изведуваат на сличен начин:

A = ;
B = оние (3);
C = A+B; % додавање на две матрици со иста големина
D = A+5; % собирање на матрица и број
E = A*B; % множење на матрицата А со Б
F = B*A; % множење на матрицата Б со А
G = 5*A; % множење матрица со број

Операциите за пресметување на инверзната матрица, како и транспонирање на матрици и вектори, се напишани на следниов начин:

a = ; % вектор на ред
b = a’; % колона вектор формиран од
% со транспонирање на векторот на ред а.
A = ; % 3x3 елемент матрица
B = a*A; %B = – вектор на ред
C = A*b; %C = – вектор на колона
D = a*A*a’; % D = 45 – број, збир на елементи од матрицата А
E = A'; % E – транспонирана матрица А
F = inv(A); % F – инверзна матрица А
G = A^-1; % G – инверзна матрица А

Од горенаведениот пример е јасно дека операцијата на транспонирање на матрици и вектори е означена со симболот „ (апостроф), кој се става по името на векторот или матрицата. Пресметувањето на инверзната матрица може да се направи со повикување на функцијата inv() или со подигање на матрицата на -1 моќност. Резултатот и во двата случаи ќе биде ист, а направени се два методи на пресметка за полесно користење при имплементирање на различни алгоритми.

Ако во процесот на пресметки е неопходно да се множат, делат или подигнат елементи на вектор или матрица елемент по елемент, тогаш за ова се користат следните оператори:

.* - множење според елементот;
./ и.\ - поделби елемент по елемент;
.^ - степенување според елементот.

Ајде да погледнеме како функционираат овие оператори користејќи го следниов пример.

a = ; % вектор на ред
b = ; % вектор на ред
c = a.*b; %c=
A = оние (3); % 3x3 матрица составена од едни
B = ; % 3x3 матрица
C = A.*B; % 3x3 матрица која се состои од
D = A./B; % 3x3 матрица која се состои од
E = A.\B; % 3x3 матрица која се состои од
F = A.^2; % квадратирање на елементите на матрицата А

За да го завршиме овој дел, ќе разгледаме неколку функции корисни при работа со вектори и матрици.

За да ја пронајдете максималната вредност на векторскиот елемент, користете ја стандардната функција max(), која ја враќа пронајдената максимална вредност на елементот и неговата позиција (индекс):

a = ;
= max(a); % v = 6, i = 2;

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

Горенаведениот пример покажува два различни начини за повикување на функцијата max(). Во првиот случај, се одредуваат и максималната вредност на елементот и неговиот индекс во векторот, а во вториот - само максималната вредност на елементот.

Во случај на матрици, оваа функција ги одредува максималните вредности што стојат во колоните, како што е прикажано во примерот подолу:

A = ;
= max(A); %V=,I=
V = max(A); %V=

Целосната синтакса на функцијата max() може да се најде со внесување на командата во командниот прозорец MatLab

помош<название функции>

Функцијата min() работи на сличен начин, која ја одредува минималната вредност на елементот на вектор или матрица и неговиот индекс.

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

a = ;
s = збир (а); % s = 3+5+4+2+1=15
A = ;
S1 = збир (A); %S1=
S2 = збир (збир (А)); % S2=39

При пресметување на збирот S2, збирот на вредностите на елементите на матрицата А прво се пресметува во колони, а потоа во редови. Како резултат на тоа, променливата S2 го содржи збирот на вредностите на сите елементи на матрицата А.

За да ги подредите вредностите на елементите на вектор или матрица во растечки или опаѓачки редослед, користете ја функцијата sort() на следниов начин:

a = ;

b1 = сорт(а); %b1=
b2 = подредување (a, „спуштање“); %b2=
b3 = подредување (a, „искачување“); %b3=

за матрици

A = ;
B1 = подредување (А); %B1=
B2 = подредување (А, „спуштање“); %B2=

Во многу практични проблеми, честопати треба да пронајдете специфичен елемент во вектор или матрица. Ова може да се направи со помош на стандардната функција find(), која како аргумент го зема условот според кој се наоѓаат бараните елементи, на пример:

a = ;
b1 = најдете(a == 2); % b1 = 4 – индекс на елементот 2
b2 = најдете(a ~= 2); % b2 = – индекси без 2
b3 = find(a > 3); % b3 =

Во дадениот пример, симболот „==“ значи проверка за еднаквост, а симболот „~=“ проверува за нееднаквост на вредностите на елементите на векторот a. Овие оператори ќе бидат подетално опишани во делот Условни оператори.

Друга корисна функција за работа со вектори и матрици е функцијата mean() за пресметување на аритметичката средина, која работи на следниов начин:

a = ;
m = средна вредност (а); % m = 3
A = ;
M1 = средна вредност (A); % M1 =
M2 = средна (средна (A)); % М2 = 4,333

Производот на матрицата (C = AB) е операција само за совпаднати матрици A и B, во кои бројот на колони од матрицата А е еднаков на бројот на редови од матрицата B:

C ⏟ m × n = A ⏟ m × p × B ⏟ p × n

Пример 1

Дадени матрици:

• A = a (i j) со димензии m × n;
• B = b (i j) со димензии p × n

Матрица C, чии елементи c i j се пресметуваат со следнава формула:

c i j = a i 1 × b 1 j + a i 2 × b 2 j + . . . + a i p × b p j, i = 1,. . . m, j = 1, . . . м

Пример 2

Да ги пресметаме производите AB=BA:

A = 1 2 1 0 1 2 , B = 1 0 0 1 1 1

Решение со користење на правилото за множење на матрицата:

A ⏟ 2 × 3 × B ⏟ 3 × 2 = 1 2 1 0 1 2 × 1 0 0 1 1 1 = 1 × 1 + 2 × 0 + 1 × 1 1 × 0 + 2 × 1 + 1 × 1 0 × 1 + 1 × 0 + 2 × 1 0 × 0 + 1 × 1 + 2 × 1 = = 2 3 2 3 ⏟ 2 × 2

B ⏟ 3 × 2 × A ⏟ 2 × 3 = 1 0 0 1 1 1 × 1 2 1 0 1 2 = 1 × 1 + 0 × 0 1 × 2 + 0 × 1 1 × 1 + 0 × 2 0 × 1 + 1 × 0 0 × 2 + 1 × 1 0 × 1 + 1 × 2 1 × 1 + 1 × 0 1 × 2 + 1 × 1 1 × 1 + 1 × 2 = 1 2 1 0 1 2 1 3 3 ⏟ 3×3

Производот A B и BA A се најдени, но тие се матрици со различни големини: A B не е еднаков на BA A.

Својства на множење на матрицата

Својства на множење на матрицата:

• (A B) C = A (B C) - асоцијативност на множење на матрицата;
• A (B + C) = A B + A C - дистрибутивност на множење;
• (A + B) C = A C + B C - дистрибутивност на множење;
• λ (A B) = (λ A) B

Ајде да го провериме имотот бр. 1: (A B) C = A (B C) :

(A × B) × A = 1 2 3 4 × 5 6 7 8 × 1 0 0 2 = 19 22 43 50 × 1 0 0 2 = 19 44 43 100,

A (B × C) = 1 2 3 4 × 5 6 7 8 1 0 0 2 = 1 2 3 4 × 5 12 7 16 = 19 44 43 100.

Пример 2

Да го провериме својството бр. 2: A (B + C) = A B + A C:

A × (B + C) = 1 2 3 4 × 5 6 7 8 + 1 0 0 2 = 1 2 3 4 × 6 6 7 10 = 20 26 46 58,

A B + A C = 1 2 3 4 × 5 6 7 8 + 1 2 3 4 × 1 0 0 2 = 19 22 43 50 + 1 4 3 8 = 20 26 46 58.

Производ од три матрици

Производот на три матрици A B C се пресметува на 2 начини:

• најдете A B и множете се со C: (A B) C;
• или прво најдете B C, а потоа помножете A (B C).

Множете ги матриците на 2 начини:

4 3 7 5 × - 28 93 38 - 126 × 7 3 2 1

Алгоритам на дејства:

• најдете производ од 2 матрици;
• потоа повторно пронајдете го производот од 2 матрици.

1). A B = 4 3 7 5 × - 28 93 38 - 126 = 4 (- 28) + 3 × 38 4 × 93 + 3 (- 126) 7 (- 28) + 5 × 38 7 × 93 + 5 (- 126 ) = 2 - 6 - 6 21

2). A B C = (A B) C = 2 - 6 - 6 21 7 3 2 1 = 2 × 7 - 6 × 2 2 × 3 - 6 × 1 - 6 × 7 + 21 × 2 - 6 × 3 + 21 × 1 = 2 0 0 3 .

Ја користиме формулата A B C = (A B) C:

1). B C = - 28 93 38 - 126 7 3 2 1 = - 28 × 7 + 93 × 2 - 28 × 3 + 93 × 1 38 × 7 - 126 × 2 38 × 3 - 126 × 1 = 2 - 14 -1

2). A B C = (A B) C = 7 3 2 1 - 10 9 14 - 12 = 4 (- 10) + 3 × 14 4 × 9 + 3 (- 12) 7 (- 10) + 5 × 14 7 × 9 + 5 (- 12) = 2 0 0 3

Одговор: 4 3 7 5 - 28 93 38 - 126 7 3 2 1 = 2 0 0 3

Множење на матрица со број

Производот на матрицата А по број k е матрицата B = A k со иста големина, која се добива од првобитната со множење на сите нејзини елементи со даден број:

b i, j = k × a i, j

Својства на множење матрица со број:

• 1 × А = А
• 0 × A = нулта матрица
• k (A + B) = k A + k B
• (k + n) A = k A + n А
• (k × n) × A = k (n × A)

Да го најдеме производот на матрицата A = 4 2 9 0 на 5.

5 A = 5 4 2 9 0 5 × 4 5 × 2 5 × 9 5 × 0 = 20 10 45 0

Множење на матрица со вектор

За да го пронајдете производот на матрица и вектор, треба да множите користејќи го правилото „ред по колона“:

• ако помножите матрица со вектор на колона, бројот на колони во матрицата мора да одговара на бројот на редови во векторот на колоната;
• Резултатот од множење на вектор на колона е само вектор на колона:

A B = a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋯ ⋯ ⋯ ⋯ a m 1 a m 2 ⋯ a m n b 1 b 2 ⋯ b 1 n = a 11 × 1 b 2 × b + a 1 n × b n a 21 × b 1 + a 22 × b 2 + ⋯ + a 2 n × b n ⋯ ⋯ ⋯ ⋯ a m 1 × b 1 + a m 2 × b 2 + ⋯ + a m n × b n = c 1 м

• ако помножите матрица со вектор на ред, тогаш матрицата што се множи мора да биде исклучиво вектор на колона, а бројот на колони мора да одговара на бројот на колони во векторот на редови:

A B = a a ⋯ a b b ⋯ b = a 1 × b 1 a 1 × b 2 ⋯ a 1 × b n a 2 × b 1 a 2 × b 2 ⋯ a 2 × b n ⋯ ⋯ ⋯ ⋯ a n × b a n × b n = c 11 c 12 ⋯ c 1 n c 21 c 22 ⋯ c 2 n ⋯ ⋯ ⋯ ⋯ c n 1 c n 2 ⋯ c n n

Пример 5

Да го најдеме производот на матрицата А и векторот на колоната B:

A B = 2 4 0 - 2 1 3 - 1 0 1 1 2 - 1 = 2 × 1 + 4 × 2 + 0 × (- 1) - 2 × 1 + 1 × 2 + 3 × (- 1) - 1 × 1 + 0 × 2 + 1 × (- 1) = 2 + 8 + 0 - 2 + 2 - 3 - 1 + 0 - 1 = 10 - 3 - 2

Пример 6

Да го најдеме производот на матрицата А и векторот на редот Б:

A = 3 2 0 - 1, B = - 1 1 0 2

A B = 3 2 0 1 × - 1 1 0 2 = 3 × (- 1) 3 × 1 3 × 0 3 × 2 2 × (- 1) 2 × 1 2 × 0 2 × 2 0 × (- 1) 0 × 1 0 × 0 0 × 2 1 × (- 1) 1 × 1 1 × 0 1 × 2 = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2

Одговор: A B = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2

Доколку забележите грешка во текстот, означете ја и притиснете Ctrl+Enter

Секој вектор може да се замисли како матрица со една колона или еден ред. Матрицата со една колона ќе ја наречеме вектор на колона, а матрицата со еден ред вектор на ред.

Ако A е матрица со големина m*n, тогаш векторот на колоната b има големина n, а векторот на редот b има големина m.

Така, за да множиме матрица со вектор, векторот мора да го сметаме како вектор на колона. Кога се множи вектор со матрица, тој мора да се третира како вектор на ред.

Множење на матрица

до комплексен вектор

Го добиваме резултатот

Како што можете да видите, со непроменета векторска димензија, можеме да имаме две решенија.

Би сакал да го привлечам вашето внимание на фактот дека матрицата во првата и втората верзија, и покрај истите вредности, се сосема различни (имаат различни димензии)

Во првиот случај, векторот се смета како колона и тогаш е неопходен множи матрица со вектор, а во вториот случај имаме вектор на ред и потоа имаме производ на вектор и матрица.

Овој бот исто така множи вектори и матрици кои имаат сложени вредности. Врз основа на поцелосен калкулатор: Множење на матрици со сложени вредности онлајн

Својства на множење матрица-вектор

Матрица

Векторска колона

Вектор на ред

Произволен број

1. Производот на матрицата со збирот на вектори на колоните е еднаков на збирот на производите на матрицата по секој од векторите

2. Производот од збирот на вектори на редови и матрицата е еднаков на збирот на производите на вектори и матрицата

3. Заедничкиот фактор на вектор може да се земе надвор од производот на матрицата со вектор/вектор по матрица

4. Производот на вектор на ред и производ на матрица и вектор на колона е еквивалентен на производот од производот на вектор на ред и матрица и вектор на колона.

Предавање 6. Паралелни нумерички алгоритми за решавање типични проблеми од пресметковната математика: множење на матрици.

Множење на матрица со вектор. Постигнување на највисоки можни перформанси. Искористување на паралелизам на средно ниво. Организација на паралелно пресметување при p = n. Употреба на ограничен сет на процесори. Множење на матрицата. Макрооперативна анализа на алгоритми за решавање проблеми. Организација на паралелизам врз основа на споделување податоци.

Множење на матрица со вектор

Проблемот на множење на матрица со вектор е дефиниран со релациите

Така, добивањето на добиениот вектор вклучува повторување на слични операции на множење на редовите на матрицата и векторот. Добивањето на секоја таква операција вклучува елементарно множење на елементите од редот на матрицата и векторот и последователно собирање на добиените производи. Вкупниот број на потребни скаларни операции се проценува според количината

Како што следува од дејствата што се вршат при множење на матрица и вектор, може да се добијат паралелни методи за решавање на проблемот врз основа на алгоритми за паралелно собирање (види став 4.1). Во овој дел, анализата на методите на паралелизација ќе биде дополнета со разгледување на прашањата за организирање на паралелно пресметување во зависност од бројот на процесори достапни за употреба. Дополнително, користејќи го примерот на проблемот со множење на матрица со вектор, ќе се привлече вниманието на потребата да се избере најсоодветната топологија на компјутерскиот систем (постоечките канали за комуникација помеѓу процесорите) за да се намалат трошоците за организирање на интерпроцесорска интеракција.

Постигнување на највисоки можни перформанси ()

Ајде да ги анализираме зависностите на информациите во алгоритмот за множење матрица-вектор за да избереме можни методи на паралелизација. Како што можете да видите, операциите на множење на поединечни редови на матрица со вектор извршени за време на пресметките се независни и можат да се вршат паралелно;

Множењето на секоја редица со вектор вклучува независни операции за множење според елементите и исто така може да се изведуваат паралелно;

Збирот на добиените производи во секоја операција на множење матрична редица со вектор може да се изврши со користење на една од претходно разгледаните варијанти на алгоритмот за сумирање (секвенцијален алгоритам, конвенционални и модифицирани каскадни шеми).

Така, максималниот потребен број на процесори се одредува според вредноста

Употребата на таков број на процесори може да се претстави на следниов начин. Многу процесори се поделени во групи

,

од кои секој претставува збир на процесори за извршување на операцијата на множење на поединечен ред од матрицата со вектор. На почетокот на пресметките, еден ред елемент од матрицата и соодветен елемент на векторот се испраќаат до секој процесор во групата. Следно, секој процесор врши операција за множење. Последователните пресметки потоа се вршат со помош на шема за каскадно сумирање. За илустрација на Сл. 6.1 ја прикажува пресметковната шема за процесорите на група со матрична димензија од .

Ориз. 6.1. Пресметковна шема за множење матрица ред со вектор

Времето на извршување на паралелен алгоритам при користење на процесори се определува со времето на извршување на операцијата паралелно множење и времето на извршување на каскадното коло

Како резултат на тоа, индикаторите за ефикасност на алгоритмот се одредуваат со следните односи:

, ,

За проблемот на множење матрица-вектор што се разгледува, најсоодветни топологии се структурите кои обезбедуваат брз пренос на податоци (патеки со должина на единицата) во коло за каскадно собирање (види Сл. 4.5). Ваквите топологии се структура со целосен систем на врски ( комплетен график) И хиперкоцка. Другите топологии доведуваат до зголемено време на комуникација поради подолгите правци за пренос на податоци. Така, со линеарно подредување на процесори со систем на врски само со најблиските соседи лево и десно ( владетелили прстен) за каскадна шема, должината на преносната патека на секој примен делумен збир при повторување, , е еднаква на . Ако претпоставиме дека преносот на податоци по должина на патеката во топологии со линеарна структура бара операции за пренос на податоци, вкупниот број на паралелни операции (вкупно времетраење на патеките) на преносот на податоци се определува со вредноста

(со исклучок на пренос на податоци за почетно вчитување на процесорите).

Примена на компјутерски систем со правоаголна топологија дводимензионална решеткаголемината води до едноставно и јасно толкување на пресметките што се вршат (структурата на мрежата одговара на структурата на обработените податоци). За таква топологија, најпрепорачливо е да се постават редовите на матрицата по хоризонталните решетки; во овој случај, елементите на векторот мора да бидат распределени по вертикалите на компјутерскиот систем. Пресметките со овој распоред на податоци може да се вршат паралелно по линиите на мрежата; како резултат на тоа, вкупниот број на пренос на податоци се совпаѓа со резултатите за линијар().

Комуникациските дејства што се вршат при решавање на дадена задача се состојат од пренос на податоци помеѓу парови MCS процесори. Детална анализа на времетраењето на спроведувањето на таквите операции е направена во став 3.3.

4. Препораки за спроведување на паралелен алгоритам. При спроведување на паралелен алгоритам, препорачливо е да се истакне почетната фаза на вчитување на користените процесори со почетни податоци. Наједноставно, таквата иницијализација е обезбедена со топологија на компјутерски систем со топологија во форма комплетен график(преземањето е обезбедено со користење на една паралелна операција за пренос на податоци). При организирање на многу процесори во форма хиперкоцкаМоже да биде корисно да се има контрола на две нивоа на процесот на подигање, во кој централниот контролен процесор гарантира дека матричните и векторските редови се испраќаат до контролните процесори на процесорските групи, кои, пак, ги испраќаат елементите на матрицата и векторски редови до извршните процесори. За топологии во форма владетелиили прстенибара секвенцијални операции за пренос на податоци со сукцесивно намалување на количината на податоци пренесени од до елементи.

Користење на паралелизам на средно ниво()

1. Избор на метод на паралелно пресметување. Кога расположливиот број на користени процесори () се намалува, вообичаената шема на каскадно сумирање при извршување на операции за множење матрични редови по вектор станува неприменлива. За да ја поедноставиме презентацијата на материјалот, да претпоставиме и користиме изменета каскадна шема. Почетното оптоварување на секој процесор во овој случај се зголемува и процесорот се вчитува () со делови од редовите на матрицата и векторот. Времето на извршување на операцијата за множење матрица со вектор може да се процени како

При користење на бројот на процесори потребни за спроведување на изменетата каскадна шема, т.е. во , овој израз дава проценка на времето на извршување (на ).

Кога бројот на процесори е , кога времето на извршување на алгоритмот се проценува како , може да се предложи нова шема за паралелно извршување на пресметките, во која за секое повторување на каскадно сумирање, множества на процесори кои не се преклопуваат. Со овој пристап, достапниот број на процесори се покажува како доволен за да се имплементира само една операција на множење матрична редица и вектор. Дополнително, при извршувањето на следната итерација на каскадно сумирање, процесорите одговорни за извршување на сите претходни повторувања се бесплатни. Сепак, овој недостаток на предложениот пристап може да се претвори во предност со користење на неактивен процесори за обработка на следните редови од матрицата. Како резултат на тоа, може да се формира следнава шема транспортервршење матрица и векторско множење:

Збир на процесори е поделен на различни процесорски групи

,

во овој случај, групата , , се состои од процесори и се користи за извршување на повторувања на каскадниот алгоритам (групата се користи за имплементирање на множење според елементите); вкупен број на процесори;

Иницијализирањето на пресметките се состои од вчитување елемент по елемент на процесорите на групата со вредностите на 1 ред од матрицата и векторот; по првичното вчитување, се врши паралелна операција на множење според елементите и последователна имплементација на вообичаеното коло за каскадно собирање;

При извршувањето на пресметките, секој пат по завршувањето на операцијата за множење според елементите, процесорите на групата се оптоваруваат со елементи од следниот ред на матрицата и се започнува процесот на пресметување за ново вчитаните податоци.

Како резултат на примената на опишаниот алгоритам, многу процесори имплементираат цевковод за извршување на операцијата за множење матрична редица со вектор. На таков транспортер може истовремено да има неколку одделни редови на матрицата во различни фази на обработка. Така, на пример, по елементарно множење на елементите од првиот ред и векторот, процесорите од групата ќе ја извршат првата итерација на каскадниот алгоритам за првиот ред од матрицата, а процесорите од групата ќе изврши елементарно множење на вредностите од вториот ред од матрицата, итн. За илустрација на Сл. 6.2 ја прикажува состојбата на процесот на пресметување по 2 повторувања на гасоводот во .

Ориз. 6.2. Состојба на цевководот за операција на множење матрична реда со вектор по завршување на 2 повторувања

2. Евалуација на индикаторите за изведба на алгоритам. Множењето на првиот ред по вектор според каскадната шема ќе се заврши како и обично по извршувањето на () паралелни операции. За другите редови - во согласност со шемата на гасоводот за организирање на пресметки - појавата на резултатите од множењето на секој следен ред ќе се појави по завршувањето на секоја наредна итерација на гасоводот. Како резултат на тоа, вкупното време на извршување на операцијата за множење матрица-вектор може да се изрази како

Оваа проценка е малку подолго од времето на извршување на паралелниот алгоритам опишан во претходниот став (), меѓутоа, новопредложениот метод бара помалку пренесени податоци (векторот се испраќа само еднаш). Дополнително, употребата на цевководна шема резултира со порано појавување на некои од пресметковните резултати (што може да биде корисно во голем број ситуации на обработка на податоци).

Како резултат на тоа, индикаторите за ефикасност на алгоритмот се одредуваат со следните односи:

3. Избор на топологија на компјутерскиот систем. Соодветната топологија на компјутерскиот систем е целосно одредена од компјутерското коло - ова е комплетно бинарно дрвовисина Бројот на пренос на податоци со таква мрежна топологија се определува со вкупниот број на повторувања извршени од гасоводот, т.е.

.

Иницијализирањето на пресметките започнува со лисјата на дрвото, резултатите од сумирањето се акумулираат во коренскиот процесор.

Анализата на сложеноста на извршените комуникациски дејства за компјутерските системи со други топологии на интерпроцесорски комуникации треба да се изврши како независна задача (види и клаузула 3.4).

Организација на паралелно пресметување во

1. Избор на метод на паралелно пресметување. Кога се користат процесори за множење матрица со вектор, може да се користи паралелниот алгоритам за множење ред по ред, претходно дискутиран во прирачникот, во кој редовите од матрицата се распределуваат меѓу процесорите ред по ред и секој процесор имплементира операцијата на множење на која било поединечна редица од матрицата со вектор. Друг можен начин за организирање на паралелно пресметување може да биде градењето цевководно коло за операција на множење матрична редица со вектор(скаларен производ на вектори) со подредување на сите достапни процесори во линеарна низа ( владетели).

Таквата шема за пресметка може да се дефинира на следниов начин. Ајде да го замислиме множеството процесори како линеарна низа (види Сл. 4.7):

Секој процесор, , се користи за множење на елементите на матрична колона и векторски елемент. Извршувањето на пресметките на секој процесор , , е како што следува:

Се бара следниот елемент од матричната колона;

Елементите и се множат;

Се бара резултат од пресметките на претходниот процесор;

Вредностите се додаваат;

Добиениот резултат се испраќа до следниот процесор.

Ориз. 6.3. Состојба на линеарниот цевковод за операција на множење матрична редица со вектор по извршување на две повторувања

При иницијализирање на опишаната шема, мора да извршите голем број дополнителни дејства:

При извршувањето на првата итерација, секој процесор дополнително бара елемент од векторот;

За да се синхронизираат пресметките (при извршување на следното повторување на колото, се бара пресметковниот резултат на претходниот процесор) во фазата на иницијализација, процесорот, , врши () циклус на чекање.

Дополнително, за хомогеноста на опишаното коло за првиот процесор, кој нема претходен процесор, препорачливо е да се воведе операција за празно додавање ( ).

За илустрација на Сл. Слика 6.3 ја прикажува состојбата на процесот на пресметување по втората итерација на цевководот во .

2. Евалуација на индикаторите за изведба на алгоритам. Множењето на првиот ред со векторот според опишаната шема на гасоводот ќе биде завршено по извршувањето на () паралелни операции. Резултатот од множењето на следните линии ќе се појави по завршувањето на секоја следна итерација на гасоводот (потсетете се дека повторувањето на секој процесор вклучува извршување на операции за множење и собирање). Како резултат на тоа, вкупното време на извршување на операцијата за множење матрица-вектор може да се изрази како:

Оваа проценка е исто така поголема од минималното можно време на извршување на паралелниот алгоритам во . Корисноста од користењето на шемата за пресметување на гасоводот е, како што беше забележано во претходниот став, во намалувањето на количината на пренесените податоци и во претходното појавување на некои од пресметковните резултати.

Индикаторите за ефикасност на оваа пресметковна шема се одредуваат со односите:

, ,

3. Избор на топологија на компјутерскиот систем. Потребната топологија на компјутерскиот систем за извршување на опишаниот алгоритам е уникатно одредена со предложената пресметковна шема - ова е линеарно подреден сет на процесори ( владетел).

Користење на ограничен сет на процесори ()

1. Избор на метод на паралелно пресметување. Со намалување на бројот на процесори до вредност, може да се добие паралелна пресметковна шема за множење матрица-вектор со прилагодување на алгоритмот за множење ред по ред. Во овој случај, каскадното коло за сумирање на резултатите од множењето според елементите дегенерира и операцијата за множење матрична редица со вектор целосно се изведува на еден процесор. Пресметковната шема добиена со овој пристап може да се специфицира на следниов начин:

Векторски и матрични редови се испраќаат до секој од достапните процесори;

Изведувањето на операција за множење на редови матрица-вектор се изведува со користење на конвенционален секвенцијален алгоритам.

Треба да се забележи дека големината на матрицата може да не е повеќекратна од бројот на процесори и тогаш матричните редови не можат да се поделат подеднакво меѓу процесорите. Во овие ситуации, можете да отстапите од барањето за униформно вчитување на процесорите и, за да добиете поедноставна пресметковна шема, да го прифатите правилото дека податоците се ставаат на процесорите само ред по ред (т.е., елементите од еден ред од матрицата не можат да се подели на неколку процесори). Нееднаков број на редови доведува до различно пресметковно оптоварување на процесорите; Така, завршувањето на пресметките (вкупното времетраење на решавањето на проблемот) ќе се определи со времето на работа на најоптоварениот процесор (во овој случај, дел од ова вкупно време, поединечните процесори може да бидат неактивен поради исцрпување на нивниот удел на пресметки). Нерамномерното оптоварување на процесорите ја намалува ефикасноста на користењето на MCS и, како резултат на разгледување на овој пример, можеме да заклучиме дека проблем со балансирање

3. Избор на топологија на компјутерскиот систем. Во согласност со природата на интерпроцесорските интеракции извршени во предложената пресметковна шема, организацијата на процесорите во форма на ѕвезди(види Сл. 1.1). Контролен процесор на таква топологија може да се користи за вчитување на компјутерските процесори со почетни податоци и за примање на резултатите од извршените пресметки.

Множење на матрицата

Проблемот на множење матрица-матрица е дефиниран со релациите

.

(за поедноставна презентација, ќе претпоставиме дека множените матрици и се квадратни и имаат ред ).

Анализата на можните методи за паралелно извршување на оваа задача може да се изврши по аналогија со разгледување на проблемот на множење на матрица со вектор. Оставајќи ја ваквата анализа за независно проучување, ќе го искористиме примерот на проблемот со множење на матрицата за да покажеме употреба на неколку општи пристапи кои ни овозможуваат да формираме паралелни методи за решавање на сложени проблеми.

Така, во претходната лекција ги разгледавме правилата за собирање и одземање матрици. Ова се толку едноставни операции што повеќето студенти ги разбираат буквално веднаш.

Сепак, рано се радувате. Бесплатата заврши - да преминеме на множење. Веднаш ќе ве предупредам: множењето две матрици воопшто не е множење броеви во ќелиите со исти координати, како што можеби мислите. Сè е многу позабавно овде. И ќе треба да започнеме со прелиминарни дефиниции.

Соодветни матрици

Една од најважните карактеристики на матрицата е нејзината големина. Веќе сме зборувале за ова сто пати: пишувањето $A=\left[ m\times n \right]$ значи дека матрицата има точно $m$ редови и $n$ колони. Веќе разговаравме како да не ги мешаме редовите со колоните. Нешто друго е важно сега.

Дефиниција. Матрици од формата $A=\left[ m\times n \right]$ и $B=\left[n\times k \right]$, во кои бројот на колони во првата матрица се совпаѓа со бројот на редови во втората, се нарекуваат конзистентни.

Уште еднаш: бројот на колони во првата матрица е еднаков на бројот на редови во втората! Од тука добиваме два заклучоци одеднаш:

1. Редоследот на матриците ни е важен. На пример, матриците $A=\лево[ 3\пати 2 \десно]$ и $B=\лево[ 2\пати 5 \десно]$ се конзистентни (2 колони во првата матрица и 2 редови во втората) , но обратно - матриците $B=\left[ 2\times 5 \right]$ and $A=\left[ 3\times 2 \right]$ веќе не се конзистентни (5 колони во првата матрица не се 3 реда во втората).
2. Доследноста може лесно да се провери со запишување на сите димензии една по друга. Користејќи го примерот од претходниот пасус: „3 2 2 5“ - во средината има идентични броеви, така што матриците се конзистентни. Но, „2 5 3 2“ не се конзистентни, бидејќи има различни бројки во средината.

Дополнително, капетанот Очигледност се чини дека навестува дека квадратните матрици со иста големина $\left[n\times n \десно]$ секогаш се конзистентни.

Во математиката, кога е важен редоследот на наведување на објекти (на пример, во дефиницијата дискутирана погоре, редоследот на матриците е важен), често зборуваме за подредени парови. Ги запознавме уште во училиште: мислам дека не е паметно што координатите $\left(1;0 \десно)$ и $\left(0;1 \десно)$ дефинираат различни точки на рамнината.

Значи: координатите се подредени и парови кои се составени од броеви. Но, ништо не ве спречува да направите таков пар од матрици. Потоа можеме да кажеме: „Реден пар матрици $\left(A;B \десно)$ е конзистентен ако бројот на колони во првата матрица е ист со бројот на редови во втората.

Па, што?

Дефиниција за множење

Размислете за две конзистентни матрици: $A=\left[ m\times n \десно]$ и $B=\left[n\times k \десно]$. И ние ја дефинираме операцијата за множење за нив.

Дефиниција. Производот на две совпаднати матрици $A=\left[ m\times n \right]$ и $B=\left[n\times k \right]$ е новата матрица $C=\left[ m\times k \ десно] $, чии елементи се пресметуваат со формулата:

\[\ почеток (порамни) & ((c)_(i;j))=((a)_(i;1))\cdot ((b)_(1;j))+((a)_ (i;2))\cdot ((b)_(2;j))+\ldots +((a)_(i;n))\cdot ((b)_(n;j))= \\ & =\sum\limits_(t=1)^(n)((a)_(i;t))\cdot ((b)_(t;j))) \end(порамни)\]

Таков производ се означува на стандарден начин: $C=A\cdot B$.

Оние кои ја гледаат оваа дефиниција за прв пат веднаш имаат две прашања:

1. Каква жестока игра е ова?
2. Зошто е толку тешко?

Па, прво прво. Да почнеме со првото прашање. Што значат сите овие индекси? И како да не се прават грешки кога работите со вистински матрици?

Најпрво забележуваме дека долгата линија за пресметување $((c)_(i;j))$ (специјално ставив точка-запирка помеѓу индексите за да не се мешам, но нема потреба да ги ставам во општо - јас самиот се изморив да ја пишувам формулата во дефиницијата) всушност се сведува на едноставно правило:

1. Земете го $i$th ред во првата матрица;
2. Земете ја колоната $j$th во втората матрица;
3. Добиваме две низи од броеви. Ние ги множиме елементите на овие низи со исти броеви, а потоа ги додаваме добиените производи.

Овој процес е лесно да се разбере од сликата:

Уште еднаш: го поправаме редот $i$ во првата матрица, колоната $j$ во втората матрица, множиме елементи со истите броеви, а потоа ги додаваме добиените производи - добиваме $((c)_(ij))$ . И така натаму за сите $1\le i\le m$ и $1\le j\le k$. Оние. Ќе има $m\times k$ од такви „перверзии“ вкупно.

Всушност, веќе наидовме на множење на матрици во училишната програма, само во значително намалена форма. Нека се дадени векторите:

\[\begin(порамни) & \vec(a)=\left(((x)_(a));((y)_(a));((z)_(a)) \десно); \\ & \overrightarrow(b)=\left(((x)_(b));((y)_(b));((z)_(b)) \десно). \\ \крај (порамни)\]

Тогаш нивниот скаларен производ ќе биде токму збирот на парните производи:

\[\overrightarrow(a)\times \overrightarrow(b)=((x)_(a))\cdot ((x)_(b))+((y)_(a))\cdot ((y )_(б))+((з)_(а))\cточка ((з)_(б))\]

Во основа, кога дрвјата беа позелени, а небото посветло, ние едноставно го множевме векторот на ред $\overrightarrow(a)$ со векторот на колоната $\overrightarrow(b)$.

Ништо не се смени денес. Само што сега има повеќе од овие вектори на редови и колони.

Но, доволно е теорија! Ајде да погледнеме во вистински примери. И да почнеме со наједноставниот случај - квадратни матрици.

Множење со квадратна матрица

Задача 1. Направете го множењето:

\[\лево[ \почеток(низа)(*(35)(r)) 1 и 2 \\ -3 и 4 \\\крај (низа) \десно]\cdot \лево[ \почеток(низа)(* (35)(r)) -2 и 4 \\ 3 и 1 \\\крај (низа) \десно]\]

Решение. Значи, имаме две матрици: $A=\лево[ 2\пати 2 \десно]$ и $B=\лево[ 2\пати 2 \десно]$. Јасно е дека тие се конзистентни (квадратните матрици со иста големина се секогаш конзистентни). Затоа, го извршуваме множењето:

\[\почеток(порамни) и \лево[ \почеток(низа)(*(35)(r)) 1 и 2 \\ -3 и 4 \\\крај (низа) \десно]\cdot \лево[ \ почеток(низа)(*(35)(r)) -2 и 4 \\ 3 и 1 \\\крај (низа) \десно]=\лево[ \почеток(низа)(*(35)(r)) 1\cdot \left(-2 \десно)+2\cdot 3 & 1\cdot 4+2\ctot 1 \\ -3\cdot \left(-2 \десно)+4\cточка 3 & -3\cdot 4+4\cточка 1 \\\крај (низа) \десно]= \\ & =\лево[ \почеток(низа)(*(35)(r)) 4 и 6 \\ 18 & -8 \\\ крај (низа)\десно]. \крај (порамни)\]

Тоа е се!

Одговор: $\лево[ \почеток(низа)(*(35)(r))4 & 6 \\ 18 & -8 \\\крај (низа) \десно]$.

Задача 2. Направете го множењето:

\[\лево[ \почеток(матрица) 1 и 3 \\ 2 и 6 \\\крај (матрица) \десно]\cdot \лево[ \почеток(низа)(*(35)(r))9 и 6 \\ -3 и -2 \\\крај (низа) \десно]\]

Решение. Повторно, конзистентни матрици, па ги извршуваме следните дејства:\[\]

\[\почеток(порамни) и \лево[ \почеток(матрица) 1 и 3 \\ 2 и 6 \\\крај (матрица) \десно]\cdot \лево[ \почеток(низа)(*(35)( ) r)) 9 и 6 \\ -3 & -2 \\\крај (низа) \десно]=\лево[ \почеток(низа)(*(35)(r)) 1\cdot 9+3\cdot \ лево(-3 \десно) и 1\cточка 6+3\cточка \лево(-2 \десно) \\ 2\cточка 9+6\cdot \лево(-3 \десно) & 2\cточка 6+6 \ cdot \лево(-2 \десно) \\\крај (низа) \десно]= \\ & =\лево[ \почеток(матрица) 0 и 0 \\ 0 и 0 \\\крај (матрица) \десно ] . \крај (порамни)\]

Како што можете да видите, резултатот е матрица исполнета со нули

Одговор: $\лево[ \почеток(матрица) 0 и 0 \\ 0 и 0 \\\крај (матрица) \десно]$.

Од горенаведените примери е очигледно дека множењето на матрицата не е толку комплицирана операција. Барем за квадратни матрици 2 на 2.

Во процесот на пресметки, составивме средна матрица, каде што директно опишавме кои броеви се вклучени во одредена ќелија. Токму тоа треба да се направи кога се решаваат вистинските проблеми.

Основни својства на матричниот производ

Накратко. Множење на матрицата:

1. Некомутативно: $A\cdot B\ne B\cdot A$ во општиот случај. Има, се разбира, специјални матрици за кои еднаквоста $A\cdot B=B\cdot A$ (на пример, ако $B=E$ е матрицата за идентитетот), но во огромното мнозинство на случаи тоа не функционира ;
2. Асоцијативно: $\left(A\cdot B \десно)\cdot C=A\cdot \left(B\cdot C \десно)$. Овде нема опции: соседните матрици може да се множат без да се грижите за тоа што е лево и десно од овие две матрици.
3. Дистрибутивно: $A\cdot \left(B+C \right)=A\cdot B+A\cdot C$ и $\left(A+B \десно)\cdot C=A\cdot C+B\cdot C $ (поради некомутативноста на производот, неопходно е посебно да се специфицира десната и левата дистрибуција.

И сега - сè е исто, но подетално.

Множењето на матрицата на многу начини е слично на класичното множење на броеви. Но, постојат разлики, од кои најважна е таа Умножувањето на матрицата е, општо земено, некомутативно.

Да ги погледнеме повторно матриците од задача 1. Ние веќе го знаеме нивниот директен производ:

\[\лево[ \почеток(низа)(*(35)(r)) 1 и 2 \\ -3 и 4 \\\крај (низа) \десно]\cdot \лево[ \почеток(низа)(* (35)(r)) -2 и 4 \\ 3 & 1 \\\end (низа) \десно]=\лево[ \почеток(низа)(*(35)(r))4 и 6 \\ 18 & -8 \\\крај (низа) \десно]\]

Но, ако ги замениме матриците, добиваме сосема поинаков резултат:

\[\лево[ \почеток(низа)(*(35)(r)) -2 и 4 \\ 3 и 1 \\\крај (низа) \десно]\cdot \лево[ \почеток(низа)(* (35)(r)) 1 и 2 \\ -3 и 4 \\\крај (низа) \десно]=\лево[ \почеток(матрица) -14 и 4 \\ 0 и 10 \\\крај (матрица )\десно]\]

Излегува дека $A\cdot B\ne B\cdot A$. Покрај тоа, операцијата за множење е дефинирана само за конзистентните матрици $A=\left[ m\times n \right]$ и $B=\left[n\times k \right]$, но никој не гарантира дека тие ќе останат доследни доколку се заменат. На пример, матриците $\left[ 2\times 3 \right]$ and $\left[ 3\times 5 \right]$ се доста конзистентни во наведениот редослед, но истите матрици $\left[ 3\time 5 \right] $ и $\left[ 2\пати 3 \десно]$ напишани во обратен редослед повеќе не се конзистентни. Тажно. :(

Помеѓу квадратните матрици со дадена големина $n$ секогаш ќе има оние што го даваат истиот резултат и кога се множат во директен и во обратен редослед. Како да се опишат сите такви матрици (и колку ги има воопшто) е тема за посебна лекција. Денеска нема да зборуваме за тоа.

Сепак, множењето на матрицата е асоцијативно:

\[\лево(A\cdot B \десно)\cdot C=A\cdot \лево(B\cточка C \десно)\]

Затоа, кога треба да множите неколку матрици по ред одеднаш, воопшто не е неопходно да го направите тоа веднаш: сосема е можно некои соседни матрици, кога се множат, да дадат интересен резултат. На пример, нулта матрица, како во задача 2 дискутирана погоре.

Во реалните проблеми, најчесто мораме да множиме квадратни матрици со големина $\left[ n\time n \десно]$. Множеството од сите такви матрици се означува со $((M)^(n))$ (т.е., записите $A=\left[ n\times n \десно]$ и \ значат истото), и тоа ќе нужно содржи матрица $E$, која се нарекува матрица за идентитет.

Дефиниција. Идентификациона матрица со големина $n$ е матрица $E$ таква што за која било квадратна матрица $A=\left[n\times n \десно]$ важи еднаквоста:

Таквата матрица секогаш изгледа исто: има такви на нејзината главна дијагонала, а нули во сите други ќелии.

\[\почеток(порамни) & A\cdot \left(B+C \десно)=A\cdot B+A\cdot C; \\ & \лево(A+B \десно)\cdot C=A\cdot C+B\cdot C. \\ \крај (порамни)\]

Со други зборови, ако треба да помножите една матрица со збир на две други, тогаш можете да ја помножите со секој од овие „два други“, а потоа да ги додадете резултатите. Во пракса, обично треба да ја извршиме спротивната операција: ја забележуваме истата матрица, ја вадиме од заградите, вршиме собирање и со тоа го поедноставуваме нашиот живот :)

Забелешка: за да ја опишеме дистрибутивноста, моравме да напишеме две формули: каде збирот е во вториот фактор и каде збирот е во првиот. Ова се случува токму затоа што множењето на матрицата е некомутативно (и воопшто, во некомутативната алгебра има многу забавни работи што дури и не ми паѓаат на ум кога работите со обични броеви). И ако, на пример, треба да го запишете овој имот на испит, тогаш задолжително напишете ги двете формули, инаку наставникот може малку да се налути.

Добро, сите овие беа бајки за квадратни матрици. Што е со правоаголните?

Случај на правоаголни матрици

Но, ништо - сè е исто како кај квадратните.

Задача 3. Направете го множењето:

\[\лево[ \почеток (матрица) \почеток (матрица) 5 \\ 2 \\ 3 \\\крај (матрица) & \почеток (матрица) 4 \\ 5 \\ 1 \\\крај (матрица) \ \\крај (матрица) \десно]\cdot \лево[ \почеток(низа)(*(35)(r)) -2 и 5 \\ 3 и 4 \\\крај (низа) \десно]\]

Решение. Имаме две матрици: $A=\лево[ 3\пати 2 \десно]$ и $B=\лево[ 2\пати 2 \десно]$. Ајде да ги запишеме броевите што ги означуваат големините по ред:

Како што можете да видите, централните два броја се совпаѓаат. Ова значи дека матриците се конзистентни и може да се множат. Покрај тоа, на излезот ја добиваме матрицата $C=\left[ 3\times 2 \десно]$:

\[\ почеток (порамни) и \лево[ \почеток (матрица) \почеток (матрица) 5 \\ 2 \\ 3 \\\крај (матрица) & \почеток (матрица) 4 \\ 5 \\ 1 \\ \end (матрица) \\\крај (матрица) \десно]\cdot \лево[ \почеток(низа)(*(35)(r)) -2 и 5 \\ 3 и 4 \\\крај (низа) \десно]=\лево[ \почеток(низа)(*(35)(r)) 5\cdot \left(-2 \десно)+4\cточка 3 и 5\cточка 5+4\cточка 4 \\ 2 \cdot \left(-2 \десно)+5\cdot 3 & 2\cdot 5+5\cdot 4 \\ 3\cdot \left(-2 \десно)+1\cточка 3 и 3\cточка 5+1 \cточка 4 \\\крај (низа) \десно]= \\ & =\лево[ \почеток(низа)(*(35)(r)) 2 и 41 \\ 11 и 30 \\ -3 и 19 \ \\крај (низа) \десно]. \крај (порамни)\]

Сè е јасно: конечната матрица има 3 реда и 2 колони. Доста $=\лево[ 3\пати 2 \десно]$.

Одговор: $\лево[ \почеток(низа)(*(35)(r)) \begin(низа)(*(35)(r)) 2 \\ 11 \\ -3 \\\крај (низа) & \почеток (матрица) 41 \\ 30 \\ 19 \\\крај (матрица) \\\крај (низа) \десно]$.

Сега да погледнеме една од најдобрите задачи за обука за оние кои штотуку почнуваат да работат со матрици. Во него не треба само да помножите две таблети, туку прво да одредите: дали е дозволено такво множење?

Задача 4. Најдете ги сите можни парови производи на матрици:

\\]; $B=\лево[ \почеток(матрица) \почеток(матрица) 0 \\ 2 \\ 0 \\ 4 \\\крај (матрица) & \почеток (матрица) 1 \\ 0 \\ 3 \\ 0 \ \\крај (матрица) \\\крај (матрица) \десно]$; $C=\лево[ \почеток(матрица)0 и 1 \\ 1 и 0 \\\крај (матрица) \десно]$.

Решение. Прво, да ги запишеме големините на матриците:

\;\ B=\лево[ 4\пати 2 \десно];\ C=\лево[ 2\пати 2 \десно]\]

Откривме дека матрицата $A$ може да се усогласи само со матрицата $B$, бидејќи бројот на колони од $A$ е 4, а само $B$ го има овој број на редови. Затоа, можеме да го најдеме производот:

\\ cdot \left[ \begin(низа)(*(35)(r)) 0 & 1 \\ 2 & 0 \\ 0 & 3 \\ 4 & 0 \\\end (низа) \десно]=\ лево[ \почеток(низа)(*(35)(r))-10 и 7 \\ 10 и 7 \\\крај (низа) \десно]\]

Предлагам читателот самостојно да ги заврши средните чекори. Само ќе забележам дека е подобро да се одреди големината на добиената матрица однапред, дури и пред какви било пресметки:

\\cточка \лево[ 4\пати 2 \десно]=\лево[ 2\пати 2 \десно]\]

Со други зборови, ние едноставно ги отстрануваме коефициентите „транзит“ што ја обезбедија конзистентноста на матриците.

Кои други опции се можни? Се разбира, може да се најде $B\cdot A$, бидејќи $B=\лево[ 4\пати 2 \десно]$, $A=\лево[ 2\пати 4 \десно]$, така што нарачаниот пар $\ left(B ;A \right)$ е конзистентно, а димензијата на производот ќе биде:

\\cточка \лево[ 2\пати 4 \десно]=\лево[ 4\пати 4 \десно]\]

Накратко, излезот ќе биде матрица $\лево[ 4\пати 4 \десно]$, чии коефициенти може лесно да се пресметаат:

\\ cdot \лево[ \почеток(низа)(*(35)(r)) 1 & -1 & 2 & -2 \\ 1 & 1 & 2 & 2 \\\крај (низа) \десно]=\ лево[ \почеток(низа)(*(35)(r))1 и 1 и 2 и 2 \\ 2 и -2 и 4 и -4 \\ 3 и 3 и 6 и 6 \\ 4 и -4 и 8 и -8 \\\крај (низа) \десно]\]

Очигледно, можете да се договорите и за $C\cdot A$ и $B\cdot C$ - и тоа е тоа. Затоа, ние едноставно ги запишуваме добиените производи:

Беше лесно. :)

Одговор: $AB=\лево[ \почеток(низа)(*(35)(r)) -10 & 7 \\ 10 & 7 \\\крај (низа) \десно]$; $BA=\лево[ \почеток(низа)(*(35)(r)) 1 и 1 и 2 и 2 \\ 2 и -2 и 4 и -4 \\ 3 и 3 и 6 и 6 \\ 4 & -4 & 8 & -8 \\\крај (низа) \десно]$; $CA=\лево[ \почеток(низа)(*(35)(r)) 1 & 1 & 2 & 2 \\ 1 & -1 & 2 & -2 \\\крај (низа) \десно]$; $BC=\left[ \begin(низа)(*(35)(r))1 & 0 \\ 0 & 2 \\ 3 & 0 \\ 0 & 4 \\\end (низа) \десно]$.

Во принцип, препорачувам сами да ја направите оваа задача. И уште една слична задача која е во домашната работа. Овие навидум едноставни мисли ќе ви помогнат да ги вежбате сите клучни фази на множење на матрицата.

Но, приказната не завршува тука. Ајде да преминеме на посебни случаи на множење :)

Вектори на редови и вектори на колони

Една од најчестите матрични операции е множењето со матрица која има една редица или една колона.

Дефиниција. Вектор на колона е матрица со големина $\left[ m\times 1 \десно]$, т.е. се состои од неколку редови и само една колона.

Вектор на ред е матрица со големина $\left[ 1\times n \десно]$, т.е. се состои од еден ред и неколку колони.

Всушност, ние веќе се сретнавме со овие објекти. На пример, обичен тродимензионален вектор од стереометријата $\overrightarrow(a)=\left(x;y;z \right)$ не е ништо повеќе од вектор на ред. Од теоретска гледна точка, речиси и да нема разлика помеѓу редовите и колоните. Треба само да бидете внимателни кога се координирате со околните матрици на множител.

Задача 5. Направете го множењето:

\[\лево[ \почеток(низа)(*(35)(r)) 2 и -1 и 3 \\ 4 и 2 и 0 \\ -1 и 1 и 1 \\\крај (низа) \десно] \cdot \лево[ \почеток(низа)(*(35)(r)) 1 \\ 2 \\ -1 \\\крај (низа) \десно]\]

Решение. Овде го имаме производот на совпаднати матрици: $\лево[ 3\пати 3 \десно]\cdot \лево[ 3\пати 1 \десно]=\лево[ 3\пати 1 \десно]$. Ајде да го најдеме ова парче:

\[\лево[ \почеток(низа)(*(35)(r)) 2 и -1 и 3 \\ 4 и 2 и 0 \\ -1 и 1 и 1 \\\крај (низа) \десно] \cdot \лево[ \почеток(низа)(*(35)(r)) 1 \\ 2 \\ -1 \\\крај (низа) \десно]=\лево[ \почеток(низа)(*(35 )(r)) 2\cточка 1+\лево(-1 \десно)\cточка 2+3\cdot \лево(-1 \десно) \\ 4\cточка 1+2\cточка 2+0\cточка 2 \ \ -1\cточка 1+1\cточка 2+1\cdot \лево(-1 \десно) \\\крај (низа) \десно]=\лево[ \почеток(низа)(*(35)(r) ) -3 \\ 8 \\ 0 \\\крај (низа) \десно]\]

Одговор: $\лево[ \почеток(низа)(*(35)(r))-3 \\ 8 \\ 0 \\\крај (низа) \десно]$.

Задача 6. Направете го множењето:

\[\лево[ \почеток(низа)(*(35)(r)) 1 & 2 & -3 \\\крај (низа) \десно]\cdot \лево[ \почеток(низа)(*(35) (р)) 3 и 1 и -1 \\ 4 и -1 и 3 \\ 2 и 6 и 0 \\\крај (низа) \десно]\]

Решение. Повторно се е договорено: $\лево[ 1\пати 3 \десно]\cdot \лево[ 3\пати 3 \десно]=\лево[ 1\пати 3 \десно]$. Го броиме производот:

\[\лево[ \почеток(низа)(*(35)(r)) 1 & 2 & -3 \\\крај (низа) \десно]\cdot \лево[ \почеток(низа)(*(35) (р)) 3 и 1 и -1 \\ 4 и -1 и 3 \\ 2 и 6 и 0 \\\крај (низа) \десно]=\лево[ \почеток(низа)(*(35)( ) r)) 5 и -19 и 5 \\\крај (низа) \десно]\]

Одговор: $\left[ \begin(матрица) 5 & -19 & 5 \\\end (матрица) \десно]$.

Како што можете да видите, кога множиме вектор на ред и вектор на колона со квадратна матрица, излезот секогаш резултира со ред или колона со иста големина. Овој факт има многу примени - од решавање на линеарни равенки до сите видови координатни трансформации (кои на крајот се сведуваат и на системи на равенки, но да не зборуваме за тажни работи).

Мислам дека сè беше очигледно овде. Ајде да преминеме на последниот дел од денешната лекција.

Матрична експоненција

Помеѓу сите операции за множење, степенувањето заслужува посебно внимание - ова е кога еден ист објект сам по себе го множиме неколку пати. Матриците не се исклучок, тие исто така можат да се подигнат на различни моќи.

Ваквите дела секогаш се договараат:

\\ cdot \left[ n\times n \десно]=\лево[n\пати n \десно]\]

И тие се назначени на ист начин како и обичните степени:

\[\begin(порамни) & A\cdot A=((A)^(2)); \\ & A\cdot A\cdot A=((A)^(3)); \\ & \underbrace(A\cdot A\cdot \ldots \cdot A)_(n)=((A)^(n)). \\ \крај (порамни)\]

На прв поглед, сè е едноставно. Ајде да видиме како ова изгледа во пракса:

Задача 7. Подигнете ја матрицата до наведената моќност:

$((\лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно])^(3))$

Решение. Добро, ајде да изградиме. Прво да го квадрираме:

\[\почеток(порамни) & ((\лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај(матрица) \десно])^(2))=\лево[ \почеток(матрица ) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно]\cdot \лево[ \почеток(матрица) 1 и 1 \\ 0 & 1 \\\крај (матрица) \десно]= \\ & =\лево[ \почеток(низа)(*(35)(r)) 1\cdot 1+1\cdot 0 & 1\cdot 1+1\ctot 1 \\ 0\cdot 1+1\cdot 0 & 0\cточка 1+1\cточка 1 \\\крај (низа) \десно]= \\ & =\лево[ \почеток(низа)(*(35)(r)) 1 и 2 \\ 0 и 1 \ \\крај (низа) \десно] \крај (порамни)\]

\[\почеток(порамни) & ((\лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно])^(3))=((\лево[ \почеток (матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно])^(3))\cdot \лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај( матрица) \десно]= \\ & =\лево[ \почеток(низа)(*(35)(r)) 1 и 2 \\ 0 и 1 \\\крај (низа) \десно]\cdot \лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно]= \\ & =\лево[ \почеток(низа)(*(35)(r)) 1 и 3 \\ 0 и 1 \\\крај (низа) \десно] \крај (порамни)\]

Тоа е се.:)

Одговор: $\лево[ \почеток(матрица)1 и 3 \\ 0 и 1 \\\крај (матрица) \десно]$.

Задача 8. Подигнете ја матрицата до наведената моќност:

\[((\лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно])^(10))\]

Решение. Само не плачете сега за фактот дека „дипломата е преголема“, „светот не е фер“ и „учителите целосно ги загубија своите брегови“. Всушност е лесно:

\[\почеток(порамни) & ((\лево[ \почеток(матрица) 1 и 1 \\ 0 & 1 \\\крај(матрица) \десно])^(10))=((\лево[ \почеток (матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно])^(3))\cdot ((\лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\ крај (матрица) \десно])^(3))\cdot ((\лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно])^(3))\ cdot \лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно]= \\ & =\лево(\лево[ \почеток(матрица) 1 и 3 \\ 0 & " \почеток(матрица) 1 и 3 \\ 0 и 1 \\\крај (матрица) \десно]\cdot \лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно ] \десно)= \\ & =\лево[ \почеток(матрица) 1 и 6 \\ 0 и 1 \\\крај (матрица) \десно]\cdot \лево[ \почеток(матрица) 1 и 4 \\ 0 и 1 \\\крај (матрица) \десно]= \\ & =\лево[ \почеток (матрица) 1 и 10 \\ 0 и 1 \\\крај (матрица) \десно] \крај (порамни)\ ]

Забележете дека во вториот ред користевме асоцијативност за множење. Всушност, го користевме во претходната задача, но таму беше имплицитно.

Одговор: $\лево[ \почеток(матрица) 1 и 10 \\ 0 и 1 \\\крај (матрица) \десно]$.

Како што можете да видите, нема ништо комплицирано во подигањето на матрицата до моќ. Последниот пример може да се сумира:

\[((\лево[ \почеток(матрица) 1 и 1 \\ 0 и 1 \\\крај (матрица) \десно])^(n))=\лево[ \почеток(низа)(*(35) (р)) 1 и n \\ 0 и 1 \\\крај (низа) \десно]\]

Овој факт е лесно да се докаже преку математичка индукција или директно множење. Сепак, не е секогаш можно да се фатат такви обрасци кога се подига на моќ. Затоа, бидете внимателни: честопати множењето на неколку матрици „по случаен избор“ излегува дека е полесно и побрзо отколку да барате некакви обрасци.

Во принцип, не барајте повисоко значење каде што нема. Како заклучок, да ја разгледаме експоненцијацијата на поголема матрица - колку $\лево[ 3\пати 3 \десно]$.

Задача 9. Подигнете ја матрицата до наведената моќност:

„

Решение. Да не бараме шаблони. Работиме напред:

\[((\лево[ \почеток(матрица) 0 и 1 и 1 \\ 1 и 0 и 1 \\ 1 и 1 и 0 \\\крај (матрица) \десно])^(3))=(( \left[ \begin(матрица) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end (матрица) \десно])^(2))\cdot \\ лево[ \почеток (матрица)0 и 1 и 1 \\ 1 и 0 и 1 \\ 1 и 1 и 0 \\\крај (матрица) \десно]\]

Прво, да ја квадрираме оваа матрица:

\[\почеток(порамни) & ((\лево[ \почеток(матрица) 0 и 1 и 1 \\ 1 и 0 и 1 \\ 1 и 1 и 0 \\\крај (матрица) \десно])^( 2))=\лево[ \почеток(матрица) 0 и 1 и 1 \\ 1 и 0 и 1 \\ 1 и 1 и 0 \\\крај (матрица) \десно]\cdot \лево[ \почеток(матрица ) 0 и 1 и 1 \\ 1 и 0 и 1 \\ 1 и 1 и 0 \\\крај (матрица) \десно]= \\ & =\лево[ \почеток(низа)(*(35)(r )) 2 и 1 и 1 \\ 1 и 2 и 1 \\ 1 и 1 и 2 \\\крај (низа) \десно] \крај (порамни)\]

Сега ајде да го коцкаме:

\[\почеток(порамни) & ((\лево[ \почеток(матрица) 0 и 1 и 1 \\ 1 и 0 и 1 \\ 1 и 1 и 0 \\\крај (матрица) \десно])^( 3))=\лево[ \почеток(низа)(*(35)(r)) 2 и 1 и 1 \\ 1 и 2 и 1 \\ 1 и 1 и 2 \\\крај (низа) \десно] \cdot \лево[ \почеток(матрица) 0 и 1 и 1 \\ 1 и 0 и 1 \\ 1 и 1 и 0 \\\крај (матрица) \десно]= \\ & =\лево[ \почеток( низа)(*(35)(r)) 2 и 3 и 3 \\ 3 и 2 и 3 \\ 3 и 3 и 2 \\\крај (низа) \десно] \крај (порамни)\]

Тоа е се. Проблемот е решен.

Одговор: $\лево[ \почеток(матрица) 2 и 3 и 3 \\ 3 и 2 и 3 \\ 3 и 3 и 2 \\\крај (матрица) \десно]$.

Како што можете да видите, обемот на пресметките стана поголем, но значењето воопшто не се промени.

Ова ја завршува лекцијата. Следниот пат ќе ја разгледаме инверзната операција: користејќи го постоечкиот производ ќе ги бараме оригиналните фактори.

Како што веројатно веќе погодивте, ќе зборуваме за инверзната матрица и методите за нејзино наоѓање.