Метод домовладельцев - Householders method

В математика, а точнее в числовой анализ, Методы домохозяина являются классом алгоритмы поиска корней которые используются для функций одной действительной переменной с непрерывными производными до некоторого порядка d + 1. Каждый из этих методов характеризуется количеством d, который известен как порядок метода. Алгоритм является итеративным и имеет скорость сходимости из d + 1.

Эти методы названы в честь американского математика. Алстон Скотт Хаусхолдер.

Метод

Метод Хаусхолдера - это численный алгоритм решения нелинейного уравнения ж(Икс) = 0. В этом случае функция ж должен быть функцией одной реальной переменной. Метод состоит из последовательности итераций

${\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}$

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

Если ж это d + 1 раз непрерывно дифференцируемая функция и а это ноль ж но не его производной, то в окрестности а, повторяется Икс_п удовлетворить:^{[нужна цитата ]}

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

Это означает, что итерации сходятся к нулю, если первоначальное предположение достаточно близко, и что сходимость имеет порядок d + 1.

Несмотря на их порядок сходимости, эти методы не получили широкого распространения, потому что выигрыш в точности не соизмерим с увеличением усилий для больших d. В Индекс Островского выражает уменьшение ошибок в количестве вычислений функции вместо количества итераций.^[2]

• Для многочленов оценка первого d производные от ж в Икс_п с использованием Метод Хорнера прилагает усилия d + 1 полиномиальные оценки. С п(d + 1) оценки за п итераций дает показатель ошибки (d + 1)^п, показатель степени для одной оценки функции равен ${\displaystyle {\sqrt[{d+1}]{d+1}}}$, численно 1.4142, 1.4422, 1.4142, 1.3797 за d = 1, 2, 3, 4, а после этого падает.
• Для общих функций оценка производной с использованием арифметики Тейлора автоматическая дифференциация требует эквивалент (d + 1)(d + 2)/2 оценки функций. Таким образом, оценка одной функции уменьшает ошибку на показатель степени ${\displaystyle {\sqrt[{3}]{2}}\approx 1.2599}$ для метода Ньютона, ${\displaystyle {\sqrt[{6}]{3}}\approx 1.2009}$ для метода Галлея и падение к единице или линейная сходимость для методов более высокого порядка.

Мотивация

Первый подход

Примерное представление о методе Хаусхолдера вытекает из геометрическая серия. Пусть настоящий -значен, непрерывно дифференцируемый функция f (x) иметь простой ноль в Икс = а, это корень ж(а) = 0 кратности один, что эквивалентно ${\displaystyle f'(a)\neq 0}$. потом 1/ж(Икс) имеет особенность на а, а именно простой полюс (тоже кратности один) и близкий к а поведение 1/ж(Икс) преобладают 1/(Икс − а). Примерно получается

${\displaystyle {\frac {1}{f(x)}}={\frac {1}{f(x)-f(a)}}={\frac {x-a}{f(x)-f(a)}}\cdot {\frac {-1}{a(1-x/a)}}\approx {\frac {-1}{af'(a)}}\cdot \sum _{k=0}^{\infty }\left({\frac {x}{a}}\right)^{k}.}$

Здесь ${\displaystyle f'(a)\neq 0}$ потому что а простой нуль ж(Икс). Коэффициент степени d имеет ценность ${\displaystyle C\,a^{-d}}$. Таким образом, теперь можно восстановить нулевой а путем деления коэффициента степени d − 1 по коэффициенту степени d. Поскольку этот геометрический ряд является приближением к Расширение Тейлора из 1/ж(Икс), можно получить оценки нуля ж(Икс) - теперь без предварительного знания местоположения этого нуля - путем деления соответствующих коэффициентов разложения Тейлора 1/ж(Икс) или, в более общем смысле, 1/ж(б+Икс). Из этого получается, что для любого целого числа d, и если соответствующие производные существуют,

${\displaystyle a\approx b+{\frac {(1/f)^{(d-1)}(b)}{(d-1)!}}\;{\frac {d!}{(1/f)^{(d)}(b)}}=b+d\;{\frac {(1/f)^{(d-1)}(b)}{(1/f)^{(d)}(b)}}.}$

Второй подход

Предполагать Икс = а это простой корень. Тогда рядом Икс = а, (1/ж)(Икс) это мероморфная функция. Предположим, у нас есть Расширение Тейлора:

${\displaystyle (1/f)(x)=\sum _{d=0}^{\infty }{\frac {(1/f)^{(d)}(b)}{d!}}(x-b)^{d}.}$

К Теорема Кенига, у нас есть:

${\displaystyle a-b=\lim _{d\rightarrow \infty }{\frac {\frac {(1/f)^{(d-1)}(b)}{(d-1)!}}{\frac {(1/f)^{(d)}(b)}{d!}}}=\lim _{d\rightarrow \infty }d{\frac {(1/f)^{(d-1)}(b)}{(1/f)^{(d)}(b)}}.}$

Это говорит о том, что итерация Хаусхолдера может быть хорошей конвергентной итерацией. Фактическое доказательство сходимости также основано на этой идее.

Методы низшего порядка

Метод домохозяина порядка 1 просто Метод Ньютона, поскольку:

${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+1\,{\frac {\left(1/f\right)(x_{n})}{\left(1/f\right)^{(1)}(x_{n})}}\\[.7em]=&x_{n}+{\frac {1}{f(x_{n})}}\cdot \left({\frac {-f'(x_{n})}{f(x_{n})^{2}}}\right)^{-1}\\[.7em]=&x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.\end{array}}}$

Для метода Хаусхолдера порядка 2 получается Метод Галлея, поскольку тождества

${\displaystyle \textstyle (1/f)'(x)=-{\frac {f'(x)}{f(x)^{2}}}\ }$

и

${\displaystyle \textstyle \ (1/f)''(x)=-{\frac {f''(x)}{f(x)^{2}}}+2{\frac {f'(x)^{2}}{f(x)^{3}}}}$

результат в

${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+2\,{\frac {\left(1/f\right)'(x_{n})}{\left(1/f\right)''(x_{n})}}\\[1em]=&x_{n}+{\frac {-2f(x_{n})\,f'(x_{n})}{-f(x_{n})f''(x_{n})+2f'(x_{n})^{2}}}\\[1em]=&x_{n}-{\frac {f(x_{n})f'(x_{n})}{f'(x_{n})^{2}-{\tfrac {1}{2}}f(x_{n})f''(x_{n})}}\\[1em]=&x_{n}+h_{n}\;{\frac {1}{1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}}.\end{array}}}$

В последней строке ${\displaystyle h_{n}=-{\tfrac {f(x_{n})}{f'(x_{n})}}}$ это обновление итерации Ньютона в точке ${\displaystyle x_{n}}$. Эта строка была добавлена, чтобы продемонстрировать, в чем заключается отличие от простого метода Ньютона.

Метод третьего порядка получается из тождества производной третьего порядка от 1/ж

${\displaystyle \textstyle (1/f)'''(x)=-{\frac {f'''(x)}{f(x)^{2}}}+6{\frac {f'(x)\,f''(x)}{f(x)^{3}}}-6{\frac {f'(x)^{3}}{f(x)^{4}}}}$

и имеет формулу

${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+3\,{\frac {\left(1/f\right)''(x_{n})}{\left(1/f\right)'''(x_{n})}}\\[1em]=&x_{n}-{\frac {6f(x_{n})\,f'(x_{n})^{2}-3f(x_{n})^{2}f''(x_{n})}{6f'(x_{n})^{3}-6f(x_{n})f'(x_{n})\,f''(x_{n})+f(x_{n})^{2}\,f'''(x_{n})}}\\[1em]=&x_{n}+h_{n}{\frac {1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}{1+(f''/f')(x_{n})\,h_{n}+{\frac {1}{6}}(f'''/f')(x_{n})\,h_{n}^{2}}}\end{array}}}$

и так далее.

Пример

Первой задачей, решенной Ньютоном методом Ньютона-Рафсона-Симпсона, было полиномиальное уравнение ${\displaystyle y^{3}-2y-5=0}$. Он заметил, что должно быть решение, близкое к 2. Замена у = Икс + 2 преобразует уравнение в

${\displaystyle 0=f(x)=-1+10x+6x^{2}+x^{3}}$.

Ряд Тейлора обратной функции начинается с

${\displaystyle {\begin{array}{rl}1/f(x)=&-1-10\,x-106\,x^{2}-1121\,x^{3}-11856\,x^{4}-125392\,x^{5}\\&-1326177\,x^{6}-14025978\,x^{7}-148342234\,x^{8}-1568904385\,x^{9}\\&-16593123232\,x^{10}+O(x^{11})\end{array}}}$

Результат применения методов Хаусхолдера разного порядка на Икс = 0 также получается делением соседних коэффициентов последнего степенного ряда. Для первых заказов после всего одного шага итерации получаются следующие значения: Например, в случае 3-го порядка,${\displaystyle x_{1}=0.0+106/1121=0.09455842997324}$.

d	Икс1
1	0.100000000000000000000000000000000
2	0.094339622641509433962264150943396
3	0.094558429973238180196253345227475
4	0.094551282051282051282051282051282
5	0.094551486538216154140615031261962
6	0.094551481438752142436492263099118
7	0.094551481543746895938379484125812
8	0.094551481542336756233561913325371
9	0.094551481542324837086869382419375
10	0.094551481542326678478801765822985

Как видите, их немного больше, чем d правильные десятичные знаки для каждого порядка d. Первые сто цифр правильного решения 0.0945514815423265914823865405793029638573061056282391803041285290453121899834836671462672817771577578.

Подсчитаем ${\displaystyle x_{2},x_{3},x_{4}}$ значения для некоторого самого низкого порядка,

${\displaystyle f=-1+10x+6x^{2}+x^{3}}$

${\displaystyle f^{\prime }=10+12x+3x^{2}}$

${\displaystyle f^{\prime \prime }=12+6x}$

${\displaystyle f^{\prime \prime \prime }=6}$

И используя следующие отношения,

1-й порядок; ${\displaystyle x_{i+1}=x_{i}-f(x_{i})/f^{\prime }(x_{i})}$

2-й порядок; ${\displaystyle x_{i+1}=x_{i}+(-2ff^{\prime })/(2{f^{\prime }}^{2}-ff^{\prime \prime })}$

3-й порядок; ${\displaystyle x_{i+1}=x_{i}-{\frac {6f{f^{\prime }}^{2}-3f^{2}f^{\prime \prime }}{6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime }}}}$

Икс	1-й (Ньютон)	2-й (Галлей)	3-й порядок	4-й порядок
Икс1	0.100000000000000000000000000000000	0.094339622641509433962264150943395	0.094558429973238180196253345227475	0.09455128205128
Икс2	0.094568121104185218165627782724844	0.094551481540164214717107966227500	0.094551481542326591482567319958483
Икс3	0.094551481698199302883823703544266	0.094551481542326591482386540579303	0.094551481542326591482386540579303
Икс4	0.094551481542326591496064847153714	0.094551481542326591482386540579303	0.094551481542326591482386540579303
Икс5	0.094551481542326591482386540579303
Икс6	0.094551481542326591482386540579303

Вывод

Точный вывод методов Хаусхолдера начинается с Приближение Паде порядка d + 1 функции, где аппроксимант с линейным числитель выбран. Как только это будет достигнуто, обновление для следующего приближения является результатом вычисления уникального нуля числителя.

Приближение Паде имеет вид

${\displaystyle f(x+h)={\frac {a_{0}+h}{b_{0}+b_{1}h+\cdots +b_{d-1}h^{d-1}}}+O(h^{d+1}).}$

Рациональная функция имеет нуль в точке ${\displaystyle h=-a_{0}}$.

Так же, как многочлен Тейлора степени d имеет d + 1 коэффициенты, зависящие от функции ж, приближение Паде также имеет d + 1 коэффициенты, зависящие от ж и его производные. Точнее, в любом приближении Паде степени полиномов числителя и знаменателя должны быть добавлены к порядку аппроксиманта. Следовательно, ${\displaystyle b_{d}=0}$ должен держать.

Можно было определить аппроксимацию Паде, исходя из полинома Тейлора от ж с помощью Алгоритм Евклида. Однако, исходя из полинома Тейлора от 1/ж короче и приводит непосредственно к данной формуле. С

${\displaystyle (1/f)(x+h)=(1/f)(x)+(1/f)'(x)h+\cdots +(1/f)^{(d-1)}(x){\frac {h^{d-1}}{(d-1)!}}+(1/f)^{(d)}(x){\frac {h^{d}}{d!}}+O(h^{d+1})}$

должно быть равно обратной величине желаемой рациональной функции, мы получаем после умножения на ${\displaystyle a_{0}+h}$ во власти ${\displaystyle h^{d}}$ уравнение

${\displaystyle 0=b_{d}=a_{0}(1/f)^{(d)}(x){\frac {1}{d!}}+(1/f)^{(d-1)}(x){\frac {1}{(d-1)!}}}$.

Теперь, решая последнее уравнение относительно нуля ${\displaystyle h=-a_{0}}$ числителя приводит к

${\displaystyle {\begin{array}{rl}h=&-a_{0}={\frac {{\frac {1}{(d-1)!}}(1/f)^{(d-1)}(x)}{{\frac {1}{d!}}(1/f)^{(d)}(x)}}\\[1em]=&d\,{\frac {(1/f)^{(d-1)}(x)}{(1/f)^{(d)}(x)}}\end{array}}}$.

Отсюда следует итерационная формула

${\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}$.

Отношение к методу Ньютона

Применение метода Хаусхолдера к вещественной функции ж(Икс) то же самое, что и метод Ньютона, примененный к функции грамм(Икс):

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

с

${\displaystyle g(x)=\left|(1/f)^{(d-1)}\right|^{-1/d}\,.}$

Особенно, d = 1 дает метод Ньютона неизменным и d = 2 дает метод Галлея.

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

1. Домохозяин, Олстон Скотт (1970). Численное рассмотрение одного нелинейного уравнения. Макгроу-Хилл. п.169. ISBN  0-07-030465-3.
2. Островский, А. М. (1966). Решение уравнений и систем уравнений. Чистая и прикладная математика. 9 (Второе изд.). Нью-Йорк: Academic Press.

внешняя ссылка

• Паскаль Себа и Ксавье Гурдон (2001). «Метод Ньютона и итерация высокого порядка». Примечание: Использовать PostScript версия этой ссылки; версия сайта скомпилирована некорректно.