Метод хорд

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

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

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

Будем искать нуль функции . Выберем две начальные точки и и проведем через них прямую. Она пересечет ось абсцисс в точке . Теперь найдем значение функции с абсциссой . Временно будем считать корнем на отрезке . Пусть точка имеет абсциссу и лежит на графике. Теперь вместо точек и мы возьмём точку и точку . Теперь с этими двумя точками проделаем ту же операцию и так далее, то есть будем получать две точки и и повторять операцию с ними. Отрезок, соединяющий последние две точки, пересекает ось абсцисс в точке, значение абсциссы которой можно приближённо считать корнем. Эти действия нужно повторять до тех пор, пока не получим значение корня с нужным приближением.

Алгебраическое описание метода секущих[править | править вики-текст]

Пусть  — абсциссы концов хорды,  — уравнение секущей, содержащей хорду. Найдем коэффициенты и из системы уравнений:

.

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

, затем найдем коэффициенты и :

, тогда

.

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

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

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

.

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

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

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

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

.

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

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

Решим уравнение методом секущих. Зададимся точностью ε=0.001 и возьмём в качестве начальных приближений и концы отрезка, на котором отделён корень: и , числовые значения и выбраны произвольно. Вычисления ведутся до тех пор, пока выполняется неравенство .

В нашем примере, в значение подставляется , а в значение подставляется . Значение это будет числовое значение полученное по этой формуле. В дальнейшем подставляем в формулу в значение , а в значение .

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

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

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

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

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

Сходимость метода секущих[править | править вики-текст]

Итерации метода секущих сходятся к корню , если начальные величины and достаточно близки к корню. Метод секущих является быстрым . Порядок сходимости α, равен золотому сечению

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

Этот результат справедлив, если дважды дифференцируема и корень не является кратным — .

Как и для большинства быстрых методов, для метода секущих трудно сформулировать условия сходимости. Если начальные точки достаточно близки к корню, то метод сходится, но нет общего определения «достаточной близости». Сходимость метода определяется, тем насколько функция «волниста» в . Например, если в интервале есть точка, в которой , то процесс может не сходиться.

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

Если  — дважды непрерывно дифференцируемая функция, и знак сохраняется на рассматриваемом промежутке, то полученные приближения будут сходиться к корню монотонно. Если корень уравнения находится на отрезке , производные и на этом промежутке непрерывны и сохраняют постоянные знаки и , то можно доказать[1], что погрешность приближенного решения стремится к нулю при , то есть метод сходится и сходится со скоростью геометрической прогрессии (при этом говорят, что он имеет линейную скорость сходимости).

Историческая справка[править | править вики-текст]

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

Ссылки[править | править вики-текст]