(Es scheint, dass die Formel möglicherweise nicht von einem Smartphone angezeigt wird. In diesem Fall sehen Sie sie bitte von einem PC usw. aus. Es tut mir leid.)
Die Fibonacci-Sequenz ist eine Sequenz, die die beiden vorherigen Begriffe hinzufügt, um den nächsten Begriff zu erstellen. Als Ausdruck ausgedrückt
\begin{cases}
a_{n+2} = a_{n+1} + a_{n}\\ a_0 = 0\\a_1 = 1
\end{cases}
Es wird sein. Die Tribonacci-Sequenz ist die Erweiterung auf den nächsten Term, der die Summe der vorherigen drei Terme ist. Als Ausdruck ausgedrückt
\begin{cases}
a_{n+3} = a_{n+2} + a_{n+1} + a_{n}\\ a_0 = 0\\a_1 = 0\\a_2 = 1
\end{cases}
Es wird sein. Wenn Sie ein wenig rechnen,
a_3 = 1+0+0=1\\
a_4 = 1+1+0=2\\
a_5 = 2+1+1=4\\
a_6 = 4+2+1=7\\
\vdots
Es wird sein.
Sei $ V $ der Raum, der durch eine Folge von reellen Zahlen gebildet wird, die den allmählichen Ausdruck erfüllen. Bei den ersten drei Termen $ a_0, a_1, a_2 $ der Folge $ \ {a_n } $ wird die Folge $ \ {a_n } $ in $ n \ geq3 $ eindeutig bestimmt.
\boldsymbol{u}=\{1,0,0,1,\dots \},\ \boldsymbol{v}=\{0,1,0,1,\dots \},\ \boldsymbol{w}=\{0,0,1,1,\dots\}
Wird besorgt. Angenommen, $ c_1 \ boldsymbol {u} + c_2 \ boldsymbol {v} + c_3 \ boldsymbol {w} = \ boldsymbol {o} $ gilt für $ c_1, c_2, c_3 \ in \ mathbb {C} $ ,
c_1\{1,0,0,\dots \}+c_2\{0,1,0,\dots \}+c_3\{0,0,1,\dots \}=\{c_1,c_2,c_3,\dots \}=\{0,0,0,\dots \}
Daher ist $ c_1 = c_2 = c_3 = 0 $. Daher ist bekannt, dass $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $ linear unabhängig sind.
Nächster,
\boldsymbol{a}= \{ a_0,a_1,a_2,\dots \}
Ist eine willkürliche Quelle von $ V $
\begin{align}
\boldsymbol{a}&=\{ a_0,0,0,\dots \}+\{0,a_1,0,\dots \} +\{0,0,a_2,\dots \} \\
&=a_0\{1,0,0,\dots \}+a_1\{0,1,0,\dots \}+a_2\{0,0,1,\dots \} \\
&=a_0\boldsymbol{u}+a_1\boldsymbol{v}+a_2\boldsymbol{w}
\end{align}
Es kann durch eine lineare Kombination von $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $ dargestellt werden. Daher generiert $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $ $ V $.
Aus dem oben Gesagten sind $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $ linear unabhängig und erzeugen $ V $, sodass sie die Basis von $ V $ sind.
Ordnen Sie nun $ f: V \ rightarrow V $ zu
f(\{ a_n\}_{n=0}^{\infty})=\{ a_n\}_{n=1}^{\infty}
Wird besorgt. $ \ boldsymbol {a} = \ {a_0, a_1, a_2, \ dots } \ in V $, $ f (\ boldsymbol {a}) = \ {a_1, a_2, a_3, \ dots } $ Es erfüllt den allmählichen Ausdruck, also ist es $ f (\ boldsymbol {a}) \ in V $.
\boldsymbol{a}=\{ a_n\}_{n=0}^{\infty}\in V \\
\boldsymbol{b}=\{ b_n\}_{n=0}^{\infty}\in V \\
c\in \mathbb{C}
Dann
f(\boldsymbol{a}+\boldsymbol{b})=f(\{ a_n+b_n\}_{n=0}^{\infty})=\{ a_n+b_n\}_{n=1}^{\infty}=\{ a_n\}_{n=1}^{\infty}+\{ b_n\}_{n=1}^{\infty}=f(\boldsymbol{a})+f(\boldsymbol{b})\\
f(c\boldsymbol{a})=f(c\{ a_n\}_{n=0}^{\infty})=c\{ a_n\}_{n=1}^{\infty}=cf(\boldsymbol{a})
Ist wahr, also ist $ f $ eine lineare Transformation von $ V $.
In Bezug auf $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $
\begin{align}
f(\boldsymbol{u})&=\{0,0,1,\dots \}=\boldsymbol{w}\\
f(\boldsymbol{v})&=\{1,0,1,\dots \}=\boldsymbol{u}+\boldsymbol{w}\\
f(\boldsymbol{w})&=\{0,1,1,\dots \}=\boldsymbol{v}+\boldsymbol{w}
\end{align}
Damit
[f(\boldsymbol{u})\quad f(\boldsymbol{v})\quad f(\boldsymbol{w})]=
[\boldsymbol{u}\ \boldsymbol{v}\ \boldsymbol{w}]
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 1 & 1
\end{bmatrix}
Kann ausgedrückt werden als. Daher ist die Repräsentationsmatrix für die Basis $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $ von $ f $
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 1 & 1
\end{bmatrix}
ist. Diese Repräsentationsmatrix sei $ A $.
\boldsymbol{p}=\{ r^{n} \}_{n=0}^{\infty}=\{1,r,r^2,\dots \}
Gehört zu $ V $
f(\boldsymbol{p})=f(\{ r^{n} \}_{n=0}^{\infty})=\{ r^{n} \}_{n=1}^{\infty}=\{ r^{n+1} \}_{n=0}^{\infty}=r\{ r^{n} \}_{n=0}^{\infty}=r\boldsymbol{p}
Daher wird $ \ boldsymbol {p} $ ein Eigenvektor mit einem Eigenwert von $ r $. Umgekehrt ist aus der obigen Gleichung ersichtlich, dass der Eigenvektor des Eigenwerts $ r $ von $ f $ eine Folge mit gleichem Verhältnis des gemeinsamen Verhältnisses $ r $ ist. Daher wissen wir, dass das gemeinsame Verhältnis und der Eigenwert gleich sind.
Finden Sie den eindeutigen Wert von $ f $. Die Eigenpolynese von $ A $ verwendet $ I $ als Einheitsmatrix.
\begin{align}
\varphi_A(\lambda)&=|A-\lambda I|\\
&=\begin{vmatrix}
0-\lambda & 1 & 0 \\
0 & 0-\lambda & 1 \\
1 & 1 & 1-\lambda
\end{vmatrix}\\
&=-\lambda^3+\lambda^2+\lambda+1
\end{align}
Es wird sein. $ \ Varphi_A (\ lambda) = 0 $ kann jedoch nicht einfach gelöst werden. Die drei Lösungen seien $ \ alpha, \ beta, \ gamma $. $ \ Alpha, \ beta, \ gamma $ finden Sie in einem späteren Kapitel. Sequenz mit gleichem Verhältnis, dh der Eigenvektor, der der Lösung $ \ alpha, \ beta, \ gamma $ entspricht
\boldsymbol{a}=\{ \alpha^{n} \}_{n=0}^{\infty}\\
\boldsymbol{b}=\{ \beta^{n} \}_{n=0}^{\infty}\\
\boldsymbol{c}=\{ \gamma^{n} \}_{n=0}^{\infty}
Gehört zu $ V $. Diese sind linear unabhängig, da sie Eigenvektoren sind, die unterschiedlichen Eigenwerten von $ f $ entsprechen, vorausgesetzt, dass $ \ alpha, \ beta, \ gamma $ alle unterschiedlich sind. Außerdem ist $ \ dim V = 3 $. Daher ist $ \ boldsymbol {a}, \ boldsymbol {b}, \ boldsymbol {c} $ die Basis von $ V $.
Von oben gibt es einige $ c_1, c_2, c_3 $,
\boldsymbol{a_n}=c_1\boldsymbol{a}+c_2\boldsymbol{b}+c_3\boldsymbol{c}
Weil es ausgedrückt werden kann als
\begin{align}
\boldsymbol{a_n}&=c_1\boldsymbol{a}+c_2\boldsymbol{b}+c_3\boldsymbol{c}\\
\Leftrightarrow \{a_0,a_1,a_2,\dots \}&=c_1\{ \alpha^{n} \}_{n=0}^{\infty}+c_2\{ \beta^{n} \}_{n=0}^{\infty}+c_3\{ \gamma^{n} \}_{n=0}^{\infty}\\
\Leftrightarrow \{0,0,1,\dots \}&=c_1\{ 1,\alpha,\alpha^2,\dots \}+c_2\{1,\beta,\beta^2,\dots \}+c_3\{ 1,\gamma,\gamma^2,\dots\} \\
\Leftrightarrow \{0,0,1,\dots \}&=\{ c_1+c_2+c_3,c_1\alpha+c_2\beta+c_3\gamma,c_1\alpha^2+c_2\beta^2+c_3\gamma^2, \dots\}
\end{align}
Dies als Matrix ausdrücken,
\begin{bmatrix}
1 & 1 & 1 \\
\alpha & \beta & \gamma \\
\alpha^2 & \beta^2 & \gamma^2
\end{bmatrix}
\begin{bmatrix}
c_1 \\ c_2 \\ c_3
\end{bmatrix}
=
\begin{bmatrix}
0 \\ 0 \\ 1
\end{bmatrix}
ist. Der Matrixausdruck der linken Matrix ist
\begin{align}
\begin{vmatrix}
1 & 1 & 1 \\
\alpha & \beta & \gamma \\
\alpha^2 & \beta^2 & \gamma^2
\end{vmatrix}
&=
\begin{vmatrix}
1 & 0 & 0 \\
\alpha & \beta-\alpha & \gamma-\alpha \\
\alpha^2 & \beta^2-\alpha^2 & \gamma^2-\alpha^2
\end{vmatrix}\\
&=
\begin{vmatrix}
\beta-\alpha & \gamma-\alpha \\
\beta^2-\alpha^2 & \gamma^2-\alpha^2
\end{vmatrix}\\
&=\begin{vmatrix}
\beta-\alpha & \gamma-\alpha \\
\beta^2-\alpha^2 - (\beta-\alpha)(\beta + \alpha) & \gamma^2-\alpha^2 - (\gamma-\alpha)(\beta + \alpha)
\end{vmatrix}\\
&=\begin{vmatrix}
\beta-\alpha & \gamma-\alpha \\
0 & (\gamma-\alpha)(\gamma+\alpha) - (\gamma-\alpha)(\beta + \alpha)
\end{vmatrix}\\
&=(\beta-\alpha)(\gamma-\alpha)(\gamma - \beta)\\
&=(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
\end{align}
Es wird sein. Dies ist auch als Van-der-Monde-Matrixgleichung bekannt. Unter Verwendung der Cramel-Formel
\begin{align}
c_1 &= \frac{
\begin{vmatrix}
0 & 1 & 1 \\
0 & \beta & \gamma \\
1 & \beta^2 & \gamma^2
\end{vmatrix}
}{
\begin{vmatrix}
1 & 1 & 1 \\
\alpha & \beta & \gamma \\
\alpha^2 & \beta^2 & \gamma^2
\end{vmatrix}
}\\
&=
\frac{
-\begin{vmatrix}
1 & \beta^2 & \gamma^2 \\
0 & \beta & \gamma \\
0 & 1 & 1
\end{vmatrix}
}{
(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}\\
&=
\frac{
-\begin{vmatrix}
\beta & \gamma\\
1 & 1
\end{vmatrix}
}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}\\
&=\frac{
\gamma-\beta
}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}\\
&=\frac{1}{(\alpha-\beta)(\alpha-\gamma)
}
\end{align}
Wird benötigt. Ähnlich
c_2 = \frac{
\alpha-\gamma
}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}=\frac{1
}{(\beta-\alpha)(\beta-\gamma)
}\\
c_3 = \frac{
\beta-\alpha
}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}
=\frac{1
}{(\gamma-\alpha)(\gamma-\beta)
}
Wird benötigt.
Von Oben,
\begin{align}
\boldsymbol{a_n} &= c_1 \boldsymbol{a} + c_2 \boldsymbol{b} + c_3 \boldsymbol{c}\\
&=\left\{ \frac{\alpha^n}{(\alpha-\beta)(\alpha-\gamma)} + \frac{\beta^n}{(\beta-\alpha)(\beta-\gamma)} + \frac{\gamma^n}{(\gamma-\alpha)(\gamma-\beta)}\right\}_{n=0}^{\infty}
\end{align}
Damit
a_n = \frac{\alpha^n}{(\alpha-\beta)(\alpha-\gamma)} + \frac{\beta^n}{(\beta-\alpha)(\beta-\gamma)} + \frac{\gamma^n}{(\gamma-\alpha)(\gamma-\beta)}
Wurde geführt.
Bisher kennen wir die Form des allgemeinen Begriffs, aber wir kennen die spezifischen Werte von $ \ alpha, \ beta, \ gamma $ nicht. Es gibt auch eine Methode, um es unter Verwendung der Formel der Lösung der kubischen Gleichung zu finden, aber dieses Mal wollen wir es mit Python finden. Es wird angenommen, dass $ a [i] $ gemäß der Definition der Tribonacci-Sequenz berechnet wird und $ b [i] $ durch den allgemeinen Term berechnet wird. Es gibt auch eine Methode, um es algebraisch mit Sympy zu lösen, aber dieses Mal wird es numerisch mit Numpy berechnet.
import numpy as np
import warnings
warnings.filterwarnings('ignore') #Bei der Berechnung komplexer Zahlen tritt eine Warnung auf. Löschen Sie sie daher.
alpha, beta, gamma = np.roots([1,-1,-1,-1]) # solve 1*x^3 + (-1)*x^2+ (-1)*x + (-1) = 0
print("alpha =", alpha)
print("beta =", beta)
print("gamma =", gamma)
a = np.zeros(101)
b = np.zeros(101)
a[2] = 1
print(" i "," a[i] "," b[i] ", " a[i]-b[i] ")
for i in range(101):
if i > 2:
a[i] = a[i-1] + a[i-2] + a[i-3]
b[i] = np.power(alpha,i)/((alpha-beta)*(alpha-gamma)) + np.power(beta,i)/((beta-alpha)*(beta-gamma)) + np.power(gamma,i)/((gamma-alpha)*(gamma-beta))
print('{:3}'.format(i), '{:26}'.format(int(a[i])), '{:26}'.format(int(round(abs(b[i])))), '{:12}'.format(int(a[i]) - int(round(abs(b[i])))))
alpha = (1.839286755214161+0j)
beta = (-0.41964337760708065+0.6062907292071997j)
gamma = (-0.41964337760708065-0.6062907292071997j)
i a[i] b[i] a[i]-b[i]
0 0 0 0
1 0 0 0
2 1 1 0
3 1 1 0
4 2 2 0
5 4 4 0
6 7 7 0
7 13 13 0
8 24 24 0
9 44 44 0
10 81 81 0
11 149 149 0
12 274 274 0
13 504 504 0
14 927 927 0
15 1705 1705 0
16 3136 3136 0
17 5768 5768 0
18 10609 10609 0
19 19513 19513 0
20 35890 35890 0
21 66012 66012 0
22 121415 121415 0
23 223317 223317 0
24 410744 410744 0
25 755476 755476 0
26 1389537 1389537 0
27 2555757 2555757 0
28 4700770 4700770 0
29 8646064 8646064 0
30 15902591 15902591 0
31 29249425 29249425 0
32 53798080 53798080 0
33 98950096 98950096 0
34 181997601 181997601 0
35 334745777 334745777 0
36 615693474 615693474 0
37 1132436852 1132436852 0
38 2082876103 2082876103 0
39 3831006429 3831006429 0
40 7046319384 7046319384 0
41 12960201916 12960201916 0
42 23837527729 23837527729 0
43 43844049029 43844049029 0
44 80641778674 80641778674 0
45 148323355432 148323355432 0
46 272809183135 272809183135 0
47 501774317241 501774317241 0
48 922906855808 922906855808 0
49 1697490356184 1697490356184 0
50 3122171529233 3122171529233 0
51 5742568741225 5742568741225 0
52 10562230626642 10562230626642 0
53 19426970897100 19426970897100 0
54 35731770264967 35731770264967 0
55 65720971788709 65720971788709 0
56 120879712950776 120879712950775 1
57 222332455004452 222332455004451 1
58 408933139743937 408933139743935 2
59 752145307699165 752145307699160 5
60 1383410902447554 1383410902447546 8
61 2544489349890656 2544489349890641 15
62 4680045560037375 4680045560037345 30
63 8607945812375585 8607945812375530 55
64 15832480722303616 15832480722303512 104
65 29120472094716576 29120472094716384 192
66 53560898629395776 53560898629395416 360
67 98513851446415968 98513851446415296 672
68 181195222170528320 181195222170527072 1248
69 333269972246340096 333269972246337792 2304
70 612979045863284352 612979045863280000 4352
71 1127444240280152832 1127444240280144512 8320
72 2073693258389777408 2073693258389762048 15360
73 3814116544533214720 3814116544533186560 28160
74 7015254043203144704 7015254043203092480 52224
75 12903063846126137344 12903063846126039040 98304
76 23732434433862496256 23732434433862311936 184320
77 43650752323191775232 43650752323191439360 335872
78 80286250603180408832 80286250603179769856 638976
79 147669437360234692608 147669437360233480192 1212416
80 271606440286606852096 271606440286604623872 2228224
81 499562128250021937152 499562128250017808384 4128768
82 918838005896863416320 918838005896855945216 7471104
83 1690006574433492271104 1690006574433477853184 14417920
84 3108406708580377427968 3108406708580351213568 26214400
85 5717251288910732984320 5717251288910684749824 48234496
86 10515664571924601634816 10515664571924511457280 90177536
87 19341322569415712047104 19341322569415540080640 171966464
88 35574238430251047714816 35574238430250737336320 310378496
89 65431225571591361396736 65431225571590774194176 587202560
90 120346786571258121158656 120346786571257030639616 1090519040
91 221352250573100547047424 221352250573098500227072 2046820352
92 407130262715950037991424 407130262715946279895040 3758096384
93 748829299860308689420288 748829299860301844316160 6845104128
94 1377311813149359375122432 1377311813149346221785088 13153337344
95 2533271375725618236751872 2533271375725593540689920 24696061952
96 4659412488735286167076864 4659412488735240533049344 45634027520
97 8569995677610263510515712 8569995677610179758653440 83751862272
98 15762679542071167914344448 15762679542071011148038144 156766306304
99 28992087708416715444453376 28992087708416427681644544 287762808832
100 53324762928098150090539008 53324762928097265327276032 884763262976
Wenn also $ i $ klein ist, stimmt es überein. Wenn $ i $ groß ist, liegt ein Fehler aufgrund von Gleitkommazahlen vor. Da der Fehler jedoch kleiner als der numerische Wert ist, wird der allgemeine Term als korrekt angesehen.
In Python wird die für die Leistung verwendete pow-Funktion wiederholt durch die Quadratmethode implementiert, sodass mit $ O (\ log N) $ schnell eine bestimmte Anzahl von $ N $ -Leistungen erhalten werden kann. Daher ist der Rechenaufwand, der erforderlich ist, um $ a [N] $ zu finden, $ O (N) $, aber $ b [N] $ kann durch $ O (\ log N) $ gefunden werden. Auf dem Computer hat $ a [i] $ die Vor- und Nachteile, dass der Wert genau berechnet werden kann, der Rechenaufwand jedoch groß ist, und $ b [i] $ mit hoher Geschwindigkeit berechnet werden kann, aber ein Fehler auftritt.
Ich schrieb einen Artikel Finden der allgemeinen Begriffe einer erweiterten Fibonacci-Sequenz (k-Bonatch-Sequenz: Summe der vorherigen k Begriffe) mit linearer Algebra und Python. Bitte sehen Sie, ob Sie möchten.
Recommended Posts