为什么我的高斯消元算法失败了？-解网

问：

在高斯消元法中，我们取矩阵 A 和另一个矩阵 I。

我们继续将矩阵 A 转换为单位矩阵。完成后，我们将对单位矩阵的 A 执行相同的步骤。然后 A 成为单位矩阵，I 成为逆矩阵。

但是，在我的代码中，A 变成了恒等式，但逆的前几行是不正确的

我花了几个多小时进行调试。我意识到，只要我的矩阵相对稀疏，我的方法就会起作用。例如，这有效 -

A = [[10., 3, 10.], [0., 9., 0.], [10.,12.,1.]]

是的，我的矩阵最终总是变成单位矩阵。问题是这不会成为AIA^{-1}

关于我的方法的快速解释。我首先致力于将我的矩阵转换为上三角形矩阵。然后我努力将其转换为单位矩阵。代码是用Python 2.7

这是我的代码 -


from fractions import Fraction

A = [[10., 3, 10.], [0., 9., 0.], [10.,12.,1.]]
for i in range(len(A)):
    for j in range(len(A)):
        A[i][j] = Fraction(A[i][j])
row = len(A)

print "row = ", row

I = [[0 for i in range(len(A))] for j in range(len(A))]
for i in range(len(I)):
    for j in range(len(I)):
        if i == j:
            I[i][j] = 1
        I[i][j] = Fraction(I[i][j])

print I
foo = {}
for i in range(len(A)):
    for j in range(len(A)):
        if i==j:
            foo[i] = A[i][j]



print "A before = ", A
print "I before = ", I

i = 0
for k in range(len(A)):
    normalize = A[k][k]
    if normalize != Fraction(0,1):
        for l in range(len(A)):
            A[k][l] = A[k][l]/normalize
        for l in range(len(I)):
            I[k][l] = I[k][l]/normalize
    i = k+1
    while i<len(A):
        coeff = A[i][k]
        for j in range(len(A)):

            A[i][j] = A[k][j]*coeff - A[i][j]

            I[i][j] = I[k][j]*coeff - I[i][j]
        i = i + 1
print "A intermediate = ", A
print "I intermediate = ", I


for i in range(len(A)):
    for j in range(len(A)):
        k = i
        while k+1<len(A):
            coeff = A[i][k+1]

            A[i][j] = A[i][j] - A[k+1][j]*coeff
            print "A[i][j] final =  ", A[i][j]

            I[i][j] = I[i][j] - I[k+1][j]*coeff
            k = k+1

print "A final = ", A
print "I final = ", I

这是输出 -

A final =  [[Fraction(1, 1), Fraction(0, 1), Fraction(0, 1)], [Fraction(0, 1), Fraction(1, 1), Fraction(0, 1)], [Fraction(0, 1), Fraction(0, 1), Fraction(1, 1)]]
I final =  [[Fraction(-1, 90), Fraction(-13, 90), Fraction(1, 9)], [Fraction(0, 1), Fraction(1, 9), Fraction(0, 1)], [Fraction(1, 9), Fraction(1, 9), Fraction(-1, 9)]]

编辑 1 - 我只需要使用标准的 Python 库来解决这个问题。

编辑 2 - 例如，如果我给出这个输入 -

A = [[5,10,20], [2, 8, 12], [4, 8, 8]]

我得到以下错误的输出 -

A final =  [[Fraction(1, 1), Fraction(0, 1), Fraction(0, 1)], [Fraction(0, 1), Fraction(1, 1), Fraction(0, 1)], [Fraction(0, 1), Fraction(0, 1), Fraction(1, 1)]]
I final =  [[Fraction(0, 1), Fraction(-1, 2), Fraction(1, 2)], [Fraction(-1, 5), Fraction(1, 4), Fraction(1, 8)], [Fraction(1, 10), Fraction(0, 1), Fraction(-1, 8)]]

这是正确的答案——

python 数学代数矩阵逆

你已经有了一个良好的开端。调试算法的方法是从问题开始，您可以准确地说出中间步骤和最终输出应该是什么。从 1 x 1 矩阵开始。您的算法是否输出正确的结果？如果是这样，请尝试 2 x 2。如果可行，请尝试 3 x 3。正如您已经说过的，它不适用于 3 x 3，因此请寻找您可以说出答案的特殊情况。例如，如果你的输入已经是一个单位矩阵怎么办？如果它是对角线矩阵呢？如果它是一个上三角形矩阵呢？一般来说，一次处理一点更复杂的问题。

答：

1赞 GabeDoubleU 7/5/2023 #1

嘿，我重写了代码，以便可以更好地突出显示计算机所执行的过程，我认为问题可能在于在行乘法之前在单位矩阵中添加行。下面是编写的代码：

from fractions import Fraction

def p_frac(x):
    if x.denominator == 0: return "NaN"
    if x.numerator == 0: return "0"
    if x.denominator == 1: return str(x.numerator)
    return str(x.numerator)+"/"+str(x.denominator)

A = [[10., 3, 10.], [0., 9., 0.], [10.,12.,1.]]
for i in range(len(A)):
    for j in range(len(A)):
        A[i][j] = Fraction(A[i][j])
row = len(A)

print ("row = ", row)

I = [[0 for i in range(len(A))] for j in range(len(A))]
for i in range(len(I)):
    for j in range(len(I)):
        if i == j:
            I[i][j] = 1
        I[i][j] = Fraction(I[i][j])

print (I)
foo = {}
for i in range(len(A)):
    for j in range(len(A)):
        if i==j:
            foo[i] = A[i][j]

print ("A before = ")
print('\n'.join(['\t'.join([p_frac(cell) for cell in row]) for row in A]))
print ("I before = ")
print('\n'.join(['\t'.join([p_frac(cell) for cell in row]) for row in I]))
i = 0
for k in range(len(A)):
    normalize = A[k][k]
    if normalize != Fraction(0,1):
        for l in range(len(A)):
            A[k][l] = A[k][l]/normalize
        for l in range(len(I)):
            I[k][l] = I[k][l]/normalize
    i = k+1
    while i<len(A):
        coeff = A[i][k]
        for j in range(len(A)):

            A[i][j] = A[k][j]*coeff - A[i][j]

            I[i][j] = I[k][j]*coeff - I[i][j]
        i = i + 1
    print("A step", str(k+1))
    print('\n'.join(['\t'.join([p_frac(cell) for cell in row]) for row in A]))
    print("I step", str(k + 1))
    print('\n'.join(['\t'.join([p_frac(cell) for cell in row]) for row in I]))

for i in range(len(A)):
    for j in range(len(A)):
        k = i
        while k+1<len(A):
            coeff = A[i][k+1]

            A[i][j] = A[i][j] - A[k+1][j]*coeff
            # print ("A[i][j] final =  ", A[i][j])

            I[i][j] = I[i][j] - I[k+1][j]*coeff
            k = k+1

print ("A final = ")
print('\n'.join(['\t'.join([p_frac(cell) for cell in row]) for row in A]))
print ("I final = ")
print('\n'.join(['\t'.join([p_frac(cell) for cell in row]) for row in I]))

这是我注意到算法差异的地方：

你在 k=0 之后有了这个

A step 1
1       3/10    1
0       -9      0
0       -9      9
I step 1
1/10    0       0
0       -1      0
1       0       -1

但是在 k=1 之后，你有

A step 2
1       3/10    1
0       1       0
0       0       -9
I step 2
1/10    0       0
0       1/9     0
-1      -1      1

如果我没记错的话，我第 2 步第三行和第二列的条目应该是 +1，对吧？

为什么我的高斯消元算法失败了？

Why is my gaussian elimination algorithm failing?

评论

评论