Границы ошибки операции с плавающей точкой - PullRequest
Новая
       11

Границы ошибки операции с плавающей точкой

2 голосов
/ 06 апреля 2011

Учитывая уравнение ax^2 + bx + c, мы знаем, что дискриминант D = b^2 - 4ac говорит нам, будет ли уравнение иметь два различных корня D > 0, один повторный корень D = 0 или нет реальных корней D < 0.Ясно, что если дискриминант равен нулю, ошибка может сделать его положительным или отрицательным, в зависимости от того, где ошибка больше.Докажите, что если дискриминант отличен от нуля, то никакая ошибка в вычислении с плавающей запятой не может изменить его знак (т. Е. С положительного на отрицательный или с отрицательного на положительный).Может ли ошибка сделать дискриминант равным нулю?

Я знаю, что это имеет мало общего с фактическим программированием, но как именно я могу показать, что для floating point calculation error of the discriminant невозможно заставить положительный дискриминант D каким-то образом статьотрицательно и наоборот.

Ответы [ 3 ]

2 голосов
/ 06 апреля 2011
  1. Утверждение не совсем верно, как написано. Он зависит от свойств двоичной арифметики с плавающей запятой и не обязательно будет выполняться, если вычисление было выполнено с другим основанием (оно не выполняется, например, в десятичной плавающей запятой IEEE-754) , По общему признанию, это крайний крайний случай, и я не ожидал, что это будет обсуждаться на курсе бакалавриата. Тем не менее, это также подсказка, на которую я вам и указываю.
  2. Катастрофическая отмена не играет роли.
  3. Доказательство почти сразу следует из основных свойств двоичной арифметики с плавающей точкой.

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

Наконец: привыкните к домашним заданиям, которые вы не знаете, как делать, особенно на курсах теоретической CS или математики. Если бы вы уже знали, как это сделать, вы бы ничего не изучали, и какой в ​​этом смысл?

Редактировать: Эрик Постпишил прав, что утверждение также ложно для некоторых краевых случаев даже в двоичной арифметике.

2 голосов
/ 10 апреля 2011

Утверждение о том, что если оценка дискриминанта дает ненулевой результат, он имеет тот же знак, что и математически точный дискриминант, неверно. Поскольку это домашнее задание, я пока не скажу больше, за исключением подсказки: учтите, что возможен недостаточный или переполненный объем, даже если конечный результат не будет выходить за пределы диапазона чисел с плавающей запятой.

0 голосов
/ 06 апреля 2011

Я думаю, что это связано с тем, что проверка, является ли определитель положительным или отрицательным, действительно проверяет, больше или меньше b^2, чем 4ac.

В обоих случаях вы умножаете два числа, поэтому ошибка будет (похожей)? Похоже, это то, что вы ищете.

Но если довести дело до крайности, если, например, ваши числа являются числами с плавающей запятой, а "ошибка" на самом деле просто использует целые числа, то можно изменить знак:

a = 2, b = 2, c = 2/3

Определитель: D = 2 ^ 2-4 * 2 * 2/3 = -1,333

Принимая ошибку, она округляет c до 0, и определитель становится: D = 2 ^ 2 - 0 = 4

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

Подробнее ...

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

Так, например, если abs(b^2) намного больше, чем abs(4ac), то определитель будет знаком abs(b^2) ... и наоборот.

...