Как иначе называют метод бисекций

Метод бисекционного деления в тестировании

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

Если найти минимальные данные для воспроизведения, то:

• Вы сэкономите время разработчику — ему не придется подключаться к тестовому стенду, самому грузить файл и дебажить
• Менеджер сможет легко оценить приоритет задачи — это нужно срочно исправлять, или баг может подождать? Пока название «некоторые файлы падают, хз почему» — это сделать сложно.
• Описание бага от понимания причины падения тоже только выиграет.

Описание метода

Метод применяется для поиска точного места падения:

1. Взять падающую пачку данных.
2. Разбить пополам.
3. Проверить половину 1

• Если упало — значит, проблема там. Работаем дальше с ней.
• Если не упало → проверяем половину 2.

Метод позволяет довольно быстро локализовать проблему, особенно если это делается программно. Разработчики встраивают такие механизмы в обработку данных. А если не встраивают, то сами и страдают потом, когда к ним приходит тестировщик и говорит «Вот на этом файле падает, а точную причину я не смог найти».

Применение тестировщиками

Строка данных

Загрузили строку в 1 млн данных — система зависла.
Пробуем 500 тыс (поделили пополам) — все еще виснет.
Пробуем 250 тыс — не виснет, все ок.

Отсюда вывод, что проблема где-то между 250 и 500 тыс. Снова применяем бисекционное деление.

Пробуем 350 тыс (поделить «на глазок» — вполне допустимо, не надо упарываться на точные цифры при ручном воспроизведении) — все ок
Пробуем 450 тыс — плохо.
Пробуем 400 тыс — плохо.

В целом, уже можно заводить баг. От тестировщика очень редко требуется сообщить, что граница или баг находится четко в числе 286 586. Вполне достаточно локализовать ее примерно — 290 тысяч.

Просто одно дело — проверить «10» и сразу «300 тысяч», и совершенно другое — предоставить более полную информацию: «до 10 тысяч все ок, от 10 до 280 тысяч начинаются тормоза, на 290 тысячах уже падает».

Понятное дело, что когда количество измеряется в тысячах, искать конкретную грань вручную будет слишком долго. Да разработчику это и не нужно. Ну а терять время впустую не хочет никто.

Разумеется, если исходная проблема была на строке длиной в 10-30 символов, можно и точную границу найти. Все дело в разумном отношении ко времени — если с помощью догадок или бисекционного деления можно быстро найти точное значение и оно небольшое (до 100 обычно) — ищем точно. Если проблемы на больших строках, более 1000 → ищем примерно.

Загрузили файл — упал! Как, почему? Сначала пытаемся сами проанализировать, что могло повлиять, что проверял наш тест? В этом фишка главного правила «сначала позитив, потом негатив». Если не пытаться запихивать в один тест все и сразу:

• Проверили небольшой файл-образец
• Проверили огромный файл на 2гб, с кучей колонок, кучей столбцов, плюс разные вариации внутренних данных

• Много строк (но данные позитивные и проверенные ранее)
• Много столбцов
• Большой вес
• .

• Разделили файл на два по 50 тысяч, проверили первый.
• Если упал, делим его
• И так, пока не найдем конкретное место падения

Если падение зависит от количества строк — ищем границу примерную: «После 5000 падает, на 4000 тысячах нет». Искать конкретное место (4589), не надо. Слишком долго и не стоит затраченного времени.

Этот баг нашли студенты в Дадате. Туда можно грузить файлы с данными, система эти данные обработает и стандартизирует: исправит опечатки, определит недостающую информацию по справочникам (код КЛАДР, ФИАС, геокоординаты, район города, индекс. ).

Девочка попробовала загрузить большой файл и получила результат: система показывает прогресс-бар на 100% загрузки и при этом висит более 30 минут.

Дальше пошла локализация — когда начинается зависание? Это важно, так как влияет на приоритет задачи. Какой типовой объем загружаемых файлов? Как часто пользователи грузят прям МНОГО?

Может быть, система предназначена для обработки тысячи строк, тогда такой баг запихивается в «Исправить когда-нибудь». Или типовые загрузки — 10-50 тысяч строк, которые обрабатывают нормально, ну, значит, баг не горит, исправим чуть позже.

• для файла с 50 тыс строк висит секунд 15,
• для файла с 100 тыс строк висит секунд 30,
• для файла с 150 тыс строк висит 1 мин,
• для файла с 165 тыс строк висит 4 мин,
• для файла 172 тыс. строк при 100% заполненном прогресс-баре зависает больше чем на пол часа

Занимает проверка тоже не слишком много времени. Можно идти или с конца — вот мы загрузили 200 тысяч строк, а когда проблема начинается? Используем метод бисекционного деления!

Или начинаем с относительно небольшого числа — 50 тысяч, постепенно увеличивая (вдвое, метод бисекционного деления, только наоборот). Зная, что на 200 тысячах будет все плохо, понимаем, что тестов будет не сильно много. Проверили 50, 100, 150 — за три теста примерную границу нашли. А дальше копать уже и не надо.

Но помним, что свою теорию тоже надо тестировать. Правда ли, что проблема именно в количестве строк, а не данных внутри файла? Проверить это очень легко — создаете файл на 5000 строк с одним-единственным «позитивным» значением. Тем значением, которое точно работает, которое вы уже проверяли ранее. Если падения нет, значит, тут дело нечисто =)) Похоже, теория о количестве строк была ошибочная и дело в самих данных.

Хотя можно попробовать 10 тысяч строк с точно позитивным значением. Вполне возможно, что падение повторится. Просто ваш исходный файл был на несколько колонок. Или там внутри были символы, занимающие больше байт, чем позитивное значение… В общем, не стоит сразу отвергать теорию о размере файла или количестве строк. Попробуйте бисекционное деление наоборот — увеличьте файл вдвое.

Но в любом случае, помните о том, что чем больше проверок смешано в одной, тем сложнее локализовать баг. Поэтому лучше сразу тестировать количество строк или столбцов на каком-то одном позитивном значении. Чтобы вы были точно уверены, что тестируете количество данных, а не сами данные. Тест-анализ и все такое =)

А что делать, если проблема не в количестве строк, а в самих данных? И вы не знаете, где конкретно. Возможно, вы запихали в тестовый файл данные из «Войны и мира», или откуда-то из интернета скачали большую таблицу… Или проблему вообще нашел пользователь — он загрузил свой файл и у него все упало. Он пришел в саппорт, саппорт пришел к вам: на тебе файл, воспроизводи.

Дальнейшие действия зависят от ситуации. Если у пользователя горят сроки или с него сначала списались деньги, а потом обработка файла упала, то это блокер-баг. И тут нет времени на обучение тестировщика локализации. Проще отдать точно-падающий файл разработчику, пусть подебажит и найдет причину сам.

А вот если вы сами нашли ошибку, то есть время копнуть самому. Опять же, не забывая о здравом смысле, как всегда при локализации. Сначала попробовали сделать выводы сами, потом пошли за помощью. Чтобы сделать вывод самому, нужно:

• проверить логи, там может быть нужный ответ;
• просмотреть содержимое файла: что-то может броситься в глаза, вот и будет первая теория;
• использовать метод бисекционного деления.

Применение разработчиками

На большом объеме данных тестировщик не ищет четкую границу, потому что это неразумно делать вручную. А вот разработчики применяют метод бисекционного деления в коде и всегда могут найти конкретное место падения. Ведь делить до победного будет система, а не человек!

Например, у нас есть механизм загрузки данных в систему. Загружаться может как 10 тысяч, так и миллион. Но это не суть важно, так как загрузка идет пачками по 200 записей. Если что-то пошло не так, система сама проводит бисекционное деление. Сама. Пока не найдет проблемное место. В логах потом так и читаешь:

• Получил 1000 записей
• Обработал 200 записей
• Обработал 400 записей
• Упс, упал на пачке размером 200 записей!
• Пробую обработать пачку размером 100
• Пробую обработать пачку размером 50
• Пробую обработать пачку размером 25

• На таких-то идентификаторах ошибка: не заполнено обязательное поле Email
• Обработал 600 записей

Тут, конечно, дальнейшая логика тоже зависит от разработчика. Или обработка прекращается после того, как столкнулись с ошибкой, или идет дальше. Споткнулись на пачке в 200 записей? Доделились до того, чтобы найти узкое место, пометили запись как ошибочную, остальные 199 обработали, поехали дальше.

А вот что делать, если вся пачка разваливается? Пометили запись как ошибочную, но оставшиеся 199 тоже не смогли обработать. Почему? Применяем все тот же метод, ищем новую проблему. Фишка в том, что всегда надо уметь вовремя остановиться.

Если количество ошибок больше 10-50-100, то лучше остановить загрузку. Вполне возможно, что в исходной системе произошла ошибка выгрузки и мы получили миллион «кривых» данных. Если система будет каждую пачку в 200 записей делить пополам, а потом оставшиеся 199 делить, и так далее, то всем будет плохо:

• Лог разрастается с привычных 15 мб до 3 гб и становится нечитаем;
• Система может упасть на попытке генерации итогового сообщения об ошибках (я рассказывала о такой ситуации в разделе «Мнемоника БМВ» ) ;
• Много времени тратится на поиск всех ошибок. Да, система делает это быстрее, чем человек, но если делить миллион пачками по 200 записей, это займет время.

Резюме

Метод бисекционного деления применяется для поиска точного места падения и локализации бага.

Ищите число и начинайте делить его пополам:

• длина строки;
• размер файла;
• вес файла;
• количество строк / столбцов;
• объем свободной памяти в мобильнике;
• .

Но помните — когда-то придется остановится! Не надо упарываться и искать точное число, если это потребует проведения тысяч дополнительных тестов. А вот минут 5-10 уделить локализации можно.

PS — больше полезных статей ищите в моем блоге по метке «полезное»

XI Международная студенческая научная конференция Студенческий научный форум — 2019

Для решения уравнений, которые не удается решить аналитическими методами, используются численные методы. Алгоритм нахождения корня уравнения с помощью численного метода состоит из двух этапов: 1) отделение или локализация корня, т. е. установление промежутка [а; b], в котором содержится один корень; 2) уточнение значения корня методом последовательных приближений [4, с. 26].

Для численного решения уравнений f ( x )=0 существует множество методов. Среди итерационных методов уточнения корня с заданной точностью наиболее известными являются метод итераций, метод Ньютона, метод хорд, и, конечно, метод бисекций (метод половинного деления). Любой из данных методов является приближенным и уточняющим значение корня вплоть до точности, заданной нами.

Для решения методом бисекций в начале необходимо определить, является ли функция непрерывной и принимает ли значения противоположных знаков на отрезке [a; b]. Если значения функции на данных концах отрезка имеют противоположные знаки, то корень лежит в пределе отрезка [a; b]. Определить знак можно путем умножения значений функции на концах отрезка, сравнения результата умножения с нулём. После этого делим пополам отрезок [a; b] и дальше будем рассматривать ту половину, на концах которых функция принимает значения разных знаков. Смещаем в середину отрезка ту границу центра [a; b], у которой знак функции совпадает со знаком функции в центральной точке. Продолжаем этот процесс деления и смещения границ до тех пор, пока длина очередного отрезка, на котором находится корень, не будет меньше требуемой величины погрешности.

Алгоритм метода половинного деления:

Найдем середину отрезка [a; b]: x=(a+b)/2; f ( x );

Если значение функции f ( x )=0, то переходим к пункту 5;

Если произведение значений функций в точках x и a меньше 0, т.е. f ( x )* f ( a )<0, то теперь точкой b станет x ( b = x ); иначе точкой a станет x ( a = x );

Вычислим модуль разность b и a : если | b — a | > ε, то переходим к пункту 1;

Выводим значение x ;

Геометрическая иллюстрация метода бисекций представлена на рис. 1.

Рис. 1. Метод бисекций

Уточним методом бисекций с точностью до ε =0,01 корень уравнения x 2 +5x-1=0, принадлежащий отрезку [0,1; 1,5]. Функция y = x 2 +5x-1 является непрерывной на всей числовой прямой. Определяем половину отрезка x=(a+b)/2 и вычисляем f(x).

Проверяем следующие условия:

1. Если f(x)f(a)<0, то корень лежит на отрезке [a; x].

2. Если f(x)f(b)<0, то корень лежит на отрезке [x; b].

3. Если f(x)=0 или |b-a|<ε, то x – корень (ε — заданная точность).

Так как f(0,1)*f(1,5)<0, то корень лежит в пределах отрезка [0,1; 1,5].

1. Находим середину отрезка: x = (0,1 + 1,5)/2 = 0,8;

2. f(x) = 3,64; f(a) = — 0,49;

3. Так как f(x)*f(a) < 0, то b = 0,8;

Поступаем аналогично с другими итерациями:

1. x = (0,1 + 0,8)/2 = 0,45;

2. f(x) = 1,453; f(a) = — 0,49 ;

3. f(x)*f(a) < 0, b = 0,45;

1. x= (0,1 + 0,45)/2 = 0,275;

2. f(x) = 0,451; f(a) = — 0,49;

1. x = (0,1+0,275) / 2 = 0,1875;

2. f(x) = — 0.0273; f(a) = — 0.49

3. f(x)*f(a) > 0, a = 0,1875;

1. x = (0,1875 + 0,275)/2 = 0,23125;

2. f(x) = 0,02072; f(a) = — 0,0273;

3. f(x)*f(a)<0, b = 0,23125;

1. x = (0,1875 + 0,23125)/2 = 0,209375;

2. f(x) = 0,0907; f(a) = — 0,0273

3. f(x)*f(a) < 0, то b = 0,209375 ;

1. x = (0,1875 + 0.209375)/2 = 0,1984375;

2. f(x) = 0,0316; f(a)= — 0,0273.

3. f(x)*f(a) < 0, то b = 0,1984375;

1. x = (0,1875 + 0.1984375)/2 = 0,19296875;

2. f(x) = 0,0316; f(a)= — 0.0273;

3. f(x)*f(a) < 0, то b = 0,19296875;

1. x=(0,1875 + 0,19296875)/2 = 0,190234375;

2. f(x)= — 0,0126; f(a)= — 0,0273;

3. f(x)*f(a) > 0, тоa = 0,190234375;

Результаты расчетов приведены в таблице 1 в программе Excel.

В последнем столбце таблицы 1 проверяем значение длины интервала b-a. Если значение меньше 0,01, то в данной строке найдено приближенное значение корня с заданной погрешностью. Так как b-a=0,00546875 < ε = 0,01, то в качестве корня можно принять x = (0,1875 + 0,19296875)/2 = 0,190234375.

Потребовалось 9 итераций для достижения требуемой точности. Приближенное значение корня с точностью до 0,01 после округления до трех знаков равно x ≈ 0,19.

Метод бисекций является достаточно популярным, т.к. вычисления очень простые и цикличные. Он обладает достаточно быстрой сходимостью [3, с.191]. Его погрешность за каждую итерацию уменьшается в два раза. Существенным недостатком метода бисекций является то, что он не обобщается на системы нелинейных уравнений.

Бахвалов, Н. С. Численные методы / Н. С. Бахвалов, Н. П.Жидков, Г. М. Кобельков. – М.: БИНОМ. Лаборатория знаний, 2012. – 636с.

Васильев А. Н. Финансовое моделирование и оптимизация средствами Excel 2007. – СПб.: Питер, 2009. – 320с.

Волков Е. А. Численные методы. – СПб.: Лань, 2008. – 256с.

Практикум по вычислительной математике / Б.В. Соболь, Б.Ч. Месхи, И.М. Пешхоев. – Ростов н/Д : Феникс, 2008. – 342с.

Метод бисекции

Метод бисекции или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида f(x)=0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях.

Содержание

Обоснование

Алгоритм основан на следующем следствии из теоремы Больцано — Коши:

Пусть непрерывная функция , то .

Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть противоположных знаков. Разделим отрезок пополам и возьмём ту из половинок, на концах которой функция по-прежнему принимает значения противоположных знаков. Если значение функции в серединной точке оказалось искомым нулём, то процесс завершается.

Точность вычислений задаётся одним из двух способов:

1. , что ближе к условию из описания алгоритма; или
2. , по оси , что может оказаться удобным в некоторых случаях.

Процедуру следует продолжать до достижения заданной точности.

Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции.

Описание алгоритма

Задача заключается в нахождении корней нелинейного уравнения

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

Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов — умножение значений функции на концах отрезка и определение знака произведения путём сравнения результата умножения с нулём:

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

Для устранения переполнения и уменьшения затрат времени, т.е. для увеличения быстродействия, на некоторых программно-компьютерных комплексах противоположность знаков значений функции на концах отрезка нужно определять по формуле:

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

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

Найдём значение в середине отрезка:

в действительных вычислениях, для уменьшения числа операций, в начале, вне цикла, вычисляют длину отрезка по формуле:

а в цикле вычисляют длину очередных новых отрезков по формуле: и новую середину по формуле:

Вычислим значение функции в середине отрезка :

• Если или, в действительных вычислениях, , то корень найден.
• Иначе или, в действительных вычислениях, на два равных отрезка: и .

Теперь найдём новый отрезок, на котором функция меняет знак:

• Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке, или , то, соответственно, корень находится внутри левого отрезка . Тогда возьмём левый отрезок присвоением , и повторим описанную процедуру до достижения требуемой точности .
• Иначе значения функции на концах отрезка имеют противоположные знаки на правом отрезке, или , то, соответственно, корень находится внутри правого отрезка . Тогда возьмём правый отрезок присвоением , и повторим описанную процедуру до достижения требуемой точности .

За количество итераций деление пополам осуществляется раз, поэтому длина конечного отрезка в раз меньше длины исходного отрезка.

Существует похожий метод, но с критерием останова вычислений по оси [1] , в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси : . В этом методе отрезок на оси может достичь заданной величины , а значения функций (особенно крутых) на оси могут очень далеко отстоять от нуля, при пологих же функциях этот метод приводит к большому числу лишних вычислений.

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

Псевдокод

• x_n – начало отрезка по х;
• x_k – конец отрезка по х;
• x_i – середина отрезка по х;
• eps_y – требуемая точность вычислений по y (заданное приближение |F(x_i)| к нулю).

Тогда алгоритм метода бисекции можно записать в псевдокоде следующим образом:

1. Начало.
2. Ввод x_n, x_k, eps_y.
3. Если F(x_n) = 0, то Вывод (корень уравнения – x_n).
4. Если F(x_k) = 0, то Вывод (корень уравнения – x_k).
5. Пока |F(x_i)| > eps_y повторять:
6. dx := (x_k — x_n) / 2;
7. x_i := x_n + dx;
8. если sign(F(x_n)) ≠ sign(F(x_i)), то x_k := x_i;
9. иначе x_n := x_i.
10. конец повторять
11. Вывод (Найден корень уравнения – x_i с точностью по y — eps_y).
12. Конец.

Поиск значения корня монотонной дискретной функции

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

Пусть переменные леваяГраница и праваяГраница содержат, соответственно, левую левГран и правую правГран границы массива, в которой находится приближение к корню. Исследование начинается с разбиения массива пополам (на две части) путём нахождения номера среднего элемента массива середина.

Если знаки значений массива массив[леваяГраница] и массив[середина] противоположны, то приближение к корню ищут в левой половине массива, то есть значением праваяГраница становится середина и на следующей итерации исследуется только левая половина массива. Если знаки значений массив[леваяГраница] и массив[середина] одинаковы, то осуществляется переход к поиску приближения к корню в правой половине массива, то есть значением переменной леваяГраница становится середина и на следующей итерации исследуется только правая половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.

Например, если длина массива равна 1023, то после первого сравнения область сужается до 511 элементов, а после второго — до 255. Т.о. для поиска приближения к корню в массиве из 1023 элементов достаточно 10 проходов (итераций).