Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Некоторые аспекты машинных вычислений


Автор: esperant0 12.6.2006, 22:57
Цитата(popovda @ 12.6.2006,  22:30)
Вообще говоря вычисление численной производной в точке - операция математически некорректная  

а можно поподробней?

в чем некорректность?

Модератор: Эта тема выделена из http://forum.vingrad.ru/index.php?showtopic=98055&unread=1&hl= 

Автор: popovda 14.6.2006, 19:46
Хотя бы в том, что на эвм одно и то же вещественное число представимо в 3-х видах:
a = 1 - точное значение
Приближенное вещественное число на ЭВМ
x = 0.(9) ; 1.00000000....0; 1.00000000.......1 

Это во-первых, а во-вторых: при вычислении производных на ЭВМ бывают разные казусы, связанные с неправильной аппроксимацией призводной для конкретной задачи. Ведь все дифференциальные уравнения представляются через конечные разности. А вот будет ли сама аппроксимация устойчивой - это вопрос зачастую нетривиальный.  Адресую к "Теории разностных схем" Годунова или Рябенького.
 

Автор: esperant0 14.6.2006, 22:09
Цитата(popovda @ 14.6.2006,  19:46)
Хотя бы в том, что на эвм одно и то же вещественное число представимо в 3-х видах:
a = 1 - точное значение
Приближенное вещественное число на ЭВМ
x = 0.(9) ; 1.00000000....0; 1.00000000.......1 

Это во-первых, а во-вторых: при вычислении производных на ЭВМ бывают разные казусы, связанные с неправильной аппроксимацией призводной для конкретной задачи. Ведь все дифференциальные уравнения представляются через конечные разности. А вот будет ли сама аппроксимация устойчивой - это вопрос зачастую нетривиальный.  Адресую к "Теории разностных схем" Годунова или Рябенького.

спасибо, я учил численный анализ.

Только я не понял связи между вашим утверждением и объяснением.

Уточните утверждение, и термин некорректная.

Вы в своем объяснении ссылаетесь к конкретнй модели ЭВМ, на которую вы не ссылаетесь в утверждении. 

Автор: popovda 15.6.2006, 12:38
Ну, во-первых, не конкретной модели ЭВМ, а к любой модели. Во-вторых, чтобы не быть голословным, поищу какой-нибудь пример (попроще) в запасниках, иллюстрирующих некорректность производной. Для начала скажу следующее: попробуйте взять численную производную кусочно-гладкой функции и сравните с аналитическим значением. 

Автор: popovda 15.6.2006, 21:22
Итак, даю достаточно подробное математическое доказательство некорректности взятия численной производной. Если Вы изучали вычислительную математику, то вопросов не возникнет. Ответ дан на примере экспоненты, так же показано, как найти оптимальный h для данного типа данных. См. прикрепленный файл
  

Автор: esperant0 15.6.2006, 22:29
праивильно ли я вас понял, что вы утверждаете, что в любой модели ЭВМ, эпсилон фиксирован и не адаптируется? 

Автор: esperant0 15.6.2006, 22:47
Цитата(popovda @ 14.6.2006,  19:46)
Хотя бы в том, что на эвм одно и то же вещественное число представимо в 3-х видах:
 

а в математике любое целое число представимо в двух видах, значит она тоже некорректна? 

Автор: maxim1000 15.6.2006, 23:36
Цитата(popovda @  15.6.2006,  20:22 Найти цитируемый пост)
Итак, даю достаточно подробное математическое доказательство некорректности взятия численной производной

ничего кроме утверждения "вычисления на компьютере проводятся с погрешностью" эти выкладки не доказывают
численная производная, как понятие, не имеет никакого отношения к компьютерам, это - просто разность на шаг сетки
некорректна она только в случае h=0
а то, что компьютерные вычисления производятся с погрешностью, так это да, никто не спорит, и рекомендации не брать h слишком маленьким полностью справедливы 

Автор: popovda 16.6.2006, 16:05
Отвечаю на вопрос по данной полемике. Мне довелось быть дипломником д.ф.-м.н., профессора из ВЦ РАН, который на вычислительной математике собаку съел. И слушать его спецкурсы. Этот человек меня научил очень многому и в своих знаниях я уверен. Поэтому:
1. 
Цитата

а в математике любое целое число представимо в двух видах, значит она тоже некорректна
Уточните про то, что Вы имели ввиду по поводу целых чисел и их 2-х представлений. Не ясно.Как раз с точки зрения вычислений к ним претензий такого вида быть не может. 

2.
Цитата

ничего кроме утверждения "вычисления на компьютере проводятся с погрешностью" эти выкладки не доказывают
численная производная, как понятие, не имеет никакого отношения к компьютерам, это - просто разность на шаг сетки
некорректна она только в случае h=0
 По поводу шага на сетке. Привожу высказывание нелюбимого многими В.И. Ленина:
"Теория без практики мертва, а практика без теории слепа." Если аналитическое и численное значения производной не совпадают, то это и есть некорректность операции дифференцирования на ЭВМ. То есть 
требуются дополнительные ограничения и подходы. Как раз этот пример и иллюстрирует, во-первых, к каким последствиям может привести незнание (точнее, непонимание) вычислительных погрешностей, во-вторых, не цепляйтесь к термину "некорректная" - это не означает, что такой подход не применим, нужны методы. В данном случае простые. Но ведь некорректные задачи математической физики - сложные задачи - решают, и успешно. Только методы надо использовать СПЕЦИАЛЬНЫЕ.
3. По поводу машинного нуля - эпсилона - он для конкретной машины фиксирован. Подумайте, как его определить (в какую отрицательную степень надо возвести 10 (мы же в 10-ой с.сч. работаем), чтобы на ЭВМ это число обратилось в 0).
4. Задачка на понимание: чем численно решать систему из N линейных уравнений и почему? N>10^3  

Автор: esperant0 16.6.2006, 19:39
Цитата(popovda @ 14.6.2006,  19:46)
Хотя бы в том, что на эвм одно и то же вещественное число представимо в 3-х видах:
a = 1 - точное значение
Приближенное вещественное число на ЭВМ
x = 0.(9) ; 1.00000000....0; 1.00000000.......1 
 

Но ведь и в математике 

1=0.(9)

Поэтому, ваше утверждение "хотя бы ....."

мне не понятно.


2) У меня такой вопрос, корректна ли программа выдающая правильные точечные значения производной, но не выполняющяя стремление к нолю предела ошибки.

Цель программы вычислять точечные значения производной. 

Автор: maxim1000 16.6.2006, 20:46
я уже давно заметил: большинство споров происходит из-за непоняток в терминологии
дело в том, что термин "некорректный" используется не только для охарактеризования каких-либо утверждений/определений
есть также понятие корректности задачи математичкской физики
например, http://a-server.math.nsc.ru/IPP/BASE_DEF/ukz.htm (первая попавшаяся ссылка из google'а)

так что, как операция, численная производная определена корректно, но само её вычисление представляет собой некорректную задачу (в смысле мат.физики) 

Автор: popovda 16.6.2006, 20:58
Отвечаю esperant0.

Ну это уже подмена терминов!!!
Во-первых, целые числа --- это целые числа! На ЭВМ они вообще представляются строгим порядком битов (в пределах размера типа данных). Т.е. однозначно!!! Это раз. Погрешности у целых чисел не накапливается. Это два.

Не забывайте о том, как хранятся ЦЕЛЫЕ (integer) и ВЕЩЕСТВЕННЫЕ (real или float,double) числа. Если Вы найдете в целом типе данных мантиссу, сообщите мне об этом. Я порадую сотрудников ВЦ.

Во-вторых, я уже писал, что термин "некоректный" не означает "неверный", а означает, что задачи такого типа должны решаться либо определенными методами, либо с осторожностью и обоснованностью (прежде всего математически). Я, вроде бы, проблемы, возникающие при малых h обосновал. Но я НИ В ОДНОМ МЕСТЕ НЕ СКАЗАЛ, ЧТО ТАК ВЫЧИСЛЯТЬ ПРОИЗВОДНЫЕ НЕЛЬЗЯ. Их так вычисляют все. А задавшего вопрос, я предостерег от ошибки, которую часто совершают.Правда конечных разностей можно выписать бесконечно много. 

В-третьих, вычисления на ЭВМ всегда приближенные, прежде всего в силу того, что порядок и мантисса числа ограниченны размером регистра, кроме того советую помнить определение вещественного числа. Поэтому всегда речь идет о заданной точности. Думаю, Вам хватит 10^-5..10^-6. Больше для производной нет смысла в силу сказанного выше. И какой тип данных Вы используете.

Напоследок вопрос: меняется ли сумма при перемене мест слагаемых? Кстати, на предыдущую задачу я ответа не получил.

И еще. Пусть заданны 2 ВЕЩЕСТВЕННЫХ числа:
a и b. Как Вы проверите, одинаковы ли они?  

Отвечаю maxim1000.

Понятие некорректности численного вычисления производной и понятие некорректности задачи МФ. Это все же разные вещи.
По-поводу корректности задачи УМФ, скажу проще, для тех, кто не знаком с функциональным анализом и УМФ.
Задача матфизики корректна, если:
1.  Ее решение существует.
2. Оно единственно.
3. Малому изменению параметра соответствует малое изменение решения.
С первыми 2-мя пунктами как в курсе обыкновенных ДУ.
А вот 3-ий и определяет корректность задачи и, если она некорректна, то методы ее решения, что уже как правило не тривиально.
Цитата

как операция, численная производная определена корректно, но само её вычисление представляет собой некорректную задачу (в смысле мат.физики) 

Все таки в смысле вычислительной математики. Полемика разгорелась из-за подмены термина "некорректный" на "неверный". Тут могу лишь посоветовать в толковый словарь почаще заглядывать. 
Кстати, а не сделать ли нам форум по вычислительной математике? 

Автор: maxim1000 16.6.2006, 21:37
Цитата(popovda @  16.6.2006,  19:58 Найти цитируемый пост)
Полемика разгорелась из-за подмены термина "некорректный" на "неверный". Тут могу лишь посоветовать в толковый словарь почаще заглядывать.

ну не совсем
"некорректность" также используется по отношению к разным определениям, утверждениям
(ещё с мат. анализа помню доказательства корректности некоторых определений, например)
Цитата(popovda @  16.6.2006,  19:58 Найти цитируемый пост)
Все таки в смысле вычислительной математики

ну тогда это - третье использование слова "некорректный" для обозначения понятия smile
хотя если подходить с таких позиций, то любые вычисления с вещественными числами в компьютере некорректны
впрочем, согласен, что в некоторых случаях обращать на это внимание "более необходимо", чем в других
и вычисление производной - тому пример
Цитата(popovda @  16.6.2006,  19:58 Найти цитируемый пост)
Кстати, а не сделать ли нам форум по вычислительной математике?

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

Автор: popovda 17.6.2006, 13:59
ОК. Подведем итогиsmile 

1. С производной все-таки разобрались. То есть на вопрос ответили. Так что не будем выходить из рамок темы.

2. С терминалогией тоже. Главное, я прошу не забывать, что численный анализ это научная дисциплина со строгими доказательствами. И, кроме того, с чего начинается любой приличный курс по вычмату? С понятия погрешности и значащих цифр.

3. По поводу форума: действительно, можно посмотреть количество обращений.

4. А задачки мои так и остались без ответов. 

Автор: esperant0 17.6.2006, 14:29
Сумма от порядка вычислений не должна меняться,но на неудачной моделе ЭВМ, она может меняться в зависимости от различных параметров.


Только мне не понятно, почему вы отвергаете модель ЭВМ увеличивающую размер мантисы(точность) по мере надобности.  

Автор: popovda 17.6.2006, 17:08
Цитата

Сумма от порядка вычислений не должна меняться,но на неудачной моделе ЭВМ, она может меняться в зависимости от различных параметров.

В ЛЮБОМ УЧЕБНИКЕ ПО ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКЕ есть этот пример. И на любой ЭВМ он будет работать! 

Цитата

Только мне не понятно, почему вы отвергаете модель ЭВМ увеличивающую размер мантисы(точность) по мере надобности.

Интересно, где Вы видели такую модель ЭВМ?
Размер вещественного типа данных определен архитектурой процессора. А всякие "длинные числа"
не удовлетворяют вычислителей по времени работы с ними. Потому, кстати, чаще всего и используют double. 
В идеале вообще - 1 операция - один такт. 
Прежде чем вступать в спор, рекомендую разобраться в вопросе. В данном случае к требованиям, предьявляемым чисметодам. 
 

Автор: esperant0 17.6.2006, 19:46
Цитата(popovda @ 17.6.2006,  17:08)
Цитата

Сумма от порядка вычислений не должна меняться,но на неудачной моделе ЭВМ, она может меняться в зависимости от различных параметров.

В ЛЮБОМ УЧЕБНИКЕ ПО ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКЕ есть этот пример. И на любой ЭВМ он будет работать! 

Цитата

Только мне не понятно, почему вы отвергаете модель ЭВМ увеличивающую размер мантисы(точность) по мере надобности.

Интересно, где Вы видели такую модель ЭВМ?
Размер вещественного типа данных определен архитектурой процессора. А всякие "длинные числа"
не удовлетворяют вычислителей по времени работы с ними. Потому, кстати, чаще всего и используют double. 
В идеале вообще - 1 операция - один такт. 
Прежде чем вступать в спор, рекомендую разобраться в вопросе. В данном случае к требованиям, предьявляемым чисметодам.

Я знаю про этот пример, но он не будет работать на любой ЭВМ..


Скажите вам знакомо понятие машины тьюринга?


Так вот для любой суммы существует машина тьюринга вычисляющая ее верно не в зависимости от порядка суммирования.


А в для ЛЮБОЙ эвм, конечно же нет. 

Автор: popovda 17.6.2006, 20:29
Знаю я про машину Тьюринга. Но покажите мне хотя бы один кластер, созданный по ее принципу. Это раз.
И два - размера вещественных данных в 128 бит (на очень дорогих кластерах уже давно 64 разрядные регистры) более
чем достаточно для всех необходимых вычислений. 
Кроме того,  как вы распаралелите работу с такими данными (время записи/чтения, например)? Рекомендую Воеводиных или Эндрюса.
Напоследок. Я жду ответа на заданные Вам задачки. Обоснованного ответа. 

И, потом, серьезные организации ориентируются на имеющийся рынок, оценивают оправданность затрат, и только потом принимают решение о закупке и внедрении. А не ищут гипотетических путей. Задача должна решаться с минимальными расходами для максимальной эффективности. 

Автор: esperant0 17.6.2006, 22:48
Задачка на понимание: чем численно решать систему из N линейных уравнений и почему? N>10^3 


Ответ зависит от многих параметров.

Если система специальо разреженаная и известен сорт - разреженности, то может понадобиться разработать индивидуальный случай.


Можно решать иттерационными методами, перед этим применив преобразования гарантирующие сходимость. В данных методах погрешность не накапливаеться, и преобразования сжатия делают свое черное дело, сжимая в решение.


Не итерационные методы(например метод илюминации Гауса) как правило не рекомендуются в таких случаях, а если и используются, то с различными дополнениями, как pivotal elumination, но все же как правило для больших систем ошибки накапливаются слишком большие.

Также надо учитывать временную сложность, работы алгоитмов. Для метода гауса она порядка куба от количества переменных. Одна итерация метода зайделя порядка квадрата от количества переменных.

вот все что вспомнилось навскидку
 

Автор: popovda 18.6.2006, 15:48
Имелся ввиду общий случай.
Верно! В итерационных методах ошибка не накапливается. После некоторых преобразований матрицы. А как - это известный фокус. Домножаем систему слева на A-транспонированную матрицу.
Цитата

Для метода гауса

Метод Гаусса (все же Гаусс - великий математик и не следует его унижать smile ) не  используется потому, что погрешность накапливается на каждом шаге и как бы изначально хорошо не была обусловлена матрица. Т.е.,например, и | det A |>>0. То с каждым шагом определитель будет стремиться к нулю. А в итерационных методах каждое приближение зависит только от предыдущего приближения (или НЕСКОЛЬКИХ предыдущих<< размерности системы) и, соответственно, накопление ошибки идет только от предыдущего приближения и не превосходит ее. Со своей стороны я уже давно считаю, что подробно ответил на поставленный вопрос и не вижу смысла продолжать дискуссию Это уже переходит в  smile .
  

Автор: maxim1000 18.6.2006, 16:12
Цитата(popovda @  18.6.2006,  14:48 Найти цитируемый пост)
Со своей стороны я уже давно считаю, что подробно ответил на поставленный вопрос и не вижу смысла продолжать дискуссию Это уже переходит в   

что правда, то правда
а потому выделю в отдельную тему (думаю, она сама по себе будет интересна) 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)