Bareiss algoritme - Bareiss algorithm

I matematikk er Bareiss-algoritmen , oppkalt etter Erwin Bareiss , en algoritme for å beregne determinanten eller echelonformen til en matrise med heltalloppføringer som bare bruker heltallsregning; eventuelle divisjoner som utføres er garantert nøyaktige (det er ingen resten ). Metoden kan også brukes til å beregne determinanten til matriser med (tilnærmet) reelle oppføringer, og unngå introduksjonen av eventuelle avrundingsfeil utover de som allerede er tilstede i inngangen.

Historie

Den generelle Bareiss-algoritmen er forskjellig fra Bareiss-algoritmen for Toeplitz-matriser .

I noen spansktalende land er denne algoritmen også kjent som Bareiss-Montante , på grunn av René Mario Montante Pardo , professor ved Universidad Autónoma de Nuevo León , Mexico , som populariserte metoden blant studentene sine.

Oversikt

Determinant definisjon har bare multiplikasjon, addisjon og subtraksjon. Tydeligvis er determinanten heltall hvis alle matriseoppføringene er heltall. Imidlertid er faktisk beregning av determinanten ved hjelp av definisjonen eller Leibniz-formelen upraktisk, da den krever O ( n! ) -Operasjoner.

Gaussisk eliminering har O ( n 3 ) kompleksitet, men introduserer deling, noe som resulterer i en avrundingsfeil når den implementeres ved hjelp av flytende punktum.

Avrundingsfeil kan unngås hvis alle tallene holdes som heltalsfraksjoner i stedet for flytende punkt. Men så vokser størrelsen på hvert element i størrelse eksponentielt med antall rader.

Bareiss tar opp et spørsmål om å utføre en heltal-bevarende eliminering mens man holder størrelsen på de mellomliggende koeffisientene rimelig liten. To algoritmer er foreslått:

  1. Divisjonsfri algoritme - utfører matriksreduksjon til trekantet form uten delingsoperasjon.
  2. Fraksjonsfri algoritme - bruker divisjon for å holde mellomoppføringene mindre, men på grunn av Sylvester's Identity er transformasjonen fremdeles heltalsbevarende (divisjonen har null rest).

For fullstendighet foreslår Bareiss også brøkproduserende multiplikasjonsfrie eliminasjonsmetoder.

Algoritmen

Programstrukturen til denne algoritmen er en enkel trippel-loop, som i standard Gaussisk eliminering. Men i dette tilfellet matrisen er modifisert slik at hver M k, k inneholder inngangs den ledende hoved moll [M] k, k . Algoritmens korrekthet vises lett ved induksjon på k .

  • Inngang: M - en n-kvadratmatrise som
    antar at de ledende hovedmindreårige [M] k, k ikke er null.
  • La M 0,0 = 1 (Merk: M 0,0 er en spesiell variabel)
  • For k fra 1 til n-1 :
    • For i fra k + 1 til n :
      • For j fra k + 1 til n :
        • Sett
  • Utgang: Matrisen er modifisert på plass ,
    hver M k, k- oppføring inneholder hovedmoll [M] k, k ,
    oppføring M n, n inneholder determinanten til den opprinnelige M.

Hvis antagelsen om hovedmindreårige viser seg å være falsk, f.eks. Hvis M k − 1, k − 1 = 0 og noe M i, k − 1 ≠ 0 (i = k, ..., n) så kan vi bytte ut k-1 rad med i- rad og endre tegnet på det endelige svaret.

Analyse

Under utførelsen av Bareiss-algoritmen er hvert heltall som beregnes determinanten til en submatrise i inngangsmatrisen. Dette gjør det mulig å bruke Hadamard-ulikheten til å binde størrelsen på disse heltallene. Ellers kan Bareiss-algoritmen bli sett på som en variant av Gauss eliminering og trenger omtrent samme antall aritmetiske operasjoner.

Det følger at for en n × n matrise med maksimal (absolutt) verdi 2 L for hver oppføring, kjører Bareiss-algoritmen i O ( n 3 ) elementære operasjoner med en O ( n n / 2  2 nL ) bundet til den absolutte verdien av nødvendige mellomverdier. Dens beregningskompleksitet er således O ( n 5 L 2  (log ( n ) 2  +  L 2 )) når du bruker elementær aritmetikk eller O ( n 4 L  (log ( n ) +  L ) log (log ( n ) +  L )) ) ved å bruke rask multiplikasjon .

Referanser