вычисление квадратного корня методом деления отрезка пополам
Метод вычисления корня функции с помощью деления отрезка пополам в общем случае уже был рассмотрен в разделе 1.5.2. Пусть надо найти квадратный корень из неотрицательного вещественного числа a с заданной точностью ?. Задача сводится к нахождению корня функции
y = x2-a
на отрезке [0,b], где b = max(1,a). На этом отрезке функция имеет ровно один корень, поcкольку она монотонно возрастает и на концах отрезка принимает значения разных знаков (или нулевое значение при a = 0 или a = 1).
Идея алгоритма состоит в том, что отрезок делится пополам и выбирается та половина, на которой функция принимает значения разных знаков. Эта операция повторяется до тех пор, пока длина отрезка не станет меньше, чем ?. Концы текущего отрезка содержатся в переменных x0, x1. В данном случае функция монотонно возрастает при x
Приведем полный текст программы:
#include <stdio.h> // Описания стандартного ввода-вывода
int main() { double a; // Число, из которого извлекается корень double x, x0, x1; // [x0, x1] - текущий отрезок double y; // Значение ф-ции в точке x double eps = 0.000001; // Точность вычисления корня
printf("Введите число a:\n"); scanf("%lf", &a);
if (a < 0.0) { printf("Число должно быть неотрицательным.\n"); return 1; // Возвращаем код } // некорректного завершения
// Задаем концы отрезка x0 = 0.0; x1 = a; if (a < 1.0) { x1 = 1.0; }
// Утверждение: x0 * x0 - a <= 0, // x1 * x1 - a >= 0
while (x1 - x0 > eps) { // Инвариант: x0 * x0 - a <= 0, // x1 * x1 - a >= 0 x = (x0 + x1) / 2.0; // середина отрезка [x0,x1] y = x * x - a; // значение ф-ции в точке x
if (y >= 0.0) { x1 = x; // выбираем левую половину отрезка } else { x0 = x; // выбираем правую половину отрезка } }
// Утверждение: x0 * x0 - a <= 0, // x1 * x1 - a >= 0, // x1 - x0 <= eps x = (x0 + x1) / 2.0; // Корень := середина отрезка
// Печатаем ответ printf("Квадратный корень = %lf\n", x);
return 0; // Возвращаем код успешного завершения }
Отметим, что существует более быстрый способ вычисления квадратного корня числа - метод итераций Ньютона, или метод касательных к графику функции, но здесь мы его не рассматриваем.
