Идеи реализации

Метод бисекций, он же метод дихотомии, он же метод половинного деления основан на теореме Больцано — Коши. Теорема утверждает, что непрерывная на некотором отрезке функция, которая на концах этого отрезка принимает значения разных знаков, непременно обращается в нуль на отрезке.

Важное понятие непрерывности функции мы не станем здесь строго определять; это было бы уместней на занятиях по математическому анализу. Воздержимся также от доказательства теоремы. Скажем лишь, что метод бисекций многое заимствует из традиционного доказательства теоремы. Интуитивное представление о непрерывной функции, то есть такой, чей график на отрезке можно начертить, не отрывая карандаша от бумаги, делает утверждение теоремы совершенно очевидным. Действительно, непрерывная линия, у которой концы лежат в верхней и нижней координатных плоскостях, обязательно пересекает ось абсцисс.

Пусть функция f x непрерывна на отрезке l r и принимает на его концах значения разных знаков. Под знаком будем понимать плюс, минус или ноль. Обозначим как m середину отрезка. Теперь можно утверждать, что на одном из отрезков l m или m r функция принимает значения разных знаков. Таким образом, задача о поиске решения уравнения f x = 0 на отрезке l r сводится к аналогичной задаче поиска решения того же уравнения на одной из половинок отрезка, на которой, естественно, функция по-прежнему непрерывна.

Рисунок 19.1. Метод бисекций

Повторяя этот процесс, получим последовательность отрезков, в которой следующий является левой или правой половинкой предыдущего (рисунок 19.1. «Метод бисекций»). Если длины отрезков в последовательности неограниченно уменьшаются до нуля, а каждый следующий отрезок целиком содержится в предыдущем, отрезки называются стягивающимися. В математическом анализе доказывается, что у всех стягивающихся отрезков имеется единственная общая точка. Благодаря непрерывности функции это и есть корень уравнения. Обратим внимание, что теорема Больцано — Коши не утверждает единственности решения. Это метод доказательства позволяет предъявить единственное решение, возможно, пропустив какое-то другое. Если про функцию f x известно кое-что дополнительно, например, известно, что функция монотонна на отрезке, тогда можно утверждать и единственность решения — ведь монотонная функция не принимает дважды одно и то же значение, в частности, нулевое.

Применим все эти соображения к решению уравнения x 2 A = 0 . Функция в левой части, конечно же, непрерывна. На практике деление отрезка пополам до бесконечности производить невозможно, поэтому алгоритм следует рано или поздно остановить. Можно, например, остановиться, когда длина отрезка станет достаточно малой, и объявить приближённым решением середину отрезка. При таком подходе в программе следует предусмотреть малое числовое значение, которое будет отвечать за точность решения. Есть и другой подход, при котором не требуется задавать точность. Алгоритм сам найдёт настолько точное решение, насколько это вообще возможно, учитывая точность представления вещественных чисел на данном компьютере.

Если функция, помимо непрерывности, обладает некоторыми дополнительными свойствами, для поиска решения уравнения f x = 0 можно применить другой, более быстрый метод, называемый методом Ньютона или методом касательных. Как минимум, требуется (хоть этого и не всегда достаточно), чтобы график функции имел бы касательную в каждой своей точке. Точный смысл понятия «касательная» придаётся в математическом анализе. Но в нашем случае, когда f x = x 2 A , касательная к графику — это прямая, имеющая с графиком ровно одну общую точку.

Выберем в качестве начального приближения к искомому решению уравнения какое-то число X, а затем станем его постепенно уточнять в надежде, что числа в полученной последовательности неограниченно приблизятся к решению (рисунок 19.2. «Метод Ньютона»).

Рисунок 19.2. Метод Ньютона

Последовательные приближения строятся так. Пусть X k — очередное приближение. Проведём касательную к графику функции в точке X. Следующим приближением станет точка X k + 1 , в которой касательная пересечёт ось абсцисс. Так будем делать столько раз, сколько потребуется, чтобы обеспечить требуемую точность.

Линейная функция l x , чьим графиком является касательная в точке X к графику функции f x , оказывается наиболее близкой, в некотором смысле, к функции f x вблизи к точке X. Это даёт нам основание заменить трудное для решения уравнение f x = 0 на более простое, линейное l x = 0 . Хотелось бы надеяться, что точное решение приближённого уравнения является приближённым решением точного уравнения.

Теперь для данного очередного приближения X k найдём следующее, более точное X k + 1 , исходя из условий:

Пусть уравнение касательной имеет вид y = a x + b . Тогда перечисленные условия приводят к уравнениям, в которых неизвестными являются буквы a, b и X k + 1 : X k 2 A = a X k + b , a 2 + 4 A + b = 0 , a X k + 1 + b = 0 . Второе уравнение служит условием единственности решения первого, квадратного уравнения — мы приравниваем нулю дискриминант. Из первых двух уравнений, исключая A + b , получаем X k = a 2 , откуда b = X k 2 A . Подставляя найденные значения a и b в третье уравнение, получим X k + 1 = 1 2 X k + A X k .

Найденная формула для построения последовательных приближений к квадратному корню из числа A известна ещё с незапамятных времён, задолго до Ньютона. Это формула Герона (да, у Герона есть ещё и такая формула).

Читатели, знакомые с дифференциальным исчислением, могут вывести и общую формулу для построения последовательных приближений к решению уравнения f x = 0 . Составим уравнение касательной в точке X k : y f X k = f X k x X k . Условие прохождения касательной через точку X k + 1 0 записывается в виде X k + 1 = X k f X k f X k . Формула Герона находится в полном согласии с этой общей формулой.

По всей видимости, автор формулы Герона получил её вот из каких соображений. Рассмотрим прямоугольник со сторонами X и A X (его площадь равна A). Преобразуем его в другой прямоугольник с той же площадью, заменив сторону X на среднее арифметическое сторон, то есть на 1 2 X + A X . Похоже, что такое преобразование делает прямоугольник более квадратным, если можно так выразиться.

Главным достоинством метода Ньютона является сверхбыстрое приближение к точному решению уравнения (сверхсходимость). Исследуем это явление на примере формулы Герона. Для этого обозначим как R k = X k A ошибку, которую даёт k-е приближение. Подставив R k + A вместо X k в формулу Герона, получим R k + 1 = R k 2 2 R k + A . Выберем в качестве начального приближения X 0 число, заведомо большее, чем точное решение A . Это значит, что начальная ошибка R 0 положительна. Видно, что в этом случае ошибка на каждом шаге останется положительной, то есть последовательные приближения подкрадываются к решению справа. Тогда, очевидно, верны неравенства R k + 1 < R k 2 , R k + 1 < R k 2 2 A . Первое означает, что после каждого шага ошибка уменьшается как минимум вдвое. Это уже неплохо, но пока не выявляет никакого преимущества метода Ньютона перед методом бисекций. Но рано или поздно величина R k станет меньше, чем 2 A , после чего из второго неравенства будет следовать R k + 1 < R k 2 . Тут начинается самое интересное. Получается, что ошибка на каждом шаге, грубо говоря, возводится в квадрат. Если, к примеру, ошибка на данном шаге меньше 0,1, то на следующем она будет меньше 0,01, затем меньше 0,0001, затем меньше 0,00000001, и так далее. Всё это означает, что каждое новое приближение содержит как минимум на одну верную двоичную цифру больше, чем предыдущее, но, начиная с некоторого шага, количество верных цифр станет с каждым шагом удваиваться. Вот это уже и есть сверхсходимость.

Удачным выбором начального приближения будет X 0 = 1 + A 2 A (неравенство следует из формулы сокращённого умножения 1 2 A + A = 1 A 2 0 ).

Нам удалось доказать сходимость и даже сверхсходимость для метода Ньютона в случае уравнения x 2 A = 0 . В общем случае всё совсем не так гладко, даже если потребовать от функции в левой части уравнения наличия касательной в каждой точке графика (то есть дифференцируемости). Очевидную проблему создают точки, в которых касательная горизонтальна (где производная обращается в нуль). Если же касательная горизонтальна в самом корне уравнения, явления сверхсходимости уже не будет. Характерный пример даёт формула Герона для случая A = 0 : X k + 1 = X k 2 .

Другое типичное осложнение возникает в случае, когда уравнение имеет несколько решений. Последовательные приближения могут метаться между этими решениями, как бы решая, к какому стоит устремиться. Такая конкуренция корней уравнения в качестве центров притяжения приближений может привести к тому, что числа X k так и не выберут себе центр притяжения, и будут приближаться лишь к некоторому подмножеству решений уравнения, прыгая от одного решения из этого подмножества к другому. Зоны притяжения корней (бассейны) обычно разбивают числовую прямую на довольно причудливые подмножества. Стоит очередному приближению попасть на границу между двумя бассейнами, или где-то поблизости от границы, и дальнейшее поведение последовательности X k станет весьма хаотическим.

На самом деле существует взаимосвязь между двумя описанными проблемами, поскольку по теореме Ролля между двумя решениями уравнения f x = 0 непременно найдётся точка, в которой касательная к графику функции f x горизонтальна.

Обсуждая методы бисекций и Ньютона, мы намеренно всячески уклонялись от формулирования точных условий остановки алгоритмов.

У описанных алгоритмов имеется общая черта: в каждом из них строится некоторая последовательность, в которой каждый следующий элемент получается из предыдущего по одному и тому же правилу, иными словами, рекуррентная последовательность первого порядка. Для метода бисекций это последовательность стягивающихся отрезков, а в случае метода Ньютона — последовательные приближения. Из главы 15. «Десятичные дроби» мы уже знаем, что рекуррентные последовательности, составленные из элементов конечного множества, всегда зацикливаются. Последовательные приближения из метода Ньютона всегда монотонно убывают, и поэтому никак не могут зациклиться (для зацикливания необходимо и достаточно наличие двух равных элементов в последовательности, что полностью исключено при строгой монотонности). Но это и неудивительно, поскольку множество вещественных чисел бесконечно. Точно так же не стоит ожидать зацикливания в методе бисекций, поскольку множество отрезков на вещественной прямой (множество числовых пар) и подавно бесконечно.

Тем не менее при реализации обоих методов на компьютере зацикливание неизбежно. Дело в том, что точное представление вещественного числа в компьютерной памяти невозможно, поскольку числовое значение потребовало бы для хранения бесконечной памяти. Поэтому используется приближённое представление, в котором для числа отводится ограниченное количество бит. Число различных состояний этого битового набора конечно, хоть, может быть, и очень велико. Так что количество компьютерных вещественных чисел конечно; конечно и количество отрезков на вещественной прямой. Вывод, который следует сделать из всех этих наблюдений, таков: любая рекуррентная последовательность, построенная на компьютере, зацикливается.

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

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

Для обнаружения циклов прекрасно подойдёт техника, описанная в разделе «Метод Черепахи и Зайца». Для наших целей будет достаточно первого забега Черепахи и Зайца. Как только произойдёт их встреча, программа остановится.

Впрочем, следует заметить, что, применяя метод Ньютона к вычислению квадратного корня, совершенно не обязательно привлекать Черепаху и Зайца. Как мы уже заметили, рекуррентная последовательность приближений, строго монотонная согласно теории, на практике уже не может быть строго монотонной. Иными словами, найдётся такой номер k, что X k + 1 X k . Это значит, что последовательность начинает зацикливаться, и пора остановиться. Наше наблюдение примерно вдвое сокращает вычислительные затраты, если сравнивать с алгоритмом, использующим метод Флойда.

Информатика-54© А. Н. Швец