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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Matrix multiplication diagram.svg

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

Սահմանում[խմբագրել | խմբագրել կոդը]

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

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

որտեղ․

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

Նկարազարդում[խմբագրել | խմբագրել կոդը]

Matrix multiplication diagram 2.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