Tridiagonal matrisealgoritme - Tridiagonal matrix algorithm

I numerisk lineær algebra er den trekantede matrisealgoritmen , også kjent som Thomas-algoritmen (oppkalt etter Llewellyn Thomas ), en forenklet form for Gaussisk eliminering som kan brukes til å løse trediagonale ligningssystemer . Et trekantet system for n ukjente kan skrives som

${\ displaystyle a_ {i} x_ {i-1} + b_ {i} x_ {i} + c_ {i} x_ {i + 1} = d_ {i},}$

hvor og . ${\ displaystyle a_ {1} = 0}$${\ displaystyle c_ {n} = 0}$

${\ displaystyle {\ begin {bmatrix} b_ {1} & c_ {1} &&& 0 \\ a_ {2} & b_ {2} & c_ {2} && \\ & a_ {3} & b_ {3} & \ ddots & \\ && \ ddots & \ ddots & c_ {n-1} \\ 0 &&& a_ {n} & b_ {n} \ end {bmatrix}} {\ begin {bmatrix} x_ {1} \\ x_ {2} \\ x_ {3} \ \\ vdots \\ x_ {n} \ end {bmatrix}} = {\ begin {bmatrix} d_ {1} \\ d_ {2} \\ d_ {3} \\\ vdots \\ d_ {n} \ end {bmatrix}}.}$

For slike systemer kan løsningen oppnås i operasjoner i stedet for å kreves av Gauss eliminering . En første feie eliminerer 's, og deretter produserer en (forkortet) bakoverbytte løsningen. Eksempler på slike matriser oppstår ofte fra diskretisering av 1D Poisson-ligning og naturlig kubisk splineinterpolasjon . ${\ displaystyle O (n)}$${\ displaystyle O (n ^ {3})}$${\ displaystyle a_ {i}}$

Thomas 'algoritme er ikke stabil generelt, men er det i flere spesielle tilfeller, for eksempel når matrisen er diagonalt dominerende (enten ved rader eller kolonner) eller symmetrisk positiv bestemt ; for en mer presis karakterisering av stabiliteten til Thomas 'algoritme, se Higham Theorem 9.12. Hvis det generelt er behov for stabilitet, anbefales Gaussisk eliminering med delvis svinging (GEPP) i stedet.

Metode

Fremover sveipingen består av beregningen av nye koeffisienter som følger, som angir de nye koeffisientene med primtall:

${\ displaystyle c '_ {i} = {\ begin {cases} {\ cfrac {c_ {i}} {b_ {i}}}, & i = 1, \\ {\ cfrac {c_ {i}} {b_ {i} -a_ {i} c '_ {i-1}}}, & i = 2,3, \ dots, n-1 \ end {cases}}}$

og

${\ displaystyle d '_ {i} = {\ begin {cases} {\ cfrac {d_ {i}} {b_ {i}}}, & i = 1, \\ {\ cfrac {d_ {i} -a_ { i} d '_ {i-1}} {b_ {i} -a_ {i} c' _ {i-1}}}, & i = 2,3, \ dots, n. \ end {cases}}}$

Løsningen oppnås deretter ved ryggsubstitusjon:

${\ displaystyle x_ {n} = d '_ {n},}$

${\ displaystyle x_ {i} = d '_ {i} -c' _ {i} x_ {i + 1}, \ quad i = n-1, n-2, \ ldots, 1.}$

Metoden ovenfor endrer ikke de opprinnelige koeffisientvektorene, men må også holde oversikt over de nye koeffisientene. Hvis koeffisientvektorene kan modifiseres, er en algoritme med mindre bokføring:

For gjør ${\ displaystyle i = 2,3, \ prikker, n,}$

${\ displaystyle w = {\ cfrac {a_ {i}} {b_ {i-1}},}$

${\ displaystyle b_ {i}: = b_ {i} -wc_ {i-1},}$

${\ displaystyle d_ {i}: = d_ {i} -wd_ {i-1},}$

etterfulgt av bakbyttet

${\ displaystyle x_ {n} = {\ cfrac {d_ {n}} {b_ {n}}},}$

${\ displaystyle x_ {i} = {\ cfrac {d_ {i} -c_ {i} x_ {i + 1}} {b_ {i}}} \ quad {\ text {for}} i = n-1, n-2, \ prikker, 1.}$

Implementeringen i en VBA- underrutine uten å bevare koeffisientvektorene:

Sub TriDiagonal_Matrix_Algorithm(N%, A#(), B#(), C#(), D#(), X#())
    Dim i%, W#
    For i = 2 To N
        W = A(i) / B(i - 1)
        B(i) = B(i) - W * C(i - 1)
        D(i) = D(i) - W * D(i - 1)
    Next i
    X(N) = D(N) / B(N)
    For i = N - 1 To 1 Step -1
        X(i) = (D(i) - C(i) * X(i + 1)) / B(i)
    Next i
End Sub

Derivasjon

Avledningen av den trekantede matrisealgoritmen er et spesielt tilfelle av Gauss eliminering .

Anta at de ukjente er , og at ligningene som skal løses, er: ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$

${\ displaystyle {\ begin {alignat} {4} &&& + b_ {1} x_ {1} && + c_ {1} x_ {2} && = d_ {1} \\ & a_ {i} x_ {i-1} && + b_ {i} x_ {i} && + c_ {i} x_ {i + 1} && = d_ {i} \ ,, \ quad i = 2, \ ldots, n-1 \\ & a_ {n} x_ {n-1} && + b_ {n} x_ {n} &&&& = d_ {n} \,. \ end {alignat}}}$

Vurder å endre den andre ( ) ligningen med den første ligningen som følger: ${\ displaystyle i = 2}$

${\ displaystyle ({\ mbox {ligning 2}}) \ cdot b_ {1} - ({\ mbox {ligning 1}}) \ cdot a_ {2}}$

som vil gi:

${\ displaystyle (b_ {2} b_ {1} -c_ {1} a_ {2}) x_ {2} + c_ {2} b_ {1} x_ {3} = d_ {2} b_ {1} -d_ {1} a_ {2}.}$

Merk at er eliminert fra den andre ligningen. Ved å bruke en lignende taktikk med den modifiserte andre ligningen på den tredje ligningen gir: ${\ displaystyle x_ {1}}$

${\ displaystyle (b_ {3} (b_ {2} b_ {1} -c_ {1} a_ {2}) - c_ {2} b_ {1} a_ {3}) x_ {3} + c_ {3} (b_ {2} b_ {1} -c_ {1} a_ {2}) x_ {4} = d_ {3} (b_ {2} b_ {1} -c_ {1} a_ {2}) - (d_ {2} b_ {1} -d_ {1} a_ {2}) a_ {3}. \,}$

Denne tiden ble eliminert. Hvis denne prosedyren gjentas til raden; det (modifiserte) ligning vil innebære bare ett ukjent, . Dette kan løses for og deretter brukes til å løse ligningen, og så videre til alle ukjente er løst for. ${\ displaystyle x_ {2}}$${\ displaystyle n ^ {th}}$${\ displaystyle n ^ {th}}$${\ displaystyle x_ {n}}$${\ displaystyle (n-1) ^ {th}}$

Det er klart at koeffisientene på de modifiserte ligningene blir mer og mer kompliserte hvis de uttrykkelig er angitt. Ved å undersøke prosedyren kan de modifiserte koeffisientene (notert med tildes) i stedet defineres rekursivt:

${\ displaystyle {\ tilde {a}} _ {i} = 0 \,}$

${\ displaystyle {\ tilde {b}} _ {1} = b_ {1} \,}$

${\ displaystyle {\ tilde {b}} _ {i} = b_ {i} {\ tilde {b}} _ {i-1} - {\ tilde {c}} _ {i-1} a_ {i} \,}$

${\ displaystyle {\ tilde {c}} _ {1} = c_ {1} \,}$

${\ displaystyle {\ tilde {c}} _ {i} = c_ {i} {\ tilde {b}} _ {i-1} \,}$

${\ displaystyle {\ tilde {d}} _ {1} = d_ {1} \,}$

${\ displaystyle {\ tilde {d}} _ {i} = d_ {i} {\ tilde {b}} _ {i-1} - {\ tilde {d}} _ {i-1} a_ {i} . \,}$

For å fremskynde løsningsprosessen ytterligere, kan deles ut (hvis det ikke er noen divisjon med null risiko), vil de nyere modifiserte koeffisientene, hver notert med en prime, være: ${\ displaystyle {\ tilde {b}} _ {i}}$

${\ displaystyle a '_ {i} = 0 \,}$

${\ displaystyle b '_ {i} = 1 \,}$

${\ displaystyle c '_ {1} = {\ frac {c_ {1}} {b_ {1}}} \,}$

${\ displaystyle c '_ {i} = {\ frac {c_ {i}} {b_ {i} -c' _ {i-1} a_ {i}}} \,}$

${\ displaystyle d '_ {1} = {\ frac {d_ {1}} {b_ {1}}} \,}$

${\ displaystyle d '_ {i} = {\ frac {d_ {i} -d' _ {i-1} a_ {i}} {b_ {i} -c '_ {i-1} a_ {i} }}. \,}$

Dette gir følgende system med de samme ukjente og koeffisientene definert i forhold til de opprinnelige:

${\ displaystyle {\ begin {array} {lcl} x_ {i} + c '_ {i} x_ {i + 1} = d' _ {i} \ qquad &; & \ i = 1, \ ldots, n -1 \\ x_ {n} = d '_ {n} \ qquad &; & \ i = n. \\\ end {array}} \,}$

Den siste ligningen involverer bare en ukjent. Å løse det igjen reduserer den neste siste ligningen til en ukjent, slik at denne tilbakestående substitusjonen kan brukes til å finne alle de ukjente:

${\ displaystyle x_ {n} = d '_ {n} \,}$

${\ displaystyle x_ {i} = d '_ {i} -c' _ {i} x_ {i + 1} \ qquad; \ i = n-1, n-2, \ ldots, 1.}$

Varianter

I noen situasjoner, spesielt de som involverer periodiske grenseforhold , kan det hende at en lett forstyrret form av det trekantede systemet må løses:

${\ displaystyle {\ begin {alignat} {4} & a_ {1} x_ {n} && + b_ {1} x_ {1} && + c_ {1} x_ {2} && = d_ {1} \\ & a_ { i} x_ {i-1} && + b_ {i} x_ {i} && + c_ {i} x_ {i + 1} && = d_ {i} \ ,, \ quad i = 2, \ ldots, n- 1 \\ & a_ {n} x_ {n-1} && + b_ {n} x_ {n} && + c_ {n} x_ {1} && = d_ {n} \,. \ End {alignat}}}$

I dette tilfellet kan vi bruke Sherman – Morrison-formelen for å unngå ytterligere operasjoner av Gauss eliminering og fortsatt bruke Thomas-algoritmen. Metoden krever å løse en modifisert ikke-syklisk versjon av systemet for både inngangen og en sparsom korrigerende vektor, og deretter kombinere løsningene. Dette kan gjøres effektivt hvis begge løsningene beregnes samtidig, da den fremre delen av den rene trekantede matrisealgoritmen kan deles.

I andre situasjoner kan ligningssystemet være trediagonalt (se blokkmatrise ), med mindre submatriser arrangert som de enkelte elementene i matrisesystemet ovenfor (f.eks. 2D Poisson-problemet ). Forenklet form for Gauss eliminering er utviklet for disse situasjonene.

Læreboka Numerisk matematikk av Quarteroni, Sacco og Saleri, viser en modifisert versjon av algoritmen som unngår noen av inndelingene (i stedet for multiplikasjoner), noe som er gunstig for noen dataarkitekturer.

Parallelle trekantede løsere har blitt publisert for mange vektor- og parallelle arkitekturer, inkludert GPUer

For en omfattende behandling av parallelle tridiagonale og blokk tridiagonale løsere se

Referanser

• Conte, SD; de Boor, C. (1972). Elementær numerisk analyse . McGraw-Hill, New York. ISBN 0070124469.
• Denne artikkelen inneholder tekst fra artikkelen Tridiagonal_matrix_algorithm _-_ TDMA_ (Thomas_algorithm) på CFD-Wiki som er under GFDL- lisensen.

• Trykk, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Avsnitt 2.4" . Numeriske oppskrifter: The Art of Scientific Computing (3. utgave). New York: Cambridge University Press. ISBN 978-0-521-88068-8.