Sistema di "quasi-equazioni" lineari

[energy-engineer]

Ciao a tutti.
Devo risolvere vari sistemi di N equazioni lineari in 8 incognite (con \(\displaystyle N\geq 8 \)) in cui i termini noti non sono "precisi", poiché approssimati all'intero più vicino. Le 8 incognite sono reali positive (non nulle).
Cerco di spiegarmi con questo esempio inventato:

\(\displaystyle \begin{cases}
2x_1+10x_2+18x_3+26x_4+34x_5+42x_6+50x_7+58x_8\simeq90\\
3x_1+11x_2+19x_3+27x_4+35x_5+43x_6+51x_7+59x_8\simeq91\\
4x_1+12x_2+20x_3+28x_4+36x_5+44x_6+52x_7+60x_8\simeq92\\
5x_1+13x_2+21x_3+29x_4+37x_5+45x_6+53x_7+61x_8\simeq93\\
6x_1+14x_2+22x_3+30x_4+38x_5+46x_6+54x_7+62x_8\simeq94\\
7x_1+15x_2+23x_3+31x_4+39x_5+47x_6+55x_7+63x_8\simeq95\\
8x_1+16x_2+24x_3+32x_4+40x_5+48x_6+56x_7+64x_8\simeq96\\
9x_1+17x_2+25x_3+33x_4+41x_5+49x_6+57x_7+65x_8\simeq97
\end{cases} \)

Il sistema non ha soluzione se considero ogni linea come un'equazione. Il motivo è proprio il fatto che i termini noti sono arrotondati all'intero più vicino (quindi, ad esempio, la prima equazione potrebbe avere un termine noto pari a 89,734 oppure pari a 90,333).
Ogni singola equazione di questo sistema, quindi, dovrebbe essere considerata a rigor di logica come un "mini-sistema" di 2 disequazioni a 8 incognite di questo tipo (prendo ad esempio la prima equazione del sistema):

\(\displaystyle \begin{cases}
2x_1+10x_2+18x_3+26x_4+34x_5+42x_6+50x_7+58x_8\geq89,5\\
2x_1+10x_2+18x_3+26x_4+34x_5+42x_6+50x_7+58x_8<90,5\\
\end{cases} \)

Questo produce il raddoppiamento delle dimensioni del sistema, che sostanzialmente diventa un sistema di 16 disequazioni lineari in 8 incognite.

Come risolvo sistemi di questo tipo? Grazie mille.

[sellacollesella]

Devo risolvere vari sistemi di N equazioni lineari in 8 incognite (con \( \displaystyle N\geq 8 \)) in cui i termini noti non sono "precisi", poiché approssimati all'intero più vicino. Le 8 incognite sono reali positive (non nulle).

In linea generale, un sistema \(Ax=b\) di \(m\) equazioni lineari in \(n\) incognite non ammette un'unica soluzione \(x\), bensì potrebbe non ammetterne oppure potrebbe ammetterne infinite. Pertanto, quello che si è soliti fare è "accontentarsi" della migliore approssimazione di \(x\) nel senso dei minimi quadrati, ossia \(\underset{x\in\mathbb{R}^n}{\min} ||Ax-b||^2\). D'altro canto, nel caso in esame ciò non basta, perché vogliamo anche che \(x_i > 0\) per ogni \(i \in [1,n]\) e ciò porta ad un problema ai minimi quadrati vincolati, che a seconda del tipo di vincoli si ramifica ulteriormente.

Cerco di spiegarmi con questo esempio inventato: [...]

Servendoci, ad esempio, di Wolfram Mathematica, possiamo risolverlo così:

Codice:

A = {{2, 10, 18, 26, 34, 42, 50, 58},
     {3, 11, 19, 27, 35, 43, 51, 59},
     {4, 12, 20, 28, 36, 44, 52, 60},
     {5, 13, 21, 29, 37, 45, 53, 61},
     {6, 14, 22, 30, 38, 46, 54, 62},
     {7, 15, 23, 31, 39, 47, 55, 63},
     {8, 16, 24, 32, 40, 48, 56, 64},
     {9, 17, 25, 33, 41, 49, 57, 65}};

x = {x1, x2, x3, x4, x5, x6, x7, x8};

b = {90, 91, 92, 93, 94, 95, 96, 97};

NMinimize[{Total[(A.x - b)^2], Thread[x > 0]}, x]

tramite il quale si ottiene come soluzione:

Codice:

{11.3552, {x1 -> 9.0716*10^-11, x2 -> 1.06002*10^-10, x3 -> 1.27402*10^-10, x4 -> 1.59503*10^-10,
x5 -> 2.13004*10^-10, x6 -> 3.20006*10^-10, x7 -> 6.41012*10^-10, x8 -> 1.5196}}

In ogni modo, se spieghi un po' come nascono queste equazioni/disequazioni forse può aiutare.

[energy-engineer]

Buona domenica, sellacollesella, e grazie per la risposta!

In ogni modo, se spieghi un po' come nascono queste equazioni/disequazioni forse può aiutare.

Sinceramente non ne ho idea da dove nasca questa richiesta di mio figlio. Se può servire a inquadrare il problema, glielo chiederò.

C'è un'ulteriore condizione che mi sono completamente dimenticato di riportare: la somma delle incognite deve fare 1. Come posso implementare nel tuo codice questa condizione? Inoltre, il tuo codice cambia se il numero di equazioni fosse superiore al numero di incognite o basterebbe semplicemente aggiungere nuove righe alle matrici A e b?

Ti ringrazio!

[sellacollesella]

Sinceramente non ne ho idea da dove nasca questa richiesta di mio figlio. Se può servire a inquadrare il problema, glielo chiederò.

Forse sarebbe meglio che lo scriva qui direttamente tuo figlio.

C'è un'ulteriore condizione che mi sono completamente dimenticato di riportare: la somma delle incognite deve fare 1. Come posso implementare nel tuo codice questa condizione?

Aggiungi al sistema l'equazione \(x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8=1\).

Inoltre, il tuo codice cambia se il numero di equazioni fosse superiore al numero di incognite o basterebbe semplicemente aggiungere nuove righe alle matrici A e b?

Il metodo ai minimi quadrati sopra citato è la via standard per approssimare soluzioni di sistemi con più equazioni che incognite (sistemi sovradeterminati). Quindi sì, basta aggiungere delle righe ad \(A\) e \(b\).

[energy-engineer]

Aggiungi al sistema l'equazione \(x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8=1\).

Purtroppo in questo modo la condizione citata viene rispettata con errori troppo grandi (mediamente del 5-6% circa). Ho bisogno invece che l'errore sia di almeno un ordine di grandezza inferiore

[ingres]

Ho bisogno invece che l'errore sia di almeno un ordine di grandezza inferiore

Se l'equazione di normalizzazione a 1 è prioritaria devi in qualche modo enfatizzarla. Ad esempio potresti provare ad aumentare il peso dell'equazione in questione moltiplicando entrambi i membri per un numero elevato tipo 10-100.

In alternativa potresti cambiare approccio e imporre la condizione in questione come funzione obiettivo di un problema di ottimo scrivendo le altre come disequazioni di vincolo.
Questo approccio può anche essere fatto con il Solver di Excel.

[energy-engineer]

Se l'equazione di normalizzazione a 1 è prioritaria devi in qualche modo enfatizzarla. Ad esempio potresti provare ad aumentare il peso dell'equazione in questione moltiplicando entrambi i membri per un numero elevato tipo 10-100.

Risolto niente

In alternativa potresti cambiare approccio e imporre la condizione in questione come funzione obiettivo di un problema di ottimo scrivendo le altre come disequazioni di vincolo.
Questo approccio può anche essere fatto con il Solver di Excel.

Molto interessante anche quest'idea! Ci provo!

[energy-engineer]

Dopo aver adeguatamente provato entrambi i metodi proposti, posso dire che questi sistemi non convergono ad alcuna soluzione accettabile. Grazie mille per il vostro aiuto e buona giornata!

[apatriarca]

Noto immediatamente che se sottraggo ogni equazione alla precedente ottengo qualcosa nella forma:
\[ \sum_{i=1}^8 x_i \approx 1. \]
In effetti ci è stato detto in seguito che questa equazione è esatta. Quindi di fatto il sistema è del tutto equivalente a
\[
\begin{cases}
\sum_{i=1}^8 \big(2 + 8\,(i-1)\big)\,x_i \ge 89.5 \\
\sum_{i=1}^8 \big(2 + 8\,(i-1)\big)\,x_i \le 90.5 \\
\sum_{i=1}^8 x_i = 1
\end{cases}
\]
Il sistema ha quindi certamente troppi gradi di libertà. Dall'equazione possiamo eliminare un grado di libertà (sostituendo ad esempio \(x_8 = 1 - \sum_{i=1}^7 x_i\)) ma a quel punto abbiamo comunque ancora due disequazioni lineari con 7 gradi di libertà.

[apatriarca]

Probabilmente un modo migliore per scrivere quell'approssimazione era comunque usare una variabile aggiuntiva e dire che era compresa tra \(-0.5\) e \(0.5\).