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
Wyszukiwarka
Podobne podstrony:
Egz dzienne 09 2009 id 151170 Nieznany
OGR dzienne lato 09 10 id 33397 Nieznany
7 Wykl 7 str 4 tab 1 N 5 id 612 Nieznany (2)
AiSD Wyklad4 dzienne id 53497 Nieznany (2)
IS wyklad 14 15 01 09 MDW id 22 Nieznany
ei 2005 09 s004 id 154186 Nieznany
cennik 09 2013 id 109720 Nieznany
09 15 id 53452 Nieznany (2)
Homines2011 09 Walkowiak id 205 Nieznany
kol1, kol2, sem 3, 09 10 id 239 Nieznany
AiSD Wyklad9 dzienne id 53501 Nieznany
ei 2005 09 s144 id 154191 Nieznany
AiSD Wyklad11 dzienne id 53494 Nieznany
Pedagogika Wczesnoszkolna id 35 Nieznany
AiSD Wyklad6 dzienne id 53499 Nieznany (2)
ei 2005 09 s150 id 154192 Nieznany
AiSD Wyklad7 dzienne id 53500 Nieznany (2)
więcej podobnych podstron