Обобщенный метод секанса Сидиса - Википедия - Sidis generalized secant method

Обобщенный метод секущих Сиди это алгоритм поиска корней, это численный метод для решения уравнения формы ${ displaystyle f (x) = 0}$ . Метод был опубликован Аврамом Сиди.^[1]

Метод является обобщением секущий метод. Подобно секущему методу, это итерационный метод что требует одной оценки ${ displaystyle f}$ в каждой итерации и нет производные из ${ displaystyle f}$. Однако метод может сходиться намного быстрее, если порядок что приближается к 2 при условии, что ${ displaystyle f}$ удовлетворяет описанным ниже условиям регулярности.

Алгоритм

Мы называем ${ displaystyle alpha}$ корень ${ displaystyle f}$, то есть, ${ Displaystyle е ( альфа) = 0}$. Метод Сиди - это итеративный метод, который генерирует последовательность ${ displaystyle {x_ {i} }}$ приближений ${ displaystyle alpha}$. Начиная с k + 1 начальное приближение ${ Displaystyle х_ {1}, точки, х_ {к + 1}}$, приближение ${ displaystyle x_ {k + 2}}$ вычисляется на первой итерации, приближение ${ displaystyle x_ {k + 3}}$ вычисляется во второй итерации и т. д. Каждая итерация принимает в качестве входных данных последний k +1 приближения и значение ${ displaystyle f}$ в этих приближениях. Следовательно п-я итерация принимает на входе приближения ${ displaystyle x_ {n}, dots, x_ {n + k}}$ и ценности ${ Displaystyle е (х_ {п}), точки, е (х_ {п + к})}$.

Номер k должно быть 1 или больше: k = 1, 2, 3, .... Остается фиксированным во время выполнения алгоритма. Для получения начальных приближений ${ Displaystyle х_ {1}, точки, х_ {к + 1}}$ можно было бы выполнить несколько итераций инициализации с меньшим значением k.

Приближение ${ Displaystyle х_ {п + к + 1}}$ рассчитывается следующим образом в пй итерация. А полином интерполяции ${ Displaystyle р_ {п, к} (х)}$ из степень k приспособлен к k +1 балл ${ Displaystyle (x_ {n}, f (x_ {n})), точки (x_ {n + k}, f (x_ {n + k}))}$. С этим полиномом следующее приближение ${ Displaystyle х_ {п + к + 1}}$ из ${ displaystyle alpha}$ рассчитывается как

${ displaystyle x_ {n + k + 1} = x_ {n + k} - { frac {f (x_ {n + k})} {p_ {n, k} '(x_ {n + k})} }}$

(1)

с ${ displaystyle p_ {n, k} '(x_ {n + k})}$ производная от ${ displaystyle p_ {n, k}}$ в ${ displaystyle x_ {n + k}}$. Подсчитав ${ Displaystyle х_ {п + к + 1}}$ один вычисляет ${ displaystyle f (x_ {n + k + 1})}$ и алгоритм может продолжить (п + 1) -я итерация. Ясно, что для этого метода требуется функция ${ displaystyle f}$ оцениваться только один раз за итерацию; он не требует производных от ${ displaystyle f}$.

Итерационный цикл останавливается, если удовлетворяется соответствующий критерий остановки. Обычно критерием является то, что последнее вычисленное приближение достаточно близко к искомому корню. ${ displaystyle alpha}$.

Для эффективного выполнения алгоритма метод Сиди вычисляет интерполирующий полином ${ Displaystyle р_ {п, к} (х)}$ в его Форма Ньютона.

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

Сиди показал, что если функция ${ displaystyle f}$ является (k + 1) -раз непрерывно дифференцируемый в открытый интервал ${ displaystyle I}$ содержащий ${ displaystyle alpha}$ (то есть, ${ displaystyle f in C ^ {k + 1} (I)}$), ${ displaystyle alpha}$ это простой корень ${ displaystyle f}$ (то есть, ${ Displaystyle е '( альфа) neq 0}$) и начальные приближения ${ Displaystyle х_ {1}, точки, х_ {к + 1}}$ выбраны достаточно близко к ${ displaystyle alpha}$, то последовательность ${ displaystyle {x_ {i} }}$ сходится к ${ displaystyle alpha}$, что означает, что следующие предел держит: ${ displaystyle lim limits _ {n to infty} x_ {n} = alpha}$.

Сиди также показал, что

${ displaystyle lim _ {n to infty} { frac {x_ {n + 1} - alpha} { prod _ {i = 0} ^ {k} (x_ {ni} - alpha)} } = L = { frac {(-1) ^ {k + 1}} {(k + 1)!}} { Frac {f ^ {(k + 1)} ( alpha)} {f '( alpha)}},}$

и что последовательность сходится к ${ displaystyle alpha}$ порядка ${ displaystyle psi _ {k}}$, т.е.

${ displaystyle lim limits _ {n to infty} { frac {| x_ {n + 1} - alpha |} {| x_ {n} - alpha | ^ { psi _ {k}} }} = | L | ^ {( psi _ {k} -1) / k}}$

Порядок сходимости ${ displaystyle psi _ {k}}$ это только положительный корень полинома

${ displaystyle s ^ {k + 1} -s ^ {k} -s ^ {k-1} - dots -s-1}$

Например, у нас есть ${ displaystyle psi _ {1} = (1 + { sqrt {5}}) / 2}$ ≈ 1.6180, ${ displaystyle psi _ {2}}$ ≈ 1,8393 и ${ displaystyle psi _ {3}}$ ≈ 1,9276. Порядок приближается к 2 снизу, если k становится большим: ${ displaystyle lim limits _ {k to infty} psi _ {k} = 2}$^[2][3]

Связанные алгоритмы

Метод Сиди сводится к методу секущих, если взять k = 1. В этом случае многочлен ${ displaystyle p_ {n, 1} (x)}$ является линейным приближением ${ displaystyle f}$ вокруг ${ displaystyle alpha}$ который используется в п-я итерация метода секущих.

Можно ожидать, что чем больше мы выберем k, лучшее ${ Displaystyle р_ {п, к} (х)}$ является приближением ${ displaystyle f (x)}$ вокруг ${ Displaystyle х = альфа}$. Кроме того, лучше ${ displaystyle p_ {n, k} '(x)}$ является приближением ${ displaystyle f '(x)}$ вокруг ${ Displaystyle х = альфа}$. Если мы заменим ${ displaystyle p_ {n, k} '}$ с ${ displaystyle f '}$ в (1) получаем, что следующее приближение на каждой итерации вычисляется как

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

(2)

Это Метод Ньютона – Рафсона. Это начинается с одного приближения ${ displaystyle x_ {1}}$ так что мы можем взять k = 0 в (2). Он не требует интерполяционного полинома, но вместо этого необходимо вычислить производную ${ displaystyle f '}$ в каждой итерации. В зависимости от характера ${ displaystyle f}$ это может быть невозможно или нецелесообразно.

Как только интерполирующий полином ${ Displaystyle р_ {п, к} (х)}$ был рассчитан, можно также рассчитать следующее приближение ${ Displaystyle х_ {п + к + 1}}$ как решение ${ displaystyle p_ {n, k} (x) = 0}$ Вместо того, чтобы использовать (1). За k = 1 эти два метода идентичны: это метод секущей. За k = 2 этот метод известен как Метод Мюллера.^[3] За k = 3 этот подход предполагает нахождение корней кубическая функция, что непривлекательно сложно. Эта проблема усугубляется при еще больших значенияхk. Дополнительная сложность заключается в том, что уравнение ${ displaystyle p_ {n, k} (x) = 0}$ в целом будет несколько решений и должен быть дан рецепт, какое из этих решений является следующим приближением ${ Displaystyle х_ {п + к + 1}}$. Мюллер делает это по делу k = 2, но таких рецептов для k > 2.

Рекомендации