Geek Answers Handbook

Eliminate rounding errors from the matrix

My problem is that I have a matrix where the sum of all rows and the sum of all columns is zero. All numbers are rounded to x decimal places.

Then I multiply the entire matrix by a number from 0 to 1 (e.g. 1/6) and round all numbers to x decimal places. Now I cannot be sure that the sum of the rows and columns will be zero. I want the sum to be zero again with the smallest possible adjustment (or at least a very small setting)

Is there an algorithm that can solve this problem?

Example (very simple): Matrix:

200 -200 0 400 400 -800 -600 -200 800

round2 ((1/6) * matrix)

 33.33 -33.33 0 66.67 66.67 -133.33 -100 -33.33 133.33
+6
source share
4 answers

This is not a solution; just a more mathematical description of what you are trying to achieve (without judging whether to do it right):

Since you round off all numbers to x decimal places, we can treat these numbers as integers (just multiply them by 10 ^ x).

Now you are trying to solve the following problem:

Given the matrix

 A11+Adj11 A12+Adj12 ... A1n+Adj1n A21+Adj21 A22+Adj22 ... A2n+Adj2n A31+Adj31 A32+Adj32 ... A3n+Adj3n ... ... ... ... Am1+Adjm1 Am2+Adjm2 ... Amn+Adjmn

Where A11..Amn are constant integers,

Find the integers Adj11 ... Adjmn

Minimum Amount (abs (Adjxy))

(or perhaps you prefer: Collapse the amount ((Adjxy) ^ 2)

Depending on the:

 - for each row m: Adjm1+Adjm2+...+Adjmn = - (Am1+Am2+...+Amn) - for each col n: Adj1n+Adj2n+...+Adjmn = - (A1n+A2n+...+Amn)

This is integer programming with m * n variables and m + n constraints. The function you are trying to minimize is not linear.

I am afraid that this problem is far from trivial. I believe that you should post it at https://math.stackexchange.com/

+1
source

What you are experiencing here is essentially a precision error. You can’t do anything if you don’t manage. This is similar to saving a photo as a 256-color image. You lose information (essentially accuracy, due to discretization), and you cannot do anything. For images, there are algorithms that allow you to make images smoother / closer to the original (for example, anti-aliasing), but you do not have such things for single values.

Possible solutions (in fact, only one with two different visualization methods):

  • Only for display. It should be possible for the user to interpret that the numbers are truncated / rounded. In your example, it should be obvious that 6.67 will actually be 6.66666...

  • Do not round and just crop numbers after a fixed number of decimals (add ... if necessary, this actually looks like a different solution).

In general, if you want to solve linear equations (or mathematics in general), always use an accessible (and reasonable, efficient) data type with the maximum available accuracy, usually being single or double precision. Otherwise, you introduce errors that are getting worse and worse, the more you count with them.

+2
source

You cannot eliminate rounding when working with floating point numbers. A better solution might be to stick to integers in the matrix and then apply the final 1/6 to the result.

0
source

A common way to ensure that small rounding errors do not lead to a large total error is to verify that the error does not become too large for each partial sum.

With one dimensional vector [a[1], a[2], ..., a[n]] you can calculate partial sums [a[1], a[1]+a[2], ..., a[1]+a[2]+...+a[n]] , multiply it and then restore a good vector by subtracting the previous cell by the current one: [a[1]*b, (a[1]+a[2])*ba[1]*b, ..., (a[1]+a[2]+...+a[n])*b-(a[1]+a[2]+...+a[n-1])*b] . Using this trick, the error for any partial sum is not more than 10 ^ (- x).

You can adapt this method to a 2-dimensional matrix using the following three procedures:

 partial_sum(M) = for i = 0 to n-1 do for j = 1 to m-1 do M[i][j] += M[i][j-1] done done for i = 0 to n-1 do for j = 1 to m-1 do M[j][i] += M[j-1][i] done done multiply(M, a) = for i = 0 to n-1 do for j = 0 to m-1 do M[i][j] *= a done done restore(M) = for i = 0 to n-1 do for j = 1 to m-1 do M[i][j] -= M[i][j-1] done done for i = 0 to n-1 do for j = 1 to m-1 do M[j][i] -= M[j-1][i] done done
0
source

More articles:


All Articles