Matematické Fórum

klinki · 23. 04. 2013 12:11

Zdravím, prosím o radu jak co nejelegantněji dokázat korektnost algoritmu násobení matic metodou rozděl a panuj.

Vpodstatě vím jak to dokázat a není to tak složité, lze na to použít indukce. Ale je to hrozně dlouhé a nepřehledné.

Chtěl jsem se zeptat, zda na to nelze jít nějak elegantněji, aby se v tom dalo vyznat...

Tady je stručný popis algoritmu a ukázka jak jsem to zkoušel dokázat:

Algoritmus se používá pro násobení čtvercovích matic o velikosti mocniny 2. Je popsán zhruba takto:
Matice A, B, C o velikosti $2^n$ se rozdělí na 4 podmatice o velikosti $2^{n-1}$ pro $n\geq1$ . Následně se vypočítají matice X1 ... X8 a z nich se vypočítá matice C (viz níže) .

Postupoval jsem tak, že jsem ověřil, zda to platí pro n = 1 (tj. matice 2x2). Když to rozepíšu, vypadá to zhruba takto:

$A = \begin{matrix} a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{matrix} \\$
$B = \begin{matrix} b_{1,1} & b_{1,2} \\ b_{2,1} & b_{2,2} \end{matrix} \\$
$C = \begin{matrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{matrix} \\$
$X_1 = a_{1,1} * b_{1,1} \\ X_2 = a_{1,2} * b_{2,1} \\ X_3 = a_{1,1} * b_{1,2} \\ X_4 = a_{1,2} * b_{2,2} \\ X_5 = a_{2,1} * b_{1,1} \\ X_6 = a_{2,2} * b_{2,1} \\ X_7 = a_{2,1} * b_{1,2} \\ X_8 = a_{2,2} * b_{2,2} \\$
$c_{1,1} = X_1 + X_2 = a_{1,1} * b_{1,1} + a_{1,2} * b_{2,1} \\ c_{1,2} = X_3 + X_4 = a_{1,1} * b_{1,2} + a_{1,2} * b_{2,2} \\ c_{2,1} = X_5 + X_6 = a_{2,1} * b_{1,1} + a_{2,2} * b_{2,1} \\ c_{2,2} = X_7 + X_8 = a_{2,1} * b_{1,2} + a_{2,2} * b_{2,2} \\$

no a když se podívám na to jak se vypočítávají jednotlivé prvky C, je vidět že je použit stejný vzorec jako v klasické definici násobení matic tudíž pro n = 1 to platí.

Klasická definice násobení matic:
$(A B)_{i,j} = \sum_{r=1}^{n}{a_{i,r} b_{r,j}} =a_{i,1} b_{1,j} + a_{i,2} b_{2,j} + \dots + a_{i,n} b_{n,j}$ pro všechny prvky $(i, j), i \in <1,m>, j \in <1, p>$ .

$c_{1,1} = (A B)_{1, 1} = a_{1,1} * b_{1,1} + a_{1,2} * b_{2,1} \\ c_{1,2} = (A B)_{1, 2} = a_{1,1} * b_{1,2} + a_{1,2} * b_{2,2} \\ c_{2,1} = (A B)_{2, 1} = a_{2,1} * b_{1,1} + a_{2,2} * b_{2,1} \\ c_{2,2} = (A B)_{2, 2} = a_{2,1} * b_{1,2} + a_{2,2} * b_{2,2} \\$

2. krok je indukční předpoklad, že když to platí pro n, bude to platit pro n+1. A tady to začíná být ošklivé. Když si rozepíšu rozložení obecné matice o velikosti 2^(n+1) tak je to docela dlouhý, nemluvě o maticích X1...X8.

$k = 2^m+1 \\ l = 2^{m+1} \\$
$A = \begin{pmatrix} a_{1,1} & \cdots & a_{1,l} \\ \vdots & \ddots & \vdots \\ a_{l,1} & \cdots & a_{l,l} \end{pmatrix}$
$A = \begin{pmatrix} A_{1,1} & A_{1, 2} \\ A_{2,1} & A_{2,2} \end{pmatrix}$
$A_{1,1} = \begin{pmatrix} a_{1,1} & \cdots & a_{1,2^{m}} \\ \vdots & \ddots & \vdots \\ a_{2^{m},1} & \cdots & a_{2^{m},2^{m}} \end{pmatrix}$

$A_{1,2} = \begin{pmatrix} a_{1,k} & \cdots & a_{1,l} \\ \vdots & \ddots & \vdots \\ a_{2^{m},1} & \cdots & a_{2^{m},l} \end{pmatrix}$
$A_{2,1} = \begin{pmatrix} a_{k,1} & \cdots & a_{k,2^{m}} \\ \vdots & \ddots & \vdots \\ a_{l,1} & \cdots & a_{l,2^{m}} \end{pmatrix}$
$A_{2,2} = \begin{pmatrix} a_{k,k} & \cdots & a_{l,l} \\ \vdots & \ddots & \vdots \\ a_{l,1} & \cdots & a_{l,l} \end{pmatrix}$

obdobně pro B a C.

V tomto kroku chci využít předpokladu, že to platí pro n, a matice X1 ... X8 vypočítat pomocí klasického násobení matic.

$X_1 = \begin{pmatrix} (a_{1,1} b_{1,1} + \dots + a_{1,2^m} b_{2^m,1}) & \cdots & (a_{1,1} b_{1,2^m} + \dots + a_{1,2^m} b_{2^m,2^m}) \\ \vdots & \ddots & \vdots \\ ( a_{2^m,1} b_{1, 1} + \dots + a_{2^m,2^m} b_{2^m, 1} )& \cdots & (a_{2^m,1} b_{1, 2^m} + \dots + a_{2^m,2^m} b_{2^m, 2^m}) \end{pmatrix}$

$X_2 = \begin{pmatrix} a_{1,k} b_{k,1} + \dots + a_{1,l} b_{l,1} & \cdots & a_{1,l} b_{1,2^m} + \dots + a_{1,2^m} b_{2^m,2^m} \\ \vdots & \ddots & \vdots \\ \dots & \cdots & \dots \end{pmatrix}$

(Už tady je to děs co se týče přehlednosti).

A teď když to sečtu..

$C_{1,1} = \begin{pmatrix} (a_{1,1} b_{1,1} + \dots + a_{1,2^m} b_{2^m,1} + a_{1,k} b_{k,1} + \dots + a_{1,l} b_{l,1}) & \cdots & ( a_{1,1} b_{1,2^m} + \dots + a_{1,2^m} b_{2^m,2^m} + a_{1,l} b_{1,2^m} + \dots + a_{1,2^m} b_{2^m,2^m}) \\ \vdots & \ddots & \vdots \\ (a_{2^m,1} b_{1, 1} + \dots + a_{2^m,2^m} b_{2^m, 1} + \dots ) & \cdots & (a_{2^m,1} b_{1, 2^m} + \dots + a_{2^m,2^m} b_{2^m, 2^m} + \dots) \end{pmatrix}$
Už se mi to nechtělo rozepisovat, princip je myslím jasnej... Obdobně bych rozepsal všechny prvky C, načež bych zjistil, že to přesně odpovídá klasickému násobení matic a bylo by to dokázané.

Je to hrozně dlouhý, nepřehledný a není snadný se v tom vyznat. Mohl bych tam sice zavést nějaké substituce, ale taky by jich bylo hrozně moc :( Nenapadá mě jak to popsat jednodušeji a elegantněji :(

kexixex · 25. 04. 2013 17:44

Ahoj, uprimne, pokud je v jakykoliv literature dukaz nejakeho pomerne jasneho tvrzeni o nasobeni matic, a ja chapu princip, konkretni, matematicky korektni zapis (tj. napr. vypisovani prvku z definice maticoveho nasobeni) nikdy nectu. (vcetne dukazu v tvem prispevku)

Prehlednost se da zlepsit napriklad pouzitim symbolu $\Sigma$ ..

Ale hlavne, kdyz dokazujes korektnost algoritmu, zpravidla dokazujes dve veci
1) algoritmus da spravny vysledek;
2) algoritmus je konecny

tedy u tveho algoritmu, kdy dostanes na vstupu matice A a B typu 2^n a na vystupu mas mit matici C=AB dokazujes

napriklad
ad 1) pouzijes tvrzeni block matrix multiplication zde: http://en.wikipedia.org/wiki/Block_matrix;
plus vlastnosti cisla 2^n

ad 2) v kazdem kroku se zmensuje velikost matic od 2^n az do 2, kdy je vynasobis vzorcem z tveho dukazu pro n=1

Taky je dobry si algoritmicky zapsat, co PRESNE chces delat v jednotlivych krocich (pak uz by te to vetsinou melo snadno navest na dokazovani 1) a 2))

Matematické Fórum

#1 23. 04. 2013 12:11

Důkaz korektnosti algoritmu

#2 25. 04. 2013 17:44

Re: Důkaz korektnosti algoritmu

Zápatí