행렬에서 반올림 오류 제거

Question

내 문제는 모든 행의 합계와 모든 열의 합이 0 인 행렬이 있다는 것입니다. 모든 숫자는 x 소수로 반올림됩니다.

그런 다음 전체 행렬에 0과 1 사이의 숫자 (예 : 1/6)를 곱하고 모든 숫자를 x 소수 자릿수로 반올림합니다. 이제 행과 열의 합이 0이 될지 확신 할 수 없습니다. 가능한 가장 작은 조정 (또는 적어도 매우 작은 조정)으로 합계를 0으로 다시 설정합니다.

이러한 문제를 해결할 수있는 알고리즘이 있습니까? (아주 간단)

예 : 매트릭스 :

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 

Answer 1

이것은 해결책이 아닙니다.

모든 숫자를 x 자릿수로 반올림하므로이 숫자를 정수로 처리 할 수 ​​있습니다 (곱하기 만하면됩니다.). 10^x 씩). 정수 Adj11 찾기, 매트릭스

A11..Amn 상수 정수

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

을 감안할 때

을 ... :

지금, 당신은 다음과 같은 문제를 해결하기 위해 노력하고있다Adjmn

최소화 합 (ABS (Adjxy는))

(또는 어쩌면 당신은 선호 :

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

이 제품은 integer programming입니다 : 합을 최소화 ((Adjxy)^2)

주제에 문제는 m * n 변수와 m + n 제약으로 최소화하려고하는 함수가 선형이 아닙니다.

이 문제는 아주 간단합니다. 더 잘 게시해야합니다. https://math.stackexchange.com/

Answer 2

. 전혀 돌아 가지 않는 한 할 수있는 일은 없습니다. 이는 사진을 256 색 이미지로 저장하는 것과 유사합니다. 당신은 정보를 잃어 버리고 있습니다 (본질적으로 정확도는 이산화). 당신이 할 수있는 일은 아무것도 없습니다. 그림의 경우 이미지가 원색 (예 : 디더링)에 더 가깝게/더 밝게 표시되도록하는 알고리즘이 있지만 단일 값의 숫자에는 해당하지 않습니다.

가능한 솔루션 (시각화하는 두 가지 방법으로 실제로 한) : 디스플레이

• 만 원. 사용자는 숫자가 절사/반올림됨을 해석 할 수 있어야합니다. 귀하의 예에서 그것은 6.67이 실제로는 6.66666... 일 것임을 분명히해야합니다.

• 고정 소수 자릿수 뒤에 숫자를 반올림하지 마십시오 (필요한 경우 ... 추가, 다른 솔루션과 실제로 비슷 함). 사용 가능한 사용 항상 선형 방정식 (또는 일반적으로 수학을) 해결하려는 경우 일반적으로

, 이용 가능한 가장 큰 정밀 (그리고 합리적인 성능 현명한) 데이터 유형을, 보통 인 단일 또는 이중 정밀도 값. 그렇지 않으면 오류 마진이 점점 악화되고 그로 인해 더 많이 계산하게됩니다.

Answer 3

부동 소수점 숫자로 작업 할 때 반올림을 제거 할 수 없습니다. 가장 좋은 해결책은 행렬에 정수를 고집 한 다음 최종 결과를 1/6에 적용하는 것입니다.

Answer 4

작은 반올림 오류로 인해 합계에 큰 오류가 발생하지 않도록하는 일반적인 방법은 오류가 각 부분 합계에서 너무 크게되지 않는지 확인하는 것입니다. 한 차원 벡터 [a[1], a[2], ..., a[n]]와

, 당신은, 부분 합계 [a[1], a[1]+a[2], ..., a[1]+a[2]+...+a[n]]을 계산 곱 후 현재에 이전 셀을 substracting하여 좋은 벡터를 복원 할 수 있습니다 [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