Toshkent axborot texnologiyalari universiteti urganch filiali kompyuter injineringi fakulteti

4.3 Matritsalarni ko'paytirish uchun ko'paytirish usullarini o'rganish
Matritsalarni ko'paytirishning sodda yondashuvi hosil bo'lgan matritsaning har bir elementini takrorlashni va ikkita matritsaning tegishli satrlari va ustunlarining nuqta mahsulotini hisoblashni o'z ichiga oladi.
Misol:
Aytaylik, biz mos ravishda m x n va n x p o‘lchamdagi ikkita A va B matritsalarni ko‘paytirmoqchimiz va natijani m x p o‘lchamli C matritsasida saqlamoqchimiz.

Chiqish:

Murakkablik tahlili:
Ushbu usulning vaqt murakkabligi O(m * n * p), chunki biz hosil bo'lgan C matritsasining har bir elementi ustida takrorlanamiz va har bir m * p element uchun n ta elementning nuqta mahsulotini hisoblaymiz. Fazoning murakkabligi O(m * p), chunki biz natijani C matritsasida saqlayapmiz.

2-usul: Strassen algoritmi

Strassen algoritmi matritsalarni ko‘paytirishning “bo‘lish va bosib olish” usuli bo‘lib, u katta matritsalar uchun zarur bo‘lgan ko‘paytirish amallari sonini kamaytiradi. Ushbu algoritm rekursiv ravishda matritsalarni yarmi kattalikdagi submatritsalarga ajratadi va natijada olingan matritsani hisoblash uchun qo'shish va ayirish kombinatsiyasidan foydalanadi.
Misol:
Aytaylik, biz 4 x 4 o'lchamdagi ikkita A va B matritsalarini ko'paytirmoqchimiz va natijani C matritsasida saqlamoqchimiz.

Chiqish:

Murakkablik tahlili:
Strassen algoritmining vaqt murakkabligi O(n^log2(7)), bu esa O(n^3) murakkabligidan kichikdir.


5.1 Determinant haqida umumiy tushuncha berish
Determinant kvadrat matritsa bilan bog'langan skalyar qiymat bo'lib, matritsa haqida muhim ma'lumot beradi. Matritsaning determinanti odatda |A|da bo'lgani kabi "det" yoki vertikal chiziqlar bilan belgilanadi. matritsa uchun A. Determinantning qiymati matritsaning elementlariga va matritsaning tartibiga bog'liq. 2x2 matritsa uchun A = [ [a, b], [c, d] ], determinant ad - bc sifatida hisoblanadi. Masalan, A = [ [2, 3], [4, 5] ] matritsasi berilganda, determinant 25 - 34 = -2 ga teng. Kattaroq matritsalar uchun determinantni Laplas kengaytirish usuli, kofaktorni kengaytirish usuli va Gauss yo'q qilish usuli kabi turli usullar yordamida hisoblash mumkin. Bu usullar matritsani qo‘shish, ayirish, ko‘paytirish va inversiya kabi turli matritsa amallarini o‘z ichiga oladi.Determinant matritsa haqida muhim ma'lumotni beradi, masalan, uning invertiv yoki yo'qligi. Agar matritsaning determinanti nolga teng bo'lsa, u holda matritsa yagona bo'lib, uni teskari qilib bo'lmaydi. Agar determinant nolga teng bo'lmasa, u holda matritsa teskari bo'lib, uni turli usullar yordamida o'zgartirish mumkin, masalan, adjugat matritsa usuli va Gauss-Jordanni yo'q qilish usuli.