Введение
Алгоритм поиска нуля функции, поиск нулей непрерывных функций
searching zeros of continuous functions
В математике метод бисекции (или деления пополам) — это метод поиска корня, применимый к любой непрерывной функции, для которой известны два значения с противоположными знаками. Метод заключается в многократном делении пополам интервала, заданного этими значениями, и последующем выборе подинтервала, в котором функция меняет знак, и, следовательно, должен содержать корень. Это очень простой и надёжный метод, но он также относительно медленный. По этой причине он часто используется для получения грубого приближения к решению, которое затем служит начальной точкой для более быстро сходящихся методов. Метод также называют методом деления интервала пополам, методом бинарного поиска или методом дихотомии. Для полиномов существуют более сложные методы проверки существования корня в интервале (правило знаков Декарта, теорема Штурма, теорема Будана). Они позволяют расширить метод бисекции до эффективных алгоритмов для нахождения всех вещественных корней полинома; см. Изоляция вещественных корней.
Метод
Метод применим для численного решения уравнения f(x) = 0 для вещественной переменной x, где f — непрерывная функция, определенная на интервале [a, b], и где f(a) и f(b) имеют противоположные знаки. В этом случае говорят, что a и b заключают корень, поскольку, согласно теореме о промежуточных значениях, непрерывная функция f должна иметь по крайней мере один корень в интервале (a, b). На каждом шаге метод делит интервал на две части, вычисляя середину интервала c = (a+b) / 2 и значение функции f(c) в этой точке. Если c является корнем, то процесс успешно завершен и останавливается. В противном случае существует только две возможности: либо f(a) и f(c) имеют противоположные знаки и заключают корень, либо f(c) и f(b) имеют противоположные знаки и заключают корень. Метод выбирает подинтервал, который гарантированно заключает корень, в качестве нового интервала для следующего шага. Таким образом, интервал, содержащий корень f, уменьшается в ширине на 50% на каждом шаге. Процесс продолжается до тех пор, пока интервал не станет достаточно малым. В частности, если f(c) = 0, то c можно принять за решение, и процесс останавливается. В противном случае, если f(a) и f(c) имеют противоположные знаки, то метод присваивает c новое значение b, а если f(b) и f(c) имеют противоположные знаки, то метод присваивает c новое значение a. В обоих случаях новые f(a) и f(b) имеют противоположные знаки, поэтому метод применим к этому меньшему интервалу.
Итерационные задачи
Входными данными для метода являются непрерывная функция f, интервал [a, b] и значения функции f(a) и f(b). Значения функции имеют противоположные знаки (в интервале есть хотя бы один ноль функции). Каждая итерация выполняет следующие шаги: вычислить c, среднюю точку интервала, c = (a+b)/2. Вычислить значение функции в средней точке, f(c). Если сходимость удовлетворительна (то есть, |c - a| достаточно мало, или |f(c)| достаточно мало), вернуть c и прекратить итерацию. Проверить знак f(c) и заменить либо (a, f(a)) или (b, f(b)) на (c, f(c)) так, чтобы в новом интервале сохранялся ноль функции. При реализации метода на компьютере могут возникнуть проблемы с конечной точностью, поэтому часто используются дополнительные тесты сходимости или ограничения на количество итераций. Хотя f непрерывна, конечная точность может препятствовать тому, чтобы значение функции когда-либо стало равным нулю. Например, рассмотрим f(x) = cos x; не существует значения с плавающей точкой, которое бы давало точно ноль. Кроме того, разница между a и b ограничена точностью представления чисел с плавающей точкой; то есть, по мере уменьшения разницы между a и b, в какой-то момент средняя точка интервала [a, b] станет численно идентичной (в пределах точности представления чисел с плавающей точкой) либо a, либо b.
Calculate c, the midpoint of the interval, c = Calculate the function value at the midpoint, f(c). If convergence is satisfactory (that is, c a is sufficiently small, or |f(c)| is sufficiently small), return c and stop iterating. Examine the sign of f(c) and replace either (a, f(a)) or (b, f(b)) with (c, f(c)) so that there is a zero crossing within the new interval. ME = bfe
When implementing the method on a computer, there can be problems with finite precision, so there are often additional convergence tests or limits to the number of iterations. Although f is continuous, finite precision may preclude a function value ever being zero. For example, consider 1=f(x) = cos x; there is no floating point value approximating that gives exactly zero. Additionally, the difference between a and b is limited by the floating point precision; i. e., as the difference between a and b decreases, at some point the midpoint of [a, b] will be numerically identical to (within floating point precision of) either a or b.
Обобщение в более высоких измерениях
Метод бисекции был обобщен на многомерные функции. Такие методы называются обобщенными методами деления пополам.
Методы, основанные на вычислении степеней
Некоторые из этих методов основаны на вычислении топологической степени.
Характерный метод бисекции
Метод половинного деления использует только знаки функции в различных точках. Пусть f – функция из Rd в Rd, для некоторого целого числа d ≥ 2. Характерный многогранник (также называемый допустимым многоугольником) функции f – это многогранник в Rd, имеющий 2d вершин, такой что в каждой вершине v комбинация знаков f(v) уникальна. Например, для d=2, характерный многогранник f является четырехугольником с вершинами (скажем) A, B, C, D, таким образом, что: Знак f(A) = (–, –), то есть f1(A) < 0, f2(A) < 0. Знак f(B) = (–, +), то есть f1(B) < 0, f2(B) > 0. Знак f(C) = (+, –), то есть f1(C) > 0, f2(C) < 0. Знак f(D) = (+, +), то есть f1(D) > 0, f2(D) > 0. Правильное ребро характерного многоугольника – это ребро между парой вершин, для которых вектор знаков отличается только одним знаком. В приведенном выше примере правильными ребрами характерного четырехугольника являются AB, AC, BD и CD. Диагональ – это пара вершин, для которых вектор знаков отличается по всем d знакам. В приведенном выше примере диагоналями являются AD и BC. На каждой итерации алгоритм выбирает правильное ребро многогранника (скажем, AB) и вычисляет знаки f в его средней точке (скажем, M). Затем он действует следующим образом:
Sign f(A) = ( , ), that is, f1(A)<0, f2(A)<0. Sign f(B) = ( ,+), that is, f1(B)<0, f2(B)>0. Sign f(C) = (+, ), that is, f1(C)>0, f2(C)<0. Sign f(D) = (+,+), that is, f1(D)>0, f2(D)>0. A proper edge of a characteristic polygon is a edge between a pair of vertices, such that the sign vector differs by only a single sign. In the above example, the proper edges of the characteristic quadrilateral are AB, AC, BD and CD. A diagonal is a pair of vertices, such that the sign vector differs by all d signs. In the above example, the diagonals are AD and BC. At each iteration, the algorithm picks a proper edge of the polyhedron (say, A B), and computes the signs of f in its mid point (say, M). Then it proceeds as follows:
If Sign f(M) = Sign(A), then A is replaced by M, and we get a smaller characteristic polyhedron. If Sign f(M) = Sign(B), then B is replaced by M, and we get a smaller characteristic polyhedron. Else, we pick a new proper edge and try again. Suppose the diameter (= length of longest proper edge) of the original characteristic polyhedron is Then, at least bisections of edges are required so that the diameter of the remaining polygon will be at most .
Если Знак f(M) = Знак(A), то A заменяется на M, и мы получаем меньший характерный многогранник. Если Знак f(M) = Знак(B), то B заменяется на M, и мы получаем меньший характерный многогранник. Иначе мы выбираем новое правильное ребро и пробуем снова. Предположим, что диаметр (= длина самого длинного правильного ребра) исходного характерного многогранника равен δ. Тогда требуется, по крайней мере, ⌈log₂ (δ/ε)⌉ половинных делений ребер, чтобы диаметр оставшегося многоугольника был не больше ε.
Sign f(A) = ( , ), that is, f1(A)<0, f2(A)<0. Sign f(B) = ( ,+), that is, f1(B)<0, f2(B)>0. Sign f(C) = (+, ), that is, f1(C)>0, f2(C)<0. Sign f(D) = (+,+), that is, f1(D)>0, f2(D)>0. A proper edge of a characteristic polygon is a edge between a pair of vertices, such that the sign vector differs by only a single sign. In the above example, the proper edges of the characteristic quadrilateral are AB, AC, BD and CD. A diagonal is a pair of vertices, such that the sign vector differs by all d signs. In the above example, the diagonals are AD and BC. At each iteration, the algorithm picks a proper edge of the polyhedron (say, A B), and computes the signs of f in its mid point (say, M). Then it proceeds as follows:
If Sign f(M) = Sign(A), then A is replaced by M, and we get a smaller characteristic polyhedron. If Sign f(M) = Sign(B), then B is replaced by M, and we get a smaller characteristic polyhedron. Else, we pick a new proper edge and try again. Suppose the diameter (= length of longest proper edge) of the original characteristic polyhedron is Then, at least bisections of edges are required so that the diameter of the remaining polygon will be at most .