Մատրիցների արտադրյալ

Մատրիցների արտադրյալ-մատրիցների նկատմամբ կատարվող հիմնական գործողություններից մեկն է։ Գործողության արդյունքում ստացված մատրիցը կոչվում է արտադրյալ մատրից։ Արտադրյալ մատրիցի տարրերի ստացումը կատարվում է ցուցադրված սխեմայի կանոններով նկարազարդում։ $A$ և $B$ մատրիցները կարելի է բազմապատկել միայն այն դեպքում, երբ նրանք համատեղելի են․ այսինքն $A$ մատրիցի սյուների թիվը հավասար է $B$ մատրիցի տողերի թվին։ Մատրիցների արտադրյալին բնորոշ են արտադրյալի բոլոր հատկությունները, բացառությամբ՝ կոմուտատիվությունից հատկությունները։ Քառակուսային մատրիցների համար իրականացվում են նաև մատրիցի աստիճան բարձրացնելու և հակադարձ մատրիցներ գտնելու գործողությունները։

Սահմանում

Դիցուք տրված են երկու ուղղանկյուն $A$ և $B$ մատրիցներ համապատասխանաբար $l\times m$ և $m\times n$ չափերով․

$A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1m}\\a_{21}&a_{22}&\cdots &a_{2m}\\\vdots &\vdots &\ddots &\vdots \\a_{l1}&a_{l2}&\cdots &a_{lm}\end{bmatrix}},\;\;\;B={\begin{bmatrix}b_{11}&b_{12}&\cdots &b_{1n}\\b_{21}&b_{22}&\cdots &b_{2n}\\\vdots &\vdots &\ddots &\vdots \\b_{m1}&b_{m2}&\cdots &b_{mn}\end{bmatrix}}.$

Ապա $C$ մատրիցի չափերը կլինեն $l\times n$:

$C={\begin{bmatrix}c_{11}&c_{12}&\cdots &c_{1n}\\c_{21}&c_{22}&\cdots &c_{2n}\\\vdots &\vdots &\ddots &\vdots \\c_{l1}&c_{l2}&\cdots &c_{ln}\end{bmatrix}},$

որտեղ․

$c_{ij}=\sum _{r=1}^{m}a_{ir}b_{rj}\;\;\;\left(i=1,2,\ldots l;\;j=1,2,\ldots n\right).$

կոչվում է նրանց արտադրյալ։ Գործողությունը հնարավոր է այն և միայն այն դեպքում, երբ առաջին արտադրիչի սյուների թիվը հավասար է երկրորդ արտադրիչի տողերի թվին։ Մասնավորապես գործողությունը միշտ հնարավոր է միևնույն կարգի քառակուսային մատրիցաների համար։ Այսպիսով․ $AB$ գոյություն ունենալուց դեռևս չի հետևում $BA$-ի գոյությունը։

Նկարազարդում

Մատրիցների արտադևյալը իր բնույթով նման է տող-վեկտորների սկալյար արտադրյալին։ AB մաթրիցի i, j ինդեքսով յուրաքանչյուր տարր ստացվում է A մատրիցի i-րդ տող-վեկտորի ևB մատրիցի j-րդ տող-վեկտորի սկալյար արտադրյալից։ Սխեմայում ներկայացած արտադրյալ մատրիցի յուրաքանչյուր հատում համապատասխանում է A մատրիցի տողերին և B մատրիցի սյուներին։ Հատումների արժեքները, որոնք նշված են շրջանակներով, կլինեն․

${\begin{aligned}{\color {Red}x_{1,2}}&=(a_{1,1},a_{1,2})\cdot (b_{1,2},b_{2,2})\\&=a_{1,1}b_{1,2}+a_{1,2}b_{2,2}\\{\color {Blue}x_{3,3}}&=(a_{3,1},a_{3,2})\cdot (b_{1,3},b_{2,3})\\&=a_{3,1}b_{1,3}+a_{3,2}b_{2,3}\end{aligned}}$

Ընդհանուր առմամբ մատրիցների արտադրյալը օժտված չէ տեղափոխական հատկությամբ։ Օրինակ․

${\overset {3\times 4{\text{ matrix}}}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot \\\color {Blue}1&\color {Blue}2&\color {Blue}3&\color {Blue}4\\\end{bmatrix}}}{\overset {4\times 5{\text{ matrix}}}{\begin{bmatrix}\cdot &\cdot &\cdot &\color {Red}a&\cdot \\\cdot &\cdot &\cdot &\color {Red}b&\cdot \\\cdot &\cdot &\cdot &\color {Red}c&\cdot \\\cdot &\cdot &\cdot &\color {Red}d&\cdot \\\end{bmatrix}}}={\overset {3\times 5{\text{matrix}}}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &x_{3,4}&\cdot \\\end{bmatrix}}}$

Э$x_{3,4}$ տարրը արտադրյալ մատրիցում կորոշվի հետևյալ կերպ․

$x_{3,4}=({\color {Blue}1},{\color {Blue}2},{\color {Blue}3},{\color {Blue}4})\cdot ({\color {Red}a},{\color {Red}b},{\color {Red}c},{\color {Red}d})={\color {Blue}1}\cdot {\color {Red}a}+{\color {Blue}2}\cdot {\color {Red}b}+{\color {Blue}3}\cdot {\color {Red}c}+{\color {Blue}4}\cdot {\color {Red}d}$

Առաջին կոորդինատը ցույց է տալիս տողը, երկրորդը՝ սյունը։ $x_{{\color {Blue}i}{\color {Red}j}}$ տարրը $i$-րդ տողի և $j$-րդ սյան հատաման արդյունքն է, որը հավասար է առաջին մատրիցի $i$-րդ տողի և երկրորդ մատրիցի $j$-րդ սյան սկալյար արտադրյալին։

Հատկություններ

Զուգորդականություն․

$\mathbf {A} (\mathbf {BC} )=(\mathbf {AB} )\mathbf {C} ;$

$\alpha (\mathbf {AB} )=(\alpha \mathbf {A} )\mathbf {B} =\mathbf {A} (\alpha \mathbf {B} )$։

Բաշխականություն (գումարման նկատմամբ)

$\mathbf {A} (\mathbf {B} +\mathbf {C} )=\mathbf {AB} +\mathbf {AC} ;$

$(\mathbf {A} +\mathbf {B} )\mathbf {C} =\mathbf {AC} +\mathbf {BC}$։

Մատրիցի արտադրյալը համապատասխան կարգի $\mathbf {E}$ միավոր մատրիցի հետ հավասար է նույն մատրիցին․

$\mathbf {EA} =\mathbf {A} ;$

$\mathbf {AE} =\mathbf {A}$։

Մատրիցի արտադրյալը համապատասխան կարգի $\mathbf {0}$ զրոյական մատրիցի հետ հավասար է զրոյական մատրիցի․

$\mathbf {0A} =\mathbf {0} ;$

$\mathbf {A0} =\mathbf {0}$։

Մատրիցների արտադրյալը ընդհանուր առմամբ տեղափոխականության հատկությամբ օժտված չէ․

$\mathbf {AB} \neq \mathbf {BA}$։

Եթե $\mathbf {AB} =\mathbf {BA}$, ապա $\mathbf {A}$ և $\mathbf {B}$ մատրիցները կոչվում են կոմուտատիվ իրենց մեջ․ Ցանկացած քառակուսի մատրիցի համար

• $\mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}}$ (մատրիցի քառակուսի բարձրացնելը);
• $\mathbf {AE} =\mathbf {EA} =\mathbf {A}$;
• $\mathbf {A0} =\mathbf {0A} =\mathbf {0}$;
• $\mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E}$։

Արտադրյալի որոշիչը և հետքը կախված չեն բազմապատկման հերթականությունից․

$\det(\mathbf {AB} )=\det(\mathbf {BA} )=\det \mathbf {A} \cdot \det \mathbf {B} ;$

${\mbox{tr}}(\mathbf {AB} )={\mbox{tr}}(\mathbf {BA} ).$

Հակադարձ մատրիցներ

$A$ քառակուսային մատրիցան կոչվում է չվերասերված, եթե գոյություն ունի $A^{-1}$ հակադարձ մատրից այնպես, որ

$AA^{-1}=A^{-1}A=E.$։ Հակառակ դեպքում այն կոչվում է վերասերված։

$n$-րդ կարգի $A=\left[a_{ik}\right]$ մատրիցը չվերասերված է այն և միայն աւյն դեպքում, երբ $\det A=\det \left[a_{ik}\right]\neq 0$ այս դեպքում $A^{-1}$ մատրիցը նույն $n$-րդ կարգի քառակուսային մատրից է։

$A^{-1}=\left[a_{ik}\right]^{-1}=\left[{\frac {A_{ki}}{\det A}}\right],$

որտեղ $A_{ik}$ — $a_{ik}$ տարրի հանրահաշվական լրացումն է $\det \left[a_{ik}\right]$ որոշիչի մեջ։

Մատրիցների արագ բազմապատկման մի քանի ալգորիթմներ

Գոյություն ունեն մի քանի էֆեկտիվ ալգորիթմներ, որոնք օգտագործում են մատրիցները արագ բազմապատկելու համար։ Դրանք կիրառվում են առանձնապես մեծ մատրիցների համար, որոնց արագ բազմապատկումը դեռևս շարունակում է մնալ գծային հանրահաշվի չլուծված խնդիրներից մեկը։

• Շտրասսենի ալգորիթմ (1969)

Առաջին արագ բազմապատկման աղյուսակը դուրս է բերվել Ֆոլկեր Շտրասսենի կողմից 1969 թվականին։ Ալգորիթմը հիմնված է մատրիցների կրկնվող բաժանման վրա 2X2 բլոկների։ Ստրասենը ապացուցեց, որ 2X2 մատրիցաները կարող են բազմապատկվել ՝ օգտագործելով յոթ բազմապատկում, այնպես որ ռեկուրսիայի յուրաքանչյուր փուլում յոթ բազմապատկումը կատարվում է ութի փոխարեն։ Արդյունքում, այս ալգորիթմի բարդությունը $O(n^{\log _{2}7})\approx O(n^{2.81})$ մեջ է։ Այս մեթոդի անբարենպաստությունը ծրագրավորման ավելի բարդությունն է `համեմատած ստանդարտ ալգորիթմի հետ, թույլ թվային կայունությունը և օգտագործված հիշողության ավելի մեծ քանակությունը։ Մեթոդի հիման վրա մշակվել են մի շարք ալգորիթմներ, որոնք բարելավում են թվային կայունությունը, կայուն արագությունը և դրա մյուս բնութագրերը։ Այնուամենայնիվ, պարզության պատճառով, Շտրասսենի ալգորիթմը շարունակում է մնալ խոշոր մատրիցները բազմապատկելու գործնական ալգորիթմներից մեկը։

• Մատրիցների բազմապատկման արագության ω ցուցանիշի բարելավում

ω-ի գնահատումների բարելավման ժամանակացույց ՝ մատրիցների բազմապատկման արագության համար:

Հետագայում խոշոր մատրիցների բազմապատկման արագության գնահատումները բազմիցս բարելավվել են։ Այնուամենայնիվ, այս ալգորիթմները տեսական են, հիմնականում մոտավոր։ Մոտեցման բազմապատկման ալգորիթմների անկայունության պատճառով դրանք ներկայումս գործնականում չեն օգտագործվում։

• Պանի ալգորիթմը (1978)

1978 թվականին Պանը առաջարկեց մատրիցների բազմապատկամն իր մեթոդը, որի բարդությունը կազմում էրΘ(n^2.78041).

• Բինի ալգորիթմ (1979)

1979 թվականին իտալացի գիտնականների մի խումբ Բինի գլխավորությամբ մշակեցին բազմապատկման եղանակ տենզորների կիրառմաբ։ Ալգորիթմի բարդությունը կազմում է Θ(n^2.7799).

• Շյոնհագի ալգորիթմները (1981)

1981 թվականին Շյոնհագը առաջարկեց մեթոդ, որն աշխատում էր Θ(n^2.695)։Հաշվարկը ստացվում է «մասնակի մատրիցի բազմապատկում» մեթոդով։

Հետագայում նրան հաջողվեց ստանալ Θ(n^2.6087) գնահատականը։

Հետագայում Շոնհագը ուղիղ գումարի մեթոդի հիման վրա ստացավ Θ(n^2.548) բարդության գնահատականը։ Ռոմանին կարողացավ իջեցնել այն մինչև Θ(n^2.5166), իսկ Պանը — մինչև Θ(n^2.5161)։

• Կոպպերսմիթ-Վինոգրադի ալգորիթմը (1990)

1990 թվականին Կոպպերսմիթը և Վինոգրադը հրապարակեցին ալգորիթմ, ըստ որի ՝ 2011-ին Վիլյամս Վասիլևսկայայի ձևափոխմամբ, մատրիցաները բազմապատկում են O(n^2.3727)արագությամբ։ Այս ալգորիթմը օգտագործում է Շտրասսենի ալգորիթմի նման գաղափարներ:Մինչ օրս ալգորիթմի փոփոխությունները ամենաշատն են ընկալվում։ Ալգորիթմը արդյունավետ է միայն աստղագիտական չափի մատրիցների վրա և չի կարող կիրառվել գործնականում։

• Կապը խմբային տեսության հետ(1979)

2003 թվականին Կոխը ու մի քանիսը իր աշխատություններում ուսումնասիրեցին Շտրասսենի և Կոպպերսմիթ-Վինոգրադի ալգորիթմները խմբային տեսանկյունից։ Նրանք ապացուցեցին, որ Շտրասսենի ալգորիթմը ճիշտ է, եթե տեղի ունի խմբային տեսության վարկածներից մեկը։

Մատրիցի աստիճանը

Քառակուսային մատրիցները կարելի է ինքն իրենով բազմապատկել մի քանի անգամ, քանի որ նրանց մոտ հավասար են տողերի և սյուների թիվը։ Այսպիսի հաջորդական բազմապատկումը կոչվում է մատրիցի «աստիճան բարձրացում»։ Ուղղանկյուն մատրիցների մոտ տողերի և սյուների քանակները հավասար չեն ուստի աստիճան բարձրացնելը նրանց դեպքում հնարավոր չէ։ n × n չափերով A մնատրիցի աստիճան բարձրացնելը որոշվում է $\mathbf {A} ^{k}=\underbrace {\mathbf {A} \mathbf {A} \cdots \mathbf {A} } _{k}$ բանաձևով և ունի հետևյալ հատկությունները․

Զրոյական աստիճան

$\mathbf {A} ^{0}=\mathbf {E}$

որտեղ E - միավոր մատրից է։ Սա անալոգն է այն փաստի, որ թվի զրոյական աստիճանը հավասար է 1։

Սկալյարով բազմապատկում (λ — սկալյար մեծություն է)

$(\lambda \mathbf {A} )^{k}=\lambda ^{k}\mathbf {A} ^{k}$

Որոշիչ

$\det(\mathbf {A} ^{k})=\det(\mathbf {A} )^{k}$։

Մատրիցի աստիճանը հաշվելու ամենապարզ մեթոդը՝ մատրիցը ինքն իրենով $k$ անգամ բազմապատկելն է։ Առանձին ուշադրության են արժանի անկլյունագծային մատրիցները։ Քանի որ նրանց արտադրյալը հանգում է անկյունագծային տարրերի արտադրյալին, ապա $A$ մատրիցի $k$ աստիճանը կլինի

$\mathbf {A} ^{k}={\begin{pmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{pmatrix}}^{k}={\begin{pmatrix}a_{11}^{k}&0&\cdots &0\\0&a_{22}^{k}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}^{k}\end{pmatrix}}.$

Այդ պատճառով էլ անկյունագծային մատրիցը աստիճան բարձրացնելը դժվար չէ։

Տես նաև

Կրոնեկերի արտադրյալ

Գրականություն

• Տ․ Կորն, Գ․ Կորն «Մատրիցների հանրահաշիվ և մատրիցային հաշնարկ»; մթեմատիկայի տեղեկագիրք, 4-րդ հրատարակություն;М: Наука, 1978։