Методы последовательного сокращения интервала неопределенности

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

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

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

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

При желании вы можете использовать параболическую интерполяцию по трем точкам, взяв третью, например, тоже в середине интервала и вычислив координату точки пересечения параболы с осью абсцисс. Если значения аргумента на границах интервала c и d, то координата внутренней точки при линейной аппроксимации

x_вн= .

Итерации прекращаются, когда расстояние между соседними приближениями станет меньше заданной погрешности.

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