मैट्रिक्स

Question

से गोल करने वाली त्रुटियों को खत्म करना मेरी समस्या यह है कि मेरे पास एक मैट्रिक्स है जहां सभी पंक्तियों का योग है, और सभी स्तंभों का योग शून्य है। सभी संख्याओं को x decimals के लिए गोल कर रहे हैं।

फिर मैं पूरे मैट्रिक्स को 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 

Answer 1

यह कोई समाधान नहीं है; आप जो हासिल करने की कोशिश कर रहे हैं, उसके बारे में सिर्फ एक और गणितीय विवरण (यह निर्णय लेने के बिना कि यह सही काम है):

चूंकि आप सभी संख्याओं को x दशमलव तक गोल कर रहे हैं, इसलिए हम इन संख्याओं को पूर्णांक के रूप में देख सकते हैं (बस गुणा करें उन्हें 10^एक्स द्वारा)। खोजें पूर्णांकों Adj11,

मैट्रिक्स

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 निरंतर पूर्णांक हैं को देखते हुए

...:

अब, आप निम्न समस्या को हल करने की कोशिश कर रहेAdjmn

को न्यूनतम राशि (पेट (Adjxy))

(या शायद आप पसंद करते हैं: राशि कम से कम ((Adjxy)^2)

विषय के लिए:

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

यह एक integer programming है समस्या, एम * एन चर और एम + एन बाधाओं के साथ। जो कार्य आप कम करने की कोशिश कर रहे हैं वह रैखिक नहीं है।

मुझे डर है कि यह समस्या तुच्छ से बहुत दूर है। मुझे विश्वास है यह है कि आपको 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