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

Метод поиска корней

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

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

Метод

Метод секущих — это итерационный численный метод нахождения нуля функции f . При двух начальных значениях x ₀ и x ₁ метод действует согласно рекуррентному соотношению

${\displaystyle 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})}}.}$

Это нелинейная рекуррентность второго порядка, которая хорошо определена при заданных f и двух начальных значениях x ₀ и x ₁ . В идеале начальные значения следует выбирать близко к желаемому нулю.

Вывод метода

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

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

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

${\displaystyle 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} ):

${\displaystyle {\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}}}$

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

Итерации метода секущей сходятся к корню , если начальные значения и достаточно близки к корню и хорошо себя ведут. Когда дважды непрерывно дифференцируемо и рассматриваемый корень является простым корнем, т. е. имеет кратность 1, порядок сходимости равен золотому сечению ^[2]. Эта сходимость является сверхлинейной, но субквадратичной. ${\displaystyle x_{n}}$ ${\displaystyle f}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{1}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \varphi =(1+{\sqrt {5}})/2\approx 1.618.}$

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

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

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

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

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

используя конечно-разностное приближение, для малого : ${\displaystyle \epsilon =x_{n-1}-x_{n-2}}$

${\displaystyle f'(x_{n-1})=\lim _{\epsilon \rightarrow 0}{\frac {f(x_{n-1})-f(x_{n-1}-\epsilon )}{\epsilon }}\approx {\frac {f(x_{n-1})-f(x_{n-2})}{x_{n-1}-x_{n-2}}}}$

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

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

Обобщение

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

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

Пример расчета

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

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

def  secant_method ( f ,  x0 ,  x1 ,  iterations ): """Возвращает корень, вычисленный с помощью метода секущих.""" for i in range ( iterations ): x2 = x1 - f ( x1 ) * ( x1 - x0 ) / float ( f ( x1 ) - f ( x0 )) x0 , x1 = x1 , x2 # Применить здесь критерий останова (см. ниже) return x2                          def  f_example ( x ):  возврат  x  **  2  -  612корень  =  секущий_метод ( f_example ,  10 ,  30 ,  5 )print ( f "Корень: { root } " )  # Корень: 24.738633748750722

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

Примечания

1. Папаконстантину, Джоанна; Тапиа, Ричард (2013). «Происхождение и эволюция метода секущих в одном измерении». American Mathematical Monthly . 120 (6): 500–518. doi :10.4169/amer.math.monthly.120.06.500. JSTOR  10.4169/amer.math.monthly.120.06.500. S2CID  17645996 – через JSTOR.
2. Chanson, Jeffrey R. (3 октября 2024 г.). «Порядок сходимости». LibreTexts Mathematics . Получено 3 октября 2024 г. .
3. "УЧЕБНОЕ РУКОВОДСТВО ПО MATLAB для первого курса. Часть 1.3: Методы секущих".

Смотрите также

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

Ссылки

• Avriel, Mordecai (1976). Нелинейное программирование: анализ и методы . Prentice Hall. стр. 220–221. ISBN 0-13-623603-0.
• Аллен, Майрон Б.; Айзексон, Эли Л. (1998). Численный анализ для прикладной науки. John Wiley & Sons . С. 188–195. ISBN 978-0-471-55266-6.

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

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