6

我的问题是我有一个矩阵，其中所有行的总和以及所有列的总和为零。所有数字都四舍五入到 x 位小数。

然后我将整个矩阵乘以 0 到 1 之间的数字（例如 1/6），并将所有数字四舍五入到小数点后 x。现在我不能确定行和列的总和是否为零。我希望通过尽可能小的调整（或至少非常小的调整）总和再次为零

是否存在可以解决此类问题的算法？

示例（非常简单）：矩阵：

    200  -200  0

    400  400  -800

   -600 -200  800

圆2（（1/6）*矩阵）

33.33  -33.33  0   

66.67  66.67   -133.33

-100   -33.33  133.33
4

4 回答 4

2

您在这里遇到的本质上是一个精度错误。除非你根本不圆，否则你无能为力。这类似于将照片保存为 256 色图像。您正在丢失信息（本质上是精度；由于离散化），您无能为力。对于图片，有一些算法可以使图像看起来更平滑/更接近原始图像（例如抖动），但是对于单值数字，您没有这样的东西。

可能的解决方案（实际上只有一种具有两种不同的可视化方式）：

  • 仅圆形显示。用户应该可以解释数字被截断/四舍五入。在您的示例中，应该很明显6.67实际上是6.66666....

  • 根本不要四舍五入，只需截断固定小数位数后的数字（...如果需要，添加；这实际上类似于其他解决方案）。

通常，如果您想求解线性方程（或一般数学），请始终使用可用的（并且合理的；性能方面的）数据类型，其具有最大可用精度，通常是单精度或双精度值。否则，你引入的误差幅度会变得越来越差，你计算的越多。

于 2012-12-05T15:08:53.850 回答
2

这不是解决方案；只是对您要实现的目标进行更数学的描述（不判断这是否是正确的做法）：

由于您将所有数字四舍五入为 x 小数，我们可以将这些数字视为整数（只需将它们乘以 10^x）。

现在，您正在尝试解决以下问题：

给定矩阵

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

其中 A11..Amn 是常量整数，

查找整数 Adj11...Adjmn

最小化总和（abs（Adjxy））

（或者您可能更喜欢：最小化总和（（Adjxy）^2）

受制于：

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

这是一个整数规划问题，具有 m*n 个变量和 m+n 个约束。您试图最小化的函数不是线性的。

恐怕这个问题远非小事。我相信你最好把它贴在https://math.stackexchange.com/

于 2012-12-05T16:41:05.797 回答
0

处理浮点数时无法消除舍入。您最好的解决方案可能是坚持矩阵中的整数，然后将最终结果应用于1/6结果。

于 2012-12-05T17:24:46.027 回答
0

确保小的舍入误差不会导致总和出现大误差的常用方法是检查每个部分总和的误差不会变得太大。

使用一维向量[a[1], a[2], ..., a[n]]，您可以计算部分和[a[1], a[1]+a[2], ..., a[1]+a[2]+...+a[n]]，将其相乘，然后通过将前一个单元格减去当前单元格来恢复良好的向量[a[1]*b, (a[1]+a[2])*b-a[1]*b, ..., (a[1]+a[2]+...+a[n])*b-(a[1]+a[2]+...+a[n-1])*b]：通过使用这个技巧，任何部分和的误差都不会超过 10^(-x)。

您可以通过以下 3 个过程将此方法用于二维矩阵：

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
于 2012-12-05T20:26:38.757 回答