Метод Галлея

В численном анализе , метод Галлея является алгоритм корневого нахождения используется для функций одной действительных переменных с непрерывной второй производной. Он назван в честь своего изобретателя Эдмонда Галлея .

Алгоритм является вторым в классе методов Хаусхолдера после метода Ньютона . Подобно последнему, он итеративно производит последовательность приближений к корню; их скорость сходимости к корню кубическая. Существуют многомерные версии этого метода.

Метод Галлея точно находит корни линейно-линейного приближения Паде к функции, в отличие от метода Ньютона или метода Секанта, который приближает функцию линейно, или метода Мюллера, который приближает функцию квадратично. ^[1]

Метод

Эдмонд Галлей был английским математиком, который представил метод, который теперь носит его имя. Метод Галлея представляет собой численный алгоритм решения нелинейного уравнения f ( x ) = 0. В этом случае функция f должна быть функцией одной действительной переменной. Метод состоит из последовательности итераций:

${\ displaystyle x_ {n + 1} = x_ {n} - {\ frac {2f (x_ {n}) f '(x_ {n})} {2 {[f' (x_ {n})]} ^ {2} -f (x_ {n}) f '' (x_ {n})}}}$

начиная с первоначального предположения x ₀ . ^[2]

Если f является трижды непрерывно дифференцируемой функцией и a является нулем функции f, но не ее производной, то в окрестности точки a итерации x _n удовлетворяют:

${\ displaystyle | x_ {n + 1} -a | \ leq K \ cdot {| x_ {n} -a |} ^ {3}, {\ text {для некоторых}} K> 0.}$

Это означает, что итерации сходятся к нулю, если первоначальное предположение достаточно близко, и что сходимость кубическая. ^[3]

Следующая альтернативная формулировка показывает сходство между методом Галлея и методом Ньютона. Выражение вычисляется только один раз и особенно полезно, когда его можно упростить:${\ Displaystyle f (x_ {n}) / f '(x_ {n})}$${\ displaystyle f '' (x_ {n}) / f '(x_ {n})}$

${\ displaystyle x_ {n + 1} = x_ {n} - {\ frac {f (x_ {n})} {f '(x_ {n}) - {\ frac {f (x_ {n})} { f '(x_ {n})}} {\ frac {f' '(x_ {n})} {2}}}} = x_ {n} - {\ frac {f (x_ {n})} {f '(x_ {n})}} \ left [1 - {\ frac {f (x_ {n})} {f' (x_ {n})}} \ cdot {\ frac {f '' (x_ {n })} {2f '(x_ {n})}} \ right] ^ {- 1}.}$

Когда вторая производная очень близка к нулю, итерация метода Галлея почти такая же, как итерация метода Ньютона.

Вывод

Рассмотрим функцию

${\ displaystyle g (x) = {\ frac {f (x)} {\ sqrt {| f '(x) |}}}.}$

Любой корень из f, который не является корнем своей производной, является корнем из g ; и любой корень r из g должен быть корнем из f при условии, что производная f в r не бесконечна. Применение метода Ньютона к g дает

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

с

${\displaystyle g'(x)={\frac {2[f'(x)]^{2}-f(x)f''(x)}{2f'(x){\sqrt {|f'(x)|}}}},}$

и результат следует. Обратите внимание, что если f ′ ( c ) = 0, то нельзя применить это в c, потому что g ( c ) будет неопределенным.

Кубическая сходимость

Предположим, что a является корнем f, но не его производной. И предположим, что третья производная f существует и непрерывна в окрестности точки a, а x _n находится в этой окрестности. Тогда из теоремы Тейлора следует:

${\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(x_{n})}{2}}(a-x_{n})^{2}+{\frac {f'''(\xi )}{6}}(a-x_{n})^{3}}$

а также

${\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(\eta )}{2}}(a-x_{n})^{2},}$

где ξ и η - числа, лежащие между a и x _n . Умножьте первое уравнение на и вычтите из него второе уравнение раз, чтобы получить:${\displaystyle 2f'(x_{n})}$${\displaystyle f''(x_{n})(a-x_{n})}$

${\displaystyle {\begin{aligned}0&=2f(x_{n})f'(x_{n})+2[f'(x_{n})]^{2}(a-x_{n})+f'(x_{n})f''(x_{n})(a-x_{n})^{2}+{\frac {f'(x_{n})f'''(\xi )}{3}}(a-x_{n})^{3}\\&\qquad -f(x_{n})f''(x_{n})(a-x_{n})-f'(x_{n})f''(x_{n})(a-x_{n})^{2}-{\frac {f''(x_{n})f''(\eta )}{2}}(a-x_{n})^{3}.\end{aligned}}}$

Условия отмены и реорганизации дают:${\displaystyle f'(x_{n})f''(x_{n})(a-x_{n})^{2}}$

${\displaystyle 0=2f(x_{n})f'(x_{n})+\left(2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})\right)(a-x_{n})+\left({\frac {f'(x_{n})f'''(\xi )}{3}}-{\frac {f''(x_{n})f''(\eta )}{2}}\right)(a-x_{n})^{3}.}$

Поместите второй член слева и разделите на

${\displaystyle 2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}$

получить:

${\displaystyle a-x_{n}={\frac {-2f(x_{n})f'(x_{n})}{2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}}-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{6(2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n}))}}(a-x_{n})^{3}.}$

Таким образом:

${\displaystyle a-x_{n+1}=-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{12[f'(x_{n})]^{2}-6f(x_{n})f''(x_{n})}}(a-x_{n})^{3}.}$

Предел коэффициента в правой части при x _n → a равен:

${\displaystyle -{\frac {2f'(a)f'''(a)-3f''(a)f''(a)}{12[f'(a)]^{2}}}.}$

Если мы возьмем K немного больше, чем абсолютное значение этого, мы можем взять абсолютные значения обеих сторон формулы и заменить абсолютное значение коэффициента его верхней границей рядом с a, чтобы получить:

${\displaystyle |a-x_{n+1}|\leq K|a-x_{n}|^{3}}$

что и должно было быть доказано.

Подвести итоги,

${\displaystyle \Delta x_{i+1}={\frac {3(f'')^{2}-2f'f'''}{12(f')^{2}}}(\Delta x_{i})^{3}+O[\Delta x_{i}]^{4},\qquad \Delta x_{i}\triangleq x_{i}-a.}$^[4]

использованная литература

Петко Д. Пройнов, Стоил И. Иванов, О сходимости метода Галлея для кратных полиномиальных нулей, Mediterranean J. Math. 12, 555 - 572 (2015)

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

• Вайсштейн, Эрик В. «Метод Галлея» . MathWorld .
• Метод Ньютона и итерации высокого порядка , Паскаль Себа и Ксавье Гурдон, 2001 (на сайте есть ссылка на версию Postscript для лучшего отображения формул)