Iteratieve methoden voor het oplossen van Ax = b – Jacobi ‘ s methode

misschien is de eenvoudigste iteratieve methode voor het oplossen van Ax = b de methode van Jacobi. Merk op dat de eenvoud van deze methode zowel goed als slecht is: goed, omdat het relatief gemakkelijk te begrijpen is en dus een goede eerste smaak van iteratieve methoden is; slecht, omdat het niet typisch in de praktijk wordt gebruikt (hoewel het potentiële nut ervan is heroverwogen met de komst van parallel computing). Toch is het een goed uitgangspunt voor het leren over nuttigere, maar ingewikkelder, iteratieve methoden.

bij een huidige benadering

x(k) = (x1(k), x2(k), x3(k), …, xn(k))

voor x is de strategie van Jacobi ‘ s methode om de eerste vergelijking en de huidige waarden van x2(k), x3(k),…, xn(k) te gebruiken om een nieuwe waarde x1(k+1) te vinden, en evenzo om een nieuwe waarde xi(k) te vinden met behulp van de i e vergelijking en de oude waarden van de andere variabelen. Dat is, gezien de huidige waarden van x(k) = (x1(k), x2(k), …, xn(k)), het vinden van nieuwe waarden door het oplossen van voor

x(k+1) = (x1(k+1), x2(k+1), …, xn(k)+1))

in

Dit systeem kan ook worden geschreven als

om duidelijk Te zijn, het subscript i betekent dat xi(k) is de i-de element van de vector

x(k) = (x1(k), x2(k), …, xi(k), …, xn(k) ),

superscript k komt overeen met het bepaalde iteratie (niet de kth kracht van xi ).

als we D, L en U schrijven voor de diagonaal, strikt onderste driehoekig en strikt bovenste driehoekig en delen van A, respectievelijk,

dan kan Jacobi ‘ s methode worden geschreven in matrix-Vector notatie als

Voorbeeld 1

laten we de methode van Jacobi toepassen op het systeem

.

bij elke stap, gegeven de huidige waarden x1(k), x2(k), x3(k), lossen we op voor x1(k+1), x2(k+1), en x3(k+1) in

.

dus, als onze initiële gok x(0) = (x1(0), x2(0), x3(0)) de nulvector 0 = (0,0,0) is — een veel voorkomende initiële gok tenzij we wat extra informatie hebben die ons leidt om een andere te kiezen-dan vinden We x(1) = (x1(1), x2(1), x3(1)) door op te lossen

dus x (1) = (x1 (1), x2 (1), x3(1)) = (3/4, 9/6, -6/7) ≈ (0.750, 1.500, -0.857). We herhalen dit proces om een reeks van steeds betere benaderingen x(0), x(1), x(2), … te vinden . We tonen de resultaten in de onderstaande tabel, met alle waarden afgerond op 3 decimalen.

we zijn geïnteresseerd in de fout e bij elke iteratie tussen de ware oplossing x en de benadering x(k): e(k) = x − x(k) . Om het gedrag van een iteratieve methode beter te begrijpen, is het echter verhelderend om de methode te gebruiken om een systeem Ax = b op te lossen waarvoor we wel de ware oplossing kennen en te analyseren hoe snel de benaderingen convergeren naar de ware oplossing. In dit voorbeeld is de ware oplossing x = (1, 2, -1).

de norm van een vector ||x|| vertelt ons hoe groot de vector als geheel is (in tegenstelling tot hoe groot elk element van de vector is). De vectornorm die het meest wordt gebruikt in de lineaire algebra is de L2-norm:

bijvoorbeeld, als x = (1, 2, -1), dan

In deze module zullen we altijd de L2 norm gebruiken (ook voor matrixnormen in latere tutorials), zodat | / / / altijd aangeeft|| ||2.

voor onze doeleinden zien we dat|| x / / klein zal zijn precies wanneer elk van de elementen x1, x2, …, xn in x = (x1, x2, …, xn ) klein is. In de volgende tabel wordt de foutnorm steeds kleiner naarmate de fout in elk van de drie elementen x1, x2, x3 kleiner wordt, of met andere woorden, naarmate de benaderingen steeds beter worden.