Метод хорд

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Геометрическое описание метода секущих[править | править исходный текст]

Будем искать нуль функции 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 — абсциссы концов хорды, 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_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}-\dfrac{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}-\dfrac{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|<\varepsilon\!.

В нашем примере, в значение 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), если начальные величины x_0 and x_1 достаточно близки к корню. Метод секущих является быстрым . Порядок сходимости α, равен золотому сечению

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

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

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

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

Критерий и скорость сходимости метода хорд[править | править исходный текст]

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

Историческая справка[править | править исходный текст]

Первым, кто смог найти приближённые решения кубических уравнений, был Диофант, тем самым заложив основу метода хорд. Сохранившиеся работы Диофанта сообщают об этом. Однако первым, кто понял его методы, был Ферма в 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;
}

Модификации[править | править исходный текст]

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

См. также[править | править исходный текст]

Литература[править | править исходный текст]

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

Примечания[править | править исходный текст]

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

Ссылки[править | править исходный текст]