Matematyka.pl

Cześć!
Mam pewien problem związany z metodami numerycznymi, z którym się trudzę od paru dobrych dni, a mianowicie nie mam pomysłu jak udowodnić, że ciąg przybliżeń uzyskanych w metodzie Newtona (stycznych) dla funkcji f w przedziale \(\displaystyle{ [c,d]}\) jest malejący, gdy \(\displaystyle{ f'(x) \cdot f''(x)>0}\) oraz jest rosnący, gdy \(\displaystyle{ f'(x)\cdot f''(x)<0}\)
Na razie doszłam do wniosku, że różnica \(\displaystyle{ n+2}\) i \(\displaystyle{ n+1}\) przybliżenia jest równa \(\displaystyle{ \frac{f(x_{n+1})}{f'(x_{n+1})}}\)
Bardzo proszę o pomoc lub jakąś wskazówkę.

Stałość znaków pierwszej i drugiej pochodnej funkcji \(\displaystyle{ f\in C^2[c,d]}\) różniczkowalnej w sposób ciągły, jest warunkiem koniecznym zbieżności Metody Newtona (Metody Stycznych)- warunkiem wyboru punktu startowego tej metody.

Metodę Newtona można traktować jako szczególny przypadek iteracji prostych,

gdzie:

\(\displaystyle{ \phi(x) = x - \frac{f(x)}{f'(x)}.}\)

Rozwijając funkcję \(\displaystyle{ \phi}\) w szereg Taylora w punkcie \(\displaystyle{ x^{*}}\) otrzymujemy:

\(\displaystyle{ x_{k} - x^{*}= \phi(x_{k-1}) - \phi(x^{*}) = (x_{k-1} - x^{*})\phi(x^{*})+ (x_{k-1}-x^{*})^2 \frac{\phi''(\xi_{k})}{2!}}\) (1)

gdzie:

\(\displaystyle{ min(x*, x_{k-1}) \leq \xi_{k}\leq max (x^{*}, x_{k-1}).}\)

Uwzględniając w równości (1) :

\(\displaystyle{ \phi'(x) = 1 - \frac{f'(x)^2 - f(x)f''(x)}{f'^2(x)}= \frac{f(x)f''(x)}{f'^2(x)}= 0}\)

oraz

\(\displaystyle{ \phi''(\xi_{k}) = \frac{f''(\xi_{k})}{f'(\xi_{k})}}\)

otrzymujemy:

\(\displaystyle{ x_{k}-x^{*} = (x_{k-1}-x^{*})^2 \frac{f''(\xi_{k})}{2f'(\xi_{k})}}\) (2)

Równość (2) możemy zapisać w postaci:

\(\displaystyle{ x_{k}-x^{*} = x_{k-1}- x^{*} - \frac{(x_{k-1}-x^{*})^2 f''(\xi_{k})}{2!(x_{k-1}-x^{*})f'(\eta_{k})}.}\)

Stąd:

\(\displaystyle{ x_{k}-x_{k-1}= -(x_{k-1}-x^{*})\frac{f''(\xi_{k})}{2!f'(\eta_{k})}}\) (3)


Z równania (3) możemy wywnioskować, że

- jeżeli iloraz, a więc i iloczyn pochodnych \(\displaystyle{ f' , f''}\) jest ujemny, to różnica

\(\displaystyle{ x_{k} - x_{k-1} >0}\) - jest dodatnia - ciąg iteracji (przybliżeń) jest rosnący.

- jeżeli iloraz, a więc i iloczyn pochodnych \(\displaystyle{ f' , f''}\) jest dodatni, to różnica
\(\displaystyle{ x_{k} - x_{k-1} <0}\) - jest ujemna - ciąg iteracji (przybliżeń) jest malejący.

Proszę wykonać odpowiednie wykresy funkcji rosnących, malejących ,wypukłych i wklęsłych, wykazując geometrycznie prawdziwość wyżej wymienionego twierdzenia.

janusz47 pisze:Stałość znaków pierwszej i drugiej pochodnej funkcji \(\displaystyle{ f\in C^2[c,d]}\) różniczkowalnej w sposób ciągły, jest warunkiem koniecznym zbieżności Metody Newtona (Metody Stycznych)- warunkiem wyboru punktu startowego tej metody.

Metodę Newtona można traktować jako szczególny przypadek iteracji prostych,

gdzie:

\(\displaystyle{ \phi(x) = x - \frac{f(x)}{f'(x)}.}\)

Rozwijając funkcję \(\displaystyle{ \phi}\) w szereg Taylora w punkcie \(\displaystyle{ x^{*}}\) otrzymujemy:

\(\displaystyle{ x_{k} - x^{*}= \phi(x_{k-1}) - \phi(x^{*}) = (x_{k-1} - x^{*})\phi(x^{*})+ (x_{k-1}-x^{*})^2 \frac{\phi''(\xi_{k})}{2!}}\) (1)

gdzie:

\(\displaystyle{ min(x*, x_{k-1}) \leq \xi_{k}\leq max (x^{*}, x_{k-1}).}\)

Uwzględniając w równości (1) :

\(\displaystyle{ \phi'(x) = 1 - \frac{f'(x)^2 - f(x)f''(x)}{f'^2(x)}= \frac{f(x)f''(x)}{f'^2(x)}= 0}\)

oraz

\(\displaystyle{ \phi''(\xi_{k}) = \frac{f''(\xi_{k})}{f'(\xi_{k})}}\)

otrzymujemy:

\(\displaystyle{ x_{k}-x^{*} = (x_{k-1}-x^{*})^2 \frac{f''(\xi_{k})}{2f'(\xi_{k})}}\) (2)

Równość (2) możemy zapisać w postaci:

\(\displaystyle{ x_{k}-x^{*} = x_{k-1}- x^{*} - \frac{(x_{k-1}-x^{*})^2 f''(\xi_{k})}{2!(x_{k-1}-x^{*})f'(\eta_{k})}.}\)

Stąd:

\(\displaystyle{ x_{k}-x_{k-1}= -(x_{k-1}-x^{*})\frac{f''(\xi_{k})}{2!f'(\eta_{k})}}\) (3)


Z równania (3) możemy wywnioskować, że

- jeżeli iloraz, a więc i iloczyn pochodnych \(\displaystyle{ f' , f''}\) jest ujemny, to różnica

\(\displaystyle{ x_{k} - x_{k-1} >0}\) - jest dodatnia - ciąg iteracji (przybliżeń) jest rosnący.

- jeżeli iloraz, a więc i iloczyn pochodnych \(\displaystyle{ f' , f''}\) jest dodatni, to różnica
\(\displaystyle{ x_{k} - x_{k-1} <0}\) - jest ujemna - ciąg iteracji (przybliżeń) jest malejący.

Proszę wykonać odpowiednie wykresy funkcji rosnących, malejących ,wypukłych i wklęsłych, wykazując geometrycznie prawdziwość wyżej wymienionego twierdzenia.

Dlaczego wyrażenie \(\displaystyle{ (x_{k-1}-x^{*})}\) jest dodatnie? I trochę nie rozumiem dlaczego zachodzi taka równość: \(\displaystyle{ \phi'(x) = 1 - \frac{f'(x)^2 - f(x)f''(x)}{f'^2(x)}= \frac{f(x)f''(x)}{f'^2(x)}= 0}\)?

Dodatniość wyrażenia wynika z rozwinięcia (1).

\(\displaystyle{ \phi'(x)}\) jest równa zeru, bo poszukujemy takiego argumentu \(\displaystyle{ x = x^{*}}\) dla którego \(\displaystyle{ f(x)= 0.}\)

janusz47 pisze:Dodatniość wyrażenia wynika z rozwinięcia (1).

\(\displaystyle{ \phi'(x)}\) jest równa zeru, bo poszukujemy takiego argumentu \(\displaystyle{ x = x^{*}}\) dla którego \(\displaystyle{ f(x)= 0.}\)

Bardzo dziękuję za pomoc! Ale niestety metoda iteracji prostej nie jest mi znana i trudno mi rozumieć przebieg Twojego rozumowania.

Proszę zapoznać się z tą metodą. Metoda Newtona jest jej jednym ze szczególnych przypadków.

janusz47 pisze:Proszę zapoznać się z tą metodą. Metoda Newtona jest jej jednym ze szczególnych przypadków.

Dlaczego dodatniość wyżej wymienionego wyrażenia, o którym była wcześniej mowa, wynika z \(\displaystyle{ (1)}\)? Mógłbyś to wytłumaczyć nieco bardziej?

Patrz rozwinięcie funkcji szereg Taylora.

janusz47 pisze:Patrz rozwinięcie funkcji szereg Taylora.

Dlaczego \(\displaystyle{ \phi''(\xi_{k}) = \frac{f''(\xi_{k})}{f'(\xi_{k})}}\) ma taką postać?

Z policzenia pochodnej drugiego rzędu \(\displaystyle{ \phi'' (x)}\), podstawienia w uzyskanym wzorze \(\displaystyle{ f(x)= 0}\) oraz uproszczenia licznika i mianownika przez \(\displaystyle{ f'^2(x).}\)

janusz47 pisze:Z policzenia pochodnej drugiego rzędu \(\displaystyle{ \phi'' (x)}\), podstawienia w uzyskanym wzorze \(\displaystyle{ f(x)= 0}\) oraz uproszczenia licznika i mianownika przez \(\displaystyle{ f'^2(x).}\)

Dlaczego podstawiamy za \(\displaystyle{ f(x)=0}\) skoro obliczamy drugą pochodną dla \(\displaystyle{ x=\xi_{k}}\) funkcji \(\displaystyle{ \phi(x)}\), a w naszym przypadku poszukujemy takiego \(\displaystyle{ x^{*}}\), dla którego \(\displaystyle{ f(x^{*})=0}\)?

Bo Metoda Newtona jak i inne metody numeryczne rozwiązywania jednoargumentowych równań nieliniowych np. Metoda Bisekcji(Połowienia), Metoda Cięciw, Reguła Falsi, Fixed Point ... znajdują argumenty w których wartość funkcji jest równa zeru.

janusz47 pisze:Bo Metoda Newtona jak i inne metody numeryczne rozwiązywania jednoargumentowych równań nieliniowych np. Metoda Bisekcji(Połowienia), Metoda Cięciw, Reguła Falsi, Fixed Point ... znajdują argumenty w których wartość funkcji jest równa zeru.

i dlatego możemy od tak sobie przyjąć, że \(\displaystyle{ f(x)=0}\) mimo, że liczymy pochodną dla punktu, w którym nie musi tak być?

Tak, uwzględniając już wartość zerową funkcji w pochodnej \(\displaystyle{ \phi'(x).}\)

Proponuję Pani podręcznik z Metod Numerycznych np:

Michelle Schatzmann. Numerical Analysis a mathematical introduction. Ed. CLARENDON PRESS OXFORD 2002.

lub

Endre Suli and David Mayers An Introduction to Numerical Analysis .Ed. CAMBRIDGE UNIVERSITY PRESS 2003.

janusz47 pisze:Tak, uwzględniając już wartość zerową funkcji w pochodnej \(\displaystyle{ \phi'(x).}\)

Proponuję Pani podręcznik z Metod Numerycznych np:

Michelle Schatzmann. Numerical Analysis a mathematical introduction. Ed. CLARENDON PRESS OXFORD 2002.

lub

Endre Suli and David Mayers An Introduction to Numerical Analysis .Ed. CAMBRIDGE UNIVERSITY PRESS 2003.

Moje ostatnie pytanie:
Skąd takie przekształcenie? \(\displaystyle{ x_{k}-x^{*} = x_{k-1}- x^{*} - \frac{(x_{k-1}-x^{*})^2 f''(\xi_{k})}{2!(x_{k-1}-x^{*})f'(\eta_{k})}.}\)?