Локализация корней. Ясно, что задача локализации корней непрерывной функции на отрезке [a; b] не всегда разрешима, т.к

Ясно, что задача локализации корней непрерывной функции на отрезке [a; b] не всегда разрешима, т.к. существуют непрерывные функции, имеющие бесконечное количество корней. Например, непрерывная функция f(x) = имеет на отрезке [0; 1] бесконечно много корней: x₀ = 0, x_n = (n Î N ).

Другое ограничение на функции для успешного решения задачи локализации корней состоит в том, что при заданной допустимой погрешности D вычисления корней бессмысленно рассматривать интервалы [a_i; b_i ] с длиной b_i – a_i < D. Следовательно, процесс локализации корней не применим к функциям, у которых несколько корней сосредоточены на отрезке длины меньше D. Эта проблема возникает даже для простейших функций – многочленов от одного переменного: если степень многочлена n такова, что < D, и многочлен имеет n различных корней, то они не могут быть локализованы с заданной погрешностью D, т.к. расстояние между какими-то двумя корнями обязательно окажется меньше D.

Бессмысленно говорить о локализации корней с точностью D и в том случае, когда погрешность вычисления значений функции не меньше D. Как правило, современные ЭВМ позволяют вычислять элементарные функции с очень высокой точностью (десять и более цифр после запятой), так что при разумном выборе D подобная проблема возникает редко.

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

Теорема (о существовании корня непрерывной функции). Пусть f: [a; b] ® R – непрерывная функция, причём f(a)·f(b) < 0. Тогда функция f имеет корень r Î (a; b). Если функция строго монотонна на (a; b), то этот корень единственен на рассматриваемом отрезке [a; b].

Простейший (грубейший) алгоритм локализации корней:

1. разбиваем отрезок [a; b] точками a_i = a + i·D (1 £ i £ n–1, n = ) на части, считая a₀ = a и a_n = b;

2. вычисляем значения f_i = f(a_i) (0 £ i £ n);

3. если f_i = 0, то a_i – корень уравнения f(x) = 0, содержащийся в отрезке [a_i; a_i];

4. если f_i·f_i+1 > 0, то считаем, что на отрезке [a_i; a_i+1] нет корней;

5. если f_i·f_i+1 < 0, то считаем, что [a_i; a_i+1] содержит один корень.

Таким образом, будут найдены не более n отрезков вида [a_i; b_i ], где b_i = a_i или b_i = a_i+1, на каждом из которых считается, что функция имеет ровно один корень. Если эти отрезки не пересекаются, то задача локализации корней решена. Если же среди полученных отрезков встречаются два соседних [g; d ] и [d; e ], то f(d) ¹ 0, и можно найти такое малое x > 0, что числа f(d – x) и f(d + x) имеют один знак с f(d). После этого пересекающиеся интервалы [g; d ] и [d; e ] можно заменить на непересекающиеся [g; d – x] и [d + x; e ].

Конечно, этот алгоритм слишком примитивен. Он может пропускать корни, не замечать корней на некоторых отрезках [a_i; a_i+1], или видеть на этом отрезке только один корень вместо нескольких.

Примеры: 1. Локализовать корни уравнения x – cos 2·x = 0 с погрешностью D = 0, 5.

В предыдущей серии примеров было получено ограничение корней: x Î [–1; 1]. Следуя алгоритму локализации, полагаем a₀ = –1, a₁ = –0, 5, a₂ = 0, a₃ = 0, 5, a₄ = 1 и вычисляем значения функции f(x) = x – cos 2·x в каждой точке:

Таким образом, предложенный алгоритм локализации корней выделяет один корень на отрезке [a₃; a₄] = [0, 5; 1]. Можно убедиться, что рассматриваемое уравнение действительно имеет единственный корень.

2. Локализовать корни уравнения 32·x³ – 48·x² + 22·x – 3 = 0 с погрешностью D = 0, 5.

По теореме о границах корней многочлена имеем , т.е. 0, 19 < |x| < 4. Замечая, что у многочлена f(x) = 32·x³ – 48·x² + 22·x – 3 нет отрицательных корней ( при x < 0 будет f(x) < 0), можно ограничиться отрезком [0, 19; 4].

Таким образом, предложенный алгоритм локализации корней выделяет один корень на отрезке [a₁; a₂] = [0, 69; 1, 19]. Это не соответствует действительности: на самом деле у многочлена f(x) есть три корня x₁ = 0, 25, x₂ = 0, 5 и x₃ = 0, 75.

Как улучшить этот метод? Например, можно произвести смещение узлов расчётной сетки a_i на , полагая a₀ = a – , a_i = a₀ + i·D (1 £ i £ n – 1), если, конечно, область определения функции позволяет это сделать:

Получается ещё один корень на отрезке [–0, 06; 0, 44].

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

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

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