Алгоритм Кэхэна
В вычислительной математике алгоритм Кэхэна (также известный как компенсационное суммирование) — это алгоритм вычисления суммы последовательности чисел c плавающей запятой, который значительно уменьшает вычислительную погрешность по сравнению с наивным подходом. Уменьшение погрешности достигается введением дополнительной переменной для хранения нарастающей суммы погрешностей.
В частности, простое суммирование n чисел в худшем случае имеет погрешность, которая растет пропорционально n и при суммировании случайных чисел имеет среднее квадратичное отклонение равное <math>\sqrt{n}</math> (ошибки округления вызывают случайное блуждание)[1]. При компенсационном суммировании погрешность даже в худшем случае не зависит от n, так что большое число слагаемых могут быть просуммированы с погрешностью, зависящей только от точности числа с плавающей запятой[1].
Авторство над алгоритмом приписывают Уильяму Кэхэну[2].
Содержание
Алгоритм
В псевдокоде алгоритм можно записать так:
function KahanSum(input)
var sum = 0.0
var c = 0.0 //Сумма погрешностей.
for i = 1 to Len(input) do
y = input[i] - c //Пока все хорошо: c - ноль.
t = sum + y //Увы, sum велика, y мало, так что младшие разряды y потеряны.
c = (t - sum) - y //(t - sum) восстанавливает старшие разряды y; вычитание y восстанавливает -(младшие разряды y)
sum = t //Алгебраически, c всегда должна равняться нулю. Берегитесь слишком оптимизирующих компиляторов!
//В следующий раз потерянные младшие разряды будут заново прибавлены к y.
return sum
Пример исполнения
В данном примере будем использовать десятичные дроби. Компьютеры обычно используют двоичную арифметику, но иллюстрируемый алгоритм от этого не меняется. Представим что используется шестиразрядная арифметика с плавающей точкой, sum было присвоено значение 10000.0, и следующие два значения input(i) равны 3.14159 и 2.71828. Точный результат равен 10005.85987, что округляется до 10005.9. При простом суммировании порядок каждого входящего значения был бы выравнен с sum, и много младших разрядов было бы потеряно (округлено или отброшено). Первый результат после округления был бы 10003.1. Второй результат был бы 10005.81828 до округления, и 10005.8 после. Что не верно.
При компенсационном суммировании мы бы получили правильный округленный результат 10005.9.
Предположим, что начальное значение c — 0.
y = 3.14159 - 0 y = input[i] - c
t = 10000.0 + 3.14159
= 10003.1 Много разрядов потеряно!
c = (10003.1 - 10000.0) - 3.14159 Это нужно вычислять как записано!
= 3.10000 - 3.14159 Восстановлена не вошедшая в t часть y , а не все исходное y.
= -.0415900 Завершаюшие нули показаны, потому что это шестиразрядная арифметика.
sum = 10003.1 Таким образом не все разряды из input(i) включены в sum.
Сумма настолько велика, что сохраняются только старшие разряды слагаемого. К счастью, на следующем шаге c хранит погрешность.
y = 2.71828 - -.0415900 Учитывается погрешность с предыдущего шага.
= 2.75987 Её порядок не слишком отличается от y. Большинство разрядов учтены.
t = 10003.1 + 2.75987 Но только немногие разряды попадают в sum.
= 10005.85987, округляется до 10005.9
c = (10005.9 - 10003.1) - 2.75987 Здесь извлекается то что пришло
= 2.80000 - 2.75987 В данном случае слишком много.
= .040130 Так или иначе излишек будет вычтен в следующий раз.
sum = 10005.9 Точный результат: 10005.85987, что корректно округлено до 6 знаков.
Таким образом сложение происходит в двух переменных: sum хранит сумму, и c хранит часть суммы, которая не попала в sum, чтобы быть учтенной в sum на следующей итерации. Хотя суммировать, храня младшие разряды в c лучше, чем не храня их нигде, это все же не так точно, как производить вычисление, используя ввод двойной точности. Тем не менее, просто увеличивать точность вычислений в целом не практично; если input уже имеет двойную точность, немногие системы могут предоставить учетверенную точность вычислений, и, если бы могли, ввод тоже мог бы иметь учетверённую точность.
Напишите отзыв о статье "Алгоритм Кэхэна"
Примечания
- ↑ 1 2 Higham, Nicholas J. (1993), "[dx.doi.org/10.1137%2F0914050 The accuracy of floating point summation]", SIAM Journal on Scientific Computing Т. 14 (4): 783–799, DOI 10.1137/0914050
- ↑ Kahan, William (January 1965), "[dx.doi.org/10.1145%2F363707.363723 Further remarks on reducing truncation errors]", Communications of the ACM Т. 8 (1): 40, DOI 10.1145/363707.363723
Ссылки
- Evan Manning, [www.drdobbs.com/floating-point-summation/184403224 Floating-point Summation] Dr. Dobb’s Journal September, September 01, 1996
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Алгоритм Кэхэна
Но император улыбнулся и перебил его:– Сколько миль?
– Откуда и докуда, ваше величество?
– От Дюренштейна до Кремса?
– Три с половиною мили, ваше величество.
– Французы оставили левый берег?
– Как доносили лазутчики, в ночь на плотах переправились последние.
– Достаточно ли фуража в Кремсе?
– Фураж не был доставлен в том количестве…
Император перебил его.
– В котором часу убит генерал Шмит?…
– В семь часов, кажется.
– В 7 часов. Очень печально! Очень печально!
Император сказал, что он благодарит, и поклонился. Князь Андрей вышел и тотчас же со всех сторон был окружен придворными. Со всех сторон глядели на него ласковые глаза и слышались ласковые слова. Вчерашний флигель адъютант делал ему упреки, зачем он не остановился во дворце, и предлагал ему свой дом. Военный министр подошел, поздравляя его с орденом Марии Терезии З й степени, которым жаловал его император. Камергер императрицы приглашал его к ее величеству. Эрцгерцогиня тоже желала его видеть. Он не знал, кому отвечать, и несколько секунд собирался с мыслями. Русский посланник взял его за плечо, отвел к окну и стал говорить с ним.
Вопреки словам Билибина, известие, привезенное им, было принято радостно. Назначено было благодарственное молебствие. Кутузов был награжден Марией Терезией большого креста, и вся армия получила награды. Болконский получал приглашения со всех сторон и всё утро должен был делать визиты главным сановникам Австрии. Окончив свои визиты в пятом часу вечера, мысленно сочиняя письмо отцу о сражении и о своей поездке в Брюнн, князь Андрей возвращался домой к Билибину. У крыльца дома, занимаемого Билибиным, стояла до половины уложенная вещами бричка, и Франц, слуга Билибина, с трудом таща чемодан, вышел из двери.
Прежде чем ехать к Билибину, князь Андрей поехал в книжную лавку запастись на поход книгами и засиделся в лавке.
– Что такое? – спросил Болконский.
– Ach, Erlaucht? – сказал Франц, с трудом взваливая чемодан в бричку. – Wir ziehen noch weiter. Der Bosewicht ist schon wieder hinter uns her! [Ах, ваше сиятельство! Мы отправляемся еще далее. Злодей уж опять за нами по пятам.]
– Что такое? Что? – спрашивал князь Андрей.
Билибин вышел навстречу Болконскому. На всегда спокойном лице Билибина было волнение.
– Non, non, avouez que c'est charmant, – говорил он, – cette histoire du pont de Thabor (мост в Вене). Ils l'ont passe sans coup ferir. [Нет, нет, признайтесь, что это прелесть, эта история с Таборским мостом. Они перешли его без сопротивления.]
Князь Андрей ничего не понимал.
– Да откуда же вы, что вы не знаете того, что уже знают все кучера в городе?
– Я от эрцгерцогини. Там я ничего не слыхал.
– И не видали, что везде укладываются?
– Не видал… Да в чем дело? – нетерпеливо спросил князь Андрей.
– В чем дело? Дело в том, что французы перешли мост, который защищает Ауэсперг, и мост не взорвали, так что Мюрат бежит теперь по дороге к Брюнну, и нынче завтра они будут здесь.
– Как здесь? Да как же не взорвали мост, когда он минирован?
– А это я у вас спрашиваю. Этого никто, и сам Бонапарте, не знает.
Болконский пожал плечами.
– Но ежели мост перейден, значит, и армия погибла: она будет отрезана, – сказал он.
– В этом то и штука, – отвечал Билибин. – Слушайте. Вступают французы в Вену, как я вам говорил. Всё очень хорошо. На другой день, то есть вчера, господа маршалы: Мюрат Ланн и Бельяр, садятся верхом и отправляются на мост. (Заметьте, все трое гасконцы.) Господа, – говорит один, – вы знаете, что Таборский мост минирован и контраминирован, и что перед ним грозный tete de pont и пятнадцать тысяч войска, которому велено взорвать мост и нас не пускать. Но нашему государю императору Наполеону будет приятно, ежели мы возьмем этот мост. Проедемте втроем и возьмем этот мост. – Поедемте, говорят другие; и они отправляются и берут мост, переходят его и теперь со всею армией по сю сторону Дуная направляются на нас, на вас и на ваши сообщения.
– Полноте шутить, – грустно и серьезно сказал князь Андрей.
Известие это было горестно и вместе с тем приятно князю Андрею.
Как только он узнал, что русская армия находится в таком безнадежном положении, ему пришло в голову, что ему то именно предназначено вывести русскую армию из этого положения, что вот он, тот Тулон, который выведет его из рядов неизвестных офицеров и откроет ему первый путь к славе! Слушая Билибина, он соображал уже, как, приехав к армии, он на военном совете подаст мнение, которое одно спасет армию, и как ему одному будет поручено исполнение этого плана.
