Come identificare i calcoli in virgola mobile instabili?

15

In numeri, è molto importante essere in grado di identificare instabile schemi e migliorare la loro stabilità. Come identificare instabile calcoli in virgola mobile?

Sto lavorando a una simulazione molto complessa in cui molti schemi numerici funzionano insieme e sto cercando una metodica per identificare le sue parti deboli. Sto lavorando a un modello fisico che coinvolge equazioni differenziali. Una vista a volo d'uccello del processo complessivo è:

  1. (Fase preliminare) Raccogli le osservazioni fisiche P .

  2. Determina i parametri iniziali della simulazione. Questo utilizza un algoritmo di ottimizzazione, in cui camminiamo in uno spazio parametrico e cerchiamo parametri C tali che una funzione di errore E (F (C), P) sia minimizzata, dove F è una certa quantità derivata dei parametri.

  3. Plug C nel motore di simulazione. Questo è uno schema di Eulero dell'EDP, in modo che in ogni fase temporale calcoliamo i termini che guidano la dinamica (ognuno di essi è una funzione complessa, potenzialmente soggetta a instabilità) e alimentiamo lo schema di Eulero con questi termini dinamici per calcolare il prossimo stato. Questo va avanti per migliaia di punti temporali.

  4. Al termine della simulazione, calcoliamo alcune funzioni Prova (S) dello stato finale S e confrontiamo con alcune quantità Richiedi ( P) dedotto dalle quantità osservate. Questa non è una prova formale del risultato, più un controllo di plausibilità.

Inoltre, vedo una torre di operazioni complesse (calcolo di termini dinamici, all'interno dello schema di Eulero, all'interno di Proof ). E vorrebbe riconoscere "parti cattive" e correggerle.

Ho ipotizzato che usando un'implementazione software di virgola mobile i numeri con precisione ridotta amplificano l'instabilità di schemi numerici, facilitando così il confronto tra diversi implementazioni. È una tecnica comune per indagare su questo domanda? È possibile utilizzare una macchina virtuale, come Bochs, per raggiungere questo senza alterare il programma?

Affrontare adeguatamente la questione della stabilità, a volte è così accettabile per indirizzare l'input tipico della procedura numerica, quindi che può essere sintonizzato per fare bene su quell'input e forse meno bene su altro input valido, ma improbabile. Dato un campione di input tipici, è possibile snoop alcuni risultati intermedi e preparare a profilo statistico per loro. Ancora una volta, è una tecnica comune a studiare i problemi di stabilità? Una macchina virtuale è utile per questo?

    
posta user40989 11.12.2013 - 10:50
fonte

4 risposte

6

Lo studio della stabilità del calcolo in virgola mobile fa parte dell'analisi numerica e se vuoi davvero un risultato sonoro, vuoi davvero che qualcuno esperto in quel dominio faccia l'analisi degli algoritmi usati.

Ci sono alcune cose che possono aiutare a identificare sperimentalmente algoritmi instabili. In esecuzione con arrotondamento impostato su diverse modalità (su / giù / casuale) o con diversa precisione e controllando che il risultato non vari troppo. Rispondere a è troppo? non è affatto semplice e anche quando la risposta è no non significa che l'algoritmo sia stabile, solo che non è stato rilevato instabile sul set di dati che hai usato.

L'aritmetica dell'intervallo è stata proposta nei commenti. Quando l'ho guardato, anche il più rabbioso sostenitore dell'aritmetica intervallata ha ammesso che ha funzionato bene con algoritmi progettati per l'aritmetica a intervalli, ma che passare ad esso senza analizzare l'algoritmo e assicurarsi che non ci fossero pattern noti per non funzionare bene non essere utile (gli avversari sembravano dell'opinione che le pre-condizioni per l'aritmetica degli intervalli fossero utili laddove troppo restrittive per essere di interesse pratico)

    
risposta data 13.12.2013 - 15:41
fonte
3

La progettazione di algoritmi floating point stabili è altamente non banale. Quelli più matematicamente abili di me suggeriscono di utilizzare biblioteche ben considerate laddove possibile piuttosto che tentare di far girare il proprio. Il riferimento standard nell'area sembra essere:

N. J. Higham. Precisione e stabilità degli algoritmi numerici. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, seconda edizione, 2002. ISBN 0-89871-521-0

Non sapere di più su quali tipi di calcoli, lingue, ecc. rende difficile dare una risposta molto concreta. C'è una buona lezione qui: link questo può essere un po 'di base, ma è una buona introduzione se sei usando java.

    
risposta data 17.12.2013 - 19:25
fonte
1

How to identify unstable floating point computations? Is this a common technique to investigate this question?

Penso che se non hai bisogno di mostrare alcune statistiche sull'errore, non hai davvero bisogno di raccogliere campioni. Quello di cui hai bisogno è Analisi numerica , che rientra anche nelle materie dei metodi numerici, dell'algebra lineare numerica, ecc. fa parte dell'informatica, quindi potresti ottenere alcune risposte anche in cs.stackexchange.

In ogni caso, nella programmazione generale, la maggior parte dei problemi è facile da individuare, dato un po 'di comprensione di base su come funziona in virgola mobile e metodi numerici di base. Ma anche problemi più complessi sono "più facili" da risolvere oggi con disponibilità di float a 128 bit, motivo ancora meno per produrre campioni di errori. Ecco alcuni problemi di esempio per mostrare il mio punto:

  1. utilizzando il virgola mobile per il calcolo dei valori monetari.
  2. utilizzo di virgola mobile per numeri grandi.
  3. non fare divisioni prima di altre operazioni quando è possibile farlo. (per rendere il valore più vicino a 0).
  4. calcolo lungo senza trattamento speciale per la propagazione degli errori.

C'è anche un esempio di algoritmo ingenuo e algoritmo compensato in errore qui algoritmo per il calcolo della varianza . Nell'esempio, guardando la versione ingenua, puoi solo odorare che fare dei calcoli nei loop porti degli errori e non viene compensato.

    
risposta data 11.12.2013 - 22:08
fonte
0

È possibile evitare errori numerici utilizzando tipi di dati appropriati (come, ad esempio, le frazioni continue). Se hai bisogno o vuoi utilizzare l'aritmetica in virgola mobile, devi applicare il know-how numerico per conoscere gli errori.

    
risposta data 12.12.2013 - 12:17
fonte

Leggi altre domande sui tag