Метод хорд

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

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

Геометрическое описание

Будем искать корень функции $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}$ имеет абсцисcу $x_{3}$ и лежит на графике. Теперь вместо точек $C_{1}$ и $C_{2}$ мы возьмём точку $C_{3}$ и точку $C_{2}$. Теперь с этими двумя точками проделаем ту же операцию и так далее, то есть будем получать две точки $C_{n+1}$ и $C_{n}$ и повторять операцию с ними. Отрезок, соединяющий последние 2 точки, пересекает ось абсцисс в точке, значение абсциссы которой можно приближённо считать корнем. Эти действия нужно повторять до тех пор, пока не получим значение корня с нужным приближением.

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

Пусть $x_1, x_2$ − абсциссы концов хорды, $y=kx+b$ − уравнение прямой, содержащей хорду. Найдем коэффициенты $k$ и $b$ из системы уравнений:

$\left\{ \begin{array}{rcl} f(x_1) & = & kx_1+b,\\ f(x_2) & = & kx_2+b. \\ \end{array} \right.$.

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

$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_2=x_1-\frac{(x_2-x_1)f(x_1)}{f(x_2)-f(x_1)}$

Теперь возьмем координаты $x_2$ и $x_3$ и повторим все проделанные операции, найдя новое приближение к корню. Повторять операцию следует до тех пор, пока $|x_n-x_{n-1}|$ не станет меньше или равно заданному значению погрешности.

Пример использования

Решим уравнение $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|<\varepsilon\!$.

Итерационная формула метода хорд имеет вид:

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

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

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

Первый случай

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

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

Второй случай

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

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

Критерий сходимости

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

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

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

Пример кода

Пример функции вычисления корня методом хорд на отрезке [а; b] на Си/Си++.

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 = b - (b - a) * f(b)/(f(b) - f(a));
        b = a - (a - b) * f(a)/(f(a) - f(b));
    }
 
    // a - i-1, b - i-тый члены
 
    return b;
}

См. также

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

Литература

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

Примечания

1. ↑ Алгебра
2. ↑ Математика и ее история. Джон Стиллвелл

Ссылки

• «Методы решения алгебраических уравнений» на сайте www.petrsu.ru
• «Методы дихотомии» на сайте www.epikoiros.narod.ru
• Численные методы решения нелинейных уравнений на сайте Интуит.ру