Methode van Jacobi

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de numerieke wiskunde is de methode van Jacobi (genoemd naar de Duitse wiskundige Carl Jacobi) een algoritme om een geschatte oplossing voor stelsels van lineaire vergelijkingen van de vorm

 Ax = b \,

te vinden. De methode van Jacobi is net als "Gauss-Seidel methode" en de "SOR-methode" een speciale vorm van splitsingsmethode. De methode werd ontwikkeld, omdat de Gauss-eliminatie weliswaar een exacte oplossing geeft, maar wel erg gevoelig is voor rekenfouten. Een iteratieve benadering heeft hier minder last van.

Beschrijving van de methode[bewerken]

Gegeven een stelsel van lineaire vergelijkingen met n vergelijkingen in n onbekenden


\begin{matrix}
a_{1,1}\cdot x_1+\dots+a_{1,n}\cdot x_n&=&b_1\\
a_{2,1}\cdot x_1+\dots+a_{2,n}\cdot x_n&=&b_2\\
&\vdots&\\
a_{n,1}\cdot x_1+\dots+a_{n,n}\cdot x_n&=&b_n\\
\end{matrix}

Om dit stelsel op te lossen, moet de i-de vergelijking naar de i-de variabele x_i worden opgelost,

x_i^{(m+1)}:=\frac1{a_{i,i}}\left(b_i-\sum_{j\not=i} a_{i,j}\cdot x_j^{(m)}\right),

en deze vervanging wordt, uitgaande van een willekeurige startwaarde x^{(0)} van de variabelen, periodiek herhaald. Als minimale voorwaarde laat zich hier voorschrijven dat de diagonaalelementen ai,i van nul moeten verschillen. Voor de convergentie van de methode van Jacobi is strikte diagonale dominantie van de systeemmatrix voldoende.

Een schets van het algoritme in c iteraties en met n rijen respectievelijk kolommen ziet er in pseudocode als volgt uit:

voor m=1 tot c 
  voor i=1 tot n
    x_i=0
       voor j=1 tot n
         als j != i
            x_i=x_i+a_{i,j}x_j^{(m-1)};
       einde
       x_i=(b_i-x_i)/a_{i,i};
  einde
  x^{(m)}=x;
einde

Daarbij fungeren de willekeurige eerstbezettingen van de variabelenvectoren als inputparameters van het algoritme, de benaderinsgoplossing bestaat uit de grootte van de door de methode van Jacobi geretourneerde vector.

Beschrijving in matrixnotatie[bewerken]

De matrix A \, van het stelsel van lineaire vergelijkingen  A \cdot x = b wordt ter voorbereiding in een diagonaalmatrix D, een strikte benedendriehoeksmatrix  L en een strikte bovendriehoeksmatrix U opgedeeld, zodat geldt:

 A = L+D+U \,.

Het bovenstaande in delen opgedeelde iteratievoorschrift laat zich als volgt voor de complete vector beschrijven:

x^{(m+1)} = D^{-1} \left( b - \left(L + U\right) x^{(m)} \right).

Referenties[bewerken]

Externe links[bewerken]