Drejningselement - Pivot element

Den pivot eller drejeelement er elementet i en matrix , eller en opstilling , som er valgt af såvel en algoritme (f.eks Gauss-eliminering , simplex algoritme , etc.), til at gøre visse beregninger. I tilfælde af matrixalgoritmer kræves en drejepost normalt at være mindst forskellig fra nul og ofte fjernt fra den; i dette tilfælde kaldes drejning at finde dette element . Drejning kan efterfølges af en udveksling af rækker eller kolonner for at bringe drejningen til en fast position og tillade algoritmen at fortsætte med succes og muligvis reducere afrundingsfejl. Det bruges ofte til at verificere række echelon form .

Drejning kan betragtes som at bytte eller sortere rækker eller kolonner i en matrix, og det kan således repræsenteres som multiplikation med permutationsmatricer . Imidlertid flytter algoritmer sjældent matrixelementerne, fordi dette vil koste for meget tid; i stedet holder de bare styr på permutationerne.

Samlet set tilføjer drejning flere operationer til beregningsomkostningerne for en algoritme. Disse ekstra operationer er undertiden nødvendige for, at algoritmen overhovedet fungerer. Andre gange er disse ekstra operationer umagen værd, fordi de tilføjer numerisk stabilitet til det endelige resultat.

Eksempler på systemer, der kræver drejning

I tilfælde af Gauss-eliminering kræver algoritmen, at drejelige elementer ikke er nul. Det er nødvendigt at udveksle rækker eller kolonner i tilfælde af et nul-omdrejningselement. Systemet nedenfor kræver udveksling af række 2 og 3 for at udføre eliminering.

${\ displaystyle \ left [{\ begin {array} {ccc | c} 1 & -1 & 2 & 8 \\ 0 & 0 & -1 & -11 \\ 0 & 2 & -1 & -3 \ end {array}} \ right]}$

Systemet, der skyldes drejning, er som følger og tillader eliminationsalgoritmen og bagudskiftning at sende løsningen til systemet.

${\ displaystyle \ left [{\ begin {array} {ccc | c} 1 & -1 & 2 & 8 \\ 0 & 2 & -1 & -3 \\ 0 & 0 & -1 & -11 \ end {array}} \ right]}$

Desuden er det i Gaussisk eliminering generelt ønskeligt at vælge et drejelement med stor absolut værdi . Dette forbedrer den numeriske stabilitet . Det følgende system er dramatisk påvirket af afrundingsfejl, når Gaussisk eliminering og bagudskiftning udføres.

${\ displaystyle \ left [{\ begin {array} {cc | c} 0.00300 & 59.14 & 59.17 \\ 5.291 & -6.130 & 46.78 \\\ end {array}} \ right]}$

Dette system har den nøjagtige løsning på x ₁ = 10,00 og x ₂ = 1.000, men når eliminationsalgoritmen og bagudskiftning udføres ved hjælp af firecifret aritmetik, forårsager den lille værdi af en ₁₁ små afrundingsfejl, der udbredes. Algoritmen uden drejning giver en tilnærmelse af x ₁ ≈ 9873,3 og x ₂ ≈ 4. I dette tilfælde er det ønskeligt, at vi udveksler de to rækker, så en ₂₁ er i drejeposition

${\ displaystyle \ left [{\ begin {array} {cc | c} 5.291 & -6.130 & 46.78 \\ 0.00300 & 59.14 & 59.17 \\\ end {array}} \ right].}$

I betragtning af dette system giver eliminationsalgoritmen og bagudskiftning ved hjælp af firecifret aritmetik de korrekte værdier x ₁ = 10,00 og x ₂ = 1.000.

Delvis og fuldstændig drejning

Ved delvis drejning vælger algoritmen posten med den største absolutte værdi fra kolonnen i matrixen, der i øjeblikket betragtes som omdrejningselementet. Delvis drejning er generelt tilstrækkelig til tilstrækkeligt at reducere afrundingsfejl. For visse systemer og algoritmer kan det imidlertid være nødvendigt med fuldstændig drejning (eller maksimal drejning) for acceptabel nøjagtighed. Komplet drejningsudveksling skifter både rækker og kolonner for at bruge det største element (af absolut værdi) i matricen som omdrejningspunkt. Komplet drejning er normalt ikke nødvendigt for at sikre numerisk stabilitet, og på grund af de ekstra omkostninger ved søgning efter det maksimale element opvejes forbedringen i numerisk stabilitet, som det giver, typisk af dets reducerede effektivitet for alle undtagen de mindste matricer. Derfor bruges det sjældent.

Skaleret drejning

En variation af den delvise drejningsstrategi er skaleret drejning. I denne tilgang vælger algoritmen den post, der er størst i forhold til posterne i rækken, som pivotelementet. Denne strategi er ønskelig, når poster store forskelle i størrelse fører til udbredelse af afrundingsfejl. Skaleret drejning skal bruges i et system som det nedenfor, hvor en række poster varierer meget i størrelsesorden. I eksemplet nedenfor ville det være ønskeligt at udveksle de to rækker, fordi det aktuelle drejelement 30 er større end 5.291, men det er relativt lille sammenlignet med de andre poster i sin række. Uden rækkeudveksling i dette tilfælde udbredes afrundingsfejl som i det foregående eksempel.

${\ displaystyle \ left [{\ begin {array} {cc | c} 30 & 591400 & 591700 \\ 5.291 & -6.130 & 46.78 \\\ end {array}} \ højre]}$

Drejeposition

En drejeposition i en matrix, A, er en position i matricen, der svarer til en række, der fører 1 i den reducerede række echelonform af A. Da den reducerede række echelonform af A er unik, er drejepositionerne entydigt bestemt og afhænger ikke af, om rækkeudvekslinger udføres i reduktionsprocessen eller ej. Drejningen af ​​en række skal også vises til højre for drejningen i ovenstående række i række echelonform .

Referencer

Denne artikel indeholder materiale fra Pivoting on PlanetMath , som er licenseret under Creative Commons Attribution / Share-Alike License .

• RL Burden, JD Faires, Numerical Analysis , 8. udgave, Thomson Brooks / Cole, 2005. ISBN   0-534-39200-8
• GH Golub, CF Loan, Matrix Computations , 3. udgave, Johns Hopkins, 1996. ISBN   0-8018-5414-8 .
• Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (red.). "Kryds-tværs-metoder: En ny opfattelse af pivotalgoritmer". Matematisk programmering, Serie B . Papirer fra det 16. internationale symposium om matematisk programmering afholdt i Lausanne, 1997. 79 (1–3): 369–395. CiteSeerX   10.1.1.36.9373 . doi : 10.1007 / BF02614325 . MR   1464775 . Eftertryk efterskrift .
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivotregler for lineær programmering: En undersøgelse af nyere teoretisk udvikling". Annaler for operationsforskning . Degenerering i optimeringsproblemer. 46–47 (1): 203–233. CiteSeerX   10.1.1.36.7658 . doi : 10.1007 / BF02096264 . ISSN   0254-5330 . MR   1260019 .