矩阵复杂度的精确反演(用高斯消元)

Question

我想检查一下我所做的是否正确。如有任何意见，敬请见谅。

问题陈述：考虑一个非奇异矩阵$A_{nxn}$.构造了一种用高斯消去法求$A^{-1}$的算法。提供此算法的操作计数。

我尝试的算法和操作计数：

设$A|I$是一个增广的$n$ x $2n$矩阵。

输入:未知数和方程数n，增广矩阵

输出：$A^{-1}$，只要逆存在

步骤1:对于$i=1，\dots，n-1$ do步骤2-4

步骤2:设$p$是$i \leq \leq n$的最小整数，使$a_{pi} \neq 0$。如果不存在整数$p$，则输出(“不存在唯一解决方案”)；停止

步骤3:如果$p \neq i$，那么执行$E_p \左侧E_i$

步骤4:对于$j=i+1，\dots，n$ do步骤5-6

步骤5:设置$m_{ji}=a_{ji}/a_{ii}$。

步骤6:执行$(E_j - m_{ji}E_i) \rightarrow (E_j)$

步骤7:如果$a_{nn}=0$，则输出不存在唯一解决方案并停止

步骤8:对于$i=n-1，n-2，\dots，1美元，

对于$j=i+1，i，\dots ,1$ do步骤9和10

步骤9:设置$m_{ij}=a_{ij}/a_{jj}$

步骤10:执行$(E_i - m_{ij}E_j) \rightarrow (E_i)$

步骤11:对于$i=1，\l ldots，n$，执行$E_i/a_{ii} \右旋E_i$

步骤12:输出$A^{-1}$和STOP。

I得到的运算数如下:总计$(2n^3+9n^2+n)/3$乘法和除法，以及$(2n^3+6n^2-8n)/3$加法和减法，总计为$4n^3/3 +5N^2-7n/3$操作。这听起来对吗？

谢谢你的帮助。

Answer 1

给定一个非奇异矩阵A.构造一个使用高斯消去的算法来找出$A^{-1}$ i在python中有相同的问题和做到了吗？：

#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