Метод хорд — итерационный численный метод приближённого нахождения корня уравнения.

Геометрическое описание метода секущих

Будем искать нуль функции ${\displaystyle f(x)}$ . Выберем две начальные точки ${\displaystyle C_{1}(x_{1};y_{1})}$ и ${\displaystyle C_{2}(x_{2};y_{2})}$ и проведем через них прямую. Она пересечет ось абсцисс в точке ${\displaystyle (x_{3};0)}$ . Теперь найдем значение функции с абсциссой ${\displaystyle x_{3}}$ . Временно будем считать ${\displaystyle x_{3}}$ корнем на отрезке ${\displaystyle [x_{1};x_{2}]}$ . Пусть точка ${\displaystyle C_{3}}$ имеет абсциссу ${\displaystyle x_{3}}$ и лежит на графике. Теперь вместо точек ${\displaystyle C_{1}}$ и ${\displaystyle C_{2}}$ мы возьмём точку ${\displaystyle C_{3}}$ и точку ${\displaystyle C_{2}}$ . Теперь с этими двумя точками проделаем ту же операцию и так далее, то есть будем получать две точки ${\displaystyle C_{n+1}}$ и ${\displaystyle C_{n}}$ и повторять операцию с ними. Отрезок, соединяющий последние две точки, пересекает ось абсцисс в точке, значение абсциссы которой можно приближённо считать корнем. Эти действия нужно повторять до тех пор, пока не получим значение корня с нужным приближением.

Алгебраическое описание метода секущих

Пусть ${\displaystyle x_{1},x_{2}}$ — абсциссы концов хорды, ${\displaystyle f(x)=0}$ — уравнение функции, решаемое методом секущих. Найдём коэффициенты ${\displaystyle k}$ и ${\displaystyle b}$ из системы уравнений

${\displaystyle \left\{{\begin{aligned}f(x_{1})&=kx_{1}+b,\\f(x_{2})&=kx_{2}+b.\\\end{aligned}}\right.}$

Вычтем из первого уравнения второе:

${\displaystyle f(x_{1})-f(x_{2})=k(x_{1}-x_{2}),}$

затем найдём коэффициенты ${\displaystyle k}$ и ${\displaystyle b}$ :

${\displaystyle k={\frac {f(x_{2})-f(x_{1})}{x_{2}-x_{1}}},}$

тогда

${\displaystyle b=f(x_{1})-{\frac {(f(x_{2})-f(x_{1}))x_{1}}{x_{2}-x_{1}}}.}$

Уравнение принимает вид

${\displaystyle y={\frac {f(x_{2})-f(x_{1})}{x_{2}-x_{1}}}(x-x_{1})+f(x_{1}).}$

Таким образом, теперь можем найти первое приближение к корню, полученное методом секущих:

${\displaystyle x_{3}=x_{1}-{\frac {(x_{2}-x_{1})f(x_{1})}{f(x_{2})-f(x_{1})}}.}$

Теперь возьмём координаты ${\displaystyle x_{2}}$ и ${\displaystyle x_{3}}$ и повторим все проделанные операции, найдя новое приближение к корню. Таким образом, итерационная формула метода секущих имеет вид:

${\displaystyle x_{i+1}=x_{i-1}-{\dfrac {f(x_{i-1})\cdot (x_{i}-x_{i-1})}{f(x_{i})-f(x_{i-1})}}.}$

Повторять операцию следует до тех пор, пока ${\displaystyle |x_{i}-x_{i-1}|}$ не станет меньше или равно заданному значению погрешности.

Метод хорд с итерационной формулой

Иногда методом секущих называют метод с итерационной формулой

${\displaystyle x_{i+1}=x_{0}-{\dfrac {f(x_{0})\cdot (x_{i}-x_{0})}{f(x_{i})-f(x_{0})}}.}$

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

Пример использования метода секущих

Решим уравнение ${\displaystyle x^{3}-18x-83=0}$ методом секущих. Зададимся точностью ε=0.001 и возьмём в качестве начальных приближений ${\displaystyle x_{0}}$ и ${\displaystyle x_{1}}$ концы отрезка, на котором отделён корень: ${\displaystyle x_{0}=8}$ и ${\displaystyle x_{1}=3}$ , числовые значения ${\displaystyle x_{0}=8}$ и ${\displaystyle x_{1}=3}$ выбраны произвольно. Вычисления ведутся до тех пор, пока не будет выполнено неравенство ${\displaystyle |x_{i+1}-x_{i}|<\varepsilon }$ .

В нашем примере, в значение ${\displaystyle x_{i-1}}$ подставляется ${\displaystyle x_{0}=8}$ , а в значение ${\displaystyle x_{i}}$ подставляется ${\displaystyle x_{1}=3}$ . Значение ${\displaystyle x_{i+1}}$ это будет числовое значение ${\displaystyle x_{2}={\underline {}}4.3924051}$ полученное по этой формуле. В дальнейшем ${\displaystyle x_{2}={\underline {}}4.3924051}$ подставляем в формулу в значение ${\displaystyle x_{i}}$ , а ${\displaystyle x_{1}=3}$ в значение ${\displaystyle x_{i-1}}$ .

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

  ${\displaystyle x_{2}={\underline {}}4.3924051}$; 
  ${\displaystyle x_{3}={\underline {5}},1622721}$;
  ${\displaystyle x_{4}={\underline {5}}.4988422}$;
  ${\displaystyle x_{5}={\underline {5,6}}295040}$; 
  ${\displaystyle x_{6}={\underline {5.6}}777792}$;
  ${\displaystyle x_{7}={\underline {5.6}}952826}$;
  ${\displaystyle x_{8}={\underline {5.70}}15852}$;
  ${\displaystyle x_{9}={\underline {5.70}}38490}$;
  ${\displaystyle x_{10}={\underline {5.704}}6613}$; 
  ${\displaystyle x_{11}={\underline {5.704}}9528}$;

Проверим, что метод работает и в том случае, если ${\displaystyle x_{0}}$ и ${\displaystyle x_{1}}$ выбраны по одну и ту же сторону от корня (то есть, если корень не отделён на отрезке между начальными приближениями). Возьмём для того же уравнения ${\displaystyle x_{0}=8}$ и ${\displaystyle x_{1}=7}$ . Тогда: (картинка уже не из метода секущих, а из метода дихотомии )

  ${\displaystyle x_{2}={\underline {}}6.1125828}$; 
  ${\displaystyle x_{3}={\underline {5}}.8452240}$; 
  ${\displaystyle x_{4}={\underline {5.7}}546403}$; 
  ${\displaystyle x_{5}={\underline {5.7}}227874}$; 
  ${\displaystyle x_{6}={\underline {5.7}}114425}$;
  ${\displaystyle x_{7}={\underline {5.70}}73836}$;
  ${\displaystyle x_{8}={\underline {5.705}}9290}$; 
  ${\displaystyle x_{9}={\underline {5.705}}4075}$;

Мы получили то же значение корня за то же число итераций.

Сходимость метода секущих

Итерации метода секущих сходятся к корню ${\displaystyle f(x)}$ , если начальные величины ${\displaystyle x_{0}}$ и ${\displaystyle x_{1}}$ достаточно близки к корню. Метод секущих является быстрым. Порядок сходимости α равен золотому сечению :

${\displaystyle \alpha ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}618...}$

Таким образом, порядок сходимости больше линейного, но не квадратичен, как у родственного метода Ньютона .

Этот результат справедлив, если ${\displaystyle f(x)}$ дважды дифференцируема и корень ${\displaystyle \xi }$ не является кратным — ${\displaystyle f'(\xi )\neq 0}$ .

Как и для большинства быстрых методов, для метода секущих трудно сформулировать условия сходимости. Если начальные точки достаточно близки к корню, то метод сходится, но нет общего определения «достаточной близости». Сходимость метода определяется тем, насколько функция «волниста» в ${\displaystyle [x_{0},x_{1}]}$ . Например, если в интервале есть точка, в которой ${\displaystyle f'(x)=0}$ , то процесс может не сходиться.

Критерий и скорость сходимости метода хорд

Если ${\displaystyle f(x)}$ — дважды непрерывно дифференцируемая функция, и знак ${\displaystyle f''(x)}$ сохраняется на рассматриваемом промежутке, то полученные приближения будут сходиться к корню монотонно. Если корень ${\displaystyle \xi }$ уравнения ${\displaystyle f(\xi )=0}$ находится на отрезке ${\displaystyle [a,b]}$ , производные ${\displaystyle f'(x)}$ и ${\displaystyle f''(x)}$ на этом промежутке непрерывны и сохраняют постоянные знаки и ${\displaystyle f''(b)f(b)>0}$ , то можно доказать , что погрешность приближенного решения стремится к нулю при ${\displaystyle n\rightarrow \infty }$ , то есть метод сходится и сходится со скоростью геометрической прогрессии (при этом говорят, что он имеет линейную скорость сходимости ).

Историческая справка

Первым, кто смог найти приближённые решения кубических уравнений , был Диофант , тем самым заложив основу метода хорд. Сохранившиеся работы Диофанта сообщают об этом. Однако первым, кто понял его методы, был Ферма в XVII веке, а первым, кто дал объяснение методу хорд, был Ньютон (1670-е гг.).

Реализация

C++

#include <iostream>
#include <math.h>

double f(double x) {
    return sqrt(fabs(cos(x))) - x; // Заменить функцией, корни которой мы ищем
}

// a, b - пределы хорды, epsilon — необходимая погрешность
double findRoot(double a, double b, double epsilon) {
    while(fabs(b - a) > epsilon) {
        a = a - (b - a) * f(a) / (f(b) - f(a));
        b = b - (a - b) * f(b) / (f(a) - f(b));
    }
    // a, b — (i - 1)-й и i-й члены

    return b;
}

Python

from math import sin
from typing import Callable
import unittest


def secant(f: Callable[[float], float], x0: float, eps: float=1e-7, kmax: int=1e3) -> float:
	"""
	solves f(x) = 0 by secant method with precision eps
	:param f: f
	:param x0: starting point
	:param eps: precision wanted
	:return: root of f(x) = 0
	"""
	x, x_prev, i = x0, x0 + 2 * eps, 0
	
	while abs(x - x_prev) >= eps and i < kmax:
		x, x_prev, i = x - f(x) / (f(x) - f(x_prev)) * (x - x_prev), x, i + 1

	return x


class TestSecant(unittest.TestCase):
	def test_0(self):
		def f(x: float) -> float:
			return x**2 - 20 * sin(x)


		x0, x_star = 2, 2.7529466338187049383

		self.assertAlmostEqual(secant(f, x0), x_star)


if __name__ == '__main__':
	unittest.main()

Модификации

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

См. также

• Метод Ньютона (метод касательных)
• Метод простой итерации
• Обратная параболическая интерполяция

Литература

1. Демидович Б. П. и Марон И. А. Основы вычислительной математики. — Наука, 1970. — С. 664.
2. Бахвалов, Жидков, Кобельков. Численные методы. — Наука. — ISBN 5-94774-060-5 .

Примечания

Ссылки

• от 8 января 2018 на Wayback Machine
• Ю. Губарь, // Интуит.ру , 15.03.2007