Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
15
a
-
(
y
()
x
+
h
)
<
y
()
x
-
b
a
-
(
y
()
x
-
h
)
<
y
()
x
-
b
coprowadzidosprzeczności:
2
h
Ś
a
-
(
y
()
x
+
h
)
+
a
-
(
y
()
x
-
h
)
<
2
h
Zatempunkt
y
()
x
jestcentrumzbioru
U
()
x
.
Abywykazać,żezachodzi(1.9),przyjmiemy,że
h
±
z
-
y
()
x
dla
zE
U
()
x
.
Wtedyzdefinicjipromieniazbiorumamy
y
()
x
-
z
2
r
(
U
()
x
)
-
8
,
8
>
0
Niech
z
1
±
y
()
x
+
h
,
z
2
±
y
()
x
-
h
Jestoczywiste,że
z
1
,
z
2
E
U
()
x
,aponadtozachodzi
z
1
-
z
2
±
2
y
()
x
-
z
2
2
(
r
(
U
()
x
)
-
8
)
Ztegoizdefinicjiśrednicyzbioruwynika(1.9)
1.1.3.Algorytm,dokładnośćalgorytmu,rodzajealgorytmów
Podamyterazjednoznajważniejszychistaleobecnewnaszychrozważaniachpojęcie.
Definicja1.1
Algorytmem
O
dlazadaniaSnazywamyodwzorowaniepostaci
O
:
{
I
()
x
:
x
E
X
0
}
ą
Y
(1.10)
Algorytm(1.10)oznaczaprzepis,procedurę,któradlainformacjiodanychlubdanych
(gdy
I
()
x
±)zadaniaSgenerujerozwiązanietegozadanianależącedozbioruY.
x
Jakwspomnianowcześniej,algorytmówrozwiązującychzadanieSmożebyćwiele.
Algorytmmożebyćzadany(opisany)wróżnysposób.
Wyróżnićmożemytrzygłówneformyzadawaniaalgorytmów:
-
algorytmzadanywpostacianalitycznej(wzoru),np.
t
*
±
A
-
1
b
dlaukładurównań
At±,
b
-
algorytmzadanywpostaciiteracyjnej,
-
algorytmzadanywpostacirekurencyjnej.
Zauważmy,żeniezależnieodpostaci,wjakiejzadanyjestalgorytm,jeśli
O
(
I
()
x
)
±
y
()
x
oraz
tewielkościspełniają(1.2),toalgorytm
O
wyznacza
8
-przybliżenierozwiązania
S
()
x
.
Ponadtoztego,że
O
(
I
()
x
)
±
O
(
I
()
x
!
)
dlakażdego
xE
!
V
()
x
wynika,żealgorytm
O
winien
aproksymowaćkażdyelementzbioru
U
()
x
.
