про накопленную вычислительную погрешность.

← →
AFrolov © (2002-09-23 11:36) [0]

Привет всем.
При вычислениях засчет конечности числа удерживаемых знаков накапливанется вычислительная погрешность. Может кто-то знает как ее можно оценить? - это нужно для того что бы процесс вычислений прерывать если видно что из-за выч. погрешности результ с нужной точностью получен быть не может.
Заранее спасибо

← →
BOA_KAA © (2002-09-23 12:25) [1]

Это смотря что ты вычисляешь. Ежели, к примеру, функцию раскладываешь в ряд Фурье, то там есть такая фишка, как остаточный, пардон, член:-) Если ты решаешь диф. ур. методом конечных разностей, то там другой подход. А если ты вообще имеешь ввиду, что как округление числа влияет на точность, то я скажу чесно: практически никак. Используя типы Double или Extended точность получается такой, что такая просто не может понадобиться:-)

В общем, уточни вопрос, что именно нужно

← →
Виктор Щербаков © (2002-09-23 12:41) [2]

> Используя типы Double или Extended точность получается такой,
> что такая просто не может понадобиться:-)

Такой точности может не хватать для решения самых элементарных задач. Например, решение квадратного уравнения :)
Если конечно пользоваться "неправильными" алгоритмами.

← →
BOA_KAA © (2002-09-23 12:50) [3]

2Такой точности может не хватать для решения самых элементарных задач. Например, решение квадратного уравнения :)

Такой точности может не хватать для решения самых элементарных задач. Например, решение квадратного уравнения :)

Интересно, а что ж за алгоритм такой должен быть?:) Подстановка от -охренеть до +охренеть, что ли?:-)))) Не, ну насмешил.

← →
AFrolov © (2002-09-23 12:51) [4]

Ну вот собственно с "правильными" алгоритмами бывает напряженка.
Кроме того в ряде задач (например задачи линейной алгебры большой размерности) надо очень сильно думать, что бы подобрать хороший алгоритм. Иной раз бывает, что метод погрешности не имеет, а результат - вообще никуда не годится.

← →
BOA_KAA © (2002-09-23 12:56) [5]

2AFrolov © (23.09.02 12:51)

Кроме того в ряде задач (например задачи линейной алгебры большой размерности) надо очень сильно думать, что бы подобрать хороший алгоритм. Иной раз бывает, что метод погрешности не имеет, а результат - вообще никуда не годится.

Если метод не имеет погрешности, то откуда она возьмется???

Давай пример, разберемси:)))

← →
AFrolov © (2002-09-23 12:57) [6]

2 BOA_KAA © (23.09.02 12:50) А Вы матрицу (имя автора не помню) с элементом вычисляемым по ф-ле 1/(i+j) размерности так 40х40 попробуйте на Extended обратить (причем прямые аналитические методы нахождения обратной матрицы имееют 0 погрешность метода) - получите точно не правильный результат результат. Виной этому будут ошибки округления.

← →
Виктор Щербаков © (2002-09-23 13:03) [7]

> Интересно, а что ж за алгоритм такой должен быть?:) Подстановка
> от -охренеть до +охренеть, что ли?:-)))) Не, ну насмешил.

Ну обычный алгоритм. Квадратное уравнение задается тремя коэффициентами a, b, c.
Формулы для действ. корней:
x1 = (-b + sqrt(D))/(2*a)
x2 = (-b - sqrt(D))/(2*a)
теперь представь себе, что -b и sqrt(D) оооооочень большие числа, но их разность оооочень мала.
Решая уравнение по этим формулам, x1 получиться с нормальной относительной погрешностью, а x2 c офигенной.
Это один из самых наглядных примеров.
Потерь точности часто можно избежать совершенствуя алгоритм. Как пример - выбор ведущего элемента в методе Гаусса для решения систем лин. уравнений.
А как квадратное уравнение решить точнее - сам подумай.

← →
BOA_KAA © (2002-09-23 13:17) [8]

Не понимаю я, где-то вы замудряетесь, а где - понять не могу. Мне зачастую приходилось решать системы линейных уравнений даже не 100х100, а больше, причем каждый элемент матрицы - жуткая бяка и ничего... Ежели алгоритм хороший, то он работать будет нормально (разумеется, если я напрямик запихаю в память лимонХлимон екстендедов, то комп плеваться будет).

2 Виктор Щербаков © (23.09.02 13:03)

Я про такой способ решения квадратного уравнения совсем забыл:-)))

← →
Юрий Зотов © (2002-09-24 01:16) [9]

> BOA_KAA

1. Не стоит путать погрешность округления и накопление погрешности. Extended имеет 19-20 знаков, но при длинной цепочке вычислений (о чем и был вопрос) даже и 3-й знак может стать ошибочным. Накопление, однако...

2. Вы хотели пример - вот он. Реально решаемый когда-то.

Есть такая система уравнений (P - давление, P0 - статическое давление (константа), G - расход, X - независимая переменная, вектор Y - искомое решение).

dY1/dX = F1(X, Y1, Y2, P, G)
dY2/dX = F2(X, Y1, Y2, P, G)
P = F3(X, Y1, Y2, G)
G = F4(X, Y1, Y2, P-P0)

Как видим, последнее уравнение, в отличие от предыдущих, зависит не от абсолюта P, а от его разности с P0. Причем физическая суть задачи не позволяет избавиться от этого никакими математическими преобразованиями. Причина проста - расход зависит от перепада давлений, а в уравнение состояния входит абсолют давления.

Далее, природа задачи такова, что P и P0 отличаются друг от друга очень мало (P и P0 порядка 1E5, а их разность порядка 1E-3). Но (вследствие низкой вязкости среды) даже эта малая разность приводит к заметным значениям G и существенно влияет на значения производных в первых двух уравнениях. То есть - плохая численная обусловленность (что четко показывает якобиан, ежели его вычислить).

Соответственно, чтобы не было "качания" производных и разболтки решения, приходится вычислять P минимум с 8 верными цифрами. При весьма длинной цепочке вычислений, поскольку функции F1-F4 имеют весьма сложный вид (здесь я для краткости упростил систему, на самом же деле для вычисления этих функций приходится численно решать еще несколько систем уравнений, в которых тоже накапливается погрешность). И при такой длине цепочки не спасает никакой Extended - для того, чтобы получить 8 верных знаков, пришлось сначала исследовать саму модель, а затем разработать специальный алгоритм решения.

В итоге получилось вот что. Задача и система уравнений о которой идет речь, известна уже около 30 лет. Но на сегодня в России существуют практически только одна программы, способная получить устойчивое решение почти при любом наборе исходных данных (и то - почти при любом, но все же не при любом). Хотя попыток сделать такую программу насчитывается несколько десятков.

> AFrolov
Присоединяюсь к Виктору Щербакову - потерь точности часто можно избежать совершенствуя алгоритм. А от себя добавлю - и исследуя сначала физический смысл задачи (на предмет введения возможных допущений), а потом саму систему уравнений (на предмет ее преобразования к виду, лучше приспособленному для численного решения).

← →
zzet © (2002-09-24 01:20) [10]

никем незамеченные десятые доли копеек складываются в рубли..

Про совершенствование алгоритмов - дело известное. Общеизвестно, что для специальных случаев могут быть получены высокоточные и эффективные алгоритмы. Однако вопрос об оценивании в ходе вычислений накопленной выч. погрешности остается открытым.
Может кто поделится ссылками где про это можно почитать или книги посоветует?

Форсайт Дж., Малькольм М., Моулер Е. Машинные методы математических вычислений. М.: Мир, 1980.

Уже замучился рекомендовать, но книга действительно классная.
Если где увидите, отрывайте с руками. Мне самому хочется её из библиотеки скоммуниздить, но совесть не позволяет :(

> Юрий Зотов © (24.09.02 01:16)

А Вы собрались решать эту систему явным способом???;) В этом случае она даст погрешность еще на этапе задания краевых условий.

Еще раз всем! Я - только за совершенствование алгоримов. А то меня, как я смотрю, не очень-то правильно поняли:)))

← →
Silent (2002-10-02 16:25) [14]

> Виктор Щербаков © (24.09.02 12:34)

Переработанная и расширенная версия книги
Форсайт Дж., Малькольм М., Моулер Е. Машинные методы математических вычислений. М.: Мир, 1980.
выпущена в 2001 году издательством МИР.

Называется она
Д. Каханер, К. Моулер, С.Неш
Численные методы и программное обеспечение

В ней вторая глава как раз посвящена ошибкам округления и их накоплению.

про накопленную вычислительную погрешность. Найти похожие ветки