Podstawy informatyki 2
Podstawy informatyki 2
Politechnika Bia
Politechnika Bia
ł
ł
ostocka
ostocka
-
-
Wydzia
Wydzia
ł
ł
Elektryczny
Elektryczny
Elektrotechnika, semestr II, studia stacjonarne
Elektrotechnika, semestr II, studia stacjonarne
Rok akademicki 2006/2007
Rok akademicki 2006/2007
Wyk
Wyk
ł
ł
ad nr 9 (09.05.2007)
ad nr 9 (09.05.2007)
dr inŜ. Jarosław Forenc
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
2/44
Plan wyk
Plan wyk
ł
ł
adu nr 9
adu nr 9
Obliczanie liczby
π
metodą Monte Carlo
Całkowanie numeryczne - metoda Monte Carlo
Metody poszukiwania ekstremum funkcji jednej zmiennej
metoda dzielenia przedziału na połowę
metoda złotego podziału
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
3/44
Obliczanie liczby
Obliczanie liczby
π
π
metod
metod
ą
ą
Monte
Monte
Carlo
Carlo
załóŜmy, Ŝe chcemy obliczyć pole koła wpisanego
w kwadrat o boku równym 2r, gdzie r - promień koła
pola koła i kwadratu opisują wzory:
po porównaniu powyŜszych wzorów otrzymamy:
czyli:
mając zatem obliczone wcześniej w pewien sposób pole kwadratu i pole koła
wpisanego w ten kwadrat, moŜna w prosty sposób obliczyć wartość liczby
π
2
2
2
4
)
2
(
r
r
P
r
P
kwadrat
koło
⋅
=
⋅
=
⋅
=
π
4
2
2
kwadrat
koło
P
r
P
r
=
=
π
4
kwadrat
koło
P
P
=
π
kwadrat
koło
P
P
⋅
=
4
π
(1)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
4/44
Obliczanie liczby
Obliczanie liczby
π
π
metod
metod
ą
ą
Monte
Monte
Carlo
Carlo
podstawowe pytanie:
jak obliczyć pole koła?
Stosujemy metodę Monte Carlo:
wyznaczamy wewnątrz kwadratu bardzo duŜo
losowych punktów
zliczamy te punkty, które wpadają do wnętrza koła
stosunek liczby punktów zawierających się
w kole do wszystkich wylosowanych punktów
będzie dąŜył w nieskończoności do stosunku
pola koła do pola kwadratu:
gdzie: n
koło
- liczba punktów w kole
n
kwadrat
- liczba wszystkich punktów
pierwsze zastosowanie:
Marquis Pierre-Simon de Laplace (1886)
kwadrat
koło
kwadrat
koło
n
n
P
P
⋅
≈
⋅
=
4
4
π
(2)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
5/44
Obliczanie liczby
Obliczanie liczby
π
π
metod
metod
ą
ą
Monte
Monte
Carlo
Carlo
-
-
program w C (1/2)
program w C (1/2)
/*
Name: w09_01_pi_MonteCarlo.c
Copyright: Politechnika Białostocka, Wydział Elektryczny
Author: Jarosław Forenc (jarekf@pb.edu.pl)
Date: 06-05-2007
Description: Obliczanie liczby Pi metod
ą
Monte Carlo
*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char *argv[])
{
int
pkt_kwadrat = 1000; /* punkty w kwadracie */
int
pkt_kolo = 0; /* punkty w kole */
float
x, y; /* wspolrzedne punktu */
float
pi; /* obliczona wartosc liczby pi */
int
i;
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
6/44
srand(time(NULL));
for (i=0; i<pkt_kwadrat; i++)
{
x = 2.0 * (rand()/(float)RAND_MAX);
y = 2.0 * (rand()/(float)RAND_MAX);
if ((x-1)*(x-1)+(y-1)*(y-1) <= 1)
pkt_kolo++;
}
pi = 4.0 * (float) pkt_kolo / pkt_kwadrat;
printf("Punkty w kwadracie: %d\n",pkt_kwadrat);
printf("Punkty w kole: %d\n",pkt_kolo);
printf("Obliczona wartosc PI: %f\n",pi);
printf("Blad: %f\n",fabs(M_PI-pi));
system("pause");
return 0;
}
Obliczanie liczby
Obliczanie liczby
π
π
metod
metod
ą
ą
Monte
Monte
Carlo
Carlo
-
-
program w C (2/2)
program w C (2/2)
Punkty w kwadracie: 1000
Punkty w kole: 791
Obliczona wartosc PI: 3.164000
Blad: 0.022407
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
7/44
Obliczanie liczby
Obliczanie liczby
π
π
metod
metod
ą
ą
Monte
Monte
Carlo
Carlo
ZaleŜność dokładności wyznaczania liczby
π
od liczby losowych punktów:
w kaŜdym przypadku wyznaczano liczbę
π
10 000 razy
wartości przedstawione w tabeli są średnią arytmetyczną otrzymanych wyników
dokładność wyniku jest zaleŜna od liczby sprawdzeń i w mniejszym stopniu,
jakości uŜytego generatora liczb pseudolosowych
0,132275 %
0,004156
3,141299
78532,6
100 000
0,420880 %
0,013222
3,141234
7853,08
10 000
1,303554 %
0,040952
3,141543
785,388
1 000
4,162055 %
0,141593
3,139505
78,4887
100
13,298417 %
0,417763
3,138298
7,8459
10
Średni błąd
względny
Średni błąd
bezwzględny
Średnia wartość
liczby
π
n
koło
n
prostokat
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
8/44
Metoda Monte
Metoda Monte
Carlo
Carlo
jako
metodę Monte Carlo
(
MC
) określa się dowolną technikę uŜywającą liczb
losowych do rozwiązania problemu
Definicja Haltona (1970):
„metoda Monte Carlo jest to metoda reprezentująca rozwiązanie problemu
w postaci parametru pewnej hipotetycznej populacji i uŜywająca losowych
sekwencji liczb do skonstruowania próby losowej danej populacji, z której mogą
być otrzymane oszacowania statystyczne tego parametru”
metoda Monte Carlo jest stosowana do modelowania matematycznego procesów
zbyt złoŜonych, aby moŜna było przewidzieć ich wyniki za pomocą podejścia
analitycznego
istotną rolę w metodzie MC odgrywa
losowanie
(wybór przypadkowy) wielkości
charakteryzujących proces
zastosowania metody MC:
obliczanie całek
łańcuchy procesów statystycznych
optymalizacja
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
9/44
Ca
Ca
ł
ł
kowanie numeryczne
kowanie numeryczne
-
-
metoda Monte
metoda Monte
Carlo
Carlo
obliczamy przybliŜoną wartość całki oznaczonej:
dla funkcji
f(x)
, której całkę chcemy
obliczyć w przedziale
[x
p
,x
k
]
wyznaczamy
prostokąt obejmujący pole pod wykresem
tej funkcji o wysokości
h
i długości
podstawy
(x
k
-x
p
)
losujemy
n
punktów i zliczamy te
punkty
n
w
, które wpadają w pole
pod wykresem funkcji
wartość całki obliczana jest na podstawie
wzoru przybliŜonego:
powyŜsza metoda nazywana jest: „chybił-trafił”, „orzeł-reszka”, „sukces-poraŜka”
∫
=
k
p
x
x
dx
x
f
I
)
(
(3)
)
(
)
(
p
k
w
x
x
x
x
h
n
n
dx
x
f
I
k
p
−
≈
=
∫
(4)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
10/44
Ca
Ca
ł
ł
kowanie numeryczne
kowanie numeryczne
-
-
metoda Monte
metoda Monte
Carlo
Carlo
Wady metody:
w ogólnym przypadku mogą pojawić się problemy z wyznaczeniem wysokości
h
algorytm metody musi być dodatkowo zmodyfikowany, gdy funkcja zmienia znak
w przedziale całkowania
Inna wersja algorytmu:
na podstawie serii losowo wybranych współrzędnych
x
wyznaczamy średnią
z wartości funkcji w przedziale całkowania
otrzymana średnia jest mnoŜona przez długość przedziału całkowania:
gdzie
x
losowe
jest wartością pseudolosową z przedziału całkowania
[x
p
,x
k
]
n
x
f
x
x
dx
x
f
I
n
i
losowe
p
k
x
x
k
p
∑
∫
=
−
≈
=
1
)
(
)
(
)
(
(4)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
11/44
Ca
Ca
ł
ł
kowanie numeryczne
kowanie numeryczne
-
-
metoda Monte
metoda Monte
Carlo
Carlo
Lista kroków:
Krok 1:
Czytaj:
Krok 2:
Krok 3:
dla i = 0,1,…,n-1:
generuj x
losowe
w przedziale [x
p
,x
k
]
Krok 4:
Krok 5:
Pisz s - wartość całki
n
x
x
k
p
,
,
p
k
x
x
dx
s
−
=
=
0
)
(
losowe
x
f
s
s
+
=
n
s
dx
s
⋅
=
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
12/44
Ca
Ca
ł
ł
kowanie numeryczne
kowanie numeryczne
-
-
metoda Monte
metoda Monte
Carlo
Carlo
float MetodaMonteCarlo(float xp, float xk, int n)
{
int i;
float s=0, dx, x_los;
srand(time(NULL));
dx = xk-xp;
for (i=0; i<n; i++)
{
x_los=xp+(float)rand()/(RAND_MAX+1)*dx;
s = s + f(x_los);
}
s = dx * s / n;
return s;
}
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
13/44
Metoda Monte
Metoda Monte
Carlo
Carlo
-
-
program w C (1/2)
program w C (1/2)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
float f(float x)
{
return (x*x);
}
float MetodaMonteCarlo(float xp, float xk, int n)
{
int i;
float s=0, dx, x_losowe;
srand(time(NULL));
dx = xk-xp;
for (i=0; i<n; i++)
{
x_losowe = xp + (float)rand()/(RAND_MAX+1)*dx;
s = s + f(x_losowe);
}
s = dx * s / n;
return s;
}
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
14/44
int main()
{
float xp = 0.0, xk = 2.0, w0, w1, w2, w3, w4;
printf("Wartosc dokladna: %.10f\n\n",8.0/3.0);
printf("\nMetoda Monte Carlo:\n");
w0 = MetodaMonteCarlo(xp,xk,10);
w1 = MetodaMonteCarlo(xp,xk,100);
w2 = MetodaMonteCarlo(xp,xk,1000);
w3 = MetodaMonteCarlo(xp,xk,10000);
w4 = MetodaMonteCarlo(xp,xk,100000);
printf("n = %6d calka = %.10f roznica = %e\n",10,w0,fabs(w0-8.0/3.0));
printf("n = %6d calka = %.10f roznica = %e\n",100,w1,fabs(w1-8.0/3.0));
printf("n = %6d calka = %.10f roznica = %e\n",1000,w2,fabs(w2-8.0/3.0));
printf("n = %6d calka = %.10f roznica = %e\n",10000,w3,fabs(w3-8.0/3.0));
printf("n = %6d calka = %.10f roznica = %e\n",100000,w4,fabs(w4-8.0/3.0));
system("PAUSE");
return (0);
}
Metoda Monte
Metoda Monte
Carlo
Carlo
-
-
program w C (2/2)
program w C (2/2)
Wartosc dokladna: 2.6666666667
Metoda Monte Carlo:
n = 10 calka = 4.2252893448 roznica = 1.558623e+000
n = 100 calka = 3.1332504749 roznica = 4.665838e-001
n = 1000 calka = 2.7011361122 roznica = 3.446945e-002
n = 10000 calka = 2.6968419552 roznica = 3.017529e-002
n = 100000 calka = 2.6850614548 roznica = 1.839479e-002
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
15/44
Ekstremum funkcji
Ekstremum funkcji
ekstremum globalne
funkcji to taki punkt, w którym wartość funkcji jest większa
(
maksimum globalne
) lub mniejsza (
minimum globalne
) niŜ we wszystkich innych
punktach
ekstremum lokalne
(
ekstremum
) to taki punkt x, w którym funkcja ma wartość
większą (
maksimum lokalne
) lub odpowiednio mniejszą (
minimum lokalne
), od
wszystkich innych punktów w pewnym otoczeniu x
Przykład:
x
x
x
x
f
−
+
=
2
3
)
(
funkcja na rysunku ma jedno maksimum
lokalne i jedno minimum lokalne, nie ma
natomiast ekstremum globalnego
kaŜde ekstremum globalne jest
jednocześnie ekstremum lokalnym
dana funkcja moŜe mieć tylko jedno
minimum globalne i tylko jedno maksimum
globalne (lub nie mieć Ŝadnego), natomiast
dowolnie wiele ekstremów lokalnych
źródło: http://pl.wikipedia.org/wiki/Ekstremum
-2
-1
0
1
2
-2
-1
0
1
2
minimum
lokalne
maksimum
lokalne
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
16/44
Ekstremum lokalne a pochodna funkcji
Ekstremum lokalne a pochodna funkcji
jeśli funkcja f(x) ma w punkcie x
0
lokalne ekstremum oraz obustronną pochodną, to
jej pochodna w tym punkcie jest równa zeru
powyŜsze stwierdzenie jest
warunkiem koniecznym
istnienia ekstremum funkcji
róŜniczkowalnej w danym punkcie, nie jest to jednak
warunek wystarczający
aby w punkcie x
0
występowało lokalne maksimum dodatkowo:
w lewym sąsiedztwie punktu x
0
wartość
pochodnej musi być większa od zera
w prawym sąsiedztwie punktu x
0
wartość
pochodnej musi być mniejsza od zera
aby w punkcie x
0
występowało lokalne minimum dodatkowo:
w lewym sąsiedztwie punktu x
0
wartość
pochodnej musi być mniejsza od zera
w prawym sąsiedztwie punktu x
0
wartość
pochodnej musi być większa od zera
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
17/44
Ekstremum lokalne a pochodna funkcji
Ekstremum lokalne a pochodna funkcji
jeśli pochodna funkcji f(x) w punkcie x
0
wynosi zero: f’(x
0
) = 0, to jeśli druga
pochodna f’’(x
0
) = (f’(x
0
))’ jest:
większa od zera, to f(x) w punkcie x
0
ma minimum lokalne
mniejsza od zera, to f(x) w punkcie x
0
ma maksimum lokalne
równa zeru, to f(x) w punkcie x
0
ma punkt przegięcia
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
18/44
Optymalizacja
Optymalizacja
poszukiwanie ekstremum funkcji jednej zmiennej jest jednym z elementów
szerszego działu nauki nazywanego
optymalizacją
optymalizacja
jest to metoda wyznaczania najlepszego rozwiązania (poszukiwania
ekstremum funkcji) z punktu widzenia określonego kryterium (wskaźnika) jakości
(np. kosztu, drogi, wydajności)
w matematyce termin optymalizacja odnosi się do następującego problemu:
„dana jest funkcja f: AR, gdzie elementy zbioru A są elementami rzeczywistymi,
poszukiwany jest element x
0
∈
A taki Ŝe, f(x
0
)
≥
f(x) dla wszystkich x
∈
A
(maksymalizacja) lub f(x
0
)
≤
f(x) dla wszystkich x
∈
A (minimalizacja)”
w metodach optymalizacji funkcja
f(x)
oznaczana jest jako
C(x)
i nazywana
funkcją celu
(wskaźnikiem jakości, kryterium jakości, kryterium optymalizacyjnym)
metody poszukiwania ekstremum lokalnego funkcji jednowymiarowych dzielą się
na trzy grupy:
1)
metody oparte na zasadzie eliminacji przedziałów
2)
metody wykorzystujące aproksymacje funkcji celu
3)
metody wykorzystujące wartości pochodnych funkcji celu
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
19/44
Funkcja
Funkcja
unimodalna
unimodalna
Definicja:
„funkcja f(x) jest
unimodalna
w przedziale a
≤
x
≤
b gdy jest monotoniczna po obu
stronach punktu minimalnego x
*
w rozpatrywanym przedziale”
jeśli x
*
- jedyny punkt minimum f(x) zawiera się w przedziale a
≤
x
≤
b, to f(x) jest
unimodalna w danym przedziale wtedy i tylko wtedy, gdy dla punktów x
1
i x
2
z x
*
≤
x
1
≤
x
2
wynika, Ŝe f(x
*
)
≤
f(x
1
)
≤
f(x
2
)
i z x
*
≥
x
1
≥
x
2
wynika, Ŝe f(x
*
)
≥
f(x
1
)
≥
f(x
2
)
Przykład:
funkcja monotonicznie wzrasta przy x
≤
0
i monotonicznie wzrasta przy x
≥
0
funkcja osiąga minimum w punkcie x = x
*
i jest monotoniczna po obu stronach od
punktu minimum
funkcja f(x) jest unimodalna
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
20/44
Metody oparte na zasadzie eliminacji przedzia
Metody oparte na zasadzie eliminacji przedzia
ł
ł
ó
ó
w
w
metody te pozwalają określić ekstremum funkcji jednej zmiennej drogą kolejnego
wyboru przedziałów i kolejno drogę zmniejszania przedziału poszukiwań
w metodach tych zakłada się, Ŝe badana funkcja w dopuszczalnym przedziale
posiada właściwość unimodalności
dzięki powyŜszej właściwości, porównując wartość funkcji f(x) w dwóch róŜnych
punktach przedziału poszukiwań, moŜna określić, w którym z wyznaczonych tymi
punktami przedziałów znajduje się ekstremum
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
21/44
Metody oparte na zasadzie eliminacji przedzia
Metody oparte na zasadzie eliminacji przedzia
ł
ł
ó
ó
w
w
Twierdzenie:
niech f(x) będzie funkcją unimodalną w przedziale a
≤
x
≤
b oraz niech minimum
funkcji f(x) znajduje się w punkcie x
*
jeśli punkty x
1
i x
2
spełniają warunek a < x
1
< x
2
< b, to porównując wartości
funkcji w punktach x
1
i x
2
moŜna określić:
jeśli f(x
1
) > f(x
2
), to punkt minimum
nie leŜy w przedziale (a,x
1
),
czyli x
*
∈
(x
1
,b)
jeśli f(x
1
) < f(x
2
), to punkt minimum
nie leŜy w przedziale (x
2
,b),
czyli x
*
∈
(a,x
2
)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
22/44
Metody oparte na zasadzie eliminacji przedzia
Metody oparte na zasadzie eliminacji przedzia
ł
ł
ó
ó
w
w
przedstawione twierdzenie pozwala stosować procedurę poszukiwań ekstremum
funkcji polegającą na wykluczaniu części wejściowego przedziału
poszukiwania ekstremum są kończone, gdy przedział zmniejszy się do dostatecznie
małych rozmiarów
w opisywanym procesie poszukiwania ekstremum wyróŜniane są dwa etapy:
1) etap określania granicy przedziału
2) etap zmniejszania przedziału
metoda połowienia
metoda złotego podziału
metoda Fibonacciego
Etap określania granicy przedziału:
najczęściej poszukiwania granicznych punktów przedziału zawierającego
ekstremum wykonuje się metodami heurystycznymi (intuicyjnie)
wybierany jest punkt na podstawie którego buduje się odpowiednio szeroki
przedział zawierający ekstremum
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
23/44
Metody oparte na zasadzie eliminacji przedzia
Metody oparte na zasadzie eliminacji przedzia
ł
ł
ó
ó
w
w
Etap określania granicy przedziału (metoda Swana):
zakładamy: x
0
- dowolny punkt początkowy,
zakładamy:
∆
- dobierana pewnym sposobem wielkość kroku
kolejne punkty określa się według wzoru rekurencyjnego:
znak
∆
określa się drogą porównań wartości funkcji f(x
0
-|
∆
|), f(x
0
), f(x
0
+|
∆
|)
jeśli f(x
0
-|
∆
|)
≥
f(x
0
+|
∆
|) to z załoŜeniem unimodalności punkt minimum powinien
leŜeć w prawo od punktu x
0
i wielkość
∆
wybierana jest jako dodatnia
jeśli f(x
0
-|
∆
|) < f(x
0
+|
∆
|) to wielkość
∆
wybierana jest jako ujemna
jeśli f(x
0
-|
∆
|)
≥
f(x
0
)
≤
f(x
0
+|
∆
|) to punkt minimum leŜy między punktami
x
0
-|
∆
| i x
0
+|
∆
| i poszukiwanie punktów granicznych zostaje zakończone
,...
2
,
1
,
0
,
2
1
=
∆
⋅
±
=
+
k
x
x
k
k
k
(5)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
24/44
Metody oparte na zasadzie eliminacji przedzia
Metody oparte na zasadzie eliminacji przedzia
ł
ł
ó
ó
w
w
Etap określania granicy przedziału (metoda Swana) - przykład:
znaleźć graniczne punkty przedziału zawierającego minimum funkcji
przy punkcie początkowym x
0
= 30 i kroku |
∆
| = 5
znak |
∆
| określa się porównując wartości w punktach:
poniewaŜ:
to wielkość
∆
powinna być dodatnia
sprawdzenie znaku |
∆
| związane było takŜe z wyznaczeniem punktu x
1
:
4225
)
35
(
)
(
4900
)
30
(
)
(
5625
)
25
(
)
(
0
0
0
=
=
∆
+
=
=
=
=
∆
−
f
x
f
f
x
f
f
x
f
2
)
100
(
)
(
x
x
f
−
=
)
(
)
(
)
(
0
0
0
∆
+
≥
≥
∆
−
x
f
x
f
x
f
35
5
1
30
2
0
0
1
=
⋅
+
=
∆
⋅
+
=
x
x
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
25/44
Metody oparte na zasadzie eliminacji przedzia
Metody oparte na zasadzie eliminacji przedzia
ł
ł
ó
ó
w
w
Etap określania granicy przedziału (metoda Swana) - przykład:
dla k = 1:
dla k = 2:
45
5
2
35
2
1
1
2
=
⋅
+
=
∆
⋅
+
=
x
x
35
)
(
)
(
3025
)
(
45
4225
)
(
35
*
1
2
2
2
1
1
>
<
=
=
=
=
x
x
f
x
f
x
f
x
x
f
x
więc
65
5
4
45
2
2
2
3
=
⋅
+
=
∆
⋅
+
=
x
x
45
)
(
)
(
1225
)
(
45
3025
)
(
35
*
2
3
3
3
2
2
>
<
=
=
=
=
x
x
f
x
f
x
f
x
x
f
x
więc
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
26/44
Metody oparte na zasadzie eliminacji przedzia
Metody oparte na zasadzie eliminacji przedzia
ł
ł
ó
ó
w
w
Etap określania granicy przedziału (metoda Swana) - przykład:
dla k = 3:
dla k = 4:
stąd przedział poszukiwań ekstremum to:
105
40
65
5
8
65
2
3
3
4
=
+
=
⋅
+
=
∆
⋅
+
=
x
x
65
)
(
)
(
25
)
(
105
1225
)
(
65
*
3
4
4
4
3
3
>
<
=
=
=
=
x
x
f
x
f
x
f
x
x
f
x
więc
185
80
105
5
16
105
2
4
4
5
=
+
=
⋅
+
=
∆
⋅
+
=
x
x
185
)
(
)
(
7225
)
(
185
25
)
(
105
*
4
5
5
5
4
4
<
>
=
=
=
=
x
x
f
x
f
x
f
x
x
f
x
więc
)
185
,
65
(
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
27/44
Metody oparte na zasadzie eliminacji przedzia
Metody oparte na zasadzie eliminacji przedzia
ł
ł
ó
ó
w
w
Etap zmniejszania przedziału:
po ustaleniu granic przedziału zawierającego punkt minimum stosujemy bardziej
złoŜoną procedurę zawęŜania przedziału poszukiwań w celu otrzymania
rozwiązania (minimum) z załoŜoną dokładnością
stosując odpowiedni algorytm iteracyjny, zmniejszamy w kaŜdym kroku wielkość
przedziału
stopień zmniejszenia przedziału zaleŜny jest od połoŜenia próbnych punktów
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
28/44
Metoda dzielenia przedzia
Metoda dzielenia przedzia
ł
ł
u na po
u na po
ł
ł
ow
ow
ę
ę
metoda ta pozwala na eliminację połowy przedziału w kaŜdej iteracji
w przedziale poszukiwań ekstremum
[a,b]
wybieramy trzy punkty próbne
(
x
1
,
x
m
,
x
2
), dzielące przedział na cztery równe części:
jeśli wartość funkcji w punkcie
x
1
jest mniejsza od wartości funkcji w punkcie
x
m
(
f(x
1
)<f(x
m
)
), to jako nowy przedział poszukiwań wybieramy lewy podprzedział
[a,x
m
]
:
a
b
L
L
b
x
b
a
x
L
a
x
m
−
=
−
=
+
=
+
=
,
4
/
,
2
/
)
(
,
4
/
2
1
(6)
m
m
x
b
x
x
a
a
=
=
=
1
(7)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
29/44
Metoda dzielenia przedzia
Metoda dzielenia przedzia
ł
ł
u na po
u na po
ł
ł
ow
ow
ę
ę
jeśli wartość funkcji w punkcie
x
2
jest
mniejsza od wartości funkcji w punkcie
x
m
(
f(x
2
)<f(x
m
)
), to jako nowy przedział
poszukiwań wybieramy prawy
podprzedział
[x
m
,b]
:
jeśli Ŝaden z powyŜszych warunków
nie jest prawdziwy, to punkt środkowy,
x
m
, nie zmienia się, zaś do dalszych
obliczeń wybieramy podprzedział
[x
1
,x
2
]
:
b
b
x
x
x
a
m
m
=
=
=
2
(8)
2
1
x
b
x
x
x
a
m
m
=
=
=
(9)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
30/44
Metoda dzielenia przedzia
Metoda dzielenia przedzia
ł
ł
u na po
u na po
ł
ł
ow
ow
ę
ę
zmniejszanie długości przedziału kończymy, gdy jego długość jest mniejsza od
załoŜonej dokładności:
jako wartość ekstremum przyjmujemy środek przedziału:
Uwagi:
w kaŜdej iteracji są potrzebne nie więcej niŜ dwa obliczenia wartości funkcji
(10)
ε
2
≤
−
a
b
2
lub
2
L
a
x
b
a
x
+
=
+
=
∗
∗
(11)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
31/44
Metoda dzielenia przedzia
Metoda dzielenia przedzia
ł
ł
u na po
u na po
ł
ł
ow
ow
ę
ę
Lista kroków:
Krok 1:
Czytaj:
Krok 2:
Krok 3:
Krok 4:
jeśli f(x
1
) < f(x
m
), to:
przejdź do: Krok 7
Krok 5:
jeśli f(x
2
) < f(x
m
), to:
przejdź do: Krok 7
Krok 6:
x
m
pozostaje, zawęŜamy przedział
Krok 7:
jeśli to przejdź do: Krok 2
Krok 8:
Pisz: - wartość minimum
ε
,
, b
a
a
b
L
b
a
x
m
−
=
+
=
,
2
/
)
(
4
/
,
4
/
2
1
L
b
x
L
a
x
−
=
+
=
1
,
,
x
x
a
b
L
x
b
m
m
=
−
=
=
2
,
,
x
x
a
b
L
x
a
m
m
=
−
=
=
a
b
L
x
b
x
a
−
=
=
=
,
,
2
1
2
/
)
(
b
a
x
+
=
∗
ε
2
>
−
a
b
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
32/44
Metoda dzielenia przedzia
Metoda dzielenia przedzia
ł
ł
u na po
u na po
ł
ł
ow
ow
ę
ę
float MetodaDwudzielnosci(float a, float b, float eps)
{
float xm, x1, x2, fxm, fx1, fx2, L;
xm = (a+b)/2; fxm = f(xm); L = b-a;
do
{
x1 = a+L/4; fx1 = f(x1);
x2 = b-L/4; fx2 = f(x2);
if (fx1 < fxm)
{
b = xm; L = b-a; xm = x1; fxm = fx1;
}
else
if (fx2 < fxm)
{
a = xm; L = b-a; xm = x2; fxm = fx2;
}
else
{
a = x1; b = x2; L = b-a;
}
}
while (fabs(b-a)>2*eps);
return (a+L/2);
}
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
33/44
Metoda dzielenia przedzia
Metoda dzielenia przedzia
ł
ł
u na po
u na po
ł
ł
ow
ow
ę
ę
-
-
przyk
przyk
ł
ł
ad (1/3)
ad (1/3)
wyznaczyć minimum funkcji: w przedziale:
obliczenia wstępne:
pierwsza iteracja:
wybieramy środkowy przedział:
25
)
105
(
)
(
25
.
756
)
5
.
127
(
)
(
25
)
105
(
)
(
25
.
306
)
5
.
82
(
)
(
5
.
127
4
/
90
150
4
/
5
.
82
4
/
90
60
4
/
2
1
2
1
=
=
>
=
=
=
=
>
=
=
=
−
=
−
=
=
+
=
+
=
f
x
f
f
x
f
f
x
f
f
x
f
L
b
x
L
a
x
m
m
2
)
100
(
)
(
x
x
f
−
=
25
)
105
(
)
(
,
105
2
/
)
150
60
(
2
/
)
(
90
60
150
,
150
,
60
=
=
=
+
=
+
=
=
−
=
−
=
=
=
f
x
f
b
a
x
a
b
L
b
a
m
m
]
150
,
60
[
45
5
.
82
5
.
127
5
.
127
,
105
,
5
.
82
2
1
=
−
=
−
=
=
=
=
=
=
=
a
b
L
x
b
x
x
x
a
m
m
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
34/44
Metoda dzielenia przedzia
Metoda dzielenia przedzia
ł
ł
u na po
u na po
ł
ł
ow
ow
ę
ę
-
-
przyk
przyk
ł
ł
ad (2/3)
ad (2/3)
druga iteracja:
wybieramy środkowy przedział:
25
)
105
(
)
(
06
.
264
)
25
.
116
(
)
(
25
)
105
(
)
(
06
.
39
)
75
.
93
(
)
(
25
.
116
4
/
45
5
.
127
4
/
75
.
93
4
/
45
5
.
82
4
/
2
1
2
1
=
=
>
=
=
=
=
>
=
=
=
−
=
−
=
=
+
=
+
=
f
x
f
f
x
f
f
x
f
f
x
f
L
b
x
L
a
x
m
m
5
.
22
75
.
93
25
.
116
25
.
116
,
105
,
75
.
93
2
1
=
−
=
−
=
=
=
=
=
=
=
a
b
L
x
b
x
x
x
a
m
m
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
35/44
Metoda dzielenia przedzia
Metoda dzielenia przedzia
ł
ł
u na po
u na po
ł
ł
ow
ow
ę
ę
-
-
przyk
przyk
ł
ł
ad (3/3)
ad (3/3)
trzecia iteracja:
wybieramy lewy przedział:
...
obliczenia kończymy, gdy spełniony jest warunek:
89
.
112
)
625
.
110
(
)
(
25
)
105
(
)
(
39
.
0
)
375
.
99
(
)
(
625
.
110
4
/
5
.
22
25
.
116
4
/
375
.
99
4
/
5
.
22
75
.
93
4
/
2
1
2
1
=
=
=
=
<
=
=
=
−
=
−
=
=
+
=
+
=
f
x
f
f
x
f
f
x
f
L
b
x
L
a
x
m
25
.
11
75
.
93
105
105
,
375
.
99
,
75
.
93
1
=
−
=
−
=
=
=
=
=
=
=
a
b
L
x
b
x
x
a
a
m
m
ε
2
≤
−
a
b
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
36/44
Metoda z
Metoda z
ł
ł
otego podzia
otego podzia
ł
ł
u
u
w metodzie złotego podziału stosowane są dwa punkty próbne, które dzielą
przedział w sposób pokazany na rysunku
wartość stałej
τ
wynosi:
Dlaczego taki podział?
podział przedstawiony na rysunku spełnia trzy warunki:
1) punkty próbne są rozmieszczone w jednakowych odległościach od środka
przedziału
2) punkty próbne są rozmieszczone symetrycznie w taki sposób, ze stosunek
długości eliminowanego podprzedziału do wielkości całego podprzedziału
jest stały
3) w kaŜdej iteracji obliczana jest tylko jedna wartość funkcji
...
61803
.
0
2
/
)
1
5
(
=
−
=
τ
(12)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
37/44
Metoda z
Metoda z
ł
ł
otego podzia
otego podzia
ł
ł
u
u
Dlaczego metoda złotego podziału?
w geometrii
złotym podziałem
nazywa się taki podział odcinka na dwie części,
przy którym stosunek całego odcinka do jego większej części jest równy stosunkowi
większej części do mniejszej
Algorytm metody złotego podziału:
w przedziale poszukiwań ekstremum
[a,b]
wybieramy dwa punkty próbne
(
x
1
,
x
2
), dzielące przedział na trzy części:
gdzie:
c
b
b
a
=
a
a
b
x
b
a
b
x
+
⋅
−
=
+
−
⋅
−
=
τ
τ
)
(
)
(
)
(
2
1
(13)
...
61803
.
0
2
/
)
1
5
(
=
−
=
τ
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
38/44
Metoda z
Metoda z
ł
ł
otego podzia
otego podzia
ł
ł
u
u
Algorytm metody złotego podziału:
jeśli wartość funkcji w punkcie
x
1
jest
większa od wartości funkcji w punkcie
x
2
(
f(x
1
)>f(x
2
)
), to jako nowy przedział
poszukiwań wybieramy prawy
podprzedział
[x
1
,b]
:
w przeciwnym przypadku jako nowy
przedział poszukiwań wybieramy
lewy podprzedział
[a,x
2
]
:
(14)
b
b
a
a
b
x
x
x
x
a
=
+
⋅
−
=
=
=
τ
)
(
2
2
1
1
b
a
b
x
x
x
x
b
a
a
+
−
⋅
−
=
=
=
=
)
(
)
(
1
1
2
2
τ
(15)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
39/44
Metoda z
Metoda z
ł
ł
otego podzia
otego podzia
ł
ł
u
u
Algorytm metody złotego podziału:
zmniejszanie długości przedziału kończymy, gdy jego długość jest mniejsza od
załoŜonej dokładności:
jako wartość ekstremum przyjmujemy środek przedziału:
(16)
ε
2
≤
−
a
b
2
b
a
x
+
=
∗
(17)
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
40/44
Metoda z
Metoda z
ł
ł
otego podzia
otego podzia
ł
ł
u
u
Lista kroków:
Krok 1:
Czytaj:
Krok 2:
Krok 3:
jeśli f
1
> f
2
, to:
przejdź do: Krok 5
Krok 4:
jeśli f
1
≤
f
2
, to:
przejdź do: Krok 5
Krok 7:
jeśli to przejdź do: Krok 3
Krok 8:
Pisz: - wartość minimum
ε
,
, b
a
a
a
b
x
b
a
b
x
+
⋅
−
=
+
−
⋅
−
=
τ
τ
)
(
)
(
)
(
2
1
2
/
)
(
b
a
x
+
=
∗
ε
2
>
−
a
b
)
(
)
(
2
2
1
1
x
f
f
x
f
f
=
=
)
(
)
(
2
2
2
2
1
2
1
1
x
f
f
a
a
b
x
f
f
x
x
x
a
=
+
⋅
−
=
=
=
=
τ
)
(
)
(
)
(
1
1
1
1
2
1
2
2
x
f
f
b
a
b
x
f
f
x
x
x
b
=
+
−
⋅
−
=
=
=
=
τ
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
41/44
Metoda z
Metoda z
ł
ł
otego podzia
otego podzia
ł
ł
u
u
float ZlotyPodzial(float a, float b, float eps)
{
float x1, x2, fx1, fx2, t;
t = (sqrt(5)-1)/2;
x1 = (b-a)*(-t)+b; fx1 = f(x1);
x2 = (b-a)*t+a; fx2 = f(x2);
do
{
if (fx1 > fx2)
{
a = x1; x1 = x2; fx1 = fx2;
x2 = (b-a)*t+a; fx2 = f(x2);
}
else
{
b = x2; x2 = x1; fx2 = fx1;
x1 = (b-a)*(-t)+b; fx1 = f(x1);
}
}
while (fabs(b-a)>2*eps);
return (a+b)/2;
}
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
42/44
Metoda z
Metoda z
ł
ł
otego podzia
otego podzia
ł
ł
u
u
-
-
przyk
przyk
ł
ł
ad (1/3)
ad (1/3)
wyznaczyć minimum funkcji: w przedziale:
obliczenia wstępne:
pierwsza iteracja:
2
)
100
(
)
(
x
x
f
−
=
98
.
243
)
62
.
115
(
)
(
58
.
31
)
38
.
94
(
)
(
62
.
115
60
618
.
0
)
60
150
(
)
(
38
.
94
150
)
618
.
0
(
)
60
150
(
)
(
)
(
618
.
0
,
150
,
60
2
1
2
1
=
=
=
=
=
+
⋅
−
=
+
⋅
−
=
=
+
−
⋅
−
=
+
−
⋅
−
=
=
=
=
f
x
f
f
x
f
a
a
b
x
b
a
b
x
b
a
τ
τ
τ
]
150
,
60
[
93
.
351
)
24
.
81
(
)
(
24
.
81
62
.
115
)
618
.
0
(
)
60
62
.
115
(
)
(
)
(
58
.
31
)
(
38
.
94
62
.
115
60
)
(
)
(
98
.
243
)
62
.
115
(
)
(
,
58
.
31
)
38
.
94
(
)
(
1
1
2
1
2
2
2
1
2
1
=
=
=
+
−
⋅
−
=
+
−
⋅
−
=
=
=
=
=
=
=
=
<
=
=
=
=
f
x
f
b
a
b
x
x
f
x
x
x
b
a
a
x
f
x
f
f
x
f
f
x
f
τ
wybieramy lewy podprzedział:
]
62
.
115
,
60
[
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
43/44
Metoda z
Metoda z
ł
ł
otego podzia
otego podzia
ł
ł
u
u
-
-
przyk
przyk
ł
ł
ad (2/3)
ad (2/3)
druga iteracja:
18
.
6
)
48
.
102
(
)
(
48
.
102
24
.
81
618
.
0
)
24
.
81
62
.
115
(
)
(
58
.
31
)
(
38
.
94
62
.
115
24
.
81
)
(
)
(
58
.
31
)
38
.
94
(
)
(
,
93
.
351
)
24
.
81
(
)
(
2
2
1
2
1
1
2
1
2
1
=
=
=
+
⋅
−
=
+
⋅
−
=
=
=
=
=
=
=
=
>
=
=
=
=
f
x
f
a
a
b
x
x
f
x
x
b
b
x
a
x
f
x
f
f
x
f
f
x
f
τ
wybieramy prawy podprzedział:
]
62
.
115
,
24
.
81
[
Podstawy informatyki 2
dr inŜ. Jarosław Forenc
Wykład nr 9
44/44
Metoda z
Metoda z
ł
ł
otego podzia
otego podzia
ł
ł
u
u
-
-
przyk
przyk
ł
ł
ad (3/3)
ad (3/3)
druga iteracja:
...
obliczenia kończymy, gdy spełniony jest warunek:
25
.
56
)
5
.
107
(
)
(
5
.
107
38
.
94
618
.
0
)
38
.
94
62
.
115
(
)
(
18
.
6
)
(
48
.
102
62
.
115
38
.
94
)
(
)
(
18
.
6
)
48
.
102
(
)
(
,
58
.
31
)
38
.
94
(
)
(
2
2
1
2
1
1
2
1
2
1
=
=
=
+
⋅
−
=
+
⋅
−
=
=
=
=
=
=
=
=
>
=
=
=
=
f
x
f
a
a
b
x
x
f
x
x
b
b
x
a
x
f
x
f
f
x
f
f
x
f
τ
wybieramy prawy podprzedział:
]
62
.
115
,
38
.
94
[
ε
2
≤
−
a
b