1 Metody Numeryczne wykład no 6

2 Rozwiązywanie równań algebraicznychf(x)=0 Metoda bisekcji Przykład: x -1 -0.5 -0.25 -0.125 f(x) -4 1 -1.125 x f(x)

3 x f(x) Zaleta metody: Jeżeli pierwiastek istnieje, to go znajdziemy. Wada metody: Duża liczba obliczeń Regula falsi. Założenia: funkcja ma w przedziale [a,b] tylko jeden pierwiastek i zachodzi f(a)f(b)<0, b) jest funkcja jest klasy C2[a,b], pierwsza i druga pochodna nie zmieniają znaku na przedziale [a,b].

4 Funkcja spełniająca powyższe założenia musi mieć w otoczeniu miejsca zerowego jeden z następujących przebiegów: y y f(b) f(b) a a x x b b f(a) f(a) y y f(a) f(a) b b a a x x f(b) f(b)

5 Przebieg obliczeń metodą regula falsi:y f(b) f(x1) a x x2 x1 b f(a) analitycznie: ustalamy koniec z warunku f(x1)f(a)<0 lub f(x1)f(b)<0 Prowadzimy prostą:

6 ale f(x1)=0 stąd lub Dla n-tej iteracji mamy b=xn-1 i podstawiając mamy:

7 Ocena błędu dla dostatecznie małego przedziału [xn-1,xn]można przyjąć jako: Metoda regula falsi jest zbieżna dowolnej funkcji ciągłej na przedziale [a,b]. Poszukiwanie pierwiastka zostaje zakończone jeżeli: Metoda jest wolno zbieżna. Przykład:

8 w metodzie bisekcji potrzebowaliśmyx -1 -0.2 f(x) -4 1 0.192 Ponieważ f(-1)=-4, a f(x1)=0.192, więc stałym punktem będzie x=-1 w metodzie bisekcji potrzebowaliśmy 14 kroków x f(x) ocena błędu: x f(x)

9 ocena błędu: Metoda siecznych Przepis: Przykład: x -1 -0.2 f(x) -4 1 0.192 w regula falsi potrzeba 8 kroków

10 x f(x) 0.907E-8 w 6-tym kroku Koniecznie trzeba obliczać f(xn) i jeżeli zaczyna narastać należy zawęzić przedział i powtórzyć obliczenia. Niebezpieczeństwo znalezienia fałszywego pierwiastka. Metoda szybsza niż reguła falsi. Pierwsza iteracja musi startować z punktów spełniających warunek: f(a)f(b)<0 x1 a b

11 Pomijając małe drugiego rzędu 2 mamy, że f(x+)=0,Metoda Newtona - Raphsona Niech  małe w mamy: Pomijając małe drugiego rzędu 2 mamy, że f(x+)=0, jeżeli Graficznie: y Równanie prostej stycznej w punkcie xn jest: n x xn+1 xn

12 W 3 krokach dokładność osiągana w metodzie siecznychProsta: przechodzi przez zero, czyli y=0, w punkcie xn+1 i mamy: Przykład: x -0.25 f(x) 1 -0.2E-10 W 3 krokach dokładność osiągana w metodzie siecznych w 5 krokach

13 Metoda Newtona – Raphsona jest zbieżna kwadratowo, tzn.W obliczeniach numerycznych pochodną najczęściej oblicza się numerycznie: f(x) „Pechowe” przypadki: x2 rozbieżna x Zmniejszyć przedział [xd,x0] xd x1 x0

14 Budując procedurę należy się zabezpieczyć przed taką możliwością. f(x) cykl x2=x4=... x xd x1=x3=... Budując procedurę należy się zabezpieczyć przed taką możliwością. Wystartować z punktu x1 znajdującego się bliżej xd Pierwiastki wielokrotne: Przy pierwiastkach wielokrotnych badać funkcję:

15 Pierwiastki zespolonePrzykład Szukamy zespolonych pierwiastków metodą Newtona - Raphsona

16 Jako punkt startowy musimy wybrać liczbę zespoloną:x0=i gdzie xd= i x2= i x3= i x4= i x5= i x6= i błąd= i

17 Układy równań nieliniowychDany jest układ równań: Dla skrócenia zapisu wprowadzamy oznaczenia: oraz

18 i równanie zapisujemy krótko:Metoda iteracji prostej Równanie: zapisujemy w postaci: i procedura iteracji prostej ma postać: Stosowana szczególnie w przypadkach jeżeli mamy dobre przybliżenie początkowe. Sytuacja taka występuje np. w przypadku małej zmiany parametrów równania.

19 Przykład: którego rozwiązaniem jest: x1=1; y1=0 oraz x2=-1; y2=0 Szukamy rozwiązania układu po małej zmianie parametrów: mamy schemat iteracyjny: Jako startowy punkt wybieramy: x0=1; y0=0 i mamy:

20 n 1 2 3 4 xn yn n 5 6 7 8 xn yn n 9 10 11 12 xn yn

21 Z przedstawionych obliczeń widać, że metoda jest wolno zbieżna i dlatego stosowana tylko w przypadkach, gdy znamy bardzo dobrze zerowe przybliżenie. Zastosowanie w równaniach różniczkowych. Metoda Newtona - Raphsona Rozwijamy funkcję fk(X) w szereg Taylora w otoczeniu punktu Xi:

22 Dla uproszczenia zapisu wprowadzamy macierz Jacobiegozdefiniowaną następująco:

23 i w postaci macierzowej możemy krótko zapisać układ równań:gdzie oznaczono: i rozwiązując symbolicznie mamy:

24 Przykład

25

26

27