Çoğu zaman dikdörtgen parçalara (hücreler veya bloklar) bölünmüş matrisler kullanmanız gerekir. Bu bölümü bu tür “blok” matrislerin değerlendirilmesine ayırıyoruz.

1. Dikdörtgensel bir matris verilsin

Yatay kullanma ve dikey çizgiler Matrisi dikdörtgen bloklara keselim:

. (58)

Matris (58) için bloklara bölünmüş veya blok matris şeklinde sunulduğunu söyleyeceğiz. (58) yerine kısaltma olarak yazacağız:

Bu durumda aşağıdaki gösterimi kullanacağız:

Blok matrisleri üzerindeki eylemler, bloklar yerine sayısal elemanlarımızın olduğu durumla aynı resmi kurallara göre gerçekleştirilir. Örneğin, aynı boyutta ve bloklar halinde aynı bölüme sahip iki dikdörtgen matris verilsin:

Bunu görmek kolaydır

. (62)

Çarpma işlemine daha yakından bakalım blok matrisler. İki dikdörtgen matris çarpılırken birinci faktördeki satırların uzunluğunun ikinci faktördeki sütunların yüksekliğiyle çakışması gerektiği bilinmektedir (bkz. Bölüm I, s. 17). Bu matrislerin blok çarpımını etkinleştirmek için ek olarak bloklara bölümlendirirken tümünün de olmasını isteyeceğiz. yatay boyutlar birinci faktörde ikincideki karşılık gelen dikey boyutlarla çakıştı:

, . (63)

O zaman bunu kontrol etmek kolaydır

, Nerede . (64)

Faktörlerden birinin yarı köşegen matris olduğu özel duruma ayrıca dikkat edelim. Yarı köşegen bir matris olsun, yani ve için. Bu durumda formül (64) bize şunu verir:

Bir blok matris yarı-köşegen bir matris ile çarpıldığında, blok matrisin satırları solda yarı-köşegen matrisin karşılık gelen çapraz hücreleri ile çarpılır.

Şimdi yarı köşegen bir matris olsun, yani ve için. O halde (64)'ten şunu elde ederiz:

Sağdaki bir blok matrisi yarı köşegen bir matrisle çarparken, blok matrisin tüm sütunları sağda yarı köşegen matrisin karşılık gelen çapraz hücreleriyle çarpılır.

Faktörler aynı kare blok modellerine bölündüğünde ve faktörlerin her birinde köşegen yerlerde kare matrisler olduğunda, aynı sıradaki kare blok matrislerin çarpımının her zaman mümkün olduğunu unutmayın.

Bir blok matrise (58), üst (alt) yarı üçgen eğer ve hepsi için (sırasıyla hepsi için) denir. Yarı üçgen bir matrisin özel bir durumu, yarı köşegen bir matristir.

Formül (64)'ten iki üst (alt) yarı üçgen matrisin çarpımının yine bir üst (alt) yarı üçgen matris olduğunu görmek kolaydır; bu durumda çarpımın köşegen blokları, faktörlerin karşılık gelen köşegen bloklarının çarpılmasıyla elde edilir.

Gerçekten de, (64)’ü varsayarsak ve

.

Alt yarı üçgen matrislerin durumu da benzer şekilde analiz edilir.

Yarı üçgen bir matrisin determinantını hesaplama kuralını not edelim. Bu kural Laplace açılımına dayanarak elde edilebilir.

Kare köşegen bloklara sahip yarı üçgen (özellikle yarı köşegen) bir matris ise, bu matrisin determinantı ürüne eşitçapraz blok belirleyicileri:

(67)

2. Bir blok matrisi verilsin

(68)

Daha önce solda boyutunda dikdörtgen bir matrisle çarptığımız inci satırı, inci bloğun satırına ekleyelim. Blok matrisini alalım

. (69)

Aşağıdaki kare blok diyagramı biçiminde sunulan yardımcı bir kare matrisi tanıtalım:

. (70)

Matrisin köşegen hücreleri, sıraları sırasıyla eşit olan birim matrisler içerir; Matrisin köşegen olmayan tüm blokları, inci blok sırasının inci blok sütunu ile kesiştiği yerde bulunan blok hariç, sıfıra eşittir.

Bunu görmek zor değil

Dolayısıyla, tekil olmayan bir matris olduğundan, sahip olduğumuz matrislerin mertebeleri için

Bir kare matrisin olduğu özel durumda, (71)'den şunu elde ederiz:

Ancak yarı üçgen bir matrisin determinantı 1'dir:

Buradan,

Aynı sonuçlara, matrisin (67) herhangi bir sütununa, daha önce sağda uygun boyutlarda dikdörtgen bir matrisle çarpılmış başka bir sütun eklenirse de ulaşılabilir.

Elde edilen sonuçlar aşağıdaki teorem şeklinde formüle edilebilir.

Teorem 3. Bir blok matrisinde, daha önce solda (sağda) uygun boyutlarda dikdörtgen bir matris ile çarpılmış olan inci blok satırını (sütun) üçüncü blok satırına (sütununa) eklersek, bu dönüşüm, matrisin rütbesi ve ayrıca bir kare matris olması durumunda ve matrisin determinantı.

3. Şimdi şunu düşünün özel durum, matristeki köşegen blok bir kare olduğunda ve ayrıca tekil olmayan bir matris () olduğunda.

Matrisin üçüncü satırına soldan çarpılan ilk satırı ekliyoruz. Daha sonra matrisi elde ederiz

, (76)

. (77)

Eğer kare tekil olmayan bir matris ise bu işleme devam edilebilir. Böylece genelleştirilmiş Gauss algoritmasına ulaşıyoruz.

Bir kare matris olsun. Daha sonra

. (78)

Formül (78), bloklardan oluşan bir determinantın hesaplanmasını, bloklardan oluşan daha düşük dereceli bir determinantın hesaplanmasına indirger.

Dört bloğa bölünmüş determinantı düşünün:

nerede ve kare matrislerdir.

İzin vermek . Daha sonra, daha önce solda çarpılan ilk satırı ikinci satırdan çıkarın. Şunu elde ederiz:

. (BEN)

Aynı şekilde, eğer , o zaman ilk satırdan daha önce solda çarpılan ikinciyi çıkarırız. Şunu elde ederiz:

. (II)

Dört matrisin tamamının kare (aynı dereceden) olduğu özel durumda, Schur'un formülleri (I) ve (II)'den gelir ve üçüncü dereceden determinantın hesaplamasını, matrisin determinantının hesaplanmasına indirger. sıra:

(), (la)

(). (IIa)

Matrisler birbirleriyle değişimli ise (la)'dan şu sonuç çıkar:

(bu göz önüne alındığında). (Ib)

Aynı şekilde, eğer birbirleriyle işe gidip gelirlerse, o zaman

(bu göz önüne alındığında). (IIb)

Formül (Ib) varsayım altında ve formül (IIb) koşul altında elde edildi. Ancak süreklilik hususlarına bağlı olarak bu kısıtlamalar iptal edilebilir.

(Ia) - (IIb) formüllerinden, sağ taraftaki ve ve aynı anda yer değiştirerek altı formül daha elde edebiliriz.

.

Formül (Ib)'ye göre

.

4. Bir blok matrisi ters çevirmek için Frobenius formülünü oluşturalım. Tekil olmayan kare matrisin () bloklara bölünmesine izin verin

, (80)

ve let de tekil olmayan bir kare matristir (). Belirlenmesi gerekiyor.

Genelleştirilmiş Gauss algoritmasını matrise uygulayalım. İkinci blok satırından, daha önce solda çarpılan birinciyi çıkarırız. Bu işlem soldaki matrisi matrisle çarpmaya eşdeğerdir; burada . Bu yüzden

. (81)

Gösterimi tanıtalım

ve eşitlikten (81) şu sonucun çıktığına dikkat edin:

Bu nedenle, o zamandan beri ve . Eşitlikteki (81) ters matrislere geçerek şunu elde ederiz:

. (83)

Şeklindeki matrisin ters matrisini arayacağız. Daha sonra eşitlikten

bunu bulduk . Böylece,

. (84)

Ama sonra eşitlikten (83) şunu buluruz:

Eşitliğin (85) sağ tarafında blok matris çarpımı yaparak Frobenius formülüne ulaşıyoruz.

, (86)

. (87)

Frobenius formülü (86), bir sıra matrisinin ters çevrilmesini, iki sıra matrisin ters çevrilmesine ve , , ve boyutlarına sahip matrislerin toplama ve çarpma işlemlerine indirger.

Bunu ( yerine) varsayarsak ve matrislerin ve matrislerinin rollerini değiştirirsek, Frobenius formülünün başka bir formunu elde edebiliriz:

, (88)

. (89)

Örnek. Öğeleri bulmak için gerekli ters matris matris için

.

İnanıyoruz

Sırayla buluyoruz

, ,

, ,

,

,

,

.

Bu nedenle, (86) formülünü kullanarak şunu buluruz:

.

5. Teorem 3 aynı zamanda şunu da ifade eder:

Teorem 4. Eğer dikdörtgen matris blok şeklinde sunulur

tekil olmayan bir kare matris () nerede, o zaman matrisin sırası yalnızca eğer eşittir

Kanıt. Matrisin ikinci blok satırından daha önce solda çarpılan ilk satırı çıkaralım. Daha sonra matrisi elde ederiz

. (92)

Matrisler ve Teorem 3'e göre aynı rütbeye sahiptirler. Matrisin sıralaması, matrisin sıralamasıyla (yani c) ancak ve ancak geçerliyse, yani (91) çakışır. Teorem kanıtlandı.

Bu bulma yöntemini aşağıdaki örnekle açıklayalım.

Örnek. İzin vermek

Hesaplamak için gereklidir.

Matrise biraz değiştirilmiş bir eleme yöntemi uyguluyoruz

.

Tüm satırlara bir faktör içeren ikinci bir satır ekliyoruz ve ikinci sütun dışındaki ilk sütunun tüm öğelerinin sıfıra eşit olmasını sağlıyoruz. Bundan sonra ikinci hariç tüm satırlara bir miktar faktör içeren üçüncü bir satır ekliyoruz ve ikinci sütunda ikinci ve üçüncü hariç tüm elemanların sıfıra eşit olmasını sağlıyoruz. Bundan sonra, son üç satıra ilk satırı bir miktar faktörle ekleriz ve formun bir matrisini elde ederiz.

.

,

,

.

9. Matris transpozisyon işlemi ve özellikleri.

Tanım: A matrisinden satırların sütunlarla değiştirilmesiyle elde edilen A' matrisine A matrisine göre transpoze matris denir.

Matrislerin yer değiştirmesi için aşağıdaki kurallar geçerlidir:

(αA+αB)’=αA’ + αB’

(AB)'=B'A'

İspatın amacı (AB)' ve B'A' matrislerinin aynı boyuta sahip olduğunu ve karşılık gelen elemanlarının eşit olduğunu göstermektir.

Tanım: A keyfi bir kare matrisse ve A=A’ (-A=A’) ise A matrisine simetrik matris denir
veya çarpık simetrik

10. Ters matrisin tanımı. Her ters çevrilebilir matrisin yalnızca bir ters çevrilmesinin olduğunu kanıtlayın.

Tanım:

A A -1= A -1 A=E Buradan A -1 matrisinin tersinin (A -1) -1 =A olacağı sonucu çıkar.

Teorem: Her ters çevrilebilir matrisin benzersiz bir ters çevrilmesi vardır.

Kanıt: A matrisinin X ile birlikte başka bir ters Y matrisine sahip olduğunu varsayalım; AU=E. Daha sonra

(HA)U=AB=U ┐

X(AU)=XE=X ┘Dolayısıyla X=Y. Onlar. A matrisinin benzersiz bir dönüşümü vardır (vb.)

11. Ters matrisin tanımı. Bunu kanıtla (ABC) -1 =C -1 İÇİNDE -1 A -1 .

Tanım: AX=XA=E olacak şekilde bir X kare matrisi mevcutsa, A kare matrisinin tersinin olduğu söylenir. (1)

Eşitliği (1) karşılayan her X matrisine A matrisinin tersi veya A matrisinin tersi denir. A matrisinin ters matrisi A -1 ile gösterilir.

A A -1= A -1 A=E Buradan A -1 matrisinin tersinin (A -1) -1 =A (3) olacağı sonucu çıkar.

Teorem: Aynı mertebeden A, B, C kare matrisleri tersinirse, bunların çarpımı da tersinirdir ve (ABC) -1 =C -1 B -1 A -1 .

Kanıt: A(B(CC -1)B -1)A -1 =E ve C -1 (B -1 (A -1 A)B)C=E (h.t.d.)

Herhangi bir doğal m için, tanım gereği, A m = A*A*…*A – m-çarpı.

Tanım gereği A 0 = E.

Tanım: Her ters çevrilebilir A matrisi için, A -2 =A -1 *A -1 ; A -3 = A -1 *A -1 *A -1 (4)

(3) ve (4)'ten her tersinir A matrisi ve herhangi bir p ve q tam sayısı için elimizde olduğu sonucu çıkar: normal kurallar dereceli eylemler:

Bir r Bir q =A r+ q

(AB) p =A p B p eğer AB=BA ise

(A p) q =A p* q

12.Tersine çevrilebilir bir matrisin yer değiştirmesi sonucunda tekrar tersinir bir matris elde ettiğimizi ve ( A ’) -1 =( A -1 )’.

Teorem: Ters çevrilebilir A matrisinin transpozisyonunun bir sonucu olarak, yine ters çevrilebilir bir matris elde ederiz ve (A') -1 = (A -1)'.

Kanıt: Transpozisyon kurallarını AX=XA=E ilişkisine uygulayalım:

(AH)'=(HA)'=E'

A'X'=X'A'=E

Ters matrisin tanımından şu sonuç çıkar: (A') -1 = X'=(A -1)'(h.t.c.)

13. Matrisleri bloklayın. Blok matrislerin toplanması ve çarpımı. Yarı üçgen bir matrisin determinantı üzerine teorem.

Dikdörtgen bir matris A, dikey ve yatay çizgilerle dikdörtgen hücrelere (bloklara) bölünebilir. Özellikle matris yalnızca yatay veya yalnızca dikey çizgilerle bölünebilir. (A α,β) s , t – blok matrisi. Aynı boyutta ve aynı bloklara bölünmüş iki A ve B matrisini düşünün. Karşılık gelen A α,β ve B α,β blokları aynı boyuta sahiptir m α x n β , α=1..s, β=1..t. Daha sonra matris toplama kuralına uygun olarak aynı büyüklükte ve aynı bölmeye sahip blok matrislerin bloklara eklenmesi işlemi, sanki bloklar yerine sayısal elemanlar varmış gibi tamamen aynı şekilde gerçekleştirilir.

Matris çarpımı kuralını blok matrislere genişletmek için, birinci matrisin bloklarının tüm yatay boyutlarının, ikinci faktörün karşılık gelen boyutlarıyla çakışması gerekir. A bloğunun sütun sayısı α,β, B bloğunun satır sayısına eşittir β,c.

Β 1'den t'ye değişir, c 1'den u'ya değişir. Böylece, A ve B matrislerini sanki bloklar yerine sayısal öğeler varmış gibi biçimsel olarak çarpmak mümkündür.

Tanım: Ana köşegenin altında (yukarıda) bulunan tüm elemanların 0'a eşit olduğu kare matrise üst (alt) üçgen matris denir. Blok matrisler için benzer kavramlar tanıtılmıştır.

Tanım: Tüm diyagonal bloklar ve A matrisinin kendisi kare matris ise ve diyagonal blokların altında (yukarıda) bulunan tüm diyagonal olmayan bloklar sıfır matris ise, bir blok matrisi A'ya üst (alt) yarı üçgen matris denir.

Tanım: Tüm köşegen bloklar ve A matrisinin kendisi kare matrislerse ve köşegen olmayan tüm bloklar sıfır matris ise, A blok matrisine yarı köşegen denir.

Teorem: Yarı üçgen bir matrisin determinantı, aşağıdaki ilişkiyle köşegen matrislerin determinantıyla ilişkilidir:

(♀) burada P üründür.

Kanıt:İlk önce yarı üçgen matrisi ele alalım
burada A 12 =0,
,
,

Tanım gereği

Çünkü Ve 12 =0 ise tüm ürünler arasında yalnızca endeksleri eşit olan ürünler ≠0 olabilir
. Sonuç olarak, kalan endeksler yalnızca kümeden değer alabilir
. Bu koşullar altında bir permütasyondaki ters çevirme sayısı
eşittir:

Bunu dikkate aldığımızda şunu buluyoruz

Şunu takip ediyor

Düşünülüyor genel durum yarı üçgen matris

Bir matris gibi
Nerede

(*)'a göre elimizde olacak
. Matris
yine yarı üçgen. Üzerinde aynı işlemi gerçekleştirdikten sonra şunu elde ederiz:
. (p-1) gibi adımlardan sonra (♀) noktasına ulaşıyoruz.

Eşitlik (♀), üst yarı üçgen matrise (vb.) göre benzer şekilde kanıtlanır.

Bölüm 1
MATRİSLER VE BELİRTİCİLER

Bu bölümde gelecekte çok önemli rol oynayacak olan matris adı verilen sayı tablolarını inceleyeceğiz. Burada matrisler üzerindeki temel işlemler tanıtılmakta ve temel işlemler olan determinantların özellikleri tanıtılmaktadır. sayısal karakteristik kare matrisler.

§ 1. Matrisler

1. Matris kavramı. Matris, belirli sayıda m satır ve belirli sayıda n sütun içeren dikdörtgen bir sayı tablosudur. Tip numaralarına matris sıraları denir. M = n ise matrise kare denir ve m = n sayısı onun mertebesidir. Gelecekte matrisi yazmak için çift tire veya parantez kullanılacaktır:

Ancak, kısa tanım matrisler genellikle ya bir büyük Latin harfini (örneğin A) ya da ║ sembolünü kullanır bir ben ║ ve bazen bir açıklama ile:
Bu matrisin içerdiği a ij sayılarına onun elemanları denir. a ij girişinde - ilk indeks i satır numarasını, ikinci indeks j ise sütun numarasını ifade eder.
Kare matris durumunda

Ana ve ikincil köşegen kavramları tanıtılmaktadır. Ana diyagonal matris (1.1)'e soldan gelen a 11 a 22 ...a nn köşegeni denir üst köşe bu matrisin sağ alt köşesine. Yan diyagonal aynı matrisin sol alt köşesinden sağ üst köşesine giden köşegen a n1 a (n-1)2 ...a 1n olarak adlandırılır.

2. Matrisler üzerinde temel işlemler ve özellikleri.Öncelikle iki matrisin hesaplanmasında anlaşalım eşit, eğer bu matrisler aynı mertebelere sahipse ve karşılık gelen tüm elemanları aynıysa.
Matrisler üzerindeki temel işlemleri tanımlamaya geçelim.
A) Matris eklenmesi.Miktar iki matris A = ║ bir ben ║(i = 1, 2,..., m; j = 1, 2,..., n) ve B = (i = 1, 2,..., m; j = 1, 2,... , n) aynı mertebelerden m ve n'ye bir matris denir C= (i = 1, 2,..., m; j = 1, 2,..., n) aynı mertebelerden m ve n, elemanlar c ij - eşit olan

C ij = a ij + b ij (i = 1, 2,..., m ; j = 1, 2,... , n ) (1,2

İki matrisin toplamını belirtmek için C = A + B gösterimi kullanılır. Matrislerin toplamını oluşturma işlemine denir. ek. Yani tanım gereği

Matrislerin toplamının tanımından veya daha doğrusu formül (1.2)'den, matris toplama işleminin toplama işlemiyle aynı özelliklere sahip olduğu hemen anlaşılır. gerçek sayılar yani:
1) değişme özelliği: A + B = B + A;
2) ilişkisel özellik: (A + B) + C = A + (B + C).
Bu özellikler, iki veya daha fazlasını toplarken matrislerin terimlerinin sırası konusunda endişelenmemenizi sağlar. Daha matrisler

B) Bir matrisin bir sayıyla çarpılması. iş matris A = ║ bir ben ║(i = 1, 2,..., m; j = 1, 2,... , n) gerçel'e
λ sayısına C = (i = 1, 2,..., m; j = 1, 2,..., n) matrisi denir ve c ij elemanları eşittir

c ij = λ a ij (i = 1, 2,..., m ; j = 1, 2,... , n ) (1.3)

Bir matrisin çarpımını bir sayıyla belirtmek için C = λ A veya C = Aλ gösterimi kullanılır. Bir matrisin çarpımını bir sayıyla oluşturma işlemine matrisin bu sayıyla çarpılması denir. Doğrudan formül (1.3)'ten, bir matrisin bir sayıyla çarpılmasının aşağıdaki özelliklere sahip olduğu açıktır:
1) sayısal bir faktöre göre birleştirici özellik: (λ µ )A = λ( µ A);

2) dağılma özelliği matrislerin toplamı ile ilgili olarak: λ (A + B) = λ A + λ B;
3) sayıların toplamına ilişkin dağılım özelliği: (λ + µ )A = λBir + µ A.
Yorum. Aynı mertebeden iki A ve B matrisinin farkını, aynı m ve n mertebelerinden bir C matrisi olarak adlandırmak doğaldır; bu, B matrisinin toplamı ile A matrisini verir. İki matrisin farkını belirtmek için doğal bir gösterim kullanılır: C = A - B.
A ve B iki matrisinin C farkının C = A + (-1)B kuralıyla elde edilebileceğini doğrulamak çok kolaydır.
c) Matris çarpımı. iş matris A = ║ bir ben ║(i = 1, 2,..., m; j = 1, 2,..., n), B = (i = 1, 2,..) matrisinde sırasıyla m ve n'ye eşit mertebelere sahiptir. ., n ; j = 1, 2,..., p), sırasıyla n ve p'ye eşit olan matrislere C= (i = 1, 2,..., m; j = 1, 2,... , p), sırasıyla m ve p'ye eşit mertebelere sahiptir ve formülle tanımlanan c ij elemanları

A matrisi ile B matrisinin çarpımını belirtmek için C = A - B gösterimini kullanın. A matrisi ile B matrisinin çarpımını oluşturma işlemine denir. çarpma bu matrisler. Yukarıdaki tanımdan şu sonuç çıkıyor A matrisi her B matrisiyle çarpılamaz: A matrisinin sütun sayısının B matrisinin satır sayısına eşit olması gerekir.
Özellikle, hem A B hem de B A ürünleri, yalnızca A sütun sayısının B satır sayısıyla çakışması ve A satır sayısının B sütun sayısıyla çakışması durumunda belirlenebilir. Bu durumda, her iki A matrisi de - B ve B - A kare olacaktır ancak genel olarak sıralamaları farklı olacaktır. Hem A B hem de B A çarpımlarının sadece tanımlı olması değil aynı zamanda aynı sıraya sahip olması için hem A hem de B matrislerinin olması gerekli ve yeterlidir. kare matrisler aynı düzende.
Formül (1.4), A matrisi ile B matrisinin çarpımı olan C matrisinin elemanlarını oluşturma kuralıdır. Bu kural sözlü olarak da formüle edilebilir: eleman C ben , kavşakta duruyorumBen -satırlar veJ- inci matris sütunu

C = A B, toplamına eşit karşılık gelen elemanların ikili çarpımları i'inci çizgi A matrisi ve B matrisinin inci sütunu.
Bu kuralın uygulanmasına bir örnek olarak, ikinci dereceden kare matrislerin çarpılması formülünü sunuyoruz.

Formül (1.4)'ten şu şekilde çıkar: aşağıdaki özellikler A matrisi ile B matrisinin çarpımı:
1) ilişkisel özellik: (AB)C = A(BC);
2) matrislerin toplamına göre dağılım özelliği: (A + B)C = AC + BC veya A(B + C) = AB + AC.
Dağılma özelliği hemen (1.4) ve (1.2) formüllerinden çıkar ve kanıtlamak için ilişkisel özellik A = ║ ise şunu not etmek yeterlidir bir ben ║(i = 1, 2,..., m; j = 1, 2,..., n), B = (i = 1, 2,..., n; j = 1, 2,... , p ), C = (i = 1, 2,..., m ; j = 1, 2,... , p ), o zaman
(AB)C matrisinin d il elemanı (1.4) nedeniyle eşittir ve A(BC) matrisinin d il " elemanı eşittir ancak d il = d il " eşitliği, j ve k'ye göre toplama sırasının değiştirilme olasılığından kaynaklanır.
A matrisi ile B matrisinin çarpımının permütasyon özelliği hakkındaki sorunun yalnızca aynı mertebeden A ve B kare matrisleri için sorulması anlamlıdır (çünkü yukarıda belirtildiği gibi yalnızca bu tür matrisler için A ve B'nin her ikisi de AB ve BA'nın ürünüdür) Tanımlı ve aynı mertebeden matrislerdir). Temel örnekler şunu gösteriyor aynı mertebeden iki kare matrisin çarpımı genel olarak değişme özelliğine sahip değildir. Aslında şunu koyarsak

Ancak burada, değişme özelliğinin doğru olduğu önemli özel durumları göstereceğiz (Komütasyon özelliğinin doğru olduğu çarpım için iki matrise genellikle değişme denir). Kare matrisler arasında sözde sınıfını vurguluyoruz. diyagonal her biri sıfıra eşit ana köşegenin dışında bulunan öğelere sahip matrisler. N mertebesindeki her köşegen matris şu şekildedir:

burada d 1, d 2,..., d n herhangi bir sayıdır. Tüm bu sayıların birbirine eşit olması durumunda, yani d 1 = d 2= ...= d n = d, o zaman herhangi biri için olduğunu görmek kolaydır.
N mertebesinden A kare matrisi için AD = DA eşitliği sağlanır. Aslında, AD ve DA matrislerinin i'inci satırı ile j-ro sütununun kesişiminde bulunan elemanları sırasıyla Cij ve cf(j) simgeleriyle gösterelim. Sonra eşitlikten (1.4) ve D matrisinin formunda şunu elde ederiz: c ij =a ij d j = a ij d , c ij " = d i a ij = da ij (1.6), yani c ij = c ij " .

Eşleşen elemanlara sahip tüm köşegen matrisler (1.5) arasında d 1 = d 2= ...= d n önemli rol iki matris oynuyor. Bu matrislerden ilki d = 1 için elde edilir ve denir. n'inci dereceden kimlik matrisi ve E sembolü ile gösterilir. İkinci matris d = 0'da elde edilir ve denir n'inci dereceden sıfır matrisi ve O sembolü ile gösterilir. Böylece,

Yukarıda kanıtlanmış olanlara göre, AE = EA ve AO = O A. Ayrıca formül (1.6)'dan da açıkça görülmektedir ki

AE = EA = E, AO = OA = O. (1.7)

Formüllerden (1.7) ilki, gerçel sayıları çarparken 1 sayısının oynadığı role benzer şekilde E birim matrisinin özel rolünü karakterize eder. Sıfır matrisi O'nun özel rolüne gelince, bu sadece formüllerin (1.7) ikincisi ile değil, aynı zamanda temel doğrulanabilir eşitlik A + O = O + A = A ile de ortaya çıkar (bu eşitlik, formülün doğrudan bir sonucudur) (1.2)).
Sonuç olarak, sıfır matris kavramının kare olmayan matrisler için de getirilebileceğini not ediyoruz (sıfır matris, elemanlarının tümü sıfır olan herhangi bir matristir).
3. Matrisleri bloklayın. Diyelim ki bir A matrisi = ║ bir ben ║ yatay ve dikey çizgiler kullanılarak, her biri daha küçük boyutlu bir matris olan ve adı verilen ayrı dikdörtgen hücrelere bölünür. orijinal matrisin bloğu. Bu durumda, orijinal A matrisini yeni (blok adı verilen) bir A = ║ matrisi olarak düşünmek mümkün hale gelir. bir αβ ║, elemanlar bir αβ bu bloklar neye hizmet ediyor?
Bu unsurları büyük olarak belirtiyoruz Latince harf, genel anlamda bunların sayı değil matris olduğunu vurgulamak için ve (sıradan sayısal öğeler gibi) iki endeks sağlıyoruz; bunlardan ilki "blok" satırının numarasını ve ikincisi "blok" satırının numarasını gösteriyor " kolon. Örneğin, bir matris

elemanları aşağıdaki bloklardan oluşan bir blok matrisi olarak düşünülebilir:

Dikkat çekici olan, blok matrislerle yapılan ana işlemlerin, sıradan sayısal matrislerle gerçekleştirilen aynı kurallara göre gerçekleştirilmesi, yalnızca blokların öğe olarak hareket etmesidir.
Aslında A matrisinin = ║ olup olmadığını kontrol etmek kolaydır. bir ben ║ blok düzeyindedir ve blok düzeyinde öğelere sahiptir bir αβ, daha sonra aynı bloklara bölme ile λ A = ║λ matrisi bir ben ║λ blok elemanlarına karşılık gelir bir αβ(Bu durumda blok elemanları λ bir αβ kendileri matris çarpım kuralı kullanılarak hesaplanır bir αβλ sayısına göre).
A ve B matrislerinin aynı sıralara sahip olması ve aynı şekilde bloklara bölünmesi durumunda, A ve B matrislerinin toplamının elemanlı bir blok matrise karşılık gelip gelmediğini kontrol etmek de aynı derecede kolaydır. bir αβ = bir αβ + B αβ(Burada bir αβ Ve B αβ- A ve B matrislerinin blok elemanları).
Son olarak, A ve B'nin her bloğun sütun sayısı olacak şekilde iki blok matrisi olmasına izin verin. bir αβ B bloğundaki satır sayısına eşit β γ (Bu yüzden
herhangi biri için α, β ve γ matrislerin çarpımı tanımlanır bir αβİÇİNDE β γ ). O halde C = A B ürünü, C elemanlarını içeren bir matristir. α γ , formülle tanımlanan

Bu formülü kanıtlamak için sol ve sağ kısımlarını A ve B matrislerinin sıradan (sayısal) elemanları cinsinden yazmak yeterlidir (bunu okuyucuya bırakıyoruz).
Blok matrislerin kullanımına bir örnek olarak, kare matrislerin doğrudan toplamı kavramı üzerinde duralım. Doğrudan tutar Sırasıyla m ve n mertebelerindeki A ve B kare matrislerine, m + n mertebelerinde, eşit olan kare blok matris C denir. A ve B matrislerinin doğrudan toplamını belirtmek için C = A gösterimi kullanılır

İnşa ederken paralel yöntemler Matris çarpımını gerçekleştirmek için, matrisleri satır ve sütun kümeleri olarak kabul etmenin yanı sıra, matrislerin blok gösterimi yaygın olarak kullanılır. Daha yakından bakalım bu yöntem hesaplamaların organizasyonu.

7.4.1. Alt görevleri tanımlama

Matrisleri bölümlemeye yönelik blok şeması, "Bir matrisi bir vektörle çarpmak için paralel yöntemler" birinci bölümünde ayrıntılı olarak açıklanmaktadır. Bu veri bölme yöntemiyle, orijinal A, B matrisleri ve sonuçta ortaya çıkan C matrisi blok kümeleri olarak temsil edilir. Aşağıdaki materyalin daha basit bir sunumu için, ayrıca tüm matrislerin nxn boyutunda kareler olduğunu, blok sayısının yatay ve dikey olarak aynı ve q'ya eşit olduğunu (yani tüm blokların boyutunun kxk, k'ye eşit olduğunu) varsayacağız. =n/q). Verilerin bu temsiliyle matris işlemi matris çarpımı A ve B blok formunda şu şekilde temsil edilebilir:

C matrisinin her C ij bloğunun ifadeye göre tanımlandığı yer

Temel alt görevleri belirlemek için verileri bloklara ayırırken matris blokları üzerinde yapılan hesaplamaların esas alınması doğal görünmektedir. Yukarıdakileri dikkate alarak, temel alt görevi, C matrisinin bloklarından birinin tüm elemanlarını hesaplama prosedürü olarak tanımlıyoruz.

Gerekli tüm hesaplamaları gerçekleştirmek için, temel alt görevlerin A matrisinin uygun satır ve B matris sütunlarına erişimi olmalıdır. Gerekli tüm verilerin her bir alt göreve yerleştirilmesi, kaçınılmaz olarak çoğaltmaya ve kullanılan bellek miktarında önemli bir artışa yol açacaktır. Sonuç olarak, hesaplamalar, alt görevlerin hesaplamalar için gerekli verilerin yalnızca bir kısmını içereceği ve verilerin geri kalanına erişimin, işlemciler arasında veri aktarımı yoluyla sağlanacağı şekilde, her güncel anda düzenlenmelidir. Olası bir yaklaşım Fox algoritmasıdır ( Tilki) – bu alt bölümde daha ayrıntılı olarak ele alınmıştır. İkinci yöntem Cannon algoritmasıdır ( Top) – altbölüm 7.5'te verilmiştir.

7.4.2. Bilgi bağımlılıklarının belirlenmesi

Dolayısıyla, blok veri bölmeli matris çarpımı için paralel hesaplamaların temeli, temel alt görevlerin C matrisinin ayrı ayrı bloklarını hesaplamaktan sorumlu olduğu ve aynı zamanda hesaplamaların her yinelemesinde alt görevlerde yalnızca orijinal A ve B matrislerinin bir bloğu. Alt görevleri numaralandırmak için, alt görevlere yerleştirilen C matrisinin bloklarının indekslerini kullanacağız; alt görev (i,j), C ij bloğunun hesaplanmasından sorumludur - dolayısıyla alt görevler kümesi, C matrisinin blok temsilinin yapısına karşılık gelen kare bir kafes oluşturur.

Bu koşullar altında hesaplamaları düzenlemenin olası bir yolu, iyi bilinen yöntemi kullanmaktır. Fox algoritması (Tilki) - örneğin, [ [34] , [51] ]'e bakın.

Fox algoritmasına uygun olarak, hesaplamalar sırasında her temel alt görev (i,j) üzerinde dört matris bloğu bulunur:

• alt görev tarafından hesaplanan C matrisinin C ij bloğu;
• hesaplamaların başlamasından önce alt göreve yerleştirilen A matrisinin A ij bloğu;
• hesaplamalar sırasında alt görev tarafından elde edilen A ve B matrislerinin A" ij, B" ij blokları.

Uygulamak paralel yöntemşunları içerir:

• A ij, B ij bloklarının her bir alt göreve (i,j) aktarıldığı ve Cij bloklarının tüm alt görevlerde sıfıra sıfırlandığı başlatma aşaması;
• hesaplamaların aşaması, her yinelemede l, 0<=l

Şekil 2'de paralel yöntemin bu kurallarını açıklamak için. Şekil 7.6, hesaplama aşamasının yinelemeleri sırasında her bir alt görevdeki blokların durumunu gösterir (2x2 alt görev kafesi için).

7.4.3. Alt görevlerin işlemciler arasında ölçeklendirilmesi ve dağıtılması

Dikkate alınan paralel hesaplama şemasında, blok sayısı, blok boyutu seçimine bağlı olarak değişebilir - bu boyutlar, toplam temel alt görev sayısı p işlemci sayısıyla çakışacak şekilde seçilebilir. Dolayısıyla, örneğin en basit durumda, işlemci sayısı formda temsil edilebildiğinde (yani tam kare olduğunda), matrislerdeki blok sayısı dikey ve yatay olarak eşit olacak şekilde seçilebilir (ör. ). Blok sayısını belirlemeye yönelik bu yöntem, her bir alt görevdeki hesaplama miktarının aynı olmasına ve dolayısıyla işlemciler arasındaki hesaplama yükünün tamamen dengelenmesine yol açar. Daha genel bir durumda, isteğe bağlı sayıda işlemci ve matris boyutuyla dengeleme hesaplamaları tamamen aynı olmaktan farklı olabilir, ancak yine de uygun parametre seçimiyle işlemciler arasında gerekli doğrulukta eşit olarak dağıtılabilir.

Temel alt görevlerin kare kafes şeklinde temsil edildiği ve hesaplamalar sırasında blokların alt görev kafesinin satırları ve sütunları boyunca aktarılması işlemlerinin gerçekleştirildiği Fox algoritmasını etkin bir şekilde uygulamak için en uygun çözüm seti organize etmektir. mevcut işlemcilerin sayısı da kare kafes şeklindedir. Bu durumda, bir dizi alt görevi doğrudan birçok işlemciye eşlemek mümkündür - temel alt görev (i,j), Pi,j işlemcisinde bulunmalıdır. Bilgi işlem sisteminin topolojisinin bir kafes veya tam bir grafik biçiminde olması durumunda, veri iletim ağının gerekli yapısı fiziksel düzeyde sağlanabilir.

7.4.4. Performans Analizi

Bu Fox algoritmasının hesaplama karmaşıklığını belirleyelim. Tahminlerin oluşturulması, önceden yapılan tüm varsayımların yerine getirilmesine bağlı olarak gerçekleşecektir: tüm matrisler nxn boyutunda karedir, yatay ve dikey olarak blok sayısı aynı ve q'ya eşittir (yani, tüm blokların boyutu kxk'ye eşittir) , k=n/q), işlemciler kare kafes oluşturur ve sayıları p=q 2'ye eşittir.

Daha önce belirtildiği gibi, Fox algoritması, yürütülmesi için q yineleme gerektirir; bu sırada her işlemci, mevcut A ve B matris bloklarını çarpar ve çarpma sonuçlarını C matris bloğunun mevcut değerine ekler. Yapılan varsayımlar dikkate alındığında, bu durumda gerçekleştirilen toplam işlem sayısı n3/p düzeyinde olacaktır. Sonuç olarak, algoritmanın hızlanma ve verimlilik göstergeleri şu şekildedir:

Genel karmaşıklık analizi yine ideal paralel hesaplama verimliliği ölçümleri sağlar. Elde edilen ilişkileri açıklığa kavuşturalım - bunun için algoritmanın hesaplamalı işlemlerinin sayısını daha kesin olarak belirteceğiz ve yürütme maliyetlerini dikkate alacağız veri aktarım işlemleri işlemciler arasında.

Hesaplamalı işlemlerin sayısını belirleyelim. Uygulamanın zorluğu skaler çarpım A matris bloğunun satırları, B matris bloğunun sütun başına 2(n/q)-1 olarak tahmin edilebilir. Bloklardaki satır ve sütun sayısı n/q'ya eşittir ve bunun sonucunda blok çarpma işleminin karmaşıklığı (n 2 /p)(2n/q-1)'e eşittir. Blok eklemek n 2 /p işlemlerini gerektirir. Yukarıdaki ifadelerin tümü dikkate alınarak Fox algoritmasının hesaplamalı işlemlerinin yürütme süresi aşağıdaki şekilde tahmin edilebilir:

(bir temel skaler işlem için yürütme süresi olduğunu hatırlayın).

Uygulama maliyetlerini tahmin edelim veri aktarım işlemleri işlemciler arasında. Algoritmanın her yinelemesinde, blokları çarpmadan önce, işlemci ızgarasının bir satırındaki işlemcilerden biri, A matrisinin bloğunu satırındaki diğer işlemcilere gönderir. Daha önce belirtildiği gibi, hiperküp veya tam grafik biçimindeki bir ağ topolojisi ile bu işlem log 2 q adımlarla tamamlanabilir ve iletilen blokların hacmi n2/p'ye eşittir. Sonuç olarak, Hockney modeli kullanılarak A matrisinin bloklarının aktarılması işleminin yürütme süresi şu şekilde tahmin edilebilir:

Gecikme nerede, veri ağının verimi ve w, matris öğesinin bayt cinsinden boyutudur. İşlemci ızgarasının sıralarının topolojisinin bir halka olması durumunda, A matrisinin bloklarının iletim süresini tahmin etmeye yönelik ifade şu şekli alır:

Daha sonra, matris bloklarını çarptıktan sonra işlemciler, matris B bloklarını işlemci kafesinin sütunları boyunca önceki işlemcilere iletirler (sütunlardaki ilk işlemciler, verilerini kafesin sütunlarındaki son işlemcilere iletir). Bu işlemler işlemciler tarafından paralel olarak gerçekleştirilebilir ve dolayısıyla böyle bir iletişim işleminin süresi:

(q parametresinin işlemci ızgarasının ve ebadını belirlediğini hatırlayın).