Модуль: Бинарный поиск. Практика

Рассмотрим задачу:
Найти корень уравнения \(x^2 + \sqrt x = C\). Это монотонно возрастающая функция, определенная для неотрицательных значений
С помощью компьютера точное значение найти невозможно. Оценим возможные подходы.
Пусть:

•  \(x_0 : x_0^2 + \sqrt{x_0} = C\) - корень уравнения
•  \(x_L : x_L <= x_0, x_L^2 + \sqrt{x_L} = C_L\) - найденная оценка "слева"
•  \(x_R : x_R >= x_0, x_R^2 + \sqrt{x_R} = C_R\) - найденная оценка "справа"
• acc - параметр, определяющий достаточную точность (положительное число)

Какие варианты постановки задач могут быть:

1.  Абсолютная точность (по аргументу), то есть требование \(|x_R - x_L| \leq acc\) (Например: с точностью не менее 0,001/трех знаков после запятой)
   Условие \(|x_R - x_L| \leq acc\) с учетом \(x_L \leq x_0 \leq x_R\) гарантирует \(|x_0 - x_L| \leq acc;\ \ |x_0 - x_R| \leq acc \)
2.  Абсолютная погрешность (по значению), то есть требование \(|С_R - С| \leq acc\)  и/или \(|С_L - С| \leq acc\) (Например: с погрешность не менее 0,001/трех знаков после запятой)
   Для монотонных функций можно использоваить \(|С_R - С_L| \leq acc\)
3.  Относительная точность (по аргументу), то есть требование \(\frac{|x_R - x_0| }{|x_0|}\leq acc; \frac{|x_L - x_0| }{|x_0|}\leq acc; \) (Например: с точностью не менее 6 знаков)
   Поскольку значение корня неизвестно, то требование можно усилить, потребовав выполнение совпадения знаков для   \(x_R , x_L\), то есть \(\frac{|x_R - x_L| }{|x_L|}\leq acc; \frac{|x_L - x_R| }{|x_R|}\leq acc; \)
4. Относительная погрешность (по значению), то есть требование \(\frac{|С_R - С|}{|C|} \leq acc\)  и/или \(\ \ \frac{|С_L - С|}{|C|} \leq acc\) (Например: с погрешность не менее шести знаков)

Условия точности определяют количество шагов бинарного поиска и типа используемых аргументов.
Так, если С имеет порядок 10¹⁰,  то требование абслоютной погрешности не менее 6 знаков, есть требование получения более 10 точных знаков.
(при С порядка 10²⁰ с переменными типа double не выполнимо). Таким образом, наиболее разумным,  является требование относительной точности/погрешности