Kahanen batuketa-algoritmo

Kahanen batuketa-algoritmoa (edo batuketa konpentsatua) doitasun finituko koma higikorreko zenbakien baturan gertatzen diren zenbakizko erroreak gutxitzeko algoritmoa da, William Kahanek sortutakoa.

Doitasun finituko koma higikorreko zenbakiekin lan egiten dugunean, zenbakia adierazteko erabil dezakegun digitu kopurua mugatua da, ondorioz ezin dira zenbaki guztiak adierazi eta biribiltze eta trunkatze erroreak sortzen dira. Zenbaki askoren arteko batura egin nahi denean eta, bereziki, zenbaki handiei zenbaki txikiak gehitu nahi dizkiegunean, zenbaki txikiaren azken digituek ez dute eraginik izango baturan, galdu egingo dira. Galdutako digituek eta prezisioak, batukari askorekin, emaitzaren errorea handiegia izatera bultza dezakete eta, ondorioz, kalkulu zientifiko zehatzak beharrezkoak diren kasuetan, arazo izan daiteke.

Algoritmo honi esker, batuketa bakoitzean galdutako digituak gorde egiten dira bigarren aldagai batean, eta bildutako errore hori ondorengo batuketan eransten saiatzen da algoritmoa. Era honetan, galera txikien baturak esanguratsua izan daitekeen digitu batean eragin dezake egindako erroreak murriztuz.

Algoritmoa

 function KahanSum(input)
    var sum = 0.0
    var c = 0.0                  // batuketan galtzen diren digituak gordetzeko (negatiboan).
    for i = 1 to input.length do
        var y = input[i] - c       // Aurreko eragiketetan galdutako digituak hurrengo batugaiari gehitzen dizkio eragiketa honek (negatiboan daudenez, kendu!).
        var t = sum + y            // sum zenbaki handia bada eta y txikia, y-ko digitu asko gal daitezke.
        c = (t - sum) - y          //(t - sum) balioan agertuko dira y-ren hainbat digitu, baturan eragina izan dutenak hain zuzen ere, eta horri y kenduz, galdutako digituak lortuko ditugu negatiboan
        sum = t                  // Algebraikoki, c beti 0 izan beharko litzateke.
    next i                       // Hurrengoan, galdutako digituak y-ri gehituko zaizkio.
    return sum

Adibidea

Batuketaren hasierako balioa 234001.0 dela suposatuz, eta horri 1.427569 eta 3.139473 gehitu nahi badiogu hurrenez hurren, Kahanen batuketa-algoritmoarekin eta hau gabe lortzen ditugun emaitzak aztertuko ditugu, zenbakia 7 digitura mugatuz.

Batuketa hauen emaitza zehatza honakoa da: 234005.567042 ⇒ 7 digituetara mugatuz: 234005.6

• Batuketa arruntarekin:

234001.0 + 1.427569 = 234002.427569 ≈ 234002.4                 Jada, 4ren ondorengo digitu guztiak galdu egin dira
234002.4 + 3.139473 = 234005.539473 ≈ 234005.5                 Emaitza ez da zehatz zehatza, galdu ditugun digituengatik.
    

• Kahanen batuketa konpentsatuarekin:

sum = 234001.0                    
c = 0.0                            
y = 1.427569 – 0 = 1.427569 
t = 234001.0 + 1.427569 = 
  = 234002.427569                 Baina 7 digitu besterik ezin dira erabili! Beraz, biribildu beharra daukagu.
  = 234002.4
c = (234002.4 – 234001.0) – 1.427569 
  = 1.400000 – 1.427569 
  = -0.027569                     Batuketa honetan galdutako digituak, hurrengo batuketan erabiltzeko gordeko direnak
sum = 234002.4

Baina batuketan bakarrik 7 digitu gelditu dira, besteak galduz. Beraz, c-n galdutako digitu horiek gordetzen dira, benetan gehitu diren digituen eta gehitu behar zirenen arteko kenketa eginez.

y = 3.139473 - (-0.027569)  Aurreko atalean galdutako digituak sartzen dira. y-ren antzeko tamainakoa denez, digitu  
  = 3.167042                    gehienak kontuan hartzen dira.
t = 234002.4 + 3.167042
  = 234005.567042
  = 234005.6            Baina berriro ere, batuketan gutxi batzuk kontuan hartzen dira, emaitza 7 digituetara biribilduz.
c = (234005.6 – 234002.4) – 3.167042
  = 3.200000 – 3.167042   Hala ere, aurreko eragiketan galdutako digituak sartu dira, kasu honetan, gehiegi, c positiboa
  = 0.032958                baita. Beraz, hurrengo batuketa egongo balitz, kendu beharko lirateke.
sum = 234005.6     Horrela, biribiltze zuzena lortzen dugu.

Beraz, ikus daitekeen bezala, batuketa bi metatzailerekin gauzatzen da: sum, batuketa gordetzen duena, eta c, galdutako digituak gordetzen dituena.

Zehaztasuna

Orokorrean, horrelako eragiketen ebazpenak inplizituki hainbat errore ditu:

1. Makina epsilona deiturikoa, konputagailuek erabilitako doitasunaren araberakoa dena: ɛ = (1/2)(b^-d+1), non:

• b = erabilitako oinarria (adibidez b=2 bitarrean, b=10 hamartarrean, etab.)
• d = zenbakiak adierazteko erabiliko ditzakegun digitu kopurua

Adibidez, IEEE standard double precision floating pointerako: ɛ = (1/2)(2^-52+1) ≈ 10⁻¹⁶ .

2. Problemaren baldintzapena, adierazten duena problemaren emaitza zer nolako sentikortasuna duen sarrerako datuekiko, hau da, sarrerako datuen aldaketak edo erroreak zer nolako eragina duen emaitzan. Gaizki baldintzatutako problema batekin, sarrerako datuen aldaketa minimo batek, emaitzaren aldaketa oso esanguratsu bat suposatu dezake, problema horren emaitzen fidagarritasuna behera eginez. Problema honetarako:

$C_{n}={\frac {\sum \limits _{i=1}^{n}|x_{i}|}{\left|\sum \limits _{i=1}^{n}x_{i}\right|}}$

Algoritmo honek emaitzan duen eragin nagusia, lortutako errorearen ordena gutxitzea da: oinarrizko batuketa batekin lortutako errorea batugai kopuruaren arabera hazten den bitartean ($O(n\varepsilon )$ ordenarekin, kasu okerrenean), Kahanen algoritmoarekin errorea batugai kopuruaren independentea izatea lortzen da, soilik makina epsilon-en balioaren araberako erroreak lortuz, hau da, erabiltzen den zenbakien adierazpenak duen inplizituzko errorearen arabera: $O(\varepsilon )$.

Errorearen analisia

Izan bedi batukari baten emaitza erreala:

$S_{n}=\sum _{i=1}^{n}x_{i}$,

Batuketa konpentsatuarekin lortutako ematiza $S_{n}+E_{n}$ izango da, non errorea horrela bornatu dezakegu:

$|E_{n}|\leq \left[2\varepsilon +O(n\varepsilon ^{2})\right]\sum _{i=1}^{n}|x_{i}|$.

Datu horiekin, emaitzaren errore erlatiboa horrela bornatu dezakegu:

${\frac {|E_{n}|}{|S_{n}|}}\leq \left[2\varepsilon +O(n\varepsilon ^{2})\right]{\frac {\sum \limits _{i=1}^{n}|x_{i}|}{\left|\sum \limits _{i=1}^{n}x_{i}\right|}}$ $\Rightarrow$ $E_{er}\leq \left[2\varepsilon +O(n\varepsilon ^{2})\right]C_{n}$

Errorearen interpretazioa

Nahiz eta errorearen adierazpidean $O(n\varepsilon ^{2})$ motako ordena bat izan, horrek suposatutako errorea ≈ 0 da: Makina epsilona zenbakia ɛ izanik, zenbakiak doitasun horren arabera biribilduko dira. Hortaz, nɛ² zenbakia 0-ra biribilduko da, n≥(1/ɛ) ez bada, orokorrean praktikan gertatzen ez den kasua izanez (adibidez double floating point doitasunarekin, n≥10¹⁶ izan beharko luke). Ondorioz, baldintzapenaren zenbakiaz gain, errorea soilik $\varepsilon$-en arabera geratzen da, $n$-ren independentea izatea lortuz.

Kanpo estekak

• Datuak: Q2982293