Vi presenterar utformningen och testningen av en algoritm för iterativ förfining av lösningen av linjära ekvationer där restvärdet beräknas med extra precision. Denna algoritm föreslogs ursprungligen 1948 och analyserades på 1960-talet som ett sätt att beräkna mycket noggranna lösningar till alla utom de mest illa konditionerade linjära system. Emellertid har två hinder hittills förhindrat dess antagande i standard subrutin bibliotek som LAPACK: (1) Det fanns inget standard sätt att få tillgång till den högre precision aritmetik som behövs för att beräkna restvärden, och (2) det var oklart hur man skulle beräkna ett tillförlitligt fel som är bundet till den beräknade lösningen. Fullbordandet av den nya BLAS-standarden för tekniskt forum har i huvudsak undanröjt det första hindret. För att övervinna det andra hindret, visar vi hur tillämpningen av iterativ förfining kan användas för att beräkna ett fel som är bundet i någon norm till liten kostnad och använda detta för att beräkna både ett fel bundet i den vanliga infiniteten norm, och en komponentvis relativ fel bundet. Tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt bruk eller klassrum beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller direkt kommersiell fördel och att kopior visar detta meddelande på första sidan eller första skärmen av en skärm tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Tillstånd kan begäras från Publications Department., ACM, Inc., 1515 Broadway, New York, NY 10036 USA, fax: +1 ( Vi rapporterar omfattande testresultat på över 6,2 miljoner matriser av dimensionerna 5, 10, 100, och 1000. Så länge ett normalt (komponentvis) tillståndsnummer som beräknas av algoritmen är mindre än 1/ max{10, ε n}εw, är det beräknade normvisa (komponentvis) felet bundet högst 2 max{10, ε n} · ε w, och begränsar verkligen det verkliga felet. Här är n matrisdimensionen och ε w = 2 −24 är arbetsprecisionen. Restprodukter beräknades med dubbel precision (53 bitars precision). Med andra ord beräknade algoritmen alltid ett litet fel till försumbar extra kostnad för de flesta linjära system. Vid sämre konditionerade problem (som vi kan upptäcka med hjälp av tillståndsuppskattning) fick vi små korrekta felgränser i över 90% av fallen.
REF ger en iterativ förfiningsalgoritm för linjära system som använder högre precision aritmetisk för att beräkna restvärdet.
Error bounds from extra-precise iterative refinement
{'venue': 'TOMS', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}