Метод хорд

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

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

Будем искать нуль функции $f(x)$. Выберем две начальные точки $C_1(x_1;y_1)$ и $C_2(x_2;y_2)$ и проведем через них прямую. Она пересечет ось абсцисс в точке $(x_3;0)$. Теперь найдем значение функции с абсциссой $x_3$. Временно будем считать $x_3$ корнем на отрезке $[x_1;x_2]$. Пусть точка $C_3$ имеет абсциссу $x_3$ и лежит на графике. Теперь вместо точек $C_1$ и $C_2$ мы возьмём точку $C_3$ и точку $C_2$. Теперь с этими двумя точками проделаем ту же операцию и так далее, то есть будем получать две точки $C_{n+1}$ и $C_n$ и повторять операцию с ними. Отрезок, соединяющий последние две точки, пересекает ось абсцисс в точке, значение абсциссы которой можно приближённо считать корнем. Эти действия нужно повторять до тех пор, пока не получим значение корня с нужным приближением.

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

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

$\{\begin{array}{rl}f(x_1)& =k{x}_1+b,\\ f(x_2)& =k{x}_2+b.\\ \end{array}$

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

$f(x_1)-f(x_2)=k(x_1-x_2),$

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

$k=\frac{f(x_2)-f(x_1)}{x_2-x_1},$

тогда

$b=f(x_1)-\frac{(f(x_2)-f(x_1))x_1}{x_2-x_1}.$

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

$y=\frac{f(x_2)-f(x_1)}{x_2-x_1}(x-x_1)+f(x_1).$

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

$x_3=x_1-\frac{(x_2-x_1)f(x_1)}{f(x_2)-f(x_1)}.$

Теперь возьмём координаты $x_2$ и $x_3$ и повторим все проделанные операции, найдя новое приближение к корню. Таким образом, итерационная формула метода секущих имеет вид:

$x_{i+1}=x_{i-1}-\frac{f(x_{i-1})\cdot (x_i-x_{i-1})}{f(x_i)-f(x_{i-1})}.$

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

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

Первые три итерации метода хорд. Синим нарисована функция f(x), красными проводятся хорды

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

$x_{i+1}=x_i-\frac{f(x_i)\cdot (x_i-x_0)}{f(x_i)-f(x_0)}.$

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

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

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

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

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

Метод секущих. Первый случай

  $x_2=\underset{}{\_}4.3924051$; 
  $x_3=\underset{\_}{5},1622721$;
  $x_4=\underset{\_}{5}.4988422$;
  $x_5=\underset{\_}{5,6}295040$; 
  $x_6=\underset{\_}{5.6}777792$;
  $x_7=\underset{\_}{5.6}952826$;
  $x_8=\underset{\_}{5.70}15852$;
  $x_9=\underset{\_}{5.70}38490$;
  $x_{10}=\underset{\_}{5.704}6613$; 
  $x_{11}=\underset{\_}{5.704}9528$;

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

Метод секущих. Второй случай

  $x_2=\underset{}{\_}6.1125828$; 
  $x_3=\underset{\_}{5}.8452240$; 
  $x_4=\underset{\_}{5.7}546403$; 
  $x_5=\underset{\_}{5.7}227874$; 
  $x_6=\underset{\_}{5.7}114425$;
  $x_7=\underset{\_}{5.70}73836$;
  $x_8=\underset{\_}{5.705}9290$; 
  $x_9=\underset{\_}{5.705}4075$;

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

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

Итерации метода секущих сходятся к корню $f(x)$, если начальные величины $x_0$ and $x_1$ достаточно близки к корню. Метод секущих является быстрым. Порядок сходимости α равен золотому сечению:

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

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

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

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

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

Если $f(x)$ — дважды непрерывно дифференцируемая функция, и знак $f^{″}(x)$ сохраняется на рассматриваемом промежутке, то полученные приближения будут сходиться к корню монотонно. Если корень $\xi$ уравнения $f(\xi )=0$ находится на отрезке $[a,b]$, производные $f^{\prime }(x)$ и $f^{″}(x)$ на этом промежутке непрерывны и сохраняют постоянные знаки и $f^{″}(b)f(b)>0$, то можно доказать, что погрешность приближенного решения стремится к нулю при $n\to \mathrm{\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.

Ссылки

• Решение уравнений методом хорд онлайн
• «Методы решения алгебраических уравнений» на сайте www.petrsu.ru Архивная копия от 8 января 2018 на Wayback Machine
• «Методы дихотомии» на сайте www.epikoiros.narod.ru
• Ю. Губарь, Курс «Введение в математическое моделирование» Лекция 4: Численные методы решения нелинейных уравнений // Интуит.ру, 15.03.2007