矩陣複雜性的準確反演（通過高斯消除）

Question

我想檢查我所做的是否正確。請，任何輸入讚賞。

問題說明：考慮一個非奇異矩陣$ A_ {nxn} $。使用高斯消元構造算法以找到$ A^{ - 1} $。爲此算法提供操作計數。

我試圖算法和操作數：

讓$ [A | I] $是一個增強的$ n $ X $ 2N $矩陣。

INPUT：未知數和方程數n，增廣矩陣

OUTPUT：$ A^{ - 1} $，條件是該逆矩陣存在

步驟1：對於$ I = 1，\點步驟2：令$ p $爲$ i \ leq p \ leq n $的最小整數，使得$ a_ {pi} \ neq 0 $。$ n_ {pi} \ neq 0 $。如果不存在整數$ p $，則輸出（'不存在唯一的解決方案'）; STOP

步驟3：如果$ P \ NEQ I $然後執行$ E_p \ leftrightarrow E_i $

步驟4：對於$ J = + 1，\點，正$做步驟5-6

第5步：設置$ m_ {ji} = a_ {ji}/a_ {ii} $。

步驟6：執行$（E_j - M_ {吉} E_i）\ RIGHTARROW（E_j）$

步驟7：如果$ A_ {NN} = 0 $然後輸出沒有唯一解EXISTS和STOP

步驟8：對於$ I = N-1，N-2，\點，1 $，
對於$ J = + 1，I，\點，1 $做步驟9和10

STEP 9：Set $ m_ {ij} = a_ {ij}/a_ {jj} $

步驟10：執行$（E_i - m_ {ij} E_j）\ rightarrow（E_i）$

步驟11：爲$ I = 1，\ ldots，正$，做$ E_i/A_ {II} \ RIGHTARROW E_i $

步驟12：輸出$ A^{ - 1} $和STOP。

我得到的操作計數如下：總共$（2n^3 + 9n^2 + n）/ 3 $乘法和除法和總數$（2n^3 + 6n^2- 8n）/ 3 $的加法和減法，總計爲4n^3/3 + 5n^2 - 7n/3 $操作。 這聽起來沒錯嗎？

感謝您的任何幫助。

Answer 1

鑑於非奇異矩陣A.用高斯消元法找到$ A ^構造一個算法{ - 1} $ 我有同樣的問題和did it在蟒蛇：

#Helper functions: 
def check_zeros(A,I,row, col=0): 
""" 
returns recursively the next non zero matrix row A[i] 
""" 
if A[row, col] != 0: 
    return row 
else: 
    if row+1 == len(A): 
     return "The Determinant is Zero" 
    return check_zeros(A,I,row+1, col) 

def swap_rows(M,I,row,index): 
""" 
swaps two rows in a matrix 
""" 
swap = M[row].copy() 
M[row], M[index] = M[index], swap 
swap = I[row].copy() 
I[row], I[index] = I[index], swap 

# Your Matrix M 
M = np.array([[0,1,5,2],[0,4,9,23],[5,4,3,5],[2,3,1,5]], dtype=float) 
I = np.identity(len(M)) 

M_copy = M.copy() 
rows = len(M) 

for i in range(rows): 
index =check_zeros(M,I,i,i) 
while index>i: 
    swap_rows(M, I, i, index) 
    print "swaped" 
    index =check_zeros(M,I,i,i) 

I[i]=I[i]/M[i,i] 
M[i]=M[i]/M[i,i] 

for j in range(rows): 
    if j !=i: 
     I[j] = I[j] - I[i]*M[j,i] 
     M[j] = M[j] - M[i]*M[j,i] 
print M 
print I #The Inverse Matrix