Метод хорд

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

Photo from PxHere.

Для примера возьмем следующую функцию пятого порядка:

x^5 - 7.15x^4 + 19.89*x^3 - 26.8565x^2 + 17.5838x - 4.4616 = 0.

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

Рисунок 1. Функция x^5 - 7.15x^4 + 19.89*x^3 - 26.8565x^2 + 17.5838x - 4.4616 = 0 на отрезке [0; 3].

На рисунке 1 приведена исследуемая функция, а первая итерация алгоритма проиллюстрирована на рисунке 2. Зеленая линия соединяет точки, расположенные на исследуемой функции f(x) на краях рассматриваемого интервала. Эта линейная функция проходит через ноль в точке x=1.122613, в которой f(x)=-0.000939. Значение функции является отрицательным, так что двигаем левую границу рассматриваемого интервала вправо в точку x=1.122613.

Рисунок 2. Функция x^5 - 7.15x^4 + 19.89*x^3 - 26.8565x^2 + 17.5838x - 4.4616 = 0 на отрезке [0; 3] и иллюстрация первого шага метода хорд.

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

Рисунок 3. Функция x^5 - 7.15x^4 + 19.89*x^3 - 26.8565x^2 + 17.5838x - 4.4616 = 0 на отрезке [1.122613; 3] и иллюстрация второго шага метода хорд.

Такая ситуация повторяется, наверное, до бесконечности, пришлось остановиться на 1399 итерации, когда значение функции слева стало очень близким к нулю (близким к решению), и значение переменной перестало изменяться в 6 знаке после запятой (рисунок 4).

Рисунок 4. Функция x^5 - 7.15x^4 + 19.89*x^3 - 26.8565x^2 + 17.5838x - 4.4616 = 0 на отрезке [1.3; 3] и иллюстрация 1399-го шага метода хорд.

Так мы нашли один из корней x=1.3. Учитывая погрешность, с которой найден этот корень, мы можем продолжить искать корни по-отдельности в отрезках [0; 1.299999] и [1.300001; 3]. В отрезке [0; 1.299999] есть либо четное количество корней, либо корней нет, потому что на границах функция имеет один и тот же знак. Поэтому разобьем отрезок [0; 1.299999] пополам и рассмотрим по-отдельности отрезки [0; 0.65] и [0.65; 1.299999], каждый из которых также либо не содержит корней, либо их количество является четным. Ну тогда разобьем отрезок на 4 равные части: [0; 0.325]; [0.325; 0.65]; [0.65; 0.975] и [0.975; 1.299999]. Среди этих четырех отрезков нечетное количество корней содержится в двух последних. Рассмотрим сначала отрезок [0.65; 0.975], в котором за 28 итераций обнаруживается корень x=0.8. Во втором отрезке [0.975; 1.299999] за 18 итераций нашелся корень x=1.3.

Другие два корня находятся в интервале [1.300001; 3], сможете их найти аналитическим или численным способом? :)

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