Rundungsfehler von Matrix zu beseitigen

Question

Mein Problem ist, dass ich eine Matrix habe, wo die Summe aller Zeilen und die Summe aller Spalten Null ist. Alle Zahlen sind auf x Dezimalstellen gerundet.

Dann multipliziere ich die gesamte Matrix mit einer Zahl zwischen 0 und 1 (zB 1/6) und runde alle Zahlen auf x Dezimalstellen. Jetzt kann ich nicht sicher sein, dass die Summe der Zeilen und Spalten Null ist. Ich möchte die Summen wieder Null mit der geringstmöglichen Anpassung (oder zumindest sehr kleine Anpassung)

Gibt es einen Algorithmus, der ein solches Problem beheben kann?

Beispiel (sehr einfach): 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 

Answer 1

Dies ist keine Lösung; nur eine mathematischere Beschreibung dessen, was Sie erreichen möchten (ohne zu beurteilen, ob dies richtig ist):

Da Sie alle Zahlen auf x Dezimalstellen runden, können wir diese Zahlen als Ganzzahlen behandeln (einfach multiplizieren sie um 10^x).

Nun versuchen Sie das folgende Problem zu lösen:

die 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 

Wo A11..Amn konstant sind ganze Zahlen gegeben,

Finden ganzen Zahlen Adj11 ...Adjmn

Minimierung der Summe (abs (Adjxy))

(oder vielleicht auch Sie bevorzugen: Die Minimierung Summe ((Adjxy)^2)

vorbehalten:

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

Dies ist ein integer programming Problem, mit m * n Variablen und m + n Einschränkungen Die Funktion, die Sie versuchen zu minimieren, ist nicht linear

Ich fürchte, dass dieses Problem nicht trivial ist Sie sollten es besser auf https://math.stackexchange.com/ senden

Answer 2

Was Sie erleben hier ist im Wesentlichen ein Genauigkeitsfehler. Es gibt nichts, was Sie tun können, wenn Sie überhaupt nicht herumrunden. Dies ähnelt dem Speichern eines Fotos als 256-Farben-Bild. Sie verlieren Informationen (im Wesentlichen Präzision; aufgrund von Diskretisierung) und es gibt nichts, was Sie tun können. Bei Bildern gibt es Algorithmen, um Bilder glatter/näher am Original erscheinen zu lassen (z. B. Dithering), aber Sie haben solche Dinge nicht für einzelne Wertnummern.

Mögliche Lösungen (eigentlich nur ein mit zwei verschiedenen Möglichkeiten zur Visualisierung):

• Nur rund für die Anzeige. Der Benutzer sollte interpretieren können, dass Zahlen abgeschnitten/gerundet sind. In Ihrem Beispiel sollte es offensichtlich sein, dass 6.67 eigentlich 6.66666... wäre.

• Runden Sie nicht und schneiden Sie nur die Zahlen nach einer festen Anzahl von Dezimalzahlen ab (fügen Sie ... hinzu, falls erforderlich; das ist tatsächlich ähnlich zu der anderen Lösung).

Im Allgemeinen, wenn Sie den verfügbare lineare Gleichungen (oder Mathematik im Allgemeinen), sollte stets lösen mögen (und vernünftig, Leistung klug) Datentyp mit der größten Genauigkeit zur Verfügung, in der Regel einfach oder doppelt seine Präzision Werte. Andernfalls führen Sie Fehlerränder immer schlimmer ein, je mehr Sie mit ihnen rechnen.

Answer 3

Sie können Rundung nicht beseitigen, wenn Sie mit Gleitkommazahlen arbeiten. Ihre beste Lösung könnte darin bestehen, mit Ganzzahlen in der Matrix zu bleiben und dann das endgültige 1/6 auf das Ergebnis anzuwenden.

Answer 4

Eine gängige Methode, um sicherzustellen, dass kleine Rundungsfehler nicht zu einem großen Fehler in der Summe führen, besteht darin, zu prüfen, ob der Fehler bei jeder Teilsumme nicht zu groß wird.

Mit einer Dimension Vektor [a[1], a[2], ..., a[n]], können Sie die Teilsummen [a[1], a[1]+a[2], ..., a[1]+a[2]+...+a[n]], multiplizieren sie berechnen und dann den guten Vektor wiederherstellen, indem Subtrahieren der vorherigen Zelle zur aktuellen: [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]. Mit diesem Trick ist der Fehler bei jeder Partialsumme nicht mehr als 10^(- x).

Sie können diese Methode anpassen für eine 2 Dimensionen Matrix mit den drei folgenden Verfahren:

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