Wprowadzenie do MES
Rachunek wariacyjny
Metody aproksymacyjnego rozwiązywania równań różniczkowych
Przykładowe zagadnienia
" Zagadnienie brachistochrony (J. Bernoulli 1696)
Dane są ustalone punkty A, B nie leżące na pionowej prostej.
Wyznaczyć linię-drogę, po której punkt materialny zsunie się
od A do B w najkrótszym czasie pod wpływem siły ciążenia.
Prędkość początkowa w punkcie A jest równa 0.
" Powierzchnia obrotowa o minimalnym polu
Dane są ustalone punkty A, B nie leżące na pionowej prostej.
Dane są ustalone punkty A, B nie leżące na pionowej prostej.
Wyznaczyć linię, która po obrocie wokół osi utworzy
powierzchniÄ™ o najmniejszym polu
" Powierzchnia o minimalnym polu przechodzÄ…ca przez danÄ… krzywÄ…
Dana jest krzywa “ w przestrzeni R3. Poszukujemy
powierzchni S, której brzegiem jest “, i której pole jest
minimalne
2
Powierzchnia obrotowa o minimalnym polu
b
a
x
u(x)
b
2
S = 2Ä„
+"u(x) 1+[u'(x)] dx min
u(x)
a
3
Warunek konieczny istnienia ekstremum funkcjonału
b
J(u)= F(x,u,u')dx min; u(a)= ua, u(b)= ub
+"
a
"J = J(u)- J(u + h), h(a)= h(b)= 0
b
"J =
+"[F(x,u + h,u'+h')- F(x,u,u')]dx
a
"F "F
F(x,u + h,u'+h')- F(x,u,u')H" F + h + h' +
"u "u'
1 "2F "2F 1 "2F
h2 + hh' + h'2 +K- F
2 "u2 "u"u' 2 "u'2
b
"F "F
îÅ‚ Å‚Å‚dx +Ä…(u, h)h
"J =
+"ðÅ‚h + h'
ïÅ‚
"u "u'śł
a
144 4
4244ûÅ‚3
ëÅ‚
ìÅ‚ ÷Å‚
´J höÅ‚ 4
íÅ‚ Å‚Å‚
Warunek konieczny istnienia ekstremum funkcjonału
Jeżeli funkcjonaÅ‚ J(u) posiada ekstremum dla u=u0 to ´J=0 dla u=u0
b
"F "F
îÅ‚h + h' Å‚Å‚dx = 0
´J(h) =
+"
ïÅ‚
"u "u'śł
ðÅ‚ ûÅ‚
a
b
b b
"F "F d "F
-
+" +"
+"h' dx = h +"h îÅ‚ Å‚Å‚
ïÅ‚"u'śł
ïÅ‚"u'śłdx
"u' "u' dx
"u' "u3 a dx
ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚
a
a
1
2'
= 0
b
d
´J(h) =
u
+"hîÅ‚F - Fu'Å‚Å‚dx = 0
ïÅ‚ śł
dx
ðÅ‚ ûÅ‚
a
d
Fu - Fu' = 0
Równanie Eulera
dx
5
Powierzchnia obrotowa o minimalnym polu
b
2
S = 2Ä„
b
a +"u(x) 1+[u'(x)] dx min
x
u(x)
u(x)
a
F(u,u') = u 1+ u'
F(u,u') = u 1+ u'2
"F " "F "u " "F "F
îÅ‚ Å‚Å‚ Å„Å‚F - u' üÅ‚
- = = 0 Ò! F - u' = C
òÅ‚ żł
ïÅ‚"u'śł
"u "u "x "u "u' "u'
ðÅ‚ ûÅ‚ ół þÅ‚
uu'2
u 1+ u'2 - = C
1+ u'2
x - C2
u = C1 cosh
C1
6
" Funkcjonał zależny od pochodnych wyższego rzędu
F(x,u,u',K,u(n))
n
"F di
i
R. Eulera : + =
ìÅ‚ ÷Å‚
"(-1) dxi ëÅ‚ "F öÅ‚ 0
"u
"u(i)
íÅ‚ Å‚Å‚
i=1
" Funkcjonał zależny od wielu funkcji
, , ,
F(x,u1,u1,u2,u2,K,un,un)
F(x,u1,u1,u2,u2,K,un,un)
ëÅ‚ öÅ‚
"F d "F
ìÅ‚ ÷Å‚
R. Eulera : - = 0 i = 1,2,K,n
ìÅ‚ ÷Å‚
"ui dx
"ui,
íÅ‚ Å‚Å‚
" Funkcjonał z nieznanymi wartościami brzegowymi
" Funkcjonał z nieznanymi granicami całkowania
" Funkcjonał z więzami lub dodatkowymi warunkami
" .......
7
Metody aproksymacyjnego rozwiązywania równań różniczkowych
Lu(x) = 0 x "&!
u = u
“
n
~
u(x) =
"a Ni(x)
i
i=1
i=1
Ni(x)  funkcje bazowe
ai  nieznane współczynniki
~
Lu(x) = R(x,ai)
8
Metody aproksymacyjnego rozwiązywania równań różniczkowych
Dobór funkcji bazowych:
" funkcje potęgowe
" funkcje (wielomiany) ortogonalne
 funkcje trygonometryczne (szeregi Fouriera)
 funkcje Bessela
 wielomiany Legendre a
 wielomiany Legendre a
 .....
" funkcje Trefftza
" ....
1. Spełniają warunki brzegowe; nie spełniają równania różniczkowego
2. Spełniają równanie różniczkowe; nie spełniają warunków brzegowych
9
Metody aproksymacyjnego rozwiązywania równań różniczkowych
Określenie wartości współczynników ai
" minimalizacja residuum w sformułowaniu silnym
 metoda residuów ważonych
" metoda Ritza
" metoda Galerkina
" metoda kollokacji
" metoda minimum odchyłek kwadratowych
" metoda minimum odchyłek kwadratowych
" ...
 metoda Trefftza (minimalizacja błędu spełnienia warunków brzegowych)
 .....
" sformułowanie słabe (wariacyjne)
 metoda Rayleigha-Ritza
 Metoda Galerkina-Ritza
 ....
10
Przykład:
d2u
+1000x2 = 0
dx2
u(0)= u(1)= 0
1000
uEX = x(1- x3)
12
11
Metoda residuów ważonych
i
+"w(x)R(x,a )d&! = 0
&!
N(x)= x(1- x)
üÅ‚
N(x)= x(1- x2)żł N(0)= N(1)= 0
þÅ‚
1
~
~
( )
Å" = (uEX - u)dx
+"
+"
0
1
~
(uEX - u)dx
+"
0
µ % = Å"100%
IEX
1
IEX =
EX
+"u dx = 25
0
12
Metoda Ritza w(x)=1
i
+"R(x,a )d&! = 0
&!
~
u = a1x(1- x) Ò! R = -2a1 +1000x2
50
1 1
Metoda Ritza
1000
exact
R(x,a1)dx = (- 2a1 +1000x2)dx = -2a1 + = 0
parabola
+" +"
qubic
3
0 0
40
1000
a1 =
6
6
30
Å" = 5.82 µ = 23.3%
20
~
u = a1x(1- x2) Ò! R = -6a1x +1000x2
1 1
1000
10
R(x,a1)dx = (- 6a1x +1000x2)dx = -3a1 + = 0
+" +"
3
0 0
1000
0
a1 =
0 0.2 0.4 0.6 0.8 1
9
Å" = 3.18 µ = 12.7%
13
Metoda kollokacji w(x)=´(x-xi)
+"´ (x - xk )R(x,ai )d&! = 0 Ô! R(xk ,ai )= 0
&!
40
Metoda kollokacji
~
exact
u = a1x(1- x2) Ò! R = -6a1x +1000x2
kollokacja
kollokacja 2
30
1 1
RëÅ‚ ,a1öÅ‚ = -3a1 +1000Å" = 0
ìÅ‚ ÷Å‚
2 4
íÅ‚ Å‚Å‚
íÅ‚ Å‚Å‚
1000
a1 =
12
20
µ = 16.7%
ëÅ‚ öÅ‚
3 6 3 1
ìÅ‚ ÷Å‚
RìÅ‚ ,a1 ÷Å‚ = - a1 +1000Å" = 0
10
3 3 3
íÅ‚ Å‚Å‚
1000
a1 =
6 3
0
µ = 8.8%
0 0.2 0.4 0.6 0.8 14 1
"R
Metoda najmniejszych kwadratów w(x)=
"ai
I =
i
+"[R(x,a )]2d&! min
&!
"I "R
= 0 Ô!
+"R d&! = 0
"ai "ai
&!
50
Metoda kollokacji
exact
min. kwadratow
~
u = a1x(1- x2) Ò! R = -6a1x +1000x2
40
"R
"R
= -6x
= -6x
"a1
30
1 1
"R
R dx = 6x)(- 6a1x +1000x2)dx = 12a1 -1500 = 0
+" +"(-
"a1
0 0
20
1000
a1 =
8
µ = 25%
10
0
0 0.2 0.4 0.6 0.8 1
15
Metoda Galerkina w(x)=Ni(x)
i
+"N (x)R(x,ai )d&! = 0
&! 50
Metoda kollokacji
exact
Galerkin
40
~
u = a1x(1- x2) Ò! R = -6a1x +1000x2
1 1
N(x)R(x,a1)dx = x(1- x2)(- 6a1x +1000x2)dx = 0
+" +"
30
0 0
5000
5000
a1 =
48
20
µ = 9.3%
10
0
0 0.2 0.4 0.6 0.8 1
16
Metoda wariacyjna Rayleigha-Ritza
d2u
Równanie wyjściowe:
+1000x2 = 0
dx2
du
F(u, , x)
Problem: znalez
ć funkcjonał dla którego równanie wyjściowe
dx
jest równaniem Eulera.
2
1 du
ëÅ‚ öÅ‚
F = - +1000x2u
ìÅ‚ ÷Å‚
2 dx
íÅ‚ Å‚Å‚
íÅ‚ Å‚Å‚
"F d "F
- = 0
Równanie Eulera:
"u dx "u'
d du
1000x2 - = 0
dx dx
17
Metoda wariacyjna Rayleigha-Ritza
1
2
îÅ‚ Å‚Å‚
1 du
I(u)=
ìÅ‚ ÷Å‚
+"ïÅ‚- ëÅ‚ öÅ‚ +1000x2uśłdx min
u
2 dx
íÅ‚ Å‚Å‚
ïÅ‚ śł
ðÅ‚ ûÅ‚
0
u = a1x(1- x2)
1
2
1
2
I(a1)= (1-
I(a1)= (1- ) )dx min
+"- a1 3x +1000x a1x(1- x
+"- a1 3x2) +1000x2a1x(1- x2)dx min
a1
2
0
1000 2
2
I(a1)= a1 - a1 min
a1
12 5
d I 1000 4 5000
= - a1 = 0 Ò! a1 =
da1 12 5 48
18
Metoda Galerkina-Ritza
d2u
= - f (x) / w
+"
dx2
L L L
2
ëÅ‚
d2u d u
w dx = - wf (x)dx Ô! ÷Å‚
+" +" +"ìÅ‚ dx2 + f (x)öÅ‚wdx
ìÅ‚ ÷Å‚
dx2
íÅ‚ Å‚Å‚
0 0 0
L
L L
du dw du
w - dx = -
w - dx = -
+" +"wf (x)dx
+" +"wf (x)dx
dx dx dx
0
0 0
L
dw du
- wf (x)öÅ‚dx - w(L)du + w(L)du = 0
ìÅ‚ ÷Å‚
+"ëÅ‚
dx dx dx dx
íÅ‚ Å‚Å‚
x=L x=0
0
19
50
Podsumowanie
1
IEX = dx = 25
EX
+"u
40
0
1
~
EX
+"(u - u)2dx
0
µ = Å"100%
IEX
30
N = x(1- x2)
20
||·|| µ
3.8337 15.33%
Metoda residuów
5.24951 20.998%
exact
7.23595 28.943% Ritz
10
kollokacja
2.62475 10.499%
min. kwadratow
Galerkin & R-R
0
0 0.2 0.4 0.6 0.8 1
20
Zbieżność typu p
w(a)= wa N(a)= wa N(0)= 0
üÅ‚ Å„Å‚ Å„Å‚
100
Ò!
òÅ‚N òÅ‚
w(b)= wb żł (b)= wb N(1)= 0
þÅ‚ ół ół
80
n = 1 N = 0
n = 2 N = x(1- x)
60
n = 3 N = x(1- x )
n = 3 N = x(1- x2)
40
( )
n = 4 N = x(1- x3)
n ||·|| µ
20
1 25 100%
0
2 5.78876 23.155%
1 2 3 4
stopien wielomianu
3 2.62475 10.499%
4 0 0%
21
r
error
Zbieżność typu h
wc
wa
wb
I
II
b
b
a c
a c
x
x
h h
Metoda Rayleigha-Ritza
1
2
îÅ‚ Å‚Å‚
1 du
I(u)=
ìÅ‚ ÷Å‚
+"ïÅ‚- ëÅ‚ öÅ‚ +1000x2uśłdx min
u
2 dx
íÅ‚ Å‚Å‚
ïÅ‚ śł
ðÅ‚ ûÅ‚
0
c b
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 dNI 2 1 dNII 2
öÅ‚ öÅ‚
I(NI, NII)= +1000x2NI dx + +1000x2NII dx min
śł śł
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
+"ïÅ‚- ëÅ‚ +"ïÅ‚- ëÅ‚
2 dx 2 dx
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
ïÅ‚ śł ïÅ‚ śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
a c
22
Zbieżność typu h (c.d.)
a = 0, b = 1, c = 0.5
wc
wa = wb = 0
x
wa=0 wb=0
I b
a c II
NI = aI + bIx NII = aII + bIIx
NI = 2wcx NII = 2wc(1- x)
"NI "NII
"NI "NII
= =
= 2wc = 2wc
"x "x
0.5 1
1 1
îÅ‚ 2 îÅ‚ 2
I(wc)=
+"ðÅ‚- (2wc) +1000x2(2wcx)Å‚Å‚dx + +"ðÅ‚- (2wc) +1000x2(2wc(1- x))Å‚Å‚dx min
ïÅ‚ śł ïÅ‚ śł
wc
2 2
ûÅ‚ ûÅ‚
0 0.5
125 1375 875
2 2 2
I(wc)= wc - wc + wc - wc = wc - 2wc
4 12 6
"I(wc) 875
= 0 Ò! wc =
"wc 24
23
Zbieżność typu h (c.d.)
wc
L1(¾) L2(¾)
1 1
wa
wb
¾
¾
0 1 0 1
b
a ¾1 c ¾2 L=F1L1(¾)+F2L2(¾)
x
10
0
1
x = xaL1(¾1)+ xcL2(¾1) x = xcL1(¾2)+ xbL2(¾2)
1 1
x = ¾1 x = (1+¾2)
2 2
w = waL1(¾1)+ wcL2(¾1) w = wcL1(¾2)+ wbL2(¾2)
w = wc¾1 w = wc(1-¾2)
b 1
F(x)dx = F[x(¾ )]J(¾)d¾
+" +"
a 0
"x 1 "x 1
J = = J = =
24
"¾1 2 "¾2 2
Zbieżność typu h (c.d.)
2 2
c b
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 dNI 1 dNII
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
I(NI, NII)=
+"ïÅ‚- ìÅ‚ dx ÷Å‚ +1000x2NI śłdx + +"ïÅ‚- ìÅ‚ dx ÷Å‚ +1000x2NII śłdx =
2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
ïÅ‚ śł ïÅ‚ śł
a c
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
2 2
1 1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
1 dNI d¾1 ÷Å‚ 1 dNII d¾2 ÷Å‚
= +1000x2(¾1)NI śłJ1d¾1 + +1000x2(¾2)NII śłJ2d¾2
+"ïÅ‚ 2 ìÅ‚ +"ïÅ‚ 2 ìÅ‚
+"ïÅ‚- ìÅ‚ ÷Å‚ +"ïÅ‚- ìÅ‚ ÷Å‚
2 d¾1 dx 2 d¾2 dx
d¾1 dx d¾2 dx
ïÅ‚ śł ïÅ‚ śł
śł śł
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
0 0
0 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
"I
= 0
"wc
25
Zbieżność typu h (c.d.)
w1
wN-1
w2
w0
wN
wN-2
x0 x1 x2 xN-2 xN-1 xN
x0 x1 x2 xN-2 xN-1 xN
h1 h2 hN-1 hN
x1 2 xN
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 dNI 1 dNN 2
ëÅ‚ öÅ‚
I(NI,K, NN)= +1000x2NN śłdx =
ìÅ‚ ÷Å‚ ïÅ‚- ìÅ‚ ÷Å‚
+"ïÅ‚- ëÅ‚ öÅ‚ +1000x2NI śłdx +K+ +"
2 dx 2 dx
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
ïÅ‚ śł ïÅ‚ śł
x0 xN -1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
2 2
1 1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
1 dNI d¾1 ÷Å‚ 1 dNN d¾2 ÷Å‚
= +1000x2(¾1)NI śłJ1d¾1 +K+ +1000x2(¾2)NN śłJNd¾N
+"ïÅ‚- ìÅ‚ ÷Å‚ +"ïÅ‚- ìÅ‚ ÷Å‚
ìÅ‚ ìÅ‚
2 d¾1 dx 2 d¾2 dx
ïÅ‚ śł ïÅ‚ śł
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
0 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
"I
= 0
"w1
K
"I
= 0
"wN-1
26
Zbieżność typu h (c.d.)
100
Zbieznosc
80
typu p
typu h
60
40
20
0
0 2 4 6 8 10
27
stopien wielomianu lub liczba podzialu
o
error
Algorytmizacja
w1
wN-1
N1 = N1(w0, w1)
w2
w0
wN
N2 = N2(w1, w2)
wN-2
K
NN -1 = NN -1(wN -2, wN -1)
N
N-1
1 2
NN = NN (wN -1, wN )
x0 x1 x2 xN-2 xN-1 xN
h1 h2 hN-1 hN
a+h1
b
2 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 dN 1 dN
1 dNI 1 dNN
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
2 2
( )
I(NI,K, NN )= +1000x2NI dx +K+ +1000x2NN dx =
ïÅ‚- ìÅ‚ ÷Å‚
śł ïÅ‚- ìÅ‚ ÷Å‚
śł
+" +"
+" +"
2 dx 2 dx
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
ïÅ‚ śł ïÅ‚ śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
a b-hN
= II(NI)+ III(NII)+K+ IN(NN )= II(w0, w1)+ III(w1, w2)+K+ IN(wN -1, wN )
"I "I1 "I2
= + = 0
"w1 "w1 "w1
"I "I2 "I3
= + = 0
"w2 "w2 "w2
K
"I "IN-2 "IN-1
= + = 0
"wN-2 "wN-2 "wN-2
"I "IN-1 "IN
= + = 0
28
"wN-1 "wN-1 "wN-1
Algorytmizacja (c.d.)
2
1
îÅ‚ Å‚Å‚
ëÅ‚
1 dNk d¾ öÅ‚
2
Ik(Nk )= Ik (wk -1, wk )=
-1
ìÅ‚ ÷Å‚
+"ïÅ‚- ìÅ‚ d¾ dx ÷Å‚ +1000[xk (1-¾ )+ xk¾] Nk śłJkd¾
2
ïÅ‚ íÅ‚ Å‚Å‚ śł
0
ðÅ‚ ûÅ‚
dx d¾ 1
= xk - xk -1 = hk Ò! Jk = hk , =
d¾ dx hk
dNk d
= [wk -1(1-¾ )+ wk¾]= wk - wk -1
d¾ d¾
2
1
Å„Å‚ üÅ‚
ëÅ‚ öÅ‚
ôÅ‚ 1 wk - wk -1 ÷Å‚
2
Ik = +1000[xk -1(1-¾ )+ xk¾] [wk -1(1-¾ )+ wk¾]ôÅ‚hkd¾
żł
+"òÅ‚- ìÅ‚
ìÅ‚
2 hk ÷Å‚
ôÅ‚ íÅ‚ Å‚Å‚ ôÅ‚
0
ół þÅ‚
Å„Å‚
"Ik 1 wk - wk -1
2
= +1000[xk -1(1-¾)+ xk¾] (1-¾ )üÅ‚hkd¾
żł
2
+"òÅ‚
"wk -1 0 ół hk
þÅ‚
1 1 1
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
1 1
2
= wk -1 ìÅ‚ ÷Å‚d¾ + wk ìÅ‚ ÷Å‚d¾ + {1000[xk -1(1-¾)+ xk¾] (1-¾ )}hkd¾
+"ìÅ‚- ÷Å‚ +"ìÅ‚ ÷Å‚ +"
hk
íÅ‚ Å‚Å‚3 1 hk 4 144444424444443
íÅ‚
0 0 0
1424 42Å‚Å‚3
Kk -1,k -1 Kk -1,k Fk -1
Kk -1,k-1 Kk-1,k îÅ‚ Å‚Å‚ îÅ‚ -1Å‚Å‚
wk-1 Fk
îÅ‚ Å‚Å‚
Å„Å‚ üÅ‚
"Ik 1 wk - wk -1
2
= +1000[xk -1(1-¾ )+ xk¾] ¾ d¾
+
żłh
k
+"òÅ‚- 2
ïÅ‚
"wk 0 ół hk
þÅ‚ Kk -1,k Kk ,k śłïÅ‚ śł ïÅ‚ śł
wk Fk
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚
1 1 1
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
1 1
2
= wk -1 ìÅ‚ ÷Å‚d¾ + wk ìÅ‚ ÷Å‚d¾ + {1000[xk -1(1-¾)+ xk¾] ¾}hkd¾
+"ìÅ‚ ÷Å‚ +"ìÅ‚- ÷Å‚ +"
hk hk
íÅ‚ íÅ‚ Å‚Å‚3
0 0 0
1 4 1424 1444442444443
42Å‚Å‚3
Kk -1,k Kk ,k Fk
29
Algorytmizacja (c.d.)
k -1 k -1
îÅ‚ Å‚Å‚
Kk -2,k -2 Kk-2,k -1 wk -2 îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ Fkk -1
-2
ïÅ‚ śłïÅ‚w +
odcinek k-1
k -1 k -1
Kk -1,k -1 ûÅ‚ðÅ‚ k -1 śł ïÅ‚Fkk -1śł
k -1,k -2 ûÅ‚
ðÅ‚ -1 ûÅ‚
ðÅ‚K
k k
îÅ‚ Å‚Å‚îÅ‚ -1Å‚Å‚
Kk -1,k -1 Kk -1,k wk îÅ‚ Å‚Å‚
Fkk
-1
ïÅ‚ śłïÅ‚ wk +
odcinek k
k k
Kk ,k -1 Kk ,k ûÅ‚ðÅ‚ śł ïÅ‚ śł
Fkk
ûÅ‚
ðÅ‚ ûÅ‚
ðÅ‚
k +1 k
îÅ‚ Å‚Å‚
Kk ,k Kk,+1 wk îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ Fkk +1
k +1
+
ïÅ‚K k +1 Kk +1 śł
odcinek k+1
k
Kk +1,k +1ûÅ‚ïÅ‚wk +1śł ïÅ‚Fkk +1śł
k +1
k +1,k ðÅ‚ ûÅ‚
k +1,k +1,k +1 ðÅ‚w ûÅ‚
ðÅ‚ +1 ûÅ‚
ðÅ‚Fk +1 ûÅ‚
ðÅ‚
ðÅ‚K ûÅ‚
"I "Ik "Ik +1
= + = 0
"wk "wk "wk
k -1 k -1
îÅ‚ Å‚Å‚îÅ‚ -2 Å‚Å‚
Kk -2,k -2 Kk -2,k -1 0 0 wk îÅ‚ Å‚Å‚ K
Fkk -1 îÅ‚ Å‚Å‚
-2
ïÅ‚ śłïÅ‚w śł
ïÅ‚F k -1 + Fkk śł
ïÅ‚ śł
k -1 k -1 k k
Kk -1,k 0 0
k -1 -1
ïÅ‚Kk -1,k -2 Kk -1,k -1 + Kk -1,k -1 śłïÅ‚ k -1 śł +
ïÅ‚ śł
ïÅ‚ śł
=
k k k +1 k +1
ïÅ‚
ïÅ‚
śł ïÅ‚ śł
0 Kk ,k -1 Kk ,k + Kk ,k Kk ,k +1 śłïÅ‚ wk 0
Fkk + Fkk +1 śł
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł ïÅ‚Kśł
k +1 k +1
0 0 Kk +,k Kk +1,k +1śłðÅ‚wk +1 ûÅ‚ ïÅ‚
Fkk +1 ûÅ‚ ðÅ‚ ûÅ‚
śł
ïÅ‚
ðÅ‚ +1
ðÅ‚ ûÅ‚
30
Algorytmizacja (c.d.)
K11 K12 L 0 0
w1 F1
îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚K śł
ïÅ‚ ïÅ‚
K22 L 0 0
w2 śł F2 śł
21
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł
M M M M M ïÅ‚ śł -ïÅ‚ śł
M = M
ïÅ‚
śł ïÅ‚F śł
0 0 L KN -2,N -2 KN -2,N -1śłïÅ‚
N -2
ïÅ‚ śł
ïÅ‚wN -2 śł ïÅ‚ śł
ïÅ‚
ïÅ‚
ïÅ‚FN -1 śł
ïÅ‚FN -1 śł
0 0 L KN -1,N -2 KN -1,N -1 śłðÅ‚wN -1 śł
0 0 L KN -1,N -2 KN -1,N -1 śłðÅ‚wN -1 śł
ûÅ‚ ðÅ‚ ûÅ‚
ûÅ‚ ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚ïÅ‚
ðÅ‚ ûÅ‚ïÅ‚
31