| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Некоторые аспекты машинных вычислений |
| Автор: esperant0 12.6.2006, 22:57 | ||
а можно поподробней? в чем некорректность? Модератор: Эта тема выделена из 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 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 16.6.2006, 16:05 | ||||
| Отвечаю на вопрос по данной полемике. Мне довелось быть дипломником д.ф.-м.н., профессора из ВЦ РАН, который на вычислительной математике собаку съел. И слушать его спецкурсы. Этот человек меня научил очень многому и в своих знаниях я уверен. Поэтому: 1.
2.
"Теория без практики мертва, а практика без теории слепа." Если аналитическое и численное значения производной не совпадают, то это и есть некорректность операции дифференцирования на ЭВМ. То есть требуются дополнительные ограничения и подходы. Как раз этот пример и иллюстрирует, во-первых, к каким последствиям может привести незнание (точнее, непонимание) вычислительных погрешностей, во-вторых, не цепляйтесь к термину "некорректная" - это не означает, что такой подход не применим, нужны методы. В данном случае простые. Но ведь некорректные задачи математической физики - сложные задачи - решают, и успешно. Только методы надо использовать СПЕЦИАЛЬНЫЕ. 3. По поводу машинного нуля - эпсилона - он для конкретной машины фиксирован. Подумайте, как его определить (в какую отрицательную степень надо возвести 10 (мы же в 10-ой с.сч. работаем), чтобы на ЭВМ это число обратилось в 0). 4. Задачка на понимание: чем численно решать систему из N линейных уравнений и почему? N>10^3 |
| Автор: esperant0 16.6.2006, 19:39 | ||
Но ведь и в математике 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 17.6.2006, 13:59 |
| ОК. Подведем итоги 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, 20:29 |
| Знаю я про машину Тьюринга. Но покажите мне хотя бы один кластер, созданный по ее принципу. Это раз. И два - размера вещественных данных в 128 бит (на очень дорогих кластерах уже давно 64 разрядные регистры) более чем достаточно для всех необходимых вычислений. Кроме того, как вы распаралелите работу с такими данными (время записи/чтения, например)? Рекомендую Воеводиных или Эндрюса. Напоследок. Я жду ответа на заданные Вам задачки. Обоснованного ответа. И, потом, серьезные организации ориентируются на имеющийся рынок, оценивают оправданность затрат, и только потом принимают решение о закупке и внедрении. А не ищут гипотетических путей. Задача должна решаться с минимальными расходами для максимальной эффективности. |
| Автор: esperant0 17.6.2006, 22:48 |
| Задачка на понимание: чем численно решать систему из N линейных уравнений и почему? N>10^3 Ответ зависит от многих параметров. Если система специальо разреженаная и известен сорт - разреженности, то может понадобиться разработать индивидуальный случай. Можно решать иттерационными методами, перед этим применив преобразования гарантирующие сходимость. В данных методах погрешность не накапливаеться, и преобразования сжатия делают свое черное дело, сжимая в решение. Не итерационные методы(например метод илюминации Гауса) как правило не рекомендуются в таких случаях, а если и используются, то с различными дополнениями, как pivotal elumination, но все же как правило для больших систем ошибки накапливаются слишком большие. Также надо учитывать временную сложность, работы алгоитмов. Для метода гауса она порядка куба от количества переменных. Одна итерация метода зайделя порядка квадрата от количества переменных. вот все что вспомнилось навскидку |
| Автор: popovda 18.6.2006, 15:48 | ||
| Имелся ввиду общий случай. Верно! В итерационных методах ошибка не накапливается. После некоторых преобразований матрицы. А как - это известный фокус. Домножаем систему слева на A-транспонированную матрицу.
Метод Гаусса (все же Гаусс - великий математик и не следует его унижать |
| Автор: maxim1000 18.6.2006, 16:12 | ||
что правда, то правда а потому выделю в отдельную тему (думаю, она сама по себе будет интересна) |