Jacobin menetelmä
Jacobin menetelmä , koska saksalainen matemaatikko Karl Jacobin , on iteratiivinen menetelmä ratkaista järjestelmän matriisi , joka on muotoa Ax = b . Tätä varten käytämme sekvenssiä x ( k ), joka konvergoituu kiinteään pisteeseen x , lineaaristen yhtälöiden järjestelmän ratkaisuun .
Rakentamisen periaate
Yritämme konstrukti, sillä x (0) annetaan, sekvenssin x ( k + 1) = F ( x ( k ) ) kanssa .
k∈EI{\ displaystyle k \ sisään \ mathbb {N}}
A = M - N missä M on käännettävä matriisi .
ATx=b⇔Mx=EIx+b⇔x=M-1EIx+M-1b=F(x){\ displaystyle {\ begin {matrix} Kirves = b \ Vasemmanpuoleinen nuoli Mx = Nx + b \ Vasen oikeanpuoleinen nuoli & x & = & M ^ {- 1} Nx + M ^ {- 1} b \\ && = & F ( x) \ end {matriisi}}}missä F on affiinifunktio . Matriisia B = M –1 N kutsutaan sitten Jacobi-matriisiksi .
Seuraava algoritmi on kuitenkin pätevä vain, jos matriisi A on tiukasti diagonaalisesti dominoiva linjoilla (jos matriisi M on diagonaalinen, muuten viitataan leikkausten lähentymiseen).
Algoritmi
{x(0)tiedossax(k+1)=Bx(k)+M-1b{\ displaystyle \ left \ {{\ begin {array} {l} x ^ {(0)} \; {\ mbox {tunnettu}} \\ x ^ {(k + 1)} = Bx ^ {(k) } + M ^ {- 1} b \ end {taulukko}} \ oikea.}
Virhe ja lähentyminen
Jos x on ratkaisu Ax = b: stä, se tarkistaa
x=Bx+M-1b{\ displaystyle x = Bx + M ^ {- 1} b} .
Olkoon virhevektori
e ( k )
e(k+1)=x(k+2)-x(k+1)=B(x(k+1)-x(k))=Be(k){\ displaystyle e ^ {(k + 1)} = x ^ {(k + 2)} - x ^ {(k + 1)} = B (x ^ {(k + 1)} - x ^ {(k )}) = Ole ^ {(k)}}Joka antaa
e(k+1)=Be(k)=Bk+1e(0){\ displaystyle e ^ {(k + 1)} = Be ^ {(k)} = B ^ {k + 1} e ^ {(0)}}.
Algoritmi yhtyy, jos (ts. B k pyrkii nolla-matriisiin).
limk→∞‖e(k)‖=0⟺limk→∞‖Bk‖=0{\ displaystyle \ lim _ {k \ to \ infty} \ | e ^ {(k)} \ | = 0 \ Longleftrightarrow \ lim _ {k \ to \ infty} \ | B ^ {k} \ | = 0}
Lause - Välttämätön ja riittävä ehto sille, että on se, että spektrin säde (suurin ominaisarvo moduulia) ja B on ehdottomasti pienempi kuin 1.
limk→∞‖Bk‖=0{\ displaystyle \ lim _ {k \ to \ infty} \ | B ^ {k} \ | = 0}
Lause - Menetelmä lähentyy x: stä ( 0 ) riippumatta lineaarisissa järjestelmissä, joiden matriisi on tiukasti diagonaalisesti hallitseva .
Jacobin menetelmä
Me murtaa matriisin seuraavasti: = D - E - F , jossa D lävistäjän matriisi , - E alempi kolmiomainen matriisi nolla lävistäjä ja - F yläkolmiomatriisi nolla lävistäjä. In Jacobin menetelmä, me valitsemme M = D ja N = E + F (on Gauss-Seidel menetelmä , M = D - E ja N = F ).
x(k+1)=D.-1(E+F)x(k)+D.-1b{\ displaystyle x ^ {(k + 1)} = D ^ {- 1} (E + F) x ^ {(k)} + D ^ {- 1} b}
xi(k+1)=⋯xi(k)+bikloii{\ displaystyle x_ {i} ^ {(k + 1)} = \ cdots x_ {i} ^ {(k)} + {\ frac {b_ {i}} {a_ {ii}}}} kanssa
linjan i ja D -1 ( E + F ) :-(kloi,1kloi,i,⋯,kloi,i-1kloi,i,0,kloi,i+1kloi,i,⋯,kloi,eikloi,i){\ displaystyle - \ left ({\ frac {a_ {i, 1}} {a_ {i, i}}}, \ cdots, {\ frac {a_ {i, i-1}} {a_ {i, i }}}, 0, {\ frac {a_ {i, i + 1}} {a_ {i, i}}}, \ cdots, {\ frac {a_ {i, n}} {a_ {i, i} }} \ oikea)}
xi(k+1)=-1kloii∑j=1j≠ieikloijxj(k)+bikloii{\ displaystyle x_ {i} ^ {(k + 1)} = - {\ frac {1} {a_ {ii}}} \ summa _ {j = 1 \ huipulla j \ neq i} ^ {n} a_ { ij} x_ {j} ^ {(k)} + {\ frac {b_ {i}} {a_ {ii}}}}
Jäännösvektori
Olkoon jäännösvektori. Voimme kirjoittaa jossa Rr(k)=D.e(k){\ displaystyle r ^ {(k)} = Lähettäjä ^ {(k)}}xi(k+1)=ri(k)kloi,i+xi(k){\ displaystyle x_ {i} ^ {(k + 1)} = {\ frac {r_ {i} ^ {(k)}} {a_ {i, i}}} + x_ {i} ^ {(k) }}( K )
i joka lasketaan seuraavasti:
rl(k+1)=-∑j=1j≠leiklol,jrl(k)kloj,j{\ displaystyle r_ {l} ^ {(k + 1)} = - \ summa _ {j = 1 \ huipulla j \ neq l} ^ {n} a_ {l, j} {\ frac {r_ {l} ^ {(k)}} {a_ {j, j}}}}.
Lopeta testi
Pysäytystestissä käytetään vektorijäännöksen suhteellista virhettä, joka antaa tietylle tarkkuudelle ε :
‖r(k)‖‖b‖<e{\ displaystyle {\ frac {\ | r ^ {(k)} \ |} {\ | b \ |}} <\ varepsilon}
Kustannus
Tämän menetelmän kustannukset ovat luokkaa 3 n 2 + 2 n per iteraatio. Se lähentyy vähemmän kuin Gauss-Seidelin menetelmä , mutta on hyvin helposti rinnastettavissa .
Katso myös
Aiheeseen liittyvät artikkelit
Ulkoiset linkit
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">