Pivotelement

Den här artikeln handlar om pivoter i matriser. För pivoten i quicksort-algoritmen, se Quicksort .

Pivot- eller pivotelementet är elementet i en matris , eller en array , som väljs först av en algoritm (t.ex. Gauss eliminering , simplexalgoritm , etc.), för att göra vissa beräkningar. I fallet med matrisalgoritmer krävs vanligtvis att en pivotpost är åtminstone skild från noll och ofta på avstånd från den; i det här fallet kallas det att hitta detta element pivoting . Pivotering kan följas av ett utbyte av rader eller kolumner för att föra pivoten till en fast position och tillåta algoritmen att fortsätta framgångsrikt, och möjligen för att minska avrundningsfel. Det används ofta för att verifiera rad echelon form .

Pivotering kan ses som att byta eller sortera rader eller kolumner i en matris, och därför kan den representeras som multiplikation med permutationsmatriser . Algoritmer flyttar dock sällan matriselementen eftersom detta skulle kosta för mycket tid; istället håller de bara reda på permutationerna.

Sammantaget lägger pivotering till fler operationer till beräkningskostnaden för en algoritm. Dessa ytterligare operationer är ibland nödvändiga för att algoritmen överhuvudtaget ska fungera. Andra gånger är dessa ytterligare operationer värda besväret eftersom de ger numerisk stabilitet till det slutliga resultatet.

Exempel på system som kräver svängning

I fallet med Gaussisk eliminering kräver algoritmen att pivotelementen inte är noll. Utbyte av rader eller kolumner i fallet med ett nollpivotelement är nödvändigt. Systemet nedan kräver utbyte av rad 2 och 3 för att utföra eliminering.

Systemet som resulterar från pivotering är som följer och kommer att tillåta elimineringsalgoritmen och bakåtsubstitution för att mata ut lösningen till systemet.

Vidare är det i Gaussisk eliminering i allmänhet önskvärt att välja ett pivotelement med stort absolutvärde . Detta förbättrar den numeriska stabiliteten . Följande system påverkas dramatiskt av avrundningsfel när Gaussisk eliminering och bakåtbyte utförs.

Detta system har den exakta lösningen av x 1 = 10,00 och x 2 = 1,000, men när elimineringsalgoritmen och bakåtsubstitutionen utförs med fyrsiffrig aritmetik, orsakar det lilla värdet av en 11 :a att små avrundningsfel sprids. Algoritmen utan vridning ger approximationen av x 1 ≈ 9873,3 och x 2 ≈ 4. I det här fallet är det önskvärt att vi byter ut de två raderna så att en 21:a är i pivotläget

Med tanke på detta system ger elimineringsalgoritmen och bakåtsubstitution med fyrsiffrig aritmetik de korrekta värdena x 1 = 10,00 och x 2 = 1,000.

Partiell, torn och fullständig svängning

Vid partiell pivotering väljer algoritmen posten med största absoluta värde från kolumnen i matrisen som för närvarande betraktas som pivotelement. Närmare bestämt, när man reducerar en matris till rad echelonform, byter partiell pivotering rader före kolumnens radreduktion för att få pivotelementet att ha det största absoluta värdet jämfört med elementen nedan i samma kolumn. Partiell svängning är i allmänhet tillräcklig för att adekvat reducera avrundningsfel.

För vissa system och algoritmer kan dock fullständig pivotering (eller maximal pivotering) krävas för acceptabel noggrannhet. Komplett pivotering byter ut både rader och kolumner för att använda det största (med absolut värde) elementet i matrisen som pivot. Fullständig vridning är vanligtvis inte nödvändig för att säkerställa numerisk stabilitet och, på grund av den extra kostnaden för att söka efter det maximala elementet, uppvägs förbättringen av numerisk stabilitet som det ger vanligtvis av dess minskade effektivitet för alla utom de minsta matriserna. Därför används den sällan.

En annan strategi, känd som tornpivotering, byter också ut både rader och kolumner men garanterar bara att den valda pivoten samtidigt är den största möjliga posten i sin rad och den största möjliga posten i sin kolumn, i motsats till den största möjliga i hela den återstående submatrisen. När den implementeras på seriella datorer har denna strategi förväntat sig en kostnad på bara cirka tre gånger så stor som för partiell svängning och är därför billigare än fullständig svängning. Roksvängning har visat sig vara mer stabil än partiell svängning både teoretiskt och i praktiken.

Skalad svängning

En variant av strategin för partiell pivotering är skalad pivotering. I detta tillvägagångssätt väljer algoritmen som pivotelement den post som är störst i förhållande till posterna i dess rad. Denna strategi är önskvärd när posternas stora skillnader i storlek leder till spridning av avrundningsfel. Skalad svängning bör användas i ett system som det nedan där en rads poster varierar mycket i storlek. I exemplet nedan skulle det vara önskvärt att byta ut de två raderna eftersom det aktuella vridelementet 30 är större än 5,291 men det är relativt litet jämfört med de andra ingångarna i dess rad. Utan radbyte i detta fall kommer avrundningsfel att spridas som i föregående exempel.

Pivotläge

En pivotposition i en matris, A, är en position i matrisen som motsvarar en rad-ledande 1 i den reducerade radechelonformen av A. Eftersom den reducerade radechelonformen av A är unik, är pivotpositionerna unikt bestämda och beror inte på om radbyten utförs i reduktionsprocessen. Dessutom måste pivoten för en rad visas till höger om pivoten i ovanstående rad i rad echelon form .

Den här artikeln innehåller material från Pivoting on PlanetMath , som är licensierad under Creative Commons Attribution/Share-Alike-licensen .

  1. ^ Edelman, Alan, 1992. Den fullständiga vridbara gissningen för Gaussisk eliminering är falsk. Mathematica Journal 2, nr. 2: 58-61.
  2. ^ Poole, George; Neale, Larry (november 2000). "The Rook's Pivoting Strategy" . Journal of Computational and Applied Mathematics . 123 (1–2): 353–369. doi : 10.1016/S0377-0427(00)00406-4 . Hämtad 2 mars 2022 .
Hämtad från " https://en.wikipedia.org/w/index.php?title=Pivot_element&oldid=1136188994 "