При вычислении корней квадратного уравнения a x^2 + b x + c = 0 в арифметике с плавающей точкой стандартная формула через дискриминант иногда даёт потерю значащих цифр; объясните, в каких случаях это происходит, и предложите альтернативную численно устойчивую схему вычисления корней

8 Окт в 11:38
7 +1
0
Ответы
1

Коротко — в чём проблема и как её исправить.

1) Почему теряются значащие цифры
Стандартная формула
x = −b±sqrt(b2−4ac)-b ± sqrt(b^2 − 4ac)b±sqrt(b24ac) / 2a2a2a даёт потерю значащих цифр, когда подвыражения, которые вычитаются, близки по величине. Это происходит при большом |b| и малом 4ac по сравнению с b^2, т.е. когда b^2 ≫ 4ac. Тогда sqrtDDD ≈ |b|, и один из числителей
−b + sqrtDDD или −b − sqrtDDD становится разностью двух почти равных чисел — в результате происходит катастрофическое вычитание и теряется точность (особенно для корня, соответствующего знаку «+», если b>0, и для «−», если b<0).

2) Какой корень страдает
Если b > 0, то проблемный корень — тот, где стоит +: x1 = −b+sqrt(D)−b + sqrt(D)b+sqrt(D) / 2a2a2a онмалпомодулюон мал по модулюонмалпомодулю.
Если b < 0, то проблемный — с «−»: x2 = −b−sqrt(D)−b − sqrt(D)bsqrt(D) / 2a2a2a.

3) Численно устойчивая схема рецептрецептрецепт Вместо прямого вычисления обоих корней используйте промежуточную величину
q = −0.5 b+sign(b)</em>sqrt(D) b + sign(b) </em> sqrt(D) b+sign(b)</em>sqrt(D),
где signbbb = +1 для b ≥ 0 и −1 для b < 0. Тогда один корень вычисляется как
x1 = q / a,
а второй — через соотношение произведения корней c/a:
x2 = c / q.

Пояснение: q = −b−sign(b)⋅sqrt(D)−b − sign(b)·sqrt(D)bsign(b)sqrt(D)/2 — это не даёт вычитания почти равных величин мыскладываемчислаодногознакамы складываем числа одного знакамыскладываемчислаодногознака, поэтому q вычисляется точно. Затем второй корень получаем делением c на первый корень — это также устойчиво.

4) Алгоритм псевдокодпсевдокодпсевдокод Если a == 0: решаем линейное b x + c = 0.
Иначе:

D = bb − 4a*cесли D < 0: корни комплексные — аналогично используем sqrtcomplex(D)complex(D)complex(D)sqrtD = sqrtDDDs = (b >= 0) ? 1 : −1q = −0.5 b+s</em>sqrtDb + s </em> sqrtDb+s</em>sqrtDесли q != 0:
x1 = q / a
x2 = c / q
иначе q==0,случайдвойногокорняиличисленноблизкогоq == 0, случай двойного корня или численно близкогоq==0,случайдвойногокорняиличисленноблизкого:
x1 = x2 = −b / 2∗a2*a2a

5) Пример иллюстрацияиллюстрацияиллюстрация a = 1, b = 1e8, c = 1.
Точный маленький корень ≈ −1e−8. Прямая формула для малого корня вычисляет −b+sqrt(D)−b + sqrt(D)b+sqrt(D) / 2a2a2a — вычитание двух ≈1e8 величин и в стандартной двойной точности часто даст ноль или сильно потерянную точность. Устойчивый метод: s = +1, q = −0.5*b+sqrtDb + sqrtDb+sqrtD ≈ −1e8, x_big = q/a ≈ −1e8, x_small = c/q ≈ −1e−8 — точно.

6) Замечания

Обрабатывать случай a = 0 отдельно. Если коэффициенты могут быть очень большими/маленькими, полезно предварительное шкалирование нормировкакоэффициентовнормировка коэффициентовнормировкакоэффициентов, чтобы избежать переполнения/денормализации при вычислении b^2 или sqrtDDD. Для комплексных корней аналогичный приём сохраняет устойчивость при выборе знака для суммирования. Для особо критичных задач предпочтительно использовать расширённую точность longdoublelong doublelongdouble или библиотеки с произвольной точностью.

Итого: используйте формулу с q = −0.5b+sign(b)</em>sqrt(D)b + sign(b)</em>sqrt(D)b+sign(b)</em>sqrt(D) и второй корень через c/q — это стандартный численно устойчивый приём для квадратных уравнений.

8 Окт в 12:55
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир