Iterativní metody pro řešení Ax = b-Jacobiho metoda

snad nejjednodušší iterativní metoda pro řešení Ax = b je Jacobiho metoda. Všimněte si, že jednoduchost této metody je jak dobré a špatné: dobrý, protože je poměrně snadné pochopit, a proto je dobré první chuť iterační metody; špatný, protože to není obvykle používá v praxi (i když jeho potenciální užitečnost byla přehodnocena s příchodem paralelních výpočtů). Přesto je to dobrý výchozí bod pro učení o užitečnějších, ale komplikovanějších iteračních metodách.

Vzhledem k aktuální aproximaci

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

pro x, strategie Jacobiho Metoda je použít první rovnice a aktuální hodnoty x2(k), x3(k), …, xn(k) nalézt novou hodnotu x1(k+1), a stejně tak najít novou hodnotu xi(k) pomocí i-té rovnice a staré hodnoty druhé proměnné. To je, vzhledem k tomu, aktuální hodnoty x(k) = (x1(k), x2(k), …, xn(k)), najít nové hodnoty tím, že řešení pro

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

v

Tento systém může také být psán jak

Aby bylo jasno, index i znamená, že xi(k) je i-tý prvek vektoru

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

horní index k odpovídá konkrétní iteraci (ne kth sílu xi ).

Pokud budeme psát D, L, a U na diagonále, přísné dolní trojúhelníkové a přísné horní trojúhelníkové a části, resp.,

pak Jacobiho Metoda může být napsán v matrix-vector notace jako

Příklad 1

Pojďme použít Jacobiho Metodu do systému

.

v každém kroku, vzhledem k aktuálním hodnotám x1(k), x2(k), x3(k), řešíme pro x1(k+1), x2(k+1) a x3 (k+1) v

.

Takže, pokud náš počáteční odhad x(0) = (x1(0), x2(0), x3(0)) je nulový vektor 0 = (0,0,0) — společný počáteční odhad, pokud budeme mít nějaké další informace, které nás vede k vyberte si nějaký jiný — pak zjistíme, x(1) = (x1(1), x2(1), x3(1) ) o řešení

Takže x(1) = (x1(1), x2(1), x3(1)) = (3/4, 9/6, -6/7) ≈ (0.750, 1.500, -0.857). Tento proces iterujeme, abychom našli posloupnost stále lepších aproximací x (0), x (1), x (2),…. Výsledky zobrazujeme v následující tabulce se všemi hodnotami zaokrouhlenými na 3 desetinná místa.

zajímá nás chyba e při každé iteraci mezi pravým řešením x a aproximací x(K): e(K) = x − x(k) . Samozřejmě, nemáme obvykle znát skutečné řešení x. Nicméně, aby lépe pochopit chování iterační metody, je poučné použít metodu k řešení soustavy Ax = b, pro které víme, že skutečné řešení a analyzovat, jak rychle aproximace konvergují k pravé řešení. Pro tento příklad je skutečné řešení x = (1, 2, -1).

norma vektoru|| x / / nám říká, jak velký je vektor jako celek (na rozdíl od toho, jak velký je každý prvek vektoru). Vektor normou nejvíce běžně používané v lineární algebře je l2 normou:

například, pokud x = (1, 2, -1), pak

V tomto modulu se budeme vždy používat l2 normy (včetně pro maticové normy v následné konzultace), takže || || vždy znamená|| ||2.

Pro naše účely, můžeme pozorovat, že ||x|| bude malý přesně, kdy každý z prvků x1, x2, …, xn x = (x1, x2, …, xn ) je malý. V následující tabulce normou chyba se stává postupně menší jako chyba v každém ze tří prvků x1, x2, x3 se stává menší, nebo jinými slovy, jako aproximace se postupně lepší.