6

私の問題は、すべての行の合計とすべての列の合計がゼロであるマトリックスがあることです。すべての数値は、小数点以下 x に丸められます。

次に、行列全体に 0 ～ 1 の数値 (例: 1/6) を掛け、すべての数値を x の小数に丸めます。行と列の合計がゼロになるかどうかはわかりません。可能な限り最小の調整 (または少なくとも非常に小さな調整) で合計を再びゼロにしたい

このような問題を解決できるアルゴリズムは存在しますか?

例 (非常に単純): 行列:

    200  -200  0

    400  400  -800

   -600 -200  800

round2( (1/6)*行列)

33.33  -33.33  0   

66.67  66.67   -133.33

-100   -33.33  133.33
4

4 に答える 4

2

ここで発生しているのは、本質的に精度エラーです。丸めないとどうしようもない。これは、写真を 256 色の画像として保存するのと似ています。情報を失っており (本質的に精度; 離散化による)、できることは何もありません。写真の場合、画像をより滑らかに/元の画像に近づけるためのアルゴリズムがあります (ディザリングなど) が、単一値の数値にはそのようなものはありません。

考えられる解決策 (実際には、視覚化するための 2 つの異なる方法を持つ 1 つのみ):

  • ディスプレイ用のラウンドのみ。数値が切り捨てられている/丸められているとユーザーが解釈できるようにする必要があります。あなたの例では、6.67実際には6.66666....

  • まったく四捨五入せず、小数点以下の固定数の後の数値を切り捨てます (...必要に応じて追加します。これは実際には他のソリューションと似ています)。

一般に、一次方程式 (または一般的な数学) を解きたい場合は、常に、利用可能な最大の精度 (通常は単精度または倍精度の値) で利用可能な (そして妥当な、パフォーマンス上の観点から) データ型を使用します。そうしないと、誤差マージンを計算すればするほど、誤差マージンがどんどん悪化していきます。

于 2012-12-05T15:08:53.850 に答える
2

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

Since you are rounding all the numbers to x decimals, 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 integers Adj11...Adjmn

Minimizing sum(abs(Adjxy))

(or maybe you prefer: Minimizing sum((Adjxy)^2)

Subject to:

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

This is an integer programming problem, with m*n variables and m+n constrains. The function that you are trying to minimize is not linear.

I'm afraid that this problem is far from trivial. I believe that you should better post it on https://math.stackexchange.com/

于 2012-12-05T16:41:05.797 に答える
0

浮動小数点数を扱う場合、丸めをなくすことはできません。あなたの最善の解決策は、マトリックス内の整数に固執し、最終的な1/6ものを結果に適用することです。

于 2012-12-05T17:24:46.027 に答える
0

小さな丸め誤差が合計の大きな誤差につながらないようにする一般的な方法は、各部分合計で誤差が大きくなりすぎないようにチェックすることです。

1 次元のベクトル[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 つの手順を使用して、この方法を 2 次元行列に適用できます。

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 に答える