rek05.pdf
(
183 KB
)
Pobierz
Podró»e po Imperium Liczb
Cz¦±¢ 07.
Ci¡gi rekurencyjne
Rozdział 5
5. Ogólne własno±ci liniowych ci¡gów rekurencyjnych
AndrzejNowicki17maja2012,
http://www.mat.uni.torun.pl/~anow
Spis tre±ci
5Ogólnewłasno±ciliniowychci¡gówrekurencyjnych 47
5.1
Ci¡gi a
[
s
]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
5.2
Algebra funkcji arytmetycznych jako k[x]-moduł . . . . . . . . . . . . . . . .
47
5.3
Równowa»ne definicje liniowej rekurencyjno±ci
. . . . . . . . . . . . . . . . .
48
5.4
Przykłady liniowych ci¡gów rekurencyjnych . . . . . . . . . . . . . . . . . . .
50
5.5
Algebra liniowych ci¡gów rekurencyjnych . . . . . . . . . . . . . . . . . . . .
50
5.6
Podci¡gi o indeksach tworz¡cych ci¡g arytmetyczny
. . . . . . . . . . . . . .
52
5.7
Przestrzenie L(f) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
5.8
Bazy przestrzeni L(f)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
5.9
Niejednorodne liniowe ci¡gi rekurencyjne
. . . . . . . . . . . . . . . . . . . .
55
5.10
Niejednorodne liniowe ci¡gi rekurencyjne rz¦du 1 . . . . . . . . . . . . . . . .
56
5.11
Niejednorodne liniowe ci¡gi rekurencyjne rz¦du 2 . . . . . . . . . . . . . . . .
57
5.12
Niejednorodne liniowe ci¡gi rekurencyjne rz¦du 3 . . . . . . . . . . . . . . . .
57
Wszystkie ksi¡»ki z serii ”Podró»e po Imperium Liczb” napisano w edytorze L
A
T
E
X.
Spisy tre±ci tych ksi¡»ek oraz pewne wybrane rozdziały mo»a znale¹¢ na internetowej stronie
autora:
http://www-users.mat.uni.torun.pl/~anow
.
5 Ogólne własno±ci liniowych ci¡gów rekurencyjnych
W tym rozdziale zakładamy, »e
k
jest pier±cieniem przemiennym z jedynk¡. PrzezA(
k
)
oznaczamy zbiór wszystkich funkcji zNdo
k
, tzn. zbiór wszystkich ci¡gów niesko«czonych o
wyrazach z pier±cienia
k
.
Je±li
a
i
b
s¡ elementami zbioruA(
k
), to ich sum¡ i iloczynem s¡ odpowiednio funkcje
a
+
b
:N
!
k
i
ab
:N
!
k
okre±lone wzorami
(
a
+
b
)(
n
) =
a
(
n
) +
b
(
n
)
,
(
ab
)(
n
) =
a
(
n
)
b
(
n
)
,
dla wszystkich
n
2
N. Mamy tu równie» mno»enie
k
×
A(
k
)
!
A(
k
) okre±lone w naturalny
sposób; je±li
2
k
,
a
2
A(
k
), to
a
jest funkcj¡ zNdo
k
tak¡, »e (
a
)(
n
) =
·
a
(
n
) dla
n
2
N. ZbiórA(
k
) jest przemienn¡
k
-algebr¡ ze wzgł¦du na powy»sze działania. Algebr¦ t¦
nazywamy
algebr¡ funkcji arytmetycznych
nad
k
.
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
5.1 Ci¡gi a
[
s
]
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
Je±li
a
2
A(
k
), to dla ka»dej liczby
s
2
N
0
, przez
a
[
s
]
oznacza¢ b¦dziemy ci¡g okre±lony
wzorem
a
[
s
]
(
n
) =
a
(
s
+
n
)
,
dla wszystkich
n
2
N. W szczególno±ci
a
[0]
=
a
.
a
[
r
]
[
s
]
a
[
s
]
[
r
]
=
a
[
s
+
r
]
.
5.1.1.
Je±li a
2
A(
k
)
i r,s
2
N
0
, to
=
5.1.2.
Niech a,b
2
A(
k
)
,
2
k, r
2
N
0
. Wtedy:
(1)
(
a
+
b
)
[
r
]
=
a
[
r
]
+
b
[
r
]
,
(
ab
)
[
r
]
=
a
[
r
]
b
[
r
]
,
(2)
(
a
)
[
r
]
=
a
[
r
]
.
(3)
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
5.2 Algebra funkcji arytmetycznych jako k[x]-moduł
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
Przez
k
[
x
] oznaczamy pier±cie« wielomianów jednej zmiennej
x
o współczynnikach nale-
»¡cych do pier±cienia
k
.
Niech
f
=
s
x
s
+
···
+
1
x
1
+
0
b¦dzie wielomianem nale»¡cym do
k
[
x
] i niech
a
2
A(
k
).
Przez
f
a
oznaczamy element zA(
k
) zdefiniowany wzorem
f
a
=
s
a
[
s
]
+
···
+
1
a
[1]
+
0
a
[0]
.
5.2.1.
Niech f,g
2
k
[
x
]
, a,b
2
A(
k
)
,
2
k. Wtedy:
(1)
f
(
a
+
b
) = (
f
a
) + (
f
b
)
,
(2)
(
f
+
g
)
a
= (
f
a
) + (
g
a
)
,
(3)
(
f
)
a
=
f
(
a
) =
(
f
a
)
.
47
48
AndrzejNowicki,Ci¡girekurencyjne. 5.Ogólnewłasno±ciliniowychci¡gówrekurencyjnych
5.2.2.
Niech f,g
2
k
[
x
]
, a
2
A(
k
)
. Wtedy
(
fg
)
a
=
f
(
g
a
)
.
D.
Niech
f
=
s
x
s
+
···
+
a
x
+
0
. Najpierw wykazujemy to dla
g
=
x
r
. W tym przypadku
mamy:
(
fx
r
)
a
= (
s
x
s
+
r
+
···
+
1
x
1+
r
+
0
x
r
)
a
=
s
a
[
s
+
r
]
+
···
+
1
a
[1+
r
]
+
0
a
[
r
]
=
s
a
[
r
]
[
s
]
+
···
+
1
a
[
r
]
[1]
+
0
a
[
r
]
[0]
=
f
a
[
r
]
=
f
(
x
r
a
)
.
Je±li wi¦c
g
=
x
r
, to równo±¢ (
fg
)
a
=
f
(
g
a
) jest prawdziwa. St¡d i z 5.2.1 wynika prawdziwo±¢
tej równo±ci dla dowolnego
g
.
Z powy»szych faktów otrzymujemy:
5.2.3.
Pier±cie«
A(
k
)
, funkcji arytmetycznych nad pier±cieniem k, jest k
[
x
]
-modułem ze
wzgl¦du na powy»sze mno»enie
:
k
[
x
]
×
A(
k
)
!
A(
k
)
.
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
5.3 Równowa»ne definicje liniowej rekurencyjno±ci
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
Je±li
a
2
A(
k
), to przez
I
a
oznaczamy podzbiór pier±cienia
k
[
x
] zdefiniowany jako
n
o
I
a
=
f
2
k
[
x
];
f
a
= 0
.
Jest oczywiste, »e
I
a
jest ideałem pier±cienia
k
[
x
]. Ka»dy niezerowy wielomian
f
2
k
[
x
],
nale»¡cy do
I
a
, nazywa si¦
wielomianem charakterystycznym
ci¡gu
a
.
5.3.1.
I
a
=
k
[
x
]
()
a
= 0
.
Mówimy, »e ci¡g
a
2
A(
k
) jest
liniowym ci¡giem rekurencyjnym
je±li istnieje liczba natu-
ralna
s
oraz istniej¡ elementy
0
,...,
s
−
1
2
k
takie, »e
a
n
+
s
=
s
−
1
a
n
+(
s
−
1)
+
···
+
1
a
n
+1
+
0
a
n
,
dla wszystkich
n
2
N. Powy»sz¡ równo±¢ zapisuje si¦ równie» w postaci
a
(
n
+
s
) =
s
−
1
a
(
s
−
1 +
n
) +
···
+
1
a
(1 +
n
) +
0
a
(
n
)
,
dla wszystkich
n
2
N, a to oznacza, »e
a
[
s
]
=
s
−
1
a
[
s
−
1]
+
···
+
1
a
[1]
+
0
a
[0]
,
czyli
f
a
= 0, gdzie
f
=
x
s
−
s
−
1
x
s
−
1
−···−
1
x
1
−
0
2
k
[
x
]. Wielomian
f
jest niezerowy
i nale»y do ideału
I
a
. Zatem
I
a
6
= 0. Je±li wi¦c
a
jest liniowym ci¡giem rekurencyjnym, to
I
a
6
= 0. W przypadku ciał (tzn. gdy
k
jest ciałem) zachodzi równie» oczywista inkluzja w
przeciwnym kierunku. Mamy zatem:
5.3.2.
Je±li k jest ciałem i a
2
A(
k
)
, to a jest liniowym ci¡giem rekurencyjnym wtedy i tylko
wtedy, gdy I
a
6
= 0
.
Załó»my teraz, »e
k
jest ciałem oraz, »e
a
2
A(
k
) jest liniowym ci¡giem rekurencyjnym.
Wtedy
I
a
jest niezerowym ideałem w
k
[
x
] generowanym przez jeden moniczny wielomian
nale»¡cy do
k
[
x
]. Wielomian ten nazywamy
wielomianem minimalnym
ci¡gu rekurencyjne-
go
a
. Stopie« tego wielomianu nazywamy
rz¦dem
ci¡gu rekurencyjnego
a
.
AndrzejNowicki,Ci¡girekurencyjne. 5.Ogólnewłasno±ciliniowychci¡gówrekurencyjnych
49
5.3.3.
Niech k b¦dzie ciałem. Niech a
2
A(
k
)
i
0
6
=
2
k. Wówczas a jest liniowym ci¡giem
rekurencyjnym rz¦du s wtedy i tylko wtedy, gdy a jest liniowym ci¡giem rekurencyjnym
rz¦du s. Je±li a jest liniowym ci¡giem rekurencyjnym, to wielomiany minimalne ci¡gów a i
a s¡ identyczne. Wszystko wynika z oczywistej równo±ci I
a
=
I
a
.
Niech
a
2
A(
k
), gdzie
k
jest ciałem. Przez
V
a
oznacza¢ b¦dziemy
k
-podprzestrze« liniow¡
k
-algebryA(
k
) generowan¡ przez wszystkie funkcje postaci
a
[
r
]
dla
r
= 0
,
1
,
2
,...
; innymi
słowy:
D
E
a
[
r
]
;
r
2
N
0
V
a
=
.
5.3.4.
Niech a
2
A(
k
)
, gdzie k jest ciałem. Ci¡g a jest liniowym ci¡giem rekurencyjnym
wtedy i tylko wtedy, gdy
dim
k
V
a
<
1
.
Dokładniej: a jest liniowym ci¡giem rekurencyjnym rz¦du s wtedy i tylko wtedy, gdy
dim
k
V
a
=
s.
D.
Zało»my, »e
a
jest liniowym ci¡giem rekurencyjnym rz¦du
s
. Niech
f
=
x
s
−
s
−
1
x
s
−
1
−···−
a
x
1
−
0
b¦dzie wielomianem minimalnym ci¡gu
a
. Wtedy
a
[
s
]
=
s
−
1
a
[
s
−
1]
+
···
+
1
a
[1]
+
0
a
[0]
(1)
i ta równo±¢ implikuje, »e
a
[
s
]
2
W
, gdzie
W
=
h
a
[0]
,a
[1]
,...,a
[
s
−
1]
i
. Poka»emy, »e
V
a
=
W
. W tym
celu wystarczy pokaza¢, »e
a
[
p
]
2
W
dla wszystkich
p
2
N
0
. Wiemy ju», »e tak jest dla
p
= 0
,
1
,...,s
.
Poniewa»
f
(
x
a
) = (
fx
)
a
=
x
(
f
a
) =
x
0 = 0, wi¦c
a
[1]
[
s
]
a
[1]
[
s
−
1]
a
[1]
[1]
a
[1]
[0]
=
s
−
1
+
···
+
1
+
0
,
czyli
a
[
s
+1]
=
s
−
1
a
[
s
]
+
···
+
1
a
[2]
+
0
a
[1]
i st¡d, na mocy (1),
a
[
s
+1]
2
W
. Analogicznie wykazujemy,
»e ci¡gi
a
[
s
+2]
,a
[
s
+3]
,...
nale»¡ do
W
. Zatem
V
a
=
W
. Z mninimalno±ci wielomianu
f
wynika, »e
dim
k
W
=
s
. Zatem dim
k
V
= dim
k
W
=
s <
1
.
Załó»my teraz, »e dim
k
V
a
<
1
. Poniewa» z ka»dego ci¡gu generatorów przestrzeni
V
a
mo»na
wybra¢ baz¦ tej przestrzeni, wi¦c
V
a
=
h
a
[0]
,a
[1]
,...,a
[
s
−
1]
i
dla pewnego
s
. Ale
a
[
s
]
2
V
a
, wi¦c
a
[
s
]
=
s
−
1
a
[
s
−
1]
+
···
+
1
a
[1]
+
0
a
[0]
, gdzie
0
,...,
s
−
1
s¡ pewnymi elementami ciała
k
. Mamy zatem
f
a
= 0, gdzie
f
=
x
s
−
s
−
1
x
s
−
1
−···−
1
x
−
0
. W szczególno±ci,
I
a
6
= 0, czyli
a
jest (na mocy 5.3.2)
liniowym ci¡giem rekurencyjnym. Wybieraj¡c
s
jako minimaln¡ liczb¦ naturaln¡ spełniaj¡c¡ równo±¢
V
a
=
h
a
[0]
,a
[1]
,...,a
[
s
−
1]
i
, łatwo stwierdzi¢, »e dim
k
V
=
s
oraz, »e
f
jest minimalnym wielomianem
ci¡gu
a
, tzn.
a
jest rz¦du
s
.
Plik z chomika:
xyzgeo
Inne pliki z tego folderu:
pri03.pdf
(156 KB)
pri-toc.pdf
(108 KB)
pel07.pdf
(196 KB)
pel02.pdf
(180 KB)
pel-toc.pdf
(100 KB)
Inne foldery tego chomika:
06-DLOGLI0 Podstawy logiki i teorii mnogości (geminus)
httpalgebra.rezolwenta.eu.orgMaterialy
httpmath.uni.lodz.pl~kowalcr
httpwww.fuw.edu.pl~pmajlect.php
httpwww.math.uni.wroc.pl~newelskidydaktykalogikaBlogikaB.html
Zgłoś jeśli
naruszono regulamin