Successive Over Relaxation

In analisi numerica, il metodo Successive over-relaxation, comunemente detto SOR o metodo del rilassamento successivo, è una variante del metodo di Gauss-Seidel per la risoluzione di sistemi di equazioni lineari, caratterizzato da una convergenza più rapida. Fu introdotto dal matematico statunitense David M. Young Jr. nel 1950.

Formulazione

Si consideri un sistema di $n$ equazioni lineari di incognita $\mathbf {x}$ :

A\mathbf {x} =\mathbf {b}

dove

A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.

La matrice $A$ può essere decomposta come $A=D-(E+F),$ dove $D$ è la componente diagonale, $E$ e $F$ sono le componenti triangolari superiori e inferiori strette. Introducento un parametro di rilassamento $\omega$ nel metodo di Gauss-Seidel, si ottiene:

x_{i}^{(k+1)}={\frac {\omega }{a_{ii}}}\left[b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)}-\sum _{j=i+1}^{n}a_{ij}x_{j}^{(k)}\right]+(1-\omega )x_{i}^{(k)},

per $i=1,\dots ,n.$ La formulazione vettoriale è:

(I-\omega D^{-1}E)\mathbf {x} ^{(k+1)}=[(1-\omega )I+\omega D^{-1}F]\mathbf {x} ^{(k)}+\omega D^{-1}\mathbf {b} .

Convergenza

La scelta del parametro di rilassamento $\omega$ non è un problema semplice e dipende dalle proprietà della matrice dei coefficienti. Nel 1947, Ostrowski ha dimostrato che, se $A$ è simmetrica e definita positiva, il metodo SOR converge se e solo se $0<\omega <2.$

Raggio spettrale $\rho (C_{\omega })$ della matrice di iterazione del metodo SOR. Il grafico mostra la dipendenza dal raggio spettrale della matrice di iterazione del metodo di Jacobi ${\displaystyle \mu$ .

Inoltre, nel caso in cui la matrice dei coefficienti sia anche tridiagonale, è possibile determinare un parametro ottimale in corrispondenza del quale la velocità di convergenza sia la più elevata possibile:

\omega _{opt}={\frac {2}{1+{\sqrt {1-\rho ^{2}(B_{J})}}}},

dove $B_{J}=I-D^{-1}A$ è la matrice di iterazione del metodo di Jacobi e $\rho (B_{J})$ il suo raggio spettrale. Inoltre, in corrispondenza di tale valore il fattore asintotico di convergenza è pari a

\rho (B(\omega _{opt}))={\frac {1-{\sqrt {1-\rho ^{2}(B_{J})}}}{1+{\sqrt {1-\rho ^{2}(B_{J})}}}}.

Algoritmo

Esempio con Python e NumPy

Di seguito viene riportato un esempio di implementazione in Python del metodo SOR:

import numpy as np

def successive_over_relaxation(A, b, x0, kmax, tol, omega):
    n = A.shape[0]
    x_old = x0.astype(float).copy()
    x = x_old.copy()

    k = 0
    err = tol + 1

    while err > tol:

        if k >= kmax:
            raise RuntimeError("Numero massimo di iterazioni raggiunto.")

        for i in range(n):

            if A[i, i] == 0:
                raise ValueError(f"Elemento diagonale nullo nella riga {i}")

            s = b[i]

            for j in range(i):
                s -= A[i, j] * x[j]

            for j in range(i + 1, n):
                s -= A[i, j] * x_old[j]

            x[i] = omega * (s / A[i, i]) + (1 - omega) * x_old[i]

        err = np.linalg.norm(x - x_old, ord=np.inf)
        x_old = x.copy()
        k += 1

    return x, k

Voci correlate

Collegamenti esterni

Pagina Web di David M. Young, su cs.utexas.edu. URL consultato il 4 maggio 2019 (archiviato dall'url originale il 1º dicembre 2008).* (1950)
D. R. Kincaid Celebrating Fifty Years of David M. Young's Successive Overrelaxation Method