Basen przyciągania dla metody Newtona

9

Metoda Newtona rozwiązywania równań nieliniowych jest znana, że zbiega się kwadratowo, gdy domysły początkowe są „wystarczająco blisko” do rozwiązania.

Co jest „wystarczająco blisko”?

Czy istnieje literatura na temat struktury tego basenu przyciągania?

iterative-method convergence nonlinear-equations David Ketcheson
źródło

Katalog główny powinien być izolowany (nie wielokrotny). Jeśli Hesjan jest jednoznacznie określony (wklęsły w górę lub w dół) w regionie, powinieneś iść. Oczywiście zagwarantowanie lub przetestowanie tych warunków empirycznie jest zwykle niepraktyczne.

hardmath

Pewnego dnia zobaczyłem pytanie w NA-Digest i uznałem to za intrygujące. Najwyraźniej nie byłem jedyny :-)

Wolfgang Bangerth,

8

W przypadku pojedynczego racjonalnego równania w dziedzinie złożonej, basenem przyciągania jest fraktal, uzupełnienie tak zwanego zbioru Julii. http://en.wikipedia.org/wiki/Julia_set . Teorię z kilkoma ładnymi liczbami online można znaleźć np.
Http://mathlab.mathlab.sunysb.edu/~scott/Papers/Newton/Published.pdf
http://hera.ugr.es/doi/15019160.pdf

Nawet „zglobalizowana” tłumiona metoda Newtona dla ma fraktalny basen przyciągania; patrz http://www.jstor.org/stable/10.2307/2653002 . $x^3-1=0$

Dlatego nie ma sensu szczegółowo określać, co jest „wystarczająco blisko” do rozwiązania. Jeśli znamy granice drugich pochodnych, istnieje twierdzenie Newtona - Kantorowicza, które podaje dolne granice promienia kuli, w której zbiega się metoda Newtona, ale z wyjątkiem 1D są one dość pesymistyczne.

Przydatne obliczeniowo granice można uzyskać za pomocą arytmetyki przedziałowej; patrz np. mój artykuł
Shen Zuhe i A. Neumaier, operator Krawczyka i twierdzenie Kantorovicha, J. Math. Analny. Appl. 149 (1990), 437–443.
http://www.mat.univie.ac.at/~neum/scan/61.pdf

Arnold Neumaier
źródło

Tylko w płaszczyźnie złożonej ma fraktalny basen przyciągania. W rzeczywistej linii, każde początkowe przypuszczenie zrobi (kiedy zbieżność spadnie monontonowo i szybko pojawi się szybkość kwadratowa).

x^{3} - 1 = 0

$x^3 - 1 = 0$

x > 0

$x > 0$

x > 1

$x > 1$

hardmath

1

@hardmath: tak, ale równanie złożone staje się dwoma równaniami rzeczywistymi w 2 zmiennych, do których to samo dotyczy.

Arnold Neumaier

4

„Wystarczająco blisko” jest trudne do scharakteryzowania, biorąc pod uwagę, że daje początek klasie fraktali . Metody Newtona ze strategiami globalizacji, takimi jak wyszukiwanie linii i region zaufania, rozszerzają basen przyciągania. Jeśli dostępna jest dodatkowa struktura problemu, np. W zakresie optymalizacji, założenia konieczne do konwergencji mogą zostać jeszcze bardziej osłabione.

Jed Brown
źródło

Czy dla ciekawości masz jakiś przykład na „Jeśli dostępna jest dodatkowa struktura problemu, na przykład podczas optymalizacji, założenia niezbędne do konwergencji mogą zostać jeszcze bardziej osłabione”.

vanCompute,

@vanCompute Zobacz ten przykład, aby zapoznać się z przykładem związanym z optymalizacją, w którym funkcja obiektu zapewnia informacje utracone w warunkach optymalizacyjnych pierwszego rzędu. Inną formą byłaby wiedza, że pewna kontynuacja (pseudotransjentowa, parametr, siatka itp.) Zawsze była zbieżna, ale wartość rezydualna może wymagać zwiększenia przed osiągnięciem rozwiązania, jeśli ktoś spróbuje rozwiązać problem bezpośrednio.

Jed Brown

3

Istnieje kilka użytecznych wyników dla metody Newtona zastosowanej do złożonych wielomianów.

Joel Friedman w On Convergence of Newton's Method (Theorem 2.2) podaje wyraźny promień dysku zawartego w bezpośrednim basenie przyciągania każdego z pierwiastków wielomianu : gdzie jest minimalna odległość między dwoma pierwiastkami i to stopień . $f$

r = \frac{η}{2 d}

$r=\frac{\eta}{2d}$

η

$\eta$

f

$f$

d

$d$

f

$f$

Inne wyraźne granice zostały podane przez Anthony'ego Manninga w Jak się upewnić, że znajdujemy pierwiastek złożonego wielomianu za pomocą metody Newtona (Twierdzenie 1.2).

Zobacz także Jak znaleźć wszystkie pierwiastki złożonych wielomianów metodą Newtona autorstwa Hubbarda i in.
Wymyślać. Matematyka 146 (2001), no. 1, 1–33. pdf

lhf
źródło

Na podstawie math.stackexchange.com/a/1038487/589 .

lhf

Basen przyciągania dla metody Newtona

Odpowiedzi: