Метод секущего

Первые две итерации метода секущей. Красная кривая показывает функцию f , а синие линии — секущие. В этом конкретном случае метод секущего не сходится к видимому корню.

В численном анализе метод секущего представляет собой алгоритм поиска корня , который использует последовательность корней секущих линий для лучшего приближения корня функции f . Метод секущих можно рассматривать как конечно-разностную аппроксимацию метода Ньютона . Однако метод секущих предшествует методу Ньютона более чем на 3000 лет.

Метод

Для нахождения нуля функции f метод секущего определяется рекуррентным соотношением .

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

Как видно из этой формулы, два начальных значения x ₀ и x ₁ требуются . В идеале их следует выбирать близкими к желаемому нулю.

Вывод метода

Начиная с начальных значений x ₀ и x ₁ , строим линию через точки ( x ₀ , f ( x ₀ )) и ( x ₁ , f ( x ₁ )) , как показано на рисунке выше. В форме наклона-пересечения уравнение этой линии имеет вид

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

Корень этой линейной функции, то есть значение x такое, что y = 0, равен

$x=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}.$

Затем мы используем это новое значение x как x ₂ и повторяем процесс, используя x ₁ и x ₂ вместо x ₀ и x ₁ . Мы продолжаем этот процесс, решая для x ₃ , x ₄ и т. д., пока не достигнем достаточно высокого уровня точности (достаточно небольшой разницы между x _n и x _{n −1} ):

${\begin{aligned}x_{2}&=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}},\\[6pt]x_{3}&=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}},\\[6pt]&\,\,\,\vdots \\[6pt]x_{n}&=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}.\end{aligned}}$

Конвергенция

Итерации $x_{n}$ метода секущих сходятся к корню $f$ если начальные значения $x_{0}$ и $x_{1}$ находятся достаточно близко к корню. Порядок сходимости ​ $\varphi$, где

$\varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618$

это золотое сечение . В частности, сходимость суперлинейная, но не совсем квадратичная .

Этот результат справедлив только при некоторых технических условиях, а именно, что $f$ быть дважды непрерывно дифференцируемым, а рассматриваемый корень — простым (т. е. с кратностью 1).

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

Сравнение с другими методами поиска корней

Метод секущего не требует, чтобы корень оставался в квадратных скобках, как это делает метод деления пополам , и, следовательно, он не всегда сходится. Метод ложного положения (или regula falsi ) использует ту же формулу, что и метод секущего. Однако здесь не применяется формула $x_{n-1}$ и $x_{n-2}$, как и метод секущей, но $x_{n-1}$ и на последней итерации $x_{k}$ такой, что $f(x_{k})$ и $f(x_{n-1})$ иметь другой знак. Это означает, что метод ложного положения всегда сходится; однако только с линейным порядком сходимости. Брекетинг со сверхлинейным порядком сходимости в качестве метода секущей может быть достигнут с помощью улучшений метода ложного положения (см. Regula falsi § Улучшения в regula falsi ), таких как метод ITP или метод Иллинойса .

Рекуррентную формулу метода секущего можно вывести из формулы метода Ньютона.

$x_{n}=x_{n-1}-{\frac {f(x_{n-1})}{f'(x_{n-1})}}$

используя конечно-разностное приближение, для небольшого $\epsilon$:

$f'(x_{n-1})\approx {\frac {f(x_{n-1})-f(x_{n-2})}{x_{n-1}-x_{n-2}}}\approx {\frac {f(x_{n-1}+{\frac {\epsilon }{2}})-f(x_{n-1}-{\frac {\epsilon }{2}})}{\epsilon }}$

Метод секущих можно интерпретировать как метод, в котором производная заменяется приближением, и, таким образом, является квазиньютоновским методом .

Если мы сравним метод Ньютона с методом секущих, то увидим, что метод Ньютона сходится быстрее (порядок 2 против φ ≈ 1,6). Однако метод Ньютона требует оценки обоих $f$ и его производная $f'$ на каждом шаге, тогда как метод секущих требует лишь оценки $f$. Следовательно, на практике метод секущей иногда может оказаться быстрее. Например, если мы предположим, что оценка $f$ занимает столько же времени, сколько и вычисление ее производной, и мы пренебрегаем всеми остальными затратами, мы можем выполнить два шага метода секущего (уменьшив логарифм ошибки в φ раз). ² ≈ 2,6) за ту же стоимость, что и один шаг метода Ньютона (уменьшение логарифма ошибки в 2 раза), поэтому метод секущего быстрее. Однако если мы рассмотрим параллельную обработку для вычисления производной, метод Ньютона докажет свою ценность, поскольку он быстрее по времени, хотя и требует больше шагов.

Обобщение

Метод Бройдена представляет собой обобщение метода секущего на более чем одно измерение.

На следующем графике функция f показана красным цветом, а последняя секущая линия — жирным синим цветом. На графике точка пересечения секущей линии по оси x кажется хорошим приближением корня f .

Вычислительный пример

Ниже метод секущей реализован на языке программирования Python .

Затем он применяется для нахождения корня функции f ( x ) = x ² − 612 с начальными баллами $x_{0}=10$ и $x_{1}=30$

def secant_method(f, x0, x1, iterations):    """Return the root calculated using the secant method."""    for i in range(iterations):        x2 = x1 - f(x1) * (x1 - x0) / float(f(x1) - f(x0))        x0, x1 = x1, x2        # Apply a stopping criterion here (see below)    return x2def f_example(x):    return x ** 2 - 612root = secant_method(f_example, 10, 30, 5)print(f"Root: {root}")  # Root: 24.738633748750722

Очень важно иметь хороший критерий остановки, указанный выше, иначе из-за ограниченной числовой точности чисел с плавающей запятой алгоритм может возвращать неточные результаты при выполнении слишком большого количества итераций. Например, приведенный выше цикл может остановиться, когда сначала будет достигнуто одно из следующих значений: abs(x0 - x1) < tol, или abs(x0/x1-1) < tol, или abs(f(x1)) < tol.

См. также

• Метод ложной позиции

Ссылки

• Авриэль, Мордехай (1976). Нелинейное программирование: анализ и методы . Прентис Холл. стр. 220–221. ISBN  0-13-623603-0 .
• Аллен, Майрон Б.; Исааксон, Эли Л. (1998). Численный анализ для прикладной науки . Джон Уайли и сыновья . стр. 188–195. ISBN  978-0-471-55266-6 .

Внешние ссылки

• Примечания к методу секущих , PPT, Mathcad, Maple, Mathematica, Matlab в Институте целостных численных методов
• Вайсштейн, Эрик В. «Метод секущих» . Математический мир .