Kryteria zbieżnosci metody Newtona

Przybliżanie, metoda najmniejszych kwadratów, wielomiany interpolacyjne i inne.
Awatar użytkownika
Borneq
Użytkownik
Użytkownik
Posty: 247
Rejestracja: 23 lip 2010, o 07:50
Płeć: Mężczyzna
Lokalizacja: geo:lat=0 geo:lon=0
Podziękował: 13 razy

Kryteria zbieżnosci metody Newtona

Post autor: Borneq »

Jakie są kryteria zbieżności tej metody? Zarówno w przypadku jedno- jak i wielowymiarowym, metoda Newtona znana jest jako szybka, ale niekoniecznie zbieżna metoda. Czy są jednak jakieś kryteria, po spełnieniu których (chodzi o miejsce wyboru punktu startowego) będzie zawsze zbieżna?
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Kryteria zbieżnosci metody Newtona

Post autor: janusz47 »

Metoda Newona jest zbieżna z kwadratem.

Żąda ciągłości funkcji \(\displaystyle{ f, f', f'' }\) w sąsiedztwie pierwiastka \(\displaystyle{ r }\) funkcji \(\displaystyle{ f, }\) żąda \(\displaystyle{ f'(r) \neq 0 }\) i odpowiedniego wyboru punktu początkowego (startowego) \(\displaystyle{ x_{0},\ \ |r -x_{0}| \leq \delta.}\)

Analizę zbieżności i błędu metody polecam z podręcznika

DAVID KINCAID WARD CHENEY analiza numeryczna. Wydawnictwa Naukowo - Techniczne Warszawa 2006.
Załączniki
Rozbieżność.jpg
Rozbieżność.jpg (2.04 MiB) Przejrzano 642 razy
Ostatnio zmieniony 18 wrz 2022, o 20:52 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Borneq
Użytkownik
Użytkownik
Posty: 247
Rejestracja: 23 lip 2010, o 07:50
Płeć: Mężczyzna
Lokalizacja: geo:lat=0 geo:lon=0
Podziękował: 13 razy

Re: Kryteria zbieżnosci metody Newtona

Post autor: Borneq »

Tu mam układ równań , który w Sage daje

Kod: Zaznacz cały

var ('x y')
eq1 =-0.351123+0.498491*x+0.661281*y+0.215502*x^2-0.490734*x*y-0.302189*y^2 == 0
eq2 =-0.125709+0.771403*x-0.545184*y-0.245186*x^2-1.802217*x*y+0.769120*y^2 == 0
solutions = solve([eq1, eq2], x, y)
print(solutions)
[
[x == 0.009391870239357112, y == 0.9016970198675497],
[x == 0.2185784658691063, y == 1.186851361327022],
[x == 0.4896756082345602, y == 0.1469892668728397],
[x == -1.043734230445753, y == 0.6520079185520362]
]
metoda Newtona daje jeszcze lepsze przybliżenie pierwiastków:

Kod: Zaznacz cały

roots[4][2] = {{0.00939187054983161,0.901697014632288},
                      {0.218578480937716,1.18685135954793},
                      {0.489675607879736,0.146989272115097},
                      {-1.04373412714342,0.652007908387428}};
Załączam , jak dla tego przykładu wyglądają obszary przyciągania pierwiastków
kolor szary - nie zbiega do żadnego pierwiastka
Jest to obszar [-2,2][-2,2]
Pytanie, czy jest jakieś kryterium, że dla pewnego obszaru w którym leży pierwiastek (niekoniecznie w jego środku) cały obszar jest jednego koloru?
Załączniki
obszary przyciągania pierwiastków
obszary przyciągania pierwiastków
roots_attraction.png (4.06 KiB) Przejrzano 593 razy
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Kryteria zbieżnosci metody Newtona

Post autor: janusz47 »

Metoda Newtona w dziedzinie zespolonej:

\(\displaystyle{ z_{0}= z; \ \ z_{n+1} = z_{n} - \frac{p_{n}}{p^{'}(z_{n})} , \ \ n\geq 0 }\)

Założenia:
\(\displaystyle{ p_{n}(z) }\) wielomian stopnia conamniej drugiego i \(\displaystyle{ \xi }\) - jeden z jego pierwiastków.

Jeśli \(\displaystyle{ \lim_{n\to \infty} z_{n} = \xi }\) to punkt \(\displaystyle{ z }\) jest przyciągany przez \(\displaystyle{ \xi. }\)

Zbiór wszystkich punktów \(\displaystyle{ z }\) przyciąganych przez \(\displaystyle{ \xi }\) jest zbiorem przyciągania.

Każdy pierwiastek wielomianu ma swój zbiór przyciągania. Zbiory przyciągania są parami rozłączne, bo ciąg zbieżny do jednego pierwiastka nie może być zbieżny do drugiego.

Są liczby zespolone które nie należą do żadnego zbioru przyciągania - są to punkty dla których Metoda Newtona nie jest zbieżna.

Te punkty tworzą zbiór Julii wielomianu \(\displaystyle{ p_{n} }\) dla upamiętnienia prac francuskiego matematyka Gaston Julia.

" Jeśli wszystkie pierwiastki wielomianu \(\displaystyle{ p_{n} }\) są pojedyńcze to zbiory przyciągania są otwarte, zbiór Julii składa się z brzegów tych zbiorów."

Nie spotkałem kryterium dla jednokolorowch obszarów przyciągania.
ODPOWIEDZ