Cifereca stabileco

En la cifereca analitiko, la cifereca stabileco estas dezirinda propraĵo de ciferecaj algoritmoj. La preciza difino de stabileco dependas de la ĉirkaŭteksto, sed ĝi rilatas al la fidindeco de la eligoj de algoritmo: algoritmo estas (ciferece) stabila, se ĝi produktas bonan proksimuman kalkuladon al la vera solvaĵo.

Fojfoje la sama kalkulo povas esti efektivigita laŭ pluraj metodoj, kiuj estas ĉiuj algebre ekvivalentas je idealaj reelaj aŭ kompleksaj nombroj, sed en praktiko liveras malsamajn rezultojn, ĉar ili havas malsamajn nivelojn de la cifereca stabileco] Unu el la ordinaraj taskoj de cifereca analitiko estas provi selekti algoritmojn, kiuj estas fortikaj — tio estas — kiuj havas bonan ciferecan stabilecon.

Oni deziru sumigi 100 nombrojn. La simpla algoritmo por ĉi tio estas:

 sumo = 0
 por i = 1 ĝis 100:
   sumo = sumo + a[i]

Ĉi tio estas ne stabila algoritmo. Ekzemple ni havu flosantan punkton 3 dekumaj ciferojn de precizeco (tiam ekzemple 1,553 estas konsiderata la same kiel 1,546, ili ambaŭ estas rondigataj al 1,55; 0,1553 estas rondigata al 0,155; 0,01553 estas rondigata al 0,0155).

Por malbona okazo, estu a[1]=1 kaj a[i]=0,001 por i=2 ... 100. La preciza rezulto estas 1,099, kiu estus rondigita al 1,1.

La algoritmo en la unua ripeto de la ciklo faras ke sumo=1.

En la da ripeto de la ciklo estas sumo=1+0,001=1,001, kio estas rondigata al sumo=1 denove. La samo okazas en la ceteraj 98 ripetoj.

Kaj la rezulto redonita estos 1.

La stabila algoritmo devas reordigi la nombrojn kaj komenci la sumadon ekde la plej malgrandaj nombroj, kiel

sumo = (( .... (((0,001+0,001)+0,001)+0,001)+ .... )+0,001)+1

Por kalkuli 0,001+0,001=0,002 sufiĉas nur unu cifero da precizeco, de la kalkulo estas preciza.

Plu por kalkuli 0,002+0,001=0,003 sufiĉas nur unu cifero da precizeco, de la kalkulo estas preciza, kaj tiel plu.

Ĉe la lasta ripeto estas 0,099+1=1,099 kiu estas rondigata al 1,1.

Tiel ĉi tio donas la bonan rezulton 1,1.

La nocioj antaŭena, retroena, kaj miksita stabileco ofte uziĝas en cifereca liniara algebro.

Konsideru la problemon solvendan per la cifereca algoritmo kiel funkcion f surĵetantan la datumojn x al la solvaĵo y. La reala rezulto de la algoritmo, ni diru y*, kutime iom foriĝos de la ĝusta solvo. La ĉefaj kaŭzoj de eraro estas eraro de rondigo, eraro de trunkado, kaj eraro de datumoj.

La antaŭena eraro de la algoritmo estas la diferenco inter la reala rezulto kaj la ĝusta solvo, ĉi-kaze Δy = y* − y. La retroena eraro estas la plej malgranda Δx tia, ke f(x + Δx) = y*; alivorte, la retroena eraro informas al ni, kiun problemon la algoritmo reale solvis. La antaŭena kaj retroena eraroj rilatas al la kondiĉa nombro: la antaŭena eraro maksimume tiel granda laŭ grandeco kiel la kondiĉa nombro multiplikita per la grandeco de la retroena eraro.

En multaj kazoj, pli nature estas konsideri relativan eraron

${\displaystyle {\frac {|\Delta x|}{|x|}}}$

anstataŭ la absoluta eraro Δx.

La algoritmon oni nomas kiel retroene stabila, se la retroena eraro estas malgranda por ĉiuj enigoj x. Kompreneble, "malgranda" estas relativa termino kaj ĝia difino dependas de la ĉirkaŭteksto. Ofte, oni bezonas, ke la eraro estu de la sama ordo kiel, aŭ eble nur je kelkaj ordoj de grandeco pli granda ol la rondigo de unuo.

La kutima difino de cifereca stabileco uzas pli ĝeneralan koncepton, nomitan kiel miksita stabileco, kiu kombinas la antaŭenan eraron kaj la retroenan eraron. Algoritmo estas stabila en tiu senco, se ĝi solvas apudecan problemon proksimume, tio estas, se ekzistas Δx tia, ke malgrandas Δx, kaj ankaŭ malgrandas f(x + Δx) − y*. Tial, retroene stabila algoritmo estas ĉiam stabila.

Algoritmo estas antaŭene stabila se ĝia antaŭena eraro dividita per la kondiĉa nombro de la problemo estas malgranda. Tio signifas, ke algoritmo estas antaŭene stabila, se ĝi havas antaŭenan eraron de simila grandeco kiel tiu de iu retroene stabila algoritmo.

La supraj difinoj estas aparte taŭgaj en situacioj, kie trunkaj eraroj estas ne gravaj. En aliaj ĉirkaŭtekstoj, ekzemple dum solvado de diferencialaj ekvacioj, malsama difino de cifereca stabileco estas uzata.

En ciferecaj ordinaraj diferencialaj ekvacioj, diversaj konceptoj de cifereca stabileco ekzistas, ekzemple A-stabileco. Ili rilatas al ia koncepto de stabileco en la senco de dinamikaj sistemoj, ofte ljapunova stabileco. Gravas uzi stabilan metodon dum solvado de rigida ekvacio.

Ankoraŭ alia difino estas uzata en ciferecaj partaj diferencialaj ekvacioj. Algoritmo por solvi evoluajn partajn diferencialajn ekvaciojn estas stabila, se la cifereca solvado je fiksita tempo restas barita se la ŝtupo-amplekso iras al nulo. La teoremo de ekvivalenteco de Lax diras, ke algoritmo konverĝas, se ĝi estas konsekvenca kaj stabila (en ĉi tiu senco). Stabileco fojfoje atingiĝas per inkluzivigado de cifereca difuzo. Cifereca difuzo estas matematika termo, kiu certigas, ke rondigaj kaj aliaj eraroj en la kalkulo disetendos kaj ne akumuliĝos kaŭzante la kalkulon fiaski ("eksplodiĝi").

• Nikolao J. Higham, Akurateco kaj Stabileco de Ciferecaj Algoritmoj, Socio de Industria kaj Aplikis Matematiko, Philadelphia, 1996. ISBN 0-89871-355-2. angle