Секущий метод

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

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

Метод [ править ]

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

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

Как видно из рекуррентного соотношения, метод секущей требует двух начальных значений, 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 {align} 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 {выровнено}}}$

Конвергенция [ править ]

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

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

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

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

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

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

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

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

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

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

${\displaystyle f'(x_{n-1})\approx {\frac {f(x_{n-1})-f(x_{n-2})}{x_{n-1}-x_{n-2}}}.}$

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

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

Обобщения [ править ]

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

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

Вычислительный пример [ править ]

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

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

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

Примечания [ править ]

См. Также [ править ]

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

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

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

Внешние ссылки [ править ]

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