数列を近似するアルゴリズムについて考えます。
目次
The Characteristic Root Technique
今回は数列Aを以下の式に近似する場合について考えます。
$$a_n +ca_{n-1}+da_{n-2} =0\exists c,d \in\mathbb{R}$$
$$ A =\{a_0,a_1,a_2,a_3,,,\}$$
Aを使用すれば、定数c,dを求めることができそうです。
$a_2 + ca_1+da_0=0$
$a_3 + ca_2+da_1=0$
ここで、
$$a_n +ca_{n-1}+da_{n-2} =0\to$$
$$x^2+cx+d=0$$
とすると、$a_n$は解$x_1,x_2$を用いて以下のように開くことができます。
$$a_n=. u(x_1)^n + v(x_2)^n\exists u,v \in \mathbb{r}$$
$a_0$及び$a_1$について解けば、u,vを求められそうです。
よって、数列の一般項を$a_n=. u(x_1)^n + v(x_2)^n$と近似することができます。
アルゴリズム
意外と単純作業なので、一気に自動化していきます。
import math
def get_nth(initial:list[int], n:int) -> int:
a0,a1,a2,a3 = initial[0],initial[1],initial[2],initial[3]
c = int((a2**2-a3*a1)/(a0*a2-a1**2)*a0/a1-a2/a1)
d = int((a3*a1-a2**2)/(a0*a2-a1**2))
x_p = int((-c+math.sqrt(c**2-4*d))/2)
x_n = int((-c-math.sqrt(c**2-4*d))/2)
if x_n == x_p:
an1 = a1
an2 = a0
an = 0
for i in range(1,n):
an = -c*an1 - d*an2
print(an)
an2 = an1
an1 = an
return an
u = a0 -((a1-a0*x_n)/(x_p-x_n))
v = (a1-a0*x_n)/(x_p-x_n)
return int(v*(x_p)**n + u*(x_n)**n)
