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

Matrix multiplication diagram.svg

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

ՍահմանումԽմբագրել

Դիցուք տրված են երկու ուղղանկյուն   և   մատրիցներ համապատասխանաբար   և   չափերով․

 

Ապա   մատրիցի չափերը կլինեն  :

 

որտեղ․

 

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

ՆկարազարդումԽմբագրել

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

 

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

 

Э  տարրը արտադրյալ մատրիցում կորոշվի հետևյալ կերպ․

 

Առաջին կոորդինատը ցույց է տալիս տողը, երկրորդը՝ սյունը։   տարրը  -րդ տողի և  -րդ սյան հատաման արդյունքն է, որը հավասար է առաջին մատրիցի  -րդ տողի և երկրորդ մատրիցի  -րդ սյան սկալյար արտադրյալին։

ՀատկություններԽմբագրել

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

 
 ։

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

 
 ։

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

 
 ։

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

 
 ։

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

 ։

Եթե  , ապա   և   մատրիցները կոչվում են կոմուտատիվ իրենց մեջ․ Ցանկացած քառակուսի մատրիցի համար

  •   (մատրիցի քառակուսի բարձրացնելը);
  •  ;
  •  ;
  •  ։

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

 
 

Հակադարձ մատրիցներԽմբագրել

  քառակուսային մատրիցան կոչվում է չվերասերված, եթե գոյություն ունի   հակադարձ մատրից այնպես, որ

 ։ Հակառակ դեպքում այն կոչվում է վերասերված։

 -րդ կարգի   մատրիցը չվերասերված է այն և միայն աւյն դեպքում, երբ   այս դեպքում   մատրիցը նույն  -րդ կարգի քառակուսային մատրից է։

 

որտեղ   —   տարրի հանրահաշվական լրացումն է   որոշիչի մեջ։

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

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

Առաջին արագ բազմապատկման աղյուսակը դուրս է բերվել Ֆոլկեր Շտրասսենի կողմից 1969 թվականին։ Ալգորիթմը հիմնված է մատրիցների կրկնվող բաժանման վրա 2X2 բլոկների: Ստրասենը ապացուցեց, որ 2X2 մատրիցաները կարող են բազմապատկվել ՝ օգտագործելով յոթ բազմապատկում, այնպես որ ռեկուրսիայի յուրաքանչյուր փուլում յոթ բազմապատկումը կատարվում է ութի փոխարեն: Արդյունքում, այս ալգորիթմի բարդությունը   մեջ է: Այս մեթոդի անբարենպաստությունը ծրագրավորման ավելի բարդությունն է `համեմատած ստանդարտ ալգորիթմի հետ, թույլ թվային կայունությունը և օգտագործված հիշողության ավելի մեծ քանակությունը: Մեթոդի հիման վրա մշակվել են մի շարք ալգորիթմներ, որոնք բարելավում են թվային կայունությունը, կայուն արագությունը և դրա մյուս բնութագրերը: Այնուամենայնիվ, պարզության պատճառով, Շտրասսենի ալգորիթմը շարունակում է մնալ խոշոր մատրիցները բազմապատկելու գործնական ալգորիթմներից մեկը:

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

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

  • Պանի ալգորիթմը (1978)
1978 թվականին Պանը [2] առաջարկեց մատրիցների բազմապատկամն իր մեթոդը, որի բարդությունը կազմում էրΘ(n2.78041).
  • Բինի ալգորիթմ (1979)
1979 թվականին իտալացի գիտնականների մի խումբ Բինի գլխավորությամբ [3] մշակեցին բազմապատկման եղանակ տենզորների կիրառմաբ։ Ալգորիթմի բարդությունը կազմում է Θ(n2.7799).
  • Շյոնհագի ալգորիթմները (1981)
1981 թվականին Շյոնհագը [4] առաջարկեց մեթոդ, որն աշխատում էր Θ(n2.695)։Հաշվարկը ստացվում է «մասնակի մատրիցի բազմապատկում» մեթոդով։
Հետագայում նրան հաջողվեց ստանալ Θ(n2.6087) գնահատականը։
Հետագայում Շոնհագը ուղիղ գումարի մեթոդի հիման վրա ստացավ Θ(n2.548) բարդության գնահատականը։ Ռոմանին կարողացավ իջեցնել այն մինչև Θ(n2.5166), իսկ Պանը — մինչև Θ(n2.5161)։
  • Կոպպերսմիթ-Վինոգրադի ալգորիթմը (1990)
1990 թվականին Կոպպերսմիթը և Վինոգրադը [5] հրապարակեցին ալգորիթմ, ըստ որի ՝ 2011-ին Վիլյամս Վասիլևսկայայի ձևափոխմամբ,[6] մատրիցաները բազմապատկում են O(n2.3727)արագությամբ։ Այս ալգորիթմը օգտագործում է Շտրասսենի ալգորիթմի նման գաղափարներ:Մինչ օրս ալգորիթմի փոփոխությունները ամենաշատն են ընկալվում: Ալգորիթմը արդյունավետ է միայն աստղագիտական ​​չափի մատրիցների վրա և չի կարող կիրառվել գործնականում:
  • Կապը խմբային տեսության հետ(1979)
2003 թվականին Կոխը ու մի քանիսը իր աշխատություններում ուսումնասիրեցին Շտրասսենի և Կոպպերսմիթ-Վինոգրադի ալգորիթմները խմբային տեսանկյունից։ Նրանք ապացուցեցին, որ Շտրասսենի ալգորիթմը ճիշտ է, եթե տեղի ունի խմբային տեսության վարկածներից մեկը։

Մատրիցի աստիճանըԽմբագրել

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

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

 

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

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

 

Որոշիչ

 ։

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

 

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

Տես նաևԽմբագրել

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

ԳրականությունԽմբագրել

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

ԾանոթագրություններԽմբագրել

  1. Кибернетический сборник. Новая серия. Вып. 25. Сб. статей 1983 — 1985 гг.: Пер. с англ. — М.: Мир, 1988 — В.Б. Алекссев. Сложность умножения матриц. Обзор.
  2. Pan V. Ya, Strassen’s algorithm is not optimal — trilinear technique of aggregating uniting and canceling for constructing fast algorithms for matrix operations. — Proc. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Mich., 1978
  3. Bini D., Capovani M., Lotti G., Romani F. —   complexity for approximate matrix multiplication. — Inform. Process. Lett., 1979
  4. Schonhage A. Partial and total matrix multiplication. — SIAM J. Comput., 1981
  5. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.
  6. Williams, Virginia (2011), Multiplying matices in O(n2.3727 time