Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
11
Przykład1.2
W
zadaniu
wyznaczania
miejsc
zerowych
d
wielomianu
P
()
t
±
a
0
+
a
1
t
+
a
2
t
2
+
.
.
.
+
a
n
t
n
zdefiniowanewielkościprzyjmąpostać
x±
(
a
0
,
a
1
,
.
.
.,
a
n
)
-danezadania,
przyczym
aoznaczawspółczynnikprzyzmiennejwi-tejpotędze,
i
S
()
x
±
d
-operatorrozwiązaniataki,że
P
()
d
±,
0
I
()
x
±
x
-operatorinformacji.
n-tego
stopnia
JeślidowyznaczeniamiejsczerowychtegowielomianuwykorzystamymetodęNewtona,tzn.
gdyciąggenerowanychpunktówmapostać
gdzie
t
K
+
1
±
t
K
-
P
P
!
()
()
t
t
K
K
P!
()
t
K
-pochodnawielomianu
P
()
t
wpunkcie
t,
K
tooperatorinformacji
I
()
x
przyjmujepostać
I
()
x
±
[
t
,
P
()()
t
,
P
!
t
]
Podobnezagadnieniewystępujewprzypadkuwyznaczeniaekstremumróżniczkowalnej
funkcjiwypukłej
f
()
t
,gdziewarunek
f
!
()
t
±
F
()
t
±
0
jestwarunkiemkoniecznym
iwystarczającymekstremum.
OperatorinformacjiwykorzystywanywmetodzieNewtonamiałbywtymprzypadkupostać
I
()
x
±
[
t
,
f
!
()
t
,
f
!
!
()
t
]
±
[
t
,
F
()
t
,
F
!
()
t
]
Przykład1.3
Danyjestzbiór
x±
{
x
1
,
x
2
,
.
.
.
,
x
n
}
,
x
iE
D
i
±
1
,
n
±
1
,
2
,
.
.
.
,
n
,
gdzieD-zbióruporządkowany.
Zadaniesortowaniamożnasformułowaćnastępująco:
S
()
x
±
(
x
i
1
,
x
i
2
,
.
.
.
,
x
i
n
)
gdzie
x
i
1
Ś
x
i
2
Ś
.
.
.
Ś
x
i
n
Wtymprzypadku
i
1
,
i
2
,
.
.
.
,
i
n
permutacjaliczb
I
()
x
±
x
1
,
n
.
Należyprzytejokazjizauważyć,żetakjakiwinnychprzypadkachdosformułowanego
zadaniasortowanianależyskonstruowaćmetodyjegorozwiązania.
Istniejebardzodużoróżnychmetodsortowaniaspełniającychwymaganie(1.2).
Niektóreznichomówimypóźniej.
1.1.2.Wybranewłasnościicharakterystykioperatorainformacji
Bardzoważnąwłasnościąniektórychoperatorówinformacjijestichniejednoznaczność.
Matomiejscewtedygdy
I
()
x
nieokreślajednoznacznierozwiązania
S
()
x
.
