How do I fix this weird behaviour in numpy arrays?

Question

I am working on the implementation of a gauss elimination algorithm in python using numpy. While working on it, I have noticed a weird behaviour. Here goes what I've done so far:

def gauss_elimination(a, b):
    n = len(b)
    print(a)
    for k in range(0, n-1):
        for i in range(k+1, n):
            lam = a[i, k] / a[k, k]
            a[i, k:n] = a[i, k:n] - (lam * a[k, k:n])
            b[i] = b[i] - lam * b[k]
            print(a)
    return b

With this code, considering the following arrays:

a = np.array([[4, -2, 1], [-2, 4, -2], [1, -2, 4]])
b = np.array([11, -16, 17])

The result will be:

array([ 11, -10,  10])

This is how the algorithm changed the array a:

array([[ 4, -2,  1],
       [ 0,  3, -1],
       [ 0,  0,  2]])

Which is wrong. For some reasong, the value in the second row and third column is -1, when it should -1.5. I've inserted some printing in the way to see what was actually happening, and for some reason numpy is truncating the result. This is the changed code:

def gauss_elimination(a, b):
    n = len(b)
    print(a)
    for k in range(0, n-1):
        for i in range(k+1, n):
            lam = a[i, k] / a[k, k]
            print(a[i, k:n])
            print(lam * a[k, k:n])
            print(a[i, k:n] - lam * a[k, k:n])
            a[i, k:n] = a[i, k:n] - (lam * a[k, k:n])
            b[i] = b[i] - lam * b[k]
            print(a)
    return b

And considering the same arrays that were defined a while back, the results will be:

[[ 4 -2  1]
 [-2  4 -2]
 [ 1 -2  4]]
[ 0.   3.  -1.5] # This shows that the value is being calculated as presumed
[[ 4 -2  1]
 [ 0  3 -1] # But when the object a is updated, the value is -1 and not -1.5
 [ 1 -2  4]]
[ 0.   -1.5   3.75]
[[ 4 -2  1]
 [ 0  3 -1]
 [ 0 -1  3]]
[0.                 2.6666666666666665]
[[ 4 -2  1]
 [ 0  3 -1]
 [ 0  0  2]]

I am little bit confused. Perhaps I might have made a mistake, but the printing shows that everything is being calculated as it should be. Any tips?

ddejohn · Accepted Answer · 2021-08-16 02:29:38Z

The problem

Your array's dtype is "int32":

>>> import numpy as np
>>> x = np.array([1, 2, 3])
>>> x[1] / x[2]
0.6666666666666666
>>> x[0] = x[1] / x[2]
>>> x
array([0, 2, 3])
>>> x.dtype
>>> dtype('int32')

The "solution"

You can use dtype="float64" at instantiation to fix this issue:

>>> x = np.array([1, 2, 3], dtype="float64")
>>> x[0] = x[1] / x[2]
>>> x
array([0.66666667, 2.        , 3.        ])

Of course, you could also do this without having to explicitly specify the dtype by instantiating your array with floats in the first place:

>>> x = np.array([1., 2., 3.])
>>> x.dtype
dtype('float64')

However, whenever dealing with numerical methods in programming, you should be cognizant of the limitations of floating point arithmetic. Take a look at the note at the bottom of this answer for more details.

Explanation

NumPy arrays are homogeneous arrays, meaning that every element is of the same type. The dtype or "data type" determines how much memory each element in an array requires. This in turn dictates the memory footprint of an entire array in memory.

Because NumPy arrays are homogenenous, when an array is created it is stored in a contiguous chunk of memory which makes accessing elements very vast and easy since all elements take up the same number of bytes. This is part of the reason NumPy is so fast.

Just FYI, this is a very simplified explanation of what's going on here. Essentially, NumPy arrays are arrays of a single type ("int8", or "int32", or "float64", etc).

An operation like division on integers always results in a float, and since NumPy doesn't want to assume that you wanted to change the dtype of the entire array (which would require creating an entire new array in memory), it quietly maintains the dtype of the existing array.

Note

Anytime you're dealing with numerical computations, you need to be aware of the limitations of floating point arithmetic. Floating point arithmetic is prone to inaccuracy due to the nature of how these numbers are stored in memory.

In the case of solving systems of equations using linear algebra, even after solving for a particular vector x in Ax = b using a straight forward Gaussian elimination algorithm based on floating point arithmetic, the expression Ax will not necessarily be exactly equal to b. I recommend reading further: https://en.wikipedia.org/wiki/Floating-point_arithmetic

You've stumbled upon a discipline known as numerical analysis, by the way! More specifically numerical linear algebra. This is a deep topic. Gaussian elimination is a lovely algorithm, but I also hope this answer galvanizes future readers to look into more advanced algorithms for solving systems of equations.

Collectives™ on Stack Overflow

How do I fix this weird behaviour in numpy arrays?

1 Answer 1

The problem

The "solution"

Explanation

Note

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

The problem

The "solution"

Explanation

Note

Comments

Related