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

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

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

• 1 Метод
• 2 Вывод метода
• 3 Сходимость
• 4 Сравнение с другими корневыми методы поиска
• 5 Обобщения
• 6 Вычислительный пример
• 7 Примечания
• 8 См. также
• 9 Ссылки
• 10 Внешние ссылки

Метод секущей определяется рекуррентным соотношением

$xn\; =\; xn\; -\; 1\; -\; f\; (xn\; -\; 1)\; xn\; -\; 1\; -\; xn\; -\; 2\; f\; (xn\; -\; 1)\; -\; f\; (xn\; -\; 2)\; =\; xn\; -\; 2\; f\; (xn\; -\; 1)\; -\; xn\; -\; 1\; f\; (xn\; -\; 2)\; f\; (xn\; -\; 1)\; -\; f\; (xn\; -\; 2).\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; x\_\; \{n-1\}\; -f\; (x\_\; \{n-1\})\; \{\backslash \; frac\; \{x\_\; \{n-1\}\; -x\_\; \{n-2\}\}\; \{f\; (x\_\; \{n-1)\; \})\; -\; f\; (x\_\; \{n-2\})\}\}\; =\; \{\backslash \; frac\; \{x\_\; \{n-2\}\; f\; (x\_\; \{n-1\})\; -\; x\_\; \{n-1\}\; f\; (x\_\; \{n-2\})\; \}\; \{f\; (x\_\; \{n-1\})\; -\; f\; (x\_\; \{n-2\})\}\}.\}$

Как видно из рекуррентного соотношения, секущий метод требует двух начальных значений, x 0 и x 1, которые в идеале следует выбирать так, чтобы они располагались близко к корню.

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

$y\; =\; f\; (x\; 1)\; -\; f\; (x\; 0)\; x\; 1\; -\; x\; 0\; (x\; -\; x\; 1)\; +\; f\; (x\; 1).\; \{\backslash \; displaystyle\; y\; =\; \{\backslash \; 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)\; x\; 1\; -\; x\; 0\; f\; (x\; 1)\; -\; f\; (x\; 0).\; \{\backslash \; displaystyle\; x\; =\; x\_\; \{1\}\; -f\; (x\_\; \{1\})\; \{\backslash \; frac\; \{x\_\; \{1\}\; -x\_\; \{0\}\}\; \{f\; (x\_\; \{1\})\; -\; f\; (x\_\; \{0\})\}\}.\; \}$

Затем мы используем это новое значение x как x 2 и повторяем процесс, используя x 1 и x 2 вместо x 0 и x 1. Мы продолжаем этот процесс, решая для x 3, x 4 и т. Д., Пока не достигнем достаточно высокого уровня точности (достаточно малая разница между x n и x n − 1):

$x\; 2\; =\; x\; 1\; -\; f\; (x\; 1)\; x\; 1\; -\; x\; 0\; f\; (x\; 1)\; -\; f\; (x\; 0),\; x\; 3\; =\; x\; 2\; -\; f\; (x\; 2)\; x\; 2\; -\; x\; 1\; f\; (x\; 2)\; -\; f\; (x\; 1),\; ⋮\; xn\; =\; xn\; -\; 1\; -\; f\; (xn\; -\; 1)\; xn\; -\; 1\; -\; xn\; -\; 2\; f\; (xn\; -\; 1)\; -\; f\; (xn\; -\; 2).\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; x\_\; \{2\}\; =\; x\_\; \{1\}\; -f\; (x\_\; \{1\})\; \{\backslash \; frac\; \{x\_\; \{1\}\; -x\_\; \{0\}\}\; \{f\; (x\_\; \{1\})\; -\; f\; (x\_\; \{0\})\}\},\; \backslash \backslash \; [6pt]\; x\_\; \{3\}\; =\; x\_\; \{2\}\; -f\; (x\_\; \{2\})\; \{\backslash \; frac\; \{x\_\; \{2\}\; -x\_\; \{1\}\}\; \{f\; (\; x\_\; \{2\})\; -\; f\; (x\_\; \{1\})\}\},\; \backslash \backslash \; [6pt]\; \backslash ,\; \backslash ,\; \backslash ,\; \backslash \; vdots\; \backslash \backslash \; [6pt]\; x\_\; \{n\}\; =\; x\_\; \{n-1\}\; -f\; (\; x\_\; \{n-1\})\; \{\backslash \; frac\; \{x\_\; \{n-1\}\; -x\_\; \{n-2\}\}\; \{f\; (x\_\; \{n-1\})\; -\; f\; (x\_\; \{n-2\})\}\}.\; \backslash \; end\; \{align\}\}\}$

Итерации $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$метода секущей сходятся к корню из $f\; \{\backslash \; displaystyle\; f\}$, если исходные значения $x\; 0\; \{\backslash \; displaystyle\; x\_\; \{0\}\}$и $x\; 1\; \{\backslash \; displaystyle\; x\_\; \{1\}\}$достаточно близки к корню. Порядок сходимости равен φ, где

$\phi \; =\; 1\; +\; 5\; 2\; \approx \; 1.618\; \{\backslash \; displaystyle\; \backslash \; varphi\; =\; \{\backslash \; frac\; \{1\; +\; \{\backslash \; sqrt\; \{5\}\}\}\; \{2\}\}\; \backslash \; приблизительно\; 1,618\}$

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

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

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

Метод секанса не требует, чтобы корень оставался заключенным в квадратные скобки, как это делает метод деления пополам, и, следовательно, он не всегда сходится. Метод ложного положения (или regula falsi) использует ту же формулу, что и метод секущей. Однако формула не применяется к $xn\; -\; 1\; \{\backslash \; displaystyle\; x\_\; \{n-1\}\}$и $xn\; -\; 2\; \{\backslash \; displaystyle\; x\_\; \{n-2\}\}$, как метод секущей, но на $xn\; -\; 1\; \{\backslash \; displaystyle\; x\_\; \{n-1\}\}$и на последней итерации $xk\; \{\backslash \; displaystyle\; x\_\; \{k\}\; \}$такие, что $f\; (xk)\; \{\backslash \; displaystyle\; f\; (x\_\; \{k\})\}$и $f\; (xn\; -\; 1)\; \{\backslash \; displaystyle\; f\; (x\_\; \{\; n-1\})\}$иметь другой знак. Это означает, что метод ложного положения всегда сходится.

Повторяющаяся формула метода секущих может быть получена из формулы для метода Ньютона

$xn\; =\; xn\; -\; 1\; -\; f\; (xn\; -\; 1)\; f\; \prime \; (xn\; -\; 1)\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; x\_\; \{n-1\}\; -\; \{\backslash \; frac\; \{f\; (x\_\; \{n-1\})\}\; \{f\; \text{'}(x\_\; \{n-1\})\}\}\}$

с помощью конечного -разность приближение

$f\; \prime \; (xn\; -\; 1)\; \approx \; f\; (xn\; -\; 1)\; -\; f\; (xn\; -\; 2)\; xn\; -\; 1\; -\; xn\; -\; 2.\; \{\backslash \; displaystyle\; f\; \text{'}(x\_\; \{n-1\})\; \backslash \; приблизительно\; \{\backslash \; frac\; \{f\; (x\_\; \{n-1\})\; -\; f\; (x\_\; \{n-2\})\}\; \{x\_\; \{n-1\}\; -x\_\; \{n\; -2\}\}\}.\}$

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

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

Метод Бройдена - это обобщение метода секущих более чем на одно измерение.

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

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

Затем он применяется для нахождения корня функции f (x) = x - 612 с начальными точками $x\; 0\; =\; 10\; \{\backslash \; displaystyle\; x\_\; \{0\}\; =\; 10\}$и $x\; 1\; =\; 30\; \{\backslash \; displaystyle\; x\_\; \{1\}\; =\; 30\}$

def secant_method (f, x0, x1, iterations): "" "Возвращает корень, вычисленный с использованием метода секанса." "" для i в диапазоне (итераций): x2 = x1 - f (x1) * (x1 - x0) / float (f (x1) - f (x0)) x0, x1 = x1, x2 return x2 def f_example (x): return x ** 2 - 612 root = secant_method (f_example, 10, 30, 5) print ("Root: {}". format (root)) # Root: 24.738633748750722

• Метод ложного положения

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

• Secant Method Notes, PPT, Mathcad, Maple, Mathematica, Matlab at Целостные численные методы Институт
• Вайсштейн, Эрик У. «Метод Секанта». MathWorld.