| Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален Найдите источники: «Метод домовладельца» – Новости · газеты · книги · ученый · JSTOR (Ноябрь 2013) (Узнайте, как и когда удалить этот шаблон сообщения) |
В математика, а точнее в числовой анализ, Методы домохозяина являются классом алгоритмы поиска корней которые используются для функций одной действительной переменной с непрерывными производными до некоторого порядка d + 1. Каждый из этих методов характеризуется количеством d, который известен как порядок метода. Алгоритм является итеративным и имеет скорость сходимости из d + 1.
Эти методы названы в честь американского математика. Алстон Скотт Хаусхолдер.
Метод
Метод Хаусхолдера - это численный алгоритм решения нелинейного уравнения ж(Икс) = 0. В этом случае функция ж должен быть функцией одной реальной переменной. Метод состоит из последовательности итераций
![x_ {n + 1} = x_ {n} + d ; { frac { left (1 / f right) ^ {(d-1)} (x_ {n})} { left (1 / f right) ^ {(d)} (x_ {n})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b23f6005d9794962abace270986343d6f9d5e350)
начиная с первоначального предположения Икс0.[1]
Если ж это d + 1 раз непрерывно дифференцируемая функция и а это ноль ж но не его производной, то в окрестности а, повторяется Иксп удовлетворить:[нужна цитата ]
, для некоторых ![K> 0. !](https://wikimedia.org/api/rest_v1/media/math/render/svg/81bdd129d0a5e3dd8438e878bb005ab2a64beecb)
Это означает, что итерации сходятся к нулю, если первоначальное предположение достаточно близко, и что сходимость имеет порядок d + 1.
Несмотря на их порядок сходимости, эти методы не получили широкого распространения, потому что выигрыш в точности не соизмерим с увеличением усилий для больших d. В Индекс Островского выражает уменьшение ошибок в количестве вычислений функции вместо количества итераций.[2]
- Для многочленов оценка первого d производные от ж в Иксп с использованием Метод Хорнера прилагает усилия d + 1 полиномиальные оценки. С п(d + 1) оценки за п итераций дает показатель ошибки (d + 1)п, показатель степени для одной оценки функции равен
, численно 1.4142, 1.4422, 1.4142, 1.3797 за d = 1, 2, 3, 4, а после этого падает. - Для общих функций оценка производной с использованием арифметики Тейлора автоматическая дифференциация требует эквивалент (d + 1)(d + 2)/2 оценки функций. Таким образом, оценка одной функции уменьшает ошибку на показатель степени
для метода Ньютона,
для метода Галлея и падение к единице или линейная сходимость для методов более высокого порядка.
Мотивация
Первый подход
Примерное представление о методе Хаусхолдера вытекает из геометрическая серия. Пусть настоящий -значен, непрерывно дифференцируемый функция f (x) иметь простой ноль в Икс = а, это корень ж(а) = 0 кратности один, что эквивалентно
. потом 1/ж(Икс) имеет особенность на а, а именно простой полюс (тоже кратности один) и близкий к а поведение 1/ж(Икс) преобладают 1/(Икс − а). Примерно получается
![{ frac {1} {f (x)}} = { frac {1} {f (x) -f (a)}} = { frac {xa} {f (x) -f (a)} } cdot { frac {-1} {a (1-x / a)}} приблизительно { frac {-1} {af '(a)}} cdot sum _ {k = 0} ^ { infty} left ({ frac {x} {a}} right) ^ {k}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/f332559abd236b4c7c15b1886cdbe70d21d0216f)
Здесь
потому что а простой нуль ж(Икс). Коэффициент степени d имеет ценность
. Таким образом, теперь можно восстановить нулевой а путем деления коэффициента степени d − 1 по коэффициенту степени d. Поскольку этот геометрический ряд является приближением к Расширение Тейлора из 1/ж(Икс), можно получить оценки нуля ж(Икс) - теперь без предварительного знания местоположения этого нуля - путем деления соответствующих коэффициентов разложения Тейлора 1/ж(Икс) или, в более общем смысле, 1/ж(б+Икс). Из этого получается, что для любого целого числа d, и если соответствующие производные существуют,
![a приблизительно 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)} ( б)}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dad222fa630088dc85bb4b16e171696f63849e8)
Второй подход
Предполагать Икс = а это простой корень. Тогда рядом Икс = а, (1/ж)(Икс) это мероморфная функция. Предположим, у нас есть Расширение Тейлора:
![(1 / f) (x) = sum _ {d = 0} ^ { infty} { frac {(1 / f) ^ {(d)} (b)} {d!}} (Xb) ^ {d}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/93a6d5a0637249b1b11adc3557a20cb3b73d3fce)
К Теорема Кенига, у нас есть:
![{ displaystyle ab = 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)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc118434d1f3a36431b3bb3c895e4a297cc877c3)
Это говорит о том, что итерация Хаусхолдера может быть хорошей конвергентной итерацией. Фактическое доказательство сходимости также основано на этой идее.
Методы низшего порядка
Метод домохозяина порядка 1 просто Метод Ньютона, поскольку:
![{ 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/089da8173742980ed852224fb40e27af1a93e4fe)
Для метода Хаусхолдера порядка 2 получается Метод Галлея, поскольку тождества
![textstyle (1 / f) '(x) = - { frac {f' (x)} {f (x) ^ {2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/578a2f64d134c793f8e8a0bed2baae780d87881c)
и
![textstyle (1 / f) '' (x) = - { frac {f '' (x)} {f (x) ^ {2}}} + 2 { frac {f '(x) ^ { 2}} {f (x) ^ {3}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ef41cdb9db1fc27ec56c7cf9a503774a84b1b)
результат в
![{ 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 {массив}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db7caebbe0698395a96add4668acb5f053fa1301)
В последней строке
это обновление итерации Ньютона в точке
. Эта строка была добавлена, чтобы продемонстрировать, в чем заключается отличие от простого метода Ньютона.
Метод третьего порядка получается из тождества производной третьего порядка от 1/ж
![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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83facc4433ba88201b922e1c7646bc4ce36237a6)
и имеет формулу
![{ 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 {массив}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1163f08bc9c31161fc264d21da13c020aa223927)
и так далее.
Пример
Первой задачей, решенной Ньютоном методом Ньютона-Рафсона-Симпсона, было полиномиальное уравнение
. Он заметил, что должно быть решение, близкое к 2. Замена у = Икс + 2 преобразует уравнение в
.
Ряд Тейлора обратной функции начинается с
![{ 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd7051374cce7cd55b6e791929b83b7f86f2485a)
Результат применения методов Хаусхолдера разного порядка на Икс = 0 также получается делением соседних коэффициентов последнего степенного ряда. Для первых заказов после всего одного шага итерации получаются следующие значения: Например, в случае 3-го порядка,
.
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.
Подсчитаем
значения для некоторого самого низкого порядка,
![f = -1 + 10x + 6x ^ {2} + x ^ {3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/163543aec26b1f3760d9f546a8584ec3f391d982)
![f ^ { prime} = 10 + 12x + 3x ^ {2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f7fb978564965bea5bbe0d615599389ecaae5fe)
![f ^ { prime prime} = 12 + 6x](https://wikimedia.org/api/rest_v1/media/math/render/svg/42cb5b3aebc35f4f6bc842cec94a83042033cc81)
![е ^ { прайм прайм прайм} = 6](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b6c4baa2027821702b4428dfc50aa54c91adc83)
И используя следующие отношения,
- 1-й порядок;
![x_ {i + 1} = x_ {i} -f (x_ {i}) / f ^ { prime} (x_ {i})](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2fad2a784e328c6a3a053b54d7922f0e13a5805)
- 2-й порядок;
![x_ {i + 1} = x_ {i} + (- 2ff ^ { prime}) / (2 {f ^ { prime}} ^ {2} -ff ^ { prime prime})](https://wikimedia.org/api/rest_v1/media/math/render/svg/a31789d6cf3a12c96c2cb70298218ac8c5ba75a7)
- 3-й порядок;
![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}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eafb3b0a63f6afc526a70b40218456328d50b4fc)
Икс | 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 функции, где аппроксимант с линейным числитель выбран. Как только это будет достигнуто, обновление для следующего приближения является результатом вычисления уникального нуля числителя.
Приближение Паде имеет вид
![f (x + h) = { frac {a_ {0} + h} {b_ {0} + b_ {1} h + cdots + b_ {d-1} h ^ {d-1}}} + O ( h ^ {d + 1}).](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc9f130a4b99644291437ba8ccacffe4eae2e002)
Рациональная функция имеет нуль в точке
.
Так же, как многочлен Тейлора степени d имеет d + 1 коэффициенты, зависящие от функции ж, приближение Паде также имеет d + 1 коэффициенты, зависящие от ж и его производные. Точнее, в любом приближении Паде степени полиномов числителя и знаменателя должны быть добавлены к порядку аппроксиманта. Следовательно,
должен держать.
Можно было определить аппроксимацию Паде, исходя из полинома Тейлора от ж с помощью Алгоритм Евклида. Однако, исходя из полинома Тейлора от 1/ж короче и приводит непосредственно к данной формуле. С
![(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 (ч ^ {d + 1})](https://wikimedia.org/api/rest_v1/media/math/render/svg/e858d0da3cab85d4ad8e32f80b06bd330ab34ca3)
должно быть равно обратной величине желаемой рациональной функции, мы получаем после умножения на
во власти
уравнение
.
Теперь, решая последнее уравнение относительно нуля
числителя приводит к
.
Отсюда следует итерационная формула
.
Отношение к методу Ньютона
Применение метода Хаусхолдера к вещественной функции ж(Икс) то же самое, что и метод Ньютона, примененный к функции грамм(Икс):
![x _ {{n + 1}} = x_ {n} - { frac {g (x_ {n})} {g '(x_ {n})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef0431705ae192bdb9acb705bbdc7431893412ee)
с
![{ displaystyle g (x) = left | (1 / f) ^ {(d-1)} right | ^ {- 1 / d} ,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed4239592900f00ddc026b6a81b582e01e011b60)
Особенно, d = 1 дает метод Ньютона неизменным и d = 2 дает метод Галлея.
Рекомендации
внешняя ссылка