1 Zakładamy a priori istnienie rozwiązania α układu równań.Przybliżone metody rozwiązywania układów równań nieliniowych – metody iteracyjne Metoda Newtona Zmodyfikowana metoda Newtona Metoda siecznych Zakładamy a priori istnienie rozwiązania α układu równań. Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

2 Metody rozwiązywania układów równań nieliniowych – metoda NewtonaUkład n równań nieliniowych zawierający n niewiadomych: Znane jest k-te przybliżenie wektora x Funkcje fj należy rozwinąć w szereg Taylora w otoczeniu punktu xk z dokładnością do pierwszych pochodnych. Uzyskano układ n równań liniowych. Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

3 Metody rozwiązywania układów równań nieliniowych – metoda NewtonaUzyskano układ n równań liniowych. Z wektorem zmiennych postaci: Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

4 Zapis macierzowy układu równańWartości kolejnych pochodnych dotyczą : Gdzie jest wektorem niewiadomych i W(x)- macierz Jacobiego dla k=0,1,... Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

5 Układ nieliniowych równań algebraicznychdla k=0,1,2, ...., oraz dla i=1,2,...,n Metoda Newtona jest zbieżna, jeżeli przybliżenie x0 jest dostatecznie bliskie rozwiązaniu układu równań. Przykład 1 Dany jest układ równań nieliniowych – znaleźć rozwiązania układu dla czterech przybliżeń początkowych:I [1.3,1.2,0.8]; II [10,20,-10];III [-10, -20, 10]; IV [1000,1000,2000] Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

6 Modyfikacje metody Newtona – dla dużej liczby niewiadomych nJednokrotne obliczenie macierzy Jacobiego dla zerowego przybliżenia rozwiązania dla k=0,1,2, ...., oraz Obliczenia iteracyjne dla k=0,1,2... Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

7 Nad-kreślony układ równań nieliniowych dla mnNorma Pseudo-rozwiązaniem nad-określonego układu (1) nazywamy takie , dla którego norma (2) osiąga minimum Np.: Jeśli funkcje są różniczkowalne w sposób ciągły: metody minimalizacji gradientowe Jeśli funkcje są nieregularne i nie mają wszędzie ciągłych pochodnych: metody minimalizacji bez-gradientowe z oszczędniejszą normą wektora f(x) tzw. Norma maksimum: Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

8 Metody rozwiązywania układów równań nieliniowych – metoda gradientowa – metoda najszybszego spadku NS Jeśli m=n to każde rozwiązanie układu równań nieliniowych jest zerem funkcji U(x) i na odwrót. Wektor x, dla którego U(x)=0 jest pierwiastkiem równania (1). dk- k-ty kierunek poprawy, - współczynnik kroku Współczynnik kroku  jest tak dobrany aby: jeżeli to Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

9 Metoda najszybszego spadku NSjest to metoda gradientowa, która pozwala szukać minimum różniczkowalnej funkcji nieliniowej f(x). Koncepcja metody wynika z lematu, w którym wykazano, że jeśli istnieje I kierunek d w przestrzeni taki, że oraz to Szczegółowo lemat zostanie przedstawiony w ramach wykładu nr 10. Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

10 Algorytm obliczeń – metoda NSWybierz punkt startowy xo=xk. Oblicz wartość funkcji f(xk) oraz jej gradient  f(xk) (2) Zbadaj kryterium zbieżności: Jeśli tak, to koniec, jeśli nie, to przejdź do (3) Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

11 (3) Wyznacz kierunek poszukiwań :(4) Wykonaj minimalizację kierunkową wybraną metodą: (5) Podstaw Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

12 Do minimalizacji w kierunku można użyć kilku algorytmów takich jak npAlgorytmy bez-gradientowe: złotego podziału, aproksymacji kwadratowej, Algorytmy gradientowe: ekspansji i kontrakcji geometrycznej z testem jednoskośnym, logarytmiczny złoty podział odcinka ze wstępną ekspansją i kontrakcją geometryczną, aproksymacji parabolicznej z testem jednoskośnym, bisekcji z testem dwuskośnym Goldstein’a,

13 Algorytm bisekcji z testem dwuskośnym Golstein’a – algorytm gradientowyPraktycznie do wyszukania punktów spełniających test dwuskośny Goldsteina stosuje się następujący algorytm bisekcji: Oblicz pochodną w kierunku oraz współczynnik kroku (2) Wyznacz (3) Jeśli to podstaw i przejdź do kroku (2), w przeciwnym razie przejdź do kroku (4) (4) Jeśli to podstaw i przejdź do kroku (2), w przeciwnym przypadku koniec. Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

14 Działanie algorytmu bisekcji z testem dwuskośnym Goldstein'a dla funkcji: f(x1, x2) = (x1)2 + 2(x2)2 – 6x1 + x1x2 punkt początkowy x0 = (0, 0) kierunek d = (1, 0) współczynnik testu  = początkowa wartość współczynnika kroku R = 9 dokładność dla testu Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

15 Otrzymano wartość pochodnej p:Pochodna w kierunku zatem mamy: dla x = x0 = (0, 0) Otrzymano wartość pochodnej p: Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

16 Przechodzimy do kroku (3)(2) Obliczamy Przechodzimy do kroku (3) Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

17 i przejdź do kroku (2). W przeciwnym wypadku przejdź do kroku (4) (3) Jeżeli to podstaw i przejdź do kroku (2). W przeciwnym wypadku przejdź do kroku (4)  sprawdzamy: ,75 NIE Przechodzimy do kroku (4) Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

18 i przejdź do kroku (2). W przeciwnym wypadku KONIEC (4) Jeżeli to podstaw i przejdź do kroku (2). W przeciwnym wypadku KONIEC sprawdzamy: ,75 >? TAK i przechodzimy do kroku (2)  DRUGA ITERACJA (...) Po trzeciej iteracji otrzymujemy wynik Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

19 Działanie algorytmu najszybszego spadku dla funkcji:f(x1, x2) = 2(x1)2 + (x2)2 – 2 x1x2 punkt początkowy x0 = (2, 3) współczynnik testu  = początkowa wartość współczynnika kroku R = 1

20 Ponieważ pierwsza stosowana wartość współczynnika kroku Obliczamy Ponieważ pierwsza stosowana wartość współczynnika kroku R = 1 spełnia test dwuskośny Goldsteina, więc: x1 = x0 + 0 d0 = [0 1]T W drugiej iteracji mamy: Otrzymujemy: Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

21 Zatem test dwuskośny ma postać -6  202 - 8  -2 Za pomocą algorytmu bisekcji (test dwuskośny Goldsteina) w trzeciej próbie znajdujemy wartość współczynnika 1 = 0,25 Stąd x = x1 + 1 d1 = [ ]T Postępując zgodnie z algorytmem otrzymujemy kolejne wartości punktów optymalizowanej funkcji. Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

22 TAK OTRZYMUJEMY PUNKT MIN (0,0)Kolejno podane są punkty wyznaczone za pomocą algorytmu najszybszego spadku dla funkcji: f(x1, x2) = 2(x1)2 + (x2)2 – 2 x1x2 x0 = [2 3] x1 = [0 1] x2 = [ ] x3 = [ ] x4 = [ ] itd.... I tak kolejno, aż do momentu gdy zostanie spełniony warunek TAK OTRZYMUJEMY PUNKT MIN (0,0) Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic

23 Funkcja celu f(x) Metody numeryczne i optymalizacjiDr inż. Ewa Szlachcic

24 Kolejne iteracje metody najszybszego spadku NSx0 x1 x3 x2 x5 x4 x^ Metody numeryczne i optymalizacji Dr inż. Ewa Szlachcic