線代降階法前面乘什么意思 線性代數(shù)行列式的計(jì)算方法
線性代數(shù)中矩陣的乘法代表什么意義?線性代數(shù)問(wèn)題!用降階法計(jì)算行列式。怎么知道要消哪一行哪一列?線性代數(shù)行列式中什么是降階法 概念問(wèn)題?行列式降階 線性代數(shù)行列式中什么是降階法?線代。為什么要乘以1/2?線性代數(shù)行列式中什么是降階法?
本文導(dǎo)航
- 線性代數(shù)中的矩陣總結(jié)
- 線性代數(shù)行列式的計(jì)算方法
- 線性代數(shù)先學(xué)行列式還是矩陣
- 行列式的八種基本題型降階
- 線代中向量的寫法
- 線性代數(shù)中怎么區(qū)分上三角行列式
線性代數(shù)中的矩陣總結(jié)
看樣子你是個(gè)學(xué)生,我是大學(xué)線代講師.
矩陣乘法是線性代數(shù)中最常見(jiàn)的運(yùn)算之一,它在數(shù)值計(jì)算中有廣泛的應(yīng)用。若A和B是2個(gè)n×n的矩陣,則它們的乘積C=AB同樣是一個(gè)n×n的矩陣。A和B的乘積矩陣C中的元素C[i,j]定義為:
若依此定義來(lái)計(jì)算A和B的乘積矩陣C,則每計(jì)算C的一個(gè)元素C[i,j],需要做n個(gè)乘法和n-1次加法。因此,求出矩陣C的n2個(gè)元素所需的計(jì)算時(shí)間為0(n3)。
60年代末,Strassen采用了類似于在大整數(shù)乘法中用過(guò)的分治技術(shù),將計(jì)算2個(gè)n階矩陣乘積所需的計(jì)算時(shí)間改進(jìn)到O(nlog7)=O(n2.18)。
首先,我們還是需要假設(shè)n是2的冪。將矩陣A,B和C中每一矩陣都分塊成為4個(gè)大小相等的子矩陣,每個(gè)子矩陣都是n/2×n/2的方陣。由此可將方程C=AB重寫為:
(1)
由此可得:
C11=A11B11+A12B21 (2)
C12=A11B12+A12B22 (3)
C21=A21B11+A22B21 (4)
C22=A21B12+A22B22 (5)
如果n=2,則2個(gè)2階方陣的乘積可以直接用(2)-(3)式計(jì)算出來(lái),共需8次乘法和4次加法。當(dāng)子矩陣的階大于2時(shí),為求2個(gè)子矩陣的積,可以繼續(xù)將子矩陣分塊,直到子矩陣的階降為2。這樣,就產(chǎn)生了一個(gè)分治降階的遞歸算法。依此算法,計(jì)算2個(gè)n階方陣的乘積轉(zhuǎn)化為計(jì)算8個(gè)n/2階方陣的乘積和4個(gè)n/2階方陣的加法。2個(gè)n/2×n/2矩陣的加法顯然可以在c*n2/4時(shí)間內(nèi)完成,這里c是一個(gè)常數(shù)。因此,上述分治法的計(jì)算時(shí)間耗費(fèi)T(n)應(yīng)該滿足:
這個(gè)遞歸方程的解仍然是T(n)=O(n3)。因此,該方法并不比用原始定義直接計(jì)算更有效。究其原因,乃是由于式(2)-(5)并沒(méi)有減少矩陣的乘法次數(shù)。而矩陣乘法耗費(fèi)的時(shí)間要比矩陣加減法耗費(fèi)的時(shí)間多得多。要想改進(jìn)矩陣乘法的計(jì)算時(shí)間復(fù)雜性,必須減少子矩陣乘法運(yùn)算的次數(shù)。按照上述分治法的思想可以看出,要想減少乘法運(yùn)算次數(shù),關(guān)鍵在于計(jì)算2個(gè)2階方陣的乘積時(shí),能否用少于8次的乘法運(yùn)算。Strassen提出了一種新的算法來(lái)計(jì)算2個(gè)2階方陣的乘積。他的算法只用了7次乘法運(yùn)算,但增加了加、減法的運(yùn)算次數(shù)。這7次乘法是:
M1=A11(B12-B22)
M2=(A11+A12)B22
M3=(A21+A22)B11
M4=A22(B21-B11)
M5=(A11+A22)(B11+B22)
M6=(A12-A22)(B21+B22)
M7=(A11-A21)(B11+B12)
做了這7次乘法后,再做若干次加、減法就可以得到:
C11=M5+M4-M2+M6
C12=M1+M2
C21=M3+M4
C22=M5+M1-M3-M7
以上計(jì)算的正確性很容易驗(yàn)證。例如:
C22=M5+M1-M3-M7
=(A11+A22)(B11+B22)+A11(B12-B22)-(A21+A22)B11-(A11-A21)(B11+B12)
=A11B11+A11B22+A22B11+A22B22+A11B12
-A11B22-A21B11-A22B11-A11B11-A11B12+A21B11+A21B12
=A21B12+A22B22
由(2)式便知其正確性。
至此,我們可以得到完整的Strassen算法如下:
procedure STRASSEN(n,A,B,C);begin if n=2 then MATRIX-MULTIPLY(A,B,C) else begin 將矩陣A和B依(1)式分塊; STRASSEN(n/2,A11,B12-B22,M1); STRASSEN(n/2,A11+A12,B22,M2); STRASSEN(n/2,A21+A22,B11,M3); STRASSEN(n/2,A22,B21-B11,M4); STRASSEN(n/2,A11+A22,B11+B22,M5); STRASSEN(n/2,A12-A22,B21+B22,M6); STRASSEN(n/2,A11-A21,B11+B12,M7);
;
end;
end;
其中MATRIX-MULTIPLY(A,B,C)是按通常的矩陣乘法計(jì)算C=AB的子算法。
Strassen矩陣乘積分治算法中,用了7次對(duì)于n/2階矩陣乘積的遞歸調(diào)用和18次n/2階矩陣的加減運(yùn)算。由此可知,該算法的所需的計(jì)算時(shí)間T(n)滿足如下的遞歸方程:
按照解遞歸方程的套用公式法,其解為T(n)=O(nlog7)≈O(n2.81)。由此可見(jiàn),Strassen矩陣乘法的計(jì)算時(shí)間復(fù)雜性比普通矩陣乘法有階的改進(jìn)。
有人曾列舉了計(jì)算2個(gè)2階矩陣乘法的36種不同方法。但所有的方法都要做7次乘法。除非能找到一種計(jì)算2階方陣乘積的算法,使乘法的計(jì)算次數(shù)少于7次,按上述思路才有可能進(jìn)一步改進(jìn)矩陣乘積的計(jì)算時(shí)間的上界。但是Hopcroft和Kerr(197l)已經(jīng)證明,計(jì)算2個(gè)2×2矩陣的乘積,7次乘法是必要的。因此,要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性,就不能再寄希望于計(jì)算2×2矩陣的乘法次數(shù)的減少。或許應(yīng)當(dāng)研究3×3或5×5矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。目前最好的計(jì)算時(shí)間上界是O(n2.367)。而目前所知道的矩陣乘法的最好下界仍是它的平凡下界Ω(n2)。因此到目前為止還無(wú)法確切知道矩陣乘法的時(shí)間復(fù)雜性。關(guān)于這一研究課題還有許多工作可做。
線性代數(shù)行列式的計(jì)算方法
理論上是隨意的,實(shí)際上一般挑選計(jì)算最簡(jiǎn)單的
比如含有0、1最多那行的某個(gè)非零列,這樣就可以少計(jì)算很多與0相乘或者與1相乘的子行列式
線性代數(shù)先學(xué)行列式還是矩陣
降階法就是用展開(kāi)定理把行列式降階
行列式的八種基本題型降階
展開(kāi)是一種降階辦法,還有一些定理可以降階計(jì)算http://m.doc88.com/p-981996068528.html這個(gè)文檔有一些定理也可以用來(lái)降階計(jì)算
線代中向量的寫法
是為了構(gòu)造 AX=0 的一個(gè)非零解。
A[η1 - 1/2 (η2+η3)]
=Aη1 - 1/2 (Aη2+Aη3)
=b - 1/2 (b+b)
=0。
線性代數(shù)中怎么區(qū)分上三角行列式
6.行列式計(jì)算三:降階法
掃描二維碼推送至手機(jī)訪問(wèn)。
版權(quán)聲明:本文由尚恩教育網(wǎng)發(fā)布,如需轉(zhuǎn)載請(qǐng)注明出處。