Iteratiiviset menetelmät ratkaista Ax = b-Jacobin menetelmä

ehkä yksinkertaisin iteratiivinen menetelmä ratkaista Ax = b on Jacobin menetelmä. Huomaa, että tämän menetelmän yksinkertaisuus on sekä hyvä että huono: hyvä, koska se on suhteellisen helppo ymmärtää ja siten hyvä esimakua iteratiivisista menetelmistä; huono, koska sitä ei tyypillisesti käytetä käytännössä (vaikka sen mahdollinen hyödyllisyys on harkittu uudelleen rinnakkaislaskennan myötä). Silti se on hyvä lähtökohta oppia hyödyllisempiä, mutta monimutkaisempia, iteratiivisia menetelmiä.

kun otetaan huomioon nykyinen likiarvo

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

X: lle, Jacobin menetelmän strategiana on käyttää ensimmäistä yhtälöä ja nykyisiä arvoja x2(k), x3(k), …, xn(k) uuden arvon x1(k+1) löytämiseksi, ja vastaavasti etsi uusi arvo xi(k) käyttäen i th yhtälö ja vanhat arvot muiden muuttujien. Toisin sanoen, kun otetaan huomioon nykyiset arvot x(k) = (x1(k), x2(k), …, xn (k)), etsitään uusia arvoja ratkaisemalla arvoille

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

in

tämä järjestelmä voidaan kirjoittaa myös

selvyyden vuoksi alaindeksi i tarkoittaa, että xi(k) on vektorin

x(k) = (x1(k), x2(k),…, xi(k),…, xn(k)) i: s alkio,

ja yläindeksi k vastaa tiettyä iteraatiota (ei xi: n k: n potenssia ).

jos kirjoitetaan diagonaalille D, L ja U, tiukalle ala-kolmiolle ja tiukalle yläkolmiolle sekä A: n osille vastaavasti,

silloin Jacobin menetelmä voidaan kirjoittaa matriisivektorimerkinnällä seuraavasti

Esimerkki 1

sovelletaanpa Jacobin menetelmää järjestelmään

.

jokaisessa vaiheessa, kun otetaan huomioon nykyiset arvot x1(k), x2(k), x3(k), ratkaisemme X1(k+1), x2(k+1) ja x3(k+1)

.

joten, jos alkuperäinen arvauksemme x(0) = (x1(0), x2(0), x3(0)) on nollavektori 0 = (0,0,0) — yleinen alustava arvaus, ellei meillä ole jotain lisätietoa, joka saa meidät valitsemaan jonkun muun — löydämme x(1) = (x1(1), x2(1), x3(1) ) ratkaisemalla

eli x (1) = (x1 (1), x2 (1), x3(1)) = (3/4, 9/6, -6/7) ≈ (0.750, 1.500, -0.857). Me iterate tämän prosessin löytää jono yhä parempi likiarvot x (0), x(1), x(2), … . Näytämme tulokset alla olevassa taulukossa, jossa kaikki arvot pyöristetään 3 desimaalin tarkkuudella.

meitä kiinnostaa virhe e jokaisessa iteraatiossa oikean ratkaisun x ja approksimaation x(k) välillä: e(k) = x − x(k) . On selvää, että emme yleensä tiedä todellista ratkaisua x. iteratiivisen menetelmän käyttäytymisen ymmärtämiseksi on kuitenkin valaisevaa käyttää menetelmää ratkaisemaan järjestelmä Ax = b, jolle tiedämme todellisen ratkaisun ja analysoida, kuinka nopeasti likiarvot lähentyvät todelliseen ratkaisuun. Tässä esimerkissä todellinen ratkaisu on x = (1, 2, -1).

vektorin ||x|| normi kertoo, kuinka suuri vektori on kokonaisuutena (erotuksena siitä, kuinka suuri vektorin kukin alkio on). Lineaarialgebrassa yleisimmin käytetty vektorinormi on l2-normi:

esimerkiksi jos x = (1, 2, -1), niin

tässä moduulissa käytämme aina L2-normia (mukaan lukien matriisinormit myöhemmissä tutoriaaleissa), joten | | / merkitsee aina|| ||2.

toteamme, että ||x|| on pieni juuri silloin, kun jokainen alkuaine x1, x2,…, xn in x = (x1, x2,…, xn ) on pieni. Seuraavassa taulukossa virheen normi pienenee asteittain, kun jokaisen kolmen elementin x1, x2, x3 virhe pienenee, eli toisin sanoen approksimaatioiden muuttuessa asteittain paremmiksi.