| dbo:abstract
|
- Kahanen batuketa-algoritmoa (edo batuketa konpentsatua) doitasun finituko koma higikorreko zenbakien baturan gertatzen diren zenbakizko erroreak gutxitzeko algoritmoa da, 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. (eu)
- In numerical analysis, the Kahan summation algorithm, also known as compensated summation, significantly reduces the numerical error in the total obtained by adding a sequence of finite-precision floating-point numbers, compared to the obvious approach. This is done by keeping a separate running compensation (a variable to accumulate small errors), in effect extending the precision of the sum by the precision of the compensation variable. In particular, simply summing numbers in sequence has a worst-case error that grows proportional to , and a root mean square error that grows as for random inputs (the roundoff errors form a random walk). With compensated summation, using a compensation variable with sufficiently high precision the worst-case error bound is effectively independent of , so a large number of values can be summed with an error that only depends on the floating-point precision of the result. The algorithm is attributed to William Kahan; Ivo Babuška seems to have come up with a similar algorithm independently (hence Kahan–Babuška summation). Similar, earlier techniques are, for example, Bresenham's line algorithm, keeping track of the accumulated error in integer operations (although first documented around the same time) and the delta-sigma modulation. (en)
- In analisi numerica, l'algoritmo di sommatoria di Kahan (conosciuto anche come sommatoria compensata) riduce significativamente l'errore numerico nel totale ottenuto sommando una sequenza di numeri in virgola mobile con precisione finita, se confrontato con il consueto procedimento. Ciò è ottenuto mantenendo una compensazione progressiva separata (una variabile per accumulare piccoli errori). Quando rappresentiamo un generico numero reale in virgola mobile con precisione finita, ossia con un numero finito di cifre significative, tale rappresentazione, rispetto al numero reale considerato, differisce di un certo valore, il quale corrisponde all'errore di arrotondamento ed è lo scarto tra la rappresentazione in virgola mobile e il numero stesso. Eseguendo una semplice sommatoria di più numeri reali, utilizzando però le rispettive rappresentazioni in virgola mobile, il totale ottenuto presenta un certo errore dato dalla somma algebrica dei singoli errori di arrotondamento, ossia dei singoli scarti, ed, inoltre, si ottiene un certo scarto quadratico medio, in inglese root mean square error, inteso come la radice quadrata della media aritmetica dei quadrati dei singoli scarti. In particolare, la sommatoria semplice di numeri in sequenza presenta un errore che, nel caso peggiore, cresce proporzionalmente ad ed uno scarto quadratico medio che cresce come per addendi casuali (gli errori di arrotondamento producono una passeggiata aleatoria). Invece, con la sommatoria compensata, l'errore peggiore possibile è indipendente da , dunque un gran numero di valori possono essere sommati con un errore che dipende solo dalla precisione della rappresentazione in virgola mobile. L'algoritmo è attribuito a William Kahan. Tecniche precedenti simili sono, per esempio, l'algoritmo della linea di Bresenham, che mantiene traccia dell'errore accumulato nelle operazioni sugli interi (anche se già presente in un articolo pubblicato circa nello stesso periodo) e la modulazione Sigma-Delta (che integra e non soltanto somma l'errore). (it)
- カハンの加算アルゴリズム（英語: Kahan summation algorithm、直訳するとカハンの総和アルゴリズム）とは、有限精度の浮動小数点数列の総和を計算する際の誤差を改善する計算手法・アルゴリズム。計算機において精度に制限のある計算をする場合に、計算の途中の誤差を保持することで補正する。Compensated summation（補正加算）とも呼ぶ。 単純に n 個の数値の総和を計算すると、n に比例して誤差が増えていくという最悪のケースがありうる。また、無作為な入力では二乗平均平方根の誤差すなわち に比例する誤差が生じる（丸め誤差はランダムウォークを形成する）。補正加算では最悪の場合の誤り限界 (error bound) は n とは独立なので、多数の数値を合計しても、誤差は使用する浮動小数点数の精度に依存するだけとなる。 このアルゴリズムの名は考案したウィリアム・カハンに因む。似たようなそれ以前の技法として、例えばブレゼンハムのアルゴリズムがあり、整数演算での誤差の蓄積を保持する（文書化されたのはカハンとほぼ同時期である）。その他の類似例としてはΔΣ変調が挙げられる。ΔΣでは、誤差の蓄積の保持が積分となっている。 (ja)
- Algorytm sumacyjny Kahana (zwany także algorytmem sumowania z poprawkami) – algorytm minimalizujący błędy powstałe przy dodawaniu ciągu liczb zmiennopozycyjnych o skończonej precyzji. Algorytm w pseudokodzie: function kahanSum(input, n) var sum = input[1] var c = 0.0 //Poprawka zawierająca utracone niskie bity. for i = 2 to n y = input[i] - c t = sum + y //Sum jest względnie duże w porównaniu z y co powoduje utratę bitów mniej znaczących liczby y. c = (t - sum) - y //(t - sum) odzyskuje wyższe bity y; odjęcie y odzyskuje -(niższe bity y) sum = t next i //W następnej iteracji utracone niższe bity zostaną dodane do y return sum (pl)
- В вычислительной математике алгоритм Кэхэна (также известный как компенсационное суммирование) — это алгоритм вычисления суммы последовательности чисел c плавающей запятой, который значительно уменьшает вычислительную погрешность по сравнению с наивным подходом. Уменьшение погрешности достигается введением дополнительной переменной для хранения нарастающей суммы погрешностей. В частности, простое суммирование чисел в худшем случае имеет погрешность, которая растёт пропорционально и при суммировании случайных чисел имеет среднее квадратичное отклонение, пропорциональное (ошибки округления вызывают случайное блуждание). При компенсационном суммировании погрешность даже в худшем случае не зависит от , так что большое число слагаемых могут быть просуммированы с погрешностью, зависящей только от точности числа с плавающей запятой. Авторство алгоритма приписывают Уильяму Кэхэну. (ru)
- В обчислювальній математиці алгоритм Кехена (також відомий, як компенсаційне підсумовування) — це алгоритм обчислення суми послідовності чисел з рухомою комою, який значно зменшує обчислювальну похибку у порівнянні з наївним підходом (простим послідовним підсумовуванням чисел з заокругленням результату на кожному кроці). Зменшення похибки досягається введенням додаткової змінної для збереження суми похибок. Зокрема, наївне підсумовування n чисел в найгіршому випадку дає похибку, яка росте пропорційно n і при підсумовуванні випадкових чисел має середнє квадратичне відхилення, пропорційне до (помилки заокруглення викликані випадковим блуканням).При компенсаційному підсумовуванні навіть в найгіршому випадку похибка не залежить від n, тому велика кількість доданків може бути підсумована з похибкою, яка залежить тільки від точності числа з рухомою комою. Авторство алгоритму приписують Вільяму Кехену. (uk)
|
| rdfs:comment
|
- カハンの加算アルゴリズム（英語: Kahan summation algorithm、直訳するとカハンの総和アルゴリズム）とは、有限精度の浮動小数点数列の総和を計算する際の誤差を改善する計算手法・アルゴリズム。計算機において精度に制限のある計算をする場合に、計算の途中の誤差を保持することで補正する。Compensated summation（補正加算）とも呼ぶ。 単純に n 個の数値の総和を計算すると、n に比例して誤差が増えていくという最悪のケースがありうる。また、無作為な入力では二乗平均平方根の誤差すなわち に比例する誤差が生じる（丸め誤差はランダムウォークを形成する）。補正加算では最悪の場合の誤り限界 (error bound) は n とは独立なので、多数の数値を合計しても、誤差は使用する浮動小数点数の精度に依存するだけとなる。 このアルゴリズムの名は考案したウィリアム・カハンに因む。似たようなそれ以前の技法として、例えばブレゼンハムのアルゴリズムがあり、整数演算での誤差の蓄積を保持する（文書化されたのはカハンとほぼ同時期である）。その他の類似例としてはΔΣ変調が挙げられる。ΔΣでは、誤差の蓄積の保持が積分となっている。 (ja)
- In numerical analysis, the Kahan summation algorithm, also known as compensated summation, significantly reduces the numerical error in the total obtained by adding a sequence of finite-precision floating-point numbers, compared to the obvious approach. This is done by keeping a separate running compensation (a variable to accumulate small errors), in effect extending the precision of the sum by the precision of the compensation variable. (en)
- Kahanen batuketa-algoritmoa (edo batuketa konpentsatua) doitasun finituko koma higikorreko zenbakien baturan gertatzen diren zenbakizko erroreak gutxitzeko algoritmoa da, 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, ar (eu)
- In analisi numerica, l'algoritmo di sommatoria di Kahan (conosciuto anche come sommatoria compensata) riduce significativamente l'errore numerico nel totale ottenuto sommando una sequenza di numeri in virgola mobile con precisione finita, se confrontato con il consueto procedimento. Ciò è ottenuto mantenendo una compensazione progressiva separata (una variabile per accumulare piccoli errori). (it)
- Algorytm sumacyjny Kahana (zwany także algorytmem sumowania z poprawkami) – algorytm minimalizujący błędy powstałe przy dodawaniu ciągu liczb zmiennopozycyjnych o skończonej precyzji. Algorytm w pseudokodzie: (pl)
- В вычислительной математике алгоритм Кэхэна (также известный как компенсационное суммирование) — это алгоритм вычисления суммы последовательности чисел c плавающей запятой, который значительно уменьшает вычислительную погрешность по сравнению с наивным подходом. Уменьшение погрешности достигается введением дополнительной переменной для хранения нарастающей суммы погрешностей. Авторство алгоритма приписывают Уильяму Кэхэну. (ru)
- В обчислювальній математиці алгоритм Кехена (також відомий, як компенсаційне підсумовування) — це алгоритм обчислення суми послідовності чисел з рухомою комою, який значно зменшує обчислювальну похибку у порівнянні з наївним підходом (простим послідовним підсумовуванням чисел з заокругленням результату на кожному кроці). Зменшення похибки досягається введенням додаткової змінної для збереження суми похибок. Авторство алгоритму приписують Вільяму Кехену. (uk)
|
