Идентификация ошибок в квадратичных уравнениях

Question

Предположим, вы пишите программу Python для вычисления вещественных корней топора + bx + c = 0, где приведены коэффициенты a, b и c, действительные числа. Традиционные формулы для двух растворов

x1 = (-b - sqrt(b*b-4*a*c))/2a, 
x2 = (-b + sqrt(b*b-4*a*c))/2a. 

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

Что мне нужно сделать?

Answer 1

Существует две ситуации, когда возникают проблемы. Во-первых, когда термин внутри квадратного корня (далее «дискриминантного») становится отрицательным, т.е.

if(b*b - 4*a*c < 0): 
    # do something. This doesn't have real roots 

второй является более тонким. Когда вы вычитаете два больших числа, которые имеют почти одинаковый размер, существует вероятность ошибки округления. Это произойдет для меньшего корня, когда 4*a*c << b*b. Вы могли бы сделать разложение в ряд:

b - sqrt(b*b - 4*a*c) 
= b * (1 - sqrt(1 - 4 * a * c/(b * b))) 
~ b * (1 - 1 + 2 * a * c/(b * b))  # when 4*a*c << b*b 

Этот термин становится

2 * a * c/b 

Таким образом, окончательный корень будет

x1 = - c/b 

Какой интересный результат. Конечно, другой корень еще

x2 = (b + sqrt(b * b - 4 * a * c))/(2 * a) 

Не так много распространения ошибок там - хотя можно сказать, что она будет иметь тенденцию к

x2 = - b/a 

когда с становится очень малой.

Все это не имеет ничего общего с Python - это основная математика. И я, возможно, сделал ошибки - идите вперед и посмотрите, сможете ли вы их найти.

Для получения дополнительной помощи вы можете захотеть взглянуть на http://en.wikipedia.org/wiki/Quadratic_equation#Floating-point_implementation

который обеспечивает обработку этого вопроса с точки зрения численной устойчивости. Вы найдете, среди прочего, что выведенные выше уравнения I (re) называются «формулой Витеа».