Cтраница 1
Алгоритм бисекции довольно медлителен, но зато абсолютно застрахован от неудачи. Если каждое вычисление f ( x) несложно, то обычно нет серьезных причин, чтобы отвергнуть этот метод. Единственная причина, почему мы не используем его - это то, что имеется другой алгоритм, ZEROIN, который гарантированно не может быть много медленней бисекции и быстрей ее, когда / - гладкая функция. Добавочная скорость очень полезна, если вычисление f ( x) требует много времени. [1]
Метод бисекции опирается на то, что непрерывная функция, меняющая знак в интервале, имеет нуль внутри этого интервала. Эту идею нелегко обобщить для локализации комплексных нулей аналитических функций. Одна родственная идея - это принцип аргумента: предположим, что / аналитична в области R комплексной плоскости, и пусть С - простая замкнутая кривая в R. Предположим, что когда z описывает контур С, f ( z) ровно один раз обходит начало координат. Тогда / имеет ровно один нуль внутри С. [2]
Если берется точка бисекции, то эта величина не нужна вовсе. [3]
Определенный формулой (3.3) алгоритм бисекции является интерполяционным и центральным. [4]
Как можно модифицировать теорему бисекции для определения параметров Т - и П - образной канонических схем, эквивалентных произвольному симметричному четырехполюснику. [5]
Поиск золотого сечения аналогичен методу бисекции для нахождения действительного нуля функции ( гл. [6]
Показывается, что этот алгоритм бисекции является интерполяционным центральным и почти оптимальным по сложности алгоритмом. [7]
Заметим, что комбинаторная сложность алгоритма бисекции равна двум. Отсюда заключаем, что е-сложность задачи S при использовании информации 91, е) ( см. определение 3.1 гл. [8]
Если ( Р, Q) - бисекция для А, то ( Ь) следует из определения факторизации. Аналогично показывается, что Q-суффиксный код. Отсюда вытекает и и, v v, что доказывает единственность разложения. [9]
Ясно, что в каждой итерации алгоритма бисекции приобретается один бит точности. Таким образом, при критерии f - a 2 - ( b - а) нужно t итераций. На машинах серий IBM 360 / 370 в арифметике с удвоенной точностью требуется приблизительно 56 итераций, чтобы сократить исходный интервал [1, 16] до двух последовательных чисел с плавающей точкой. [10]
Не требует каких-либо модификаций для больших задач метод бисекций. Известны случаи изучения с его помощью распределения собственных значений матриц Якоби, порядок которых превышал десятки тысяч. [11]
Для измерения пропускной способности соединительной сети часто применяется метод бисекции. Для этого из сети удаляется минимальное количество связей, так чтобы сеть распалась на две части. Затем суммируется пропускная способность удаленных линий связи. Если способов разбиения сети несколько, выбирается тот, при котором эта сумма минимальна. Чему равна бисекци-онная пропускная способность соединительной сети, представляющей собой куб 8x8x8, если пропускная способность каждой линии равна 1 Гбайт. [12]
Деление схемы двухтактного каскада на две полусхемы осуществляется с помощью теоремы бисекции ( деления), как это показано на рис. 5.6 линией MN. При анализе любой из полусхем трансформаторного двухтактного каскада транзистор и половина трансформатора, которая относится к этому плечу, заменяются их моделями или эквивалентными схемами. В результате получается эквивалентная схема одного плеча двухтактного каскада, которая анализируется методом эквивалентных схем или методом графов. При анализе оконечного каскада необходимо учитывать, что двухтактные оконечные каскады работают при большом уровне сигнала. Поэтому для них надо оценивать графическим путем максимальную мощность, которую может отдать УЭ в нагрузку, а также определять с помощью сквозной ДХ, как это делалось для бестрансформаторных двухтактных каскадов, нелинейные искажения, создаваемые каскадом. [13]
Вследствие этого методу Ньютона часто предшествует какой-нибудь глобально сходящийся алгоритм типа бисекции, прежде чем можно будет переключиться на быстро сходящиеся ньютоновы итерации. Таким образом, метод Ньютона зачастую является лишь завершающей процедурой более медленного, но зато гарантированного начального алгоритма. При таком комбинировании, к примеру, последние 25 или около того итераций бисекции могут быть заменены 6 ньютоновбгми шагами. [14]
Один из лучших имеющихся машинных алгоритмов для нахождения действительного нуля функции сочетает безотказность бисекции с асимптотической скоростью метода секущих в случае гладких функций. [15]