Επίλυση εξισώσεων στο περίπου.

[masteripper]

Έχω 1 πρόβλημα του τύπου :

Ας υποθέσουμε ότι έχουμε 10 εξισώσεις του τύπου

α1χ1α + α2χ2α+....+α7χ7α =Α

α1χ1β+α2χ2β+.....+α7χ7β =Β

..........................................

α1χ1κ+α2χ2κ+...α7χ7κ =Κ

οι τιμές χ1α,χ2α,...χ7κ είναι γνωστές σε αυτό δεν τίθεται θέμα

το πρόβλημα είναι ότι οι εξισώσεις/συντελεστές δεν είναι σωστοί για κάποιες περιπτώσεις  αλλά είναι για τις περισσότερες

δηλαδή υποθέτουμε ότι μια λύση του τύπου

α1,α2...α7 = {1,4,3,2,3,8,6}

ικανοποιεί τις 7 απο τις 10 εξισώσεις αλλά όχι και τις 10...πως θα μπορούσαμε να το προσεγγίσουμε αλγοριθμικά.

Υπόψιν ότι το παραπάνω είναι απλώς 1 παράδειγμα ...στην πραγματικότητα θα είναι χιλιάδες εξισώσεις ...οι συντελεστές και το μήκος των εξισώσεων θα είναι όμως μερικές δεκάδες το πολύ.

 

Επεξ/σία 21 Απριλίου 2019 από masteripper

[Fortistis]

Μία καλή αρχή θα ήταν να καταλάβεις εσύ τι ζητάς και να το γράψεις σωστά. 

Π.χ., γράφεις: 

1 λεπτό πριν, masteripper είπε

οι τιμές χ1α,χ2α,...χ7κ είναι γνωστές

αλλά δεν υπάρχει πουθενά "α". Υπάρχει "α1", "α2" κτλ. Οπότε, τι ακριβώς είναι το "α1" και τι το "χ1α"; είναι ίδια ή διαφορετικά; Τι ακριβώς είναι τα δεκαδικά ψηφία στις εξισώσεις; Scalars ή indices; 

Επίσης, γράφεις "Επίλυση εξισώσεων στο περίπου.". Τι ακριβώς είναι το "περίπου"; 

 

[masteripper]

Πολύ ευχαρίστως να στο εξηγήσω :

υποθετικά πάντα

1)  α1 x 10 + a2 x 11 +...a7 x 25 = 100

2)  α1 x 5 + a2 x 7 +........a7 x 3 = 110

.................................................

10) a1 x 8 + a2 x 4 +.....a7 x 13 =133

Απο αυτό το παραπάνω σετ εξισώσεων υπάρχει μια λύση α1,α2...α7 = {1,4,3,2,3,8,6} που ικανοποιεί την (1),(2),(4),(5),(7),(8),(9) και (με βάση το αν είχαμε περισσότερες εξισώσεις)  μια λύση α1,α2...α7 = {2,4,11,2,7,8,6}  που ικανοποιεί την (3),(6),(10)  

Θέλω να βρω αυτή την λύση που ικανοποιεί τις περισσότερες εξισώσεις..

[Fortistis]

2 λεπτά πριν, masteripper είπε

Πολύ ευχαρίστως να στο εξηγήσω

Σόρρυ, δεν εξηγείς αλλά αποσαφηνίζεις το μπερδεμένο σου αρχικό post. Θα εξηγούσες κάτι εάν αυτό που είχες γράψει ήταν σωστό και κατανοητό. 

Άρα, τα δεκαδικά ψηφία στο αρχικό σου post: 

17 λεπτά πριν, masteripper είπε

Ας υποθέσουμε ότι έχουμε 10 εξισώσεις του τύπου

α1χ1α + α2χ2α+....+α7χ7α =Α

α1χ1β+α2χ2β+.....+α7χ7β =Β

..........................................

α1χ1κ+α2χ2κ+...α7χ7κ =Κ

οι τιμές χ1α,χ2α,...χ7κ είναι γνωστές σε αυτό δεν τίθεται θέμα

είναι scalars ή indices; Δεν μου απάντησες. 

Επίσης, δεν μπορώ να καταλάβω πως ντε και καλά δεν υπάρχει λύση για όλες τις εξισώσεις. 

[masteripper]

9 λεπτά πριν, Fortistis είπε

scalars ή indices

Σε έχασα λίγο...απλοί αριθμοί είναι όλα...δεν έβαλα πουθενά δεκαδικά ψηφία...αν εννοείς τα χ1α,χ2α,χ1β...κτλ είναι απλώς οι διαφορετικές τιμές σε κάθε εξίσωση

για πιο απλά :

a x x1 +b x y1=z1

a x x2+b x y2=z2

9 λεπτά πριν, Fortistis είπε

καλά δεν υπάρχει λύση για όλες τις εξισώσεις

Αυτό  είναι σίγουρο...κάποιες θα είναι "θόρυβος" ...το θέμα είναι η καλύτερη προσέγγιση ...

 

Επεξ/σία 21 Απριλίου 2019 από masteripper

[Fortistis]

4 λεπτά πριν, masteripper είπε

για πιο απλά :

ax1 +by1=z1

ax2+by2=z2

Αυτό είναι διαφορετικό από το: 

31 λεπτά πριν, masteripper είπε

α1χ1α + α2χ2α+....+α7χ7α =Α

α1χ1β+α2χ2β+.....+α7χ7β =Β

..........................................

α1χ1κ+α2χ2κ+...α7χ7κ =Κ

Τι από τα δύο ισχύει τελικά; Σε αυτό που θα ισχύει, τα δεκαδικά ψηφία τι είναι τελικώς;

4 λεπτά πριν, masteripper είπε

Αυτό  είναι σίγουρο...κάποιες θα είναι "θόρυβος"

Γιατί είναι σίγουρο; Πώς αποδεικνύεται αυτό; Και τι εννοείς "θόρυβος" και από πού προέρχεται ο θόρυβος αυτός; Τι χαρακτηριστικά έχει; Προέρχεται από φυσικό μέσο ή σφάλματα στο σήμα; Έχεις κάποιο prior για την κατανομή του; 

Επίσης, έχεις τους vectors a και b ενώ πριν δεν είχες vectors αλλά είχες matrices ( ; ). Τελικά τι ισχύει στο σύστημα που έγραψες; 

Επεξ/σία 21 Απριλίου 2019 από Fortistis

[masteripper]

Για επεξήγηση :

απλώς δες αυτό την αντιστοιχιση:

α1χ1α + α2χ2α+....+α7χ7α =Α

αντιστοιχεί

α1 x 10 + a2 x 11 +...a7 x 25 = 100

χ1α = 10

χ2α = 11

χ7α = 25

μαλλον σε μπέρδεψε που χρησιμοποίησα το χ..(λάθος) ...έπρεπε να βάλω και το σύμβολο του πολλαπλασιασμού..

Όσον αφορά τον "θόρυβο"...απλώς κάποιες εξισώσεις δεν θα μπορούν να ικανοποιηθούν...

ας πούμε ότι θα έχω 10,000 εξισώσεις με 20 αγνώστους...απο αυτές θεωρώ ότι για τις 8,000 υπάρχει μια λύση (a1,a2,...a20) ,αντίστοιχα για 1500 υπάρχει μια άλλη λύση (b1,b2,...b20)...και για τις υπόλοιπες 500 υπάρχει μια 3η λύση (c1,c2,...c20)...το θέμα είναι πως θα βρω αυτή την 1η λύση...αν μπορούσα να κινηθώ και σε επίπεδο εύρους ακόμα καλύτερα..δηλαδή αν b1 παίζει σε 1 range (a1 -0.05 , a1+0.05} και ισχύει το ίδιο για τους υπόλοιπους αγνώστους θα μπορούσα να δεχτώ ότι η λύση (a1,a2,...a20) ικανοποιεί τις 9500 εξισώσεις έστω και με μια μικρή απόκλιση.

[Fortistis]

Δεν μπορώ να καταλάβω το δεδομένο ότι δεν θα ικανοποιούνται όλες οι εξισώσεις. Δηλαδή, για ποιο λόγο δεν μπορείς να βρεις τις τιμές των 20 αγνώστων που να ικανοποιούν όλες τις συνθήκες. 

[albNik]

Αν ικανοποιουνται πανω απο 20 εξισώσεις (π.χ 100) για 20 μεταβλητές, τοτε τουλάχιστον οι 80 ειναι γραμμικός συνδυασμός των υπολοιπων.

Ας πούμε εχεις 2 μεταβλητες

1. x+2y=8
2. 2x+3y=10

Οι παρακάτω ειναι συνδυασμος των αποπανω

1. 100x+200y=800
2. 3x+5y=18
3. 12x+23y=90

Δεν νομιζω  να υπαρχει αποδοτικη λυση στο πρόβλημα σου. 

 

 

 

[ajaxmonkey4hire]

6 λεπτά πριν, albNik είπε

Αν ικανοποιουνται πανω απο 20 εξισώσεις (π.χ 100) για 20 μεταβλητές, τοτε τουλάχιστον οι 80 ειναι γραμμικός συνδυασμός των υπολοιπων.

Ας πούμε εχεις 2 μεταβλητες

1. x+2y=8
2. 2x+3y=10

Οι παρακάτω ειναι συνδυασμος των αποπανω

1. 100x+200y=800
2. 3x+5y=18
3. 12x+23y=90

Δεν νομιζω  να υπαρχει αποδοτικη λυση στο πρόβλημα σου. 

έτσι όπως το λες.

[masteripper]

Επειδή βλέπω ότι προκάλεσα αρκετή σύγχυση θα επανέλθω με εκτενές παράδειγμα.

[masteripper]

Λοιπόν , ας ξεκινήσουμε με 1 απλό παράδειγμα : 3 εξισώσεις με 3 αγνώστους

a x 2 + b x 2 +c = 2

a x 1 + b x 1 +c x 2 = 4

a x 1 + b x 2 +c x 3 = 8

επιλύοντας βλέπουμε ότι η λύση είναι :

a,b,c = {-2,2,2}

εως εδώ όλα καλά

προσθέτουμε άλλη μια εξίσωση

a x 1 + b x 1 +c x 1 = 2

η λύση παραπάνω προφανώς ικανοποιεί τις απαιτήσεις της 4ης εξίσωσης

και συνεχίζουμε.....

κάποια στιγμή έχουμε  μια εξίσωση

a x 1 + b x 1 +c x 2 = 3

κάπου εδώ έχουμε πρόβλημα καθώς η παραπάνω εξίσωση είναι ίδια με μία απο τις προηγούμενες...και ουσιαστικά όλες οι παραπάνω εξισώσεις είναι άκυρες...ΑΛΛΑ

αν υποθέσουμε ότι βάζουμε στην άκρη αυτή την εξίσωση προς το παρόν...

και κάποια στιγμή έχουμε εξισώσεις

a x 2 + b x 2 +c = 1

a x 1 + b x 2 +c x 3 = 2

τώρα αρχίζει και μεγαλώνει το πρόβλημα καθώς έχουμε μια λύση για τις "κοκκινες "εξισώσεις που είναι 

a',b',c' = { 2.3 , -2.66  1.66}

κάπου εδώ αρχίζει και περιπλέκεται η υπόθεση

προχωρώντας λίγο παραπέρα...θεωρούμε ότι έχουμε 10000 εξισώσεις

και η λύση

a,b,c = {-2,2,2}

ικανοποιεί  τις 7500 εξισώσεις απο τις 10000 

όμοια η λύση  

a',b',c' = { 2.3 , -2.66  1.66}

ικανοποιεί  τις 2000 εξισώσεις απο τις 10000 

και ας υποθέσουμε ότι υπάρχει και μια 3η λύση που ικανοποιεί τις εναπομείναντες 500 εξισωσεις

a'',b'',c'' = { 2 , -3.6  4}

Το θέμα είναι πως βρίσκουμε αυτή την 1η λύση ( a,b,c = {-2,2,2} ) ) που ικανοποιεί τις περισσότερες απο τις εξισώσεις  ..

Περιπλέκοντας ακόμα περισσότερο την κατάσταση ας υποθέσουμε ότι η 2η λύση ( a',b',c' = { 2.3 , -2.66  1.66} )  ήταν τελικά a',b',c' = {-2.1,1.9,1.8} και απ'οτι βλέπουμε δεν απέχει και πολύ απο την καλή 1η λύση ( a,b,c = {-2,2,2} ) ) οπότε μπορούμε να θεωρήσουμε ότι η 1η λύση καλύπτει μια χαρά τις 9500 εξισώσεις αφού τελικά το αποτέλεσμα έχει πολύ μικρή απόκλιση.

Ελπίζω να έγινε λίγο πιο κατανοητό.

Επεξ/σία 21 Απριλίου 2019 από masteripper

[pmav99]

Θυμίζει ΧΥ πρόβλημα... Anyway

Έστω ότι έχεις Κ εξισώσεις και Ν αγνώστους με Κ >= Ν

Βήμα 1ο: μειώνεις τον αριθμό των εξισώσεων Κ πετώντας έξω όσες είναι γραμμικά εξαρτημένες. Καταλήγεις με Λ γραμμικά ανεξάρτητες εξισώσεις

Βήμα 2ο; Διαλέγεις Ν από τις Λ εξισώσεις και κοιτάς αν υπάρχει λύση. Αν δεν υπάρχει λύση διαλέγεις Ν διαφορετικές εξισώσεις και επαναλαμβάνεις μέχρι να βρεις τη λύση a.

Βήμα 3ο: Εφαρμόζεις την λύση a σε όλες τις υπόλοιπες εξισώσεις (δηλαδή σε Λ-Ν εξισώσεις). Αν κάποια εξίσωση δεν ικανοποιείται από τη λύση που βρήκες, τότε τη μαρκάρεις για να δοκιμάσεις να τη λύσεις στο επόμενο βήμα. Στο τέλος αυτού του βήματος θα πρέπει να έχεις μαρκάρει Μ εξισώσεις

Βήμα 4ο: Αν Μ >=Ν γυρνάς στα βήματα 2 και 3, μόνο που αντί για Λ εξισώσεις έχεις πλέον Μ και η λύση που θα βρεις θα είναι η b. Αν Μ < Ν τότε δεν μπορείς να λύσεις τις εξισώσεις που έμειναν

Επεξ/σία 22 Απριλίου 2019 από pmav99

[albNik]

Δεν νομιζω να υπαρχει αποδοτικός τροπος να βρεις το μεγαλύτερο subset απο N εξισώσεις. Αν ειναι χιλιάδες οπως ειπες τοτε ξεχασε το. Ειναι της ταξης του 2^N.

[pmav99]

Αν οι περισσότερες εξισώσεις έχουν όντως κοινή λύση, τότε συνήθως η πρώτη λύση που θα βρεις θα είναι τις περισσότερες φορές η «σωστή». Και αν δεν είναι σύντομα θα την πετύχεις.

Αφού βρεις μία λύση, το να τεστάρεις πόσες εξισώσεις ικανοποιεί είναι vectorized operation. Πχ σε python + numpy:

import numpy as np

# Αυτά είναι τα νούμερα που υπαρχουν αριστερά του ίσον
coefficients = np.array([
    [2, 2, 1],   # satisfied
    [1, 1, 2],   # satisfied
    [1, 2, 3],   # satisfied
    [1, 2, 2],   # not satisfied
    [1, 2, 3],   # not satisfied 
])

# Αυτή είναι τα νούμερα που υπάρχουν δεξιά του ίσον. Τα δύο τελευταία δεν ικανοποιούν την εξίσωση
expected = np.array([ 2, 4, 8, 3, 2])

# Αυτή είναι η λύση που βρήκες (με Gauss ή με ό,τι χρησιμοποιείς)
solution = np.array([-2, 2, 2])

results = coefficients * solution
unsolved = coefficients[results.sum(axis=1) != expected]

print(unsolved)
# [[1 2 2]
#  [1 2 3]]

 

Επεξ/σία 21 Απριλίου 2019 από pmav99