Algoritmi

ABS algorithm.

Una famiglia di algoritmi per la risoluzione di sistemi lineari

Come già detto si tratta di una famiglia di algoritmi per la risoluzione di sistemi lineari di m equazioni del tipo:

Ax=b

con n variabili tali che risulti n>=m.
La proprietà che li contaddistingue dagli altri tipi di algoritmi è che la k-esima iterazione x^k è la soluzione delle prime k equazioni. Gli algoritmi appartenenti a tale classe sono tutti anterirori al 1934, tale faamiglia è stata studiata e formalmente realizzata da J. Abaffy, C.G. Broyden e E. Spedicato, si può notare quindi che il nome della famiglia ABS corrisponde proprio alle iniziali dei nomi di tali studiosi.
Gli algoritmi ABS si compongono nel modo seguente.

Notazione: A_i è la i-esima riga di A.

• Inizializzazione: si sceglie x⁰ in Rⁿ, H¹ in R^n×n e nonsingolare; si pone i=1.
• Si dirige la ricerca nella direzione dⁱ = Hⁱz per ogni z che non soddisfa z'HⁱA_i=0. Si valuta quindi il residuo come: r = Axⁱ-b.
• Si itera: xⁱ⁺¹ = xⁱ - s dⁱ, dove s è il passo: s = r_i / A_i dⁱ.
• Si effettua un test per la convergenza dell'algoritmo (aggiornamento del residuo, se utilizzato nel test); il test può essere posto attraverso la seguente domanda:
  E' stata trovata la soluzione con la tolleranza richiesta? Se è vero stop; altrimenti continua.
• Aggiornamento con Hⁱ⁺¹ = Hⁱ - Dⁱ, dove Dⁱ è aggiornato nella forma HⁱA_iwHⁱ' per w tale che wHⁱA_i = 1.
• Si incrementa i e si va allo step 1.
  

Gli algoritmi ABS possono essere estesi anche all'analisi di equazioni nonlineari.

• » Invia tramite EMAIL
• » Versione per la STAMPA
• » Le vostre opinioni

I link correlati all'argomento

• I numeri di Fibonacci
• L'algoritmo dei minimi quadrati
• L'algoritmo di Eulero
• L'algoritmo di eliminazione di Gauss