線代降階法前面乘什么意思 線性代數(shù)行列式的計算方法

夢緣2022-09-04 13:09:342628

線性代數(shù)中矩陣的乘法代表什么意義?線性代數(shù)問題!用降階法計算行列式。怎么知道要消哪一行哪一列?線性代數(shù)行列式中什么是降階法 概念問題?行列式降階 線性代數(shù)行列式中什么是降階法?線代。為什么要乘以1/2?線性代數(shù)行列式中什么是降階法?

本文導(dǎo)航

線性代數(shù)中的矩陣總結(jié)

看樣子你是個學(xué)生,我是大學(xué)線代講師.

矩陣乘法是線性代數(shù)中最常見的運算之一,它在數(shù)值計算中有廣泛的應(yīng)用。若A和B是2個n×n的矩陣,則它們的乘積C=AB同樣是一個n×n的矩陣。A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來計算A和B的乘積矩陣C,則每計算C的一個元素C[i,j],需要做n個乘法和n-1次加法。因此,求出矩陣C的n2個元素所需的計算時間為0(n3)。

60年代末,Strassen采用了類似于在大整數(shù)乘法中用過的分治技術(shù),將計算2個n階矩陣乘積所需的計算時間改進到O(nlog7)=O(n2.18)。

首先,我們還是需要假設(shè)n是2的冪。將矩陣A,B和C中每一矩陣都分塊成為4個大小相等的子矩陣,每個子矩陣都是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個2階方陣的乘積可以直接用(2)-(3)式計算出來,共需8次乘法和4次加法。當子矩陣的階大于2時,為求2個子矩陣的積,可以繼續(xù)將子矩陣分塊,直到子矩陣的階降為2。這樣,就產(chǎn)生了一個分治降階的遞歸算法。依此算法,計算2個n階方陣的乘積轉(zhuǎn)化為計算8個n/2階方陣的乘積和4個n/2階方陣的加法。2個n/2×n/2矩陣的加法顯然可以在c*n2/4時間內(nèi)完成,這里c是一個常數(shù)。因此,上述分治法的計算時間耗費T(n)應(yīng)該滿足:

這個遞歸方程的解仍然是T(n)=O(n3)。因此,該方法并不比用原始定義直接計算更有效。究其原因,乃是由于式(2)-(5)并沒有減少矩陣的乘法次數(shù)。而矩陣乘法耗費的時間要比矩陣加減法耗費的時間多得多。要想改進矩陣乘法的計算時間復(fù)雜性,必須減少子矩陣乘法運算的次數(shù)。按照上述分治法的思想可以看出,要想減少乘法運算次數(shù),關(guān)鍵在于計算2個2階方陣的乘積時,能否用少于8次的乘法運算。Strassen提出了一種新的算法來計算2個2階方陣的乘積。他的算法只用了7次乘法運算,但增加了加、減法的運算次數(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

以上計算的正確性很容易驗證。例如:

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)是按通常的矩陣乘法計算C=AB的子算法。

Strassen矩陣乘積分治算法中,用了7次對于n/2階矩陣乘積的遞歸調(diào)用和18次n/2階矩陣的加減運算。由此可知,該算法的所需的計算時間T(n)滿足如下的遞歸方程:

按照解遞歸方程的套用公式法,其解為T(n)=O(nlog7)≈O(n2.81)。由此可見,Strassen矩陣乘法的計算時間復(fù)雜性比普通矩陣乘法有階的改進。

有人曾列舉了計算2個2階矩陣乘法的36種不同方法。但所有的方法都要做7次乘法。除非能找到一種計算2階方陣乘積的算法,使乘法的計算次數(shù)少于7次,按上述思路才有可能進一步改進矩陣乘積的計算時間的上界。但是Hopcroft和Kerr(197l)已經(jīng)證明,計算2個2×2矩陣的乘積,7次乘法是必要的。因此,要想進一步改進矩陣乘法的時間復(fù)雜性,就不能再寄希望于計算2×2矩陣的乘法次數(shù)的減少?;蛟S應(yīng)當研究3×3或5×5矩陣的更好算法。在Strassen之后又有許多算法改進了矩陣乘法的計算時間復(fù)雜性。目前最好的計算時間上界是O(n2.367)。而目前所知道的矩陣乘法的最好下界仍是它的平凡下界Ω(n2)。因此到目前為止還無法確切知道矩陣乘法的時間復(fù)雜性。關(guān)于這一研究課題還有許多工作可做。

線性代數(shù)行列式的計算方法

理論上是隨意的,實際上一般挑選計算最簡單的

比如含有0、1最多那行的某個非零列,這樣就可以少計算很多與0相乘或者與1相乘的子行列式

線性代數(shù)先學(xué)行列式還是矩陣

降階法就是用展開定理把行列式降階

行列式的八種基本題型降階

展開是一種降階辦法,還有一些定理可以降階計算http://m.doc88.com/p-981996068528.html這個文檔有一些定理也可以用來降階計算

線代中向量的寫法

是為了構(gòu)造 AX=0 的一個非零解。

A[η1 - 1/2 (η2+η3)]

=Aη1 - 1/2 (Aη2+Aη3)

=b - 1/2 (b+b)

=0。

線性代數(shù)中怎么區(qū)分上三角行列式

6.行列式計算三:降階法

掃描二維碼推送至手機訪問。

版權(quán)聲明:本文由尚恩教育網(wǎng)發(fā)布,如需轉(zhuǎn)載請注明出處。

本文鏈接:http://codetoknow.com/view/57225.html

“線代降階法前面乘什么意思 線性代數(shù)行列式的計算方法” 的相關(guān)文章

數(shù)學(xué)專業(yè)排名 國內(nèi)數(shù)學(xué)專業(yè)最出色的大學(xué)排名

數(shù)學(xué)專業(yè)排名 國內(nèi)數(shù)學(xué)專業(yè)最出色的大學(xué)排名

全世界哪所大學(xué)的數(shù)學(xué)系最好?有人知道嗎?全國數(shù)學(xué)專業(yè)排名,應(yīng)用數(shù)學(xué)專業(yè)大學(xué)排名,全國數(shù)學(xué)系最好的大學(xué)排名,中國什么大學(xué)數(shù)學(xué)系排名靠前?數(shù)學(xué)系全國大學(xué)排名。本文導(dǎo)航數(shù)學(xué)系最好十所大學(xué)中國大學(xué)數(shù)學(xué)專業(yè)最新排名正規(guī)大學(xué)數(shù)學(xué)專業(yè)排名國內(nèi)數(shù)學(xué)專業(yè)最出色的大學(xué)排名數(shù)學(xué)系211大學(xué)排名全國第五輪數(shù)學(xué)系排名大學(xué)數(shù)學(xué)...

數(shù)據(jù)科學(xué)專業(yè) 數(shù)據(jù)科學(xué)與大數(shù)據(jù)專業(yè)好不好

數(shù)據(jù)科學(xué)專業(yè) 數(shù)據(jù)科學(xué)與大數(shù)據(jù)專業(yè)好不好

數(shù)據(jù)科學(xué)專業(yè)有哪些就業(yè)去向,數(shù)據(jù)科學(xué)專業(yè)就業(yè)方向,什么是數(shù)據(jù)科學(xué)(Data Science)?大數(shù)據(jù)科學(xué)專業(yè)學(xué)什么?關(guān)于數(shù)據(jù)科學(xué),你知道它包含什么嗎?數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)怎么樣?前景如何?謝謝?本文導(dǎo)航數(shù)據(jù)類專業(yè)就業(yè)方向數(shù)據(jù)科學(xué)專業(yè)一覽表數(shù)據(jù)科學(xué)的三個基本要素大數(shù)據(jù)和數(shù)據(jù)科學(xué)專業(yè)學(xué)什么數(shù)據(jù)科學(xué)的...

函數(shù)連續(xù)是什么意思 函數(shù)的連續(xù)怎么定義

函數(shù)連續(xù)是什么意思 函數(shù)的連續(xù)怎么定義

函數(shù)連續(xù)性的定義是什么?如何判定一個函數(shù)是連續(xù)的?函數(shù)連續(xù)的概念是什么?一個函數(shù)連續(xù)說明了什么?連續(xù)函數(shù)的定義是什么?什么叫函數(shù)在一個區(qū)間內(nèi)連續(xù)?本文導(dǎo)航怎么判斷函數(shù)的連續(xù)性函數(shù)的連續(xù)性意味著什么函數(shù)在某點有定義與連續(xù)的關(guān)系函數(shù)的連續(xù)怎么定義函數(shù)在區(qū)間內(nèi)連續(xù)的表達怎么判斷函數(shù)的連續(xù)性函數(shù)在點X處的極...

什么是無界函數(shù) 常見的有界函數(shù)

什么是無界函數(shù) 常見的有界函數(shù)

什么叫有界函數(shù)和無界函數(shù)?什么是無界函數(shù)?函數(shù)無界是什么意思?怎樣證明函數(shù)無界?函數(shù)無界的定義是什么?無界函數(shù)的定義是什么?本文導(dǎo)航常見的有界函數(shù)怎么判斷是否是無界函數(shù)無界函數(shù)定義函數(shù)無界的判斷函數(shù)在定義域內(nèi)有界存在極限嗎無界函數(shù)的極限都不存在嗎常見的有界函數(shù)有界函數(shù)是指有最值,無界函數(shù)則無最值。例...

委培證明怎么開 規(guī)培單位委培公函模板

關(guān)于委培研究生,關(guān)于委培研究生的問題!,委培申請書怎么寫?單位證明怎么開?定向委培生單位開具證明參加公務(wù)員或遴選報考的相關(guān)文件,93屆委培生能開學(xué)歷證明嗎?本文導(dǎo)航關(guān)于委培研究生關(guān)于委培研究生的問題??!規(guī)培單位委培公函模板單位證明怎么開?定向委培生單位開具證明參加公務(wù)員或遴選報考的相關(guān)文件93屆委培...

數(shù)學(xué)刷題怎么快 數(shù)學(xué)刷題怎么刷

數(shù)學(xué)刷題怎么快 數(shù)學(xué)刷題怎么刷

怎樣才能提高數(shù)學(xué)成績 數(shù)學(xué)如何快速提分?數(shù)學(xué)怎樣快速提分?數(shù)學(xué)刷題怎么刷?數(shù)學(xué)怎么刷題?數(shù)學(xué)怎么刷題才有效?數(shù)學(xué)應(yīng)該怎么進行刷題?本文導(dǎo)航怎樣才能提高數(shù)學(xué)成績 數(shù)學(xué)如何快速提分數(shù)學(xué)怎樣快速提分數(shù)學(xué)刷題怎么刷學(xué)數(shù)學(xué)的方法技巧只有刷題嗎數(shù)學(xué)怎么刷題才有效數(shù)學(xué)不刷題方法怎樣才能提高數(shù)學(xué)成績 數(shù)學(xué)如何快速提...

發(fā)表評論

訪客

◎歡迎參與討論,請在這里發(fā)表您的看法和觀點。