将递归公式转换回原始的显式公式? [英] Converting a recursive formula back to the original explicit formula?

问题描述

有一个通用公式Z ^ N = A(Z)^ N + 1 + B(Z)^ N + 1.此公式用于将给定的递归函数转换回其原始的显式形式:

There is a generic formula Z^N = A(Z)^N+1 + B(Z)^N+1 . This formula is used to convert a given recursive function back to its original explicit form :

递归公式:

1) R(0) = 1, R(n) = (1/3) R(n-1), n = 1, 2, ...
2) P(0) = 1, P(1) = 1/3, P(n) = (4/3) P(n-1) - (1/3) P(n-2), n = 2, 3, ...
3) Q(0) = 1, Q(1) = 1/3, Q(n) = (10/3) Q(n-1) - Q(n-2), n = 2, 3, ...

然后，它表示以下形式的差异公式":

Then, it suggests that "difference formulas" of the form :

2) P(n) = A(1/3^n) + B
3) Q(n) = A(1/3^n) + B * 3^n

代表一般解决方案.

然后将差分函数"代入递归函数"以获得A，B的根，这证明递归函数确实是原始序列{Xn} = {1/3的表示形式^ n} = 1，1/3，1/9，...

Then the "difference functions" are to be substituted into the "recursive functions" to obtain root of A, B which completes the proof that the recursive function is indeed a representation of the original sequence {Xn} = {1/3^n} = 1, 1/3, 1/9, ...

我的问题是差异公式从何而来?我希望在任何主要的教科书中使用微积分或数值方法(例如Swokowski，Fink或Chapra)来引用该主题.

My Question is where the difference formulas come from? I would appreciate a reference to the subject in any major text-book in calculus or numerical methods like Swokowski, Fink, or Chapra.

推荐答案

这只是新生代数.让我们以示例3为例:

It's just a bit of freshman algebra. Let's take example 3 for instance:

Q(n+2) = (10/3)Q(n+1) + (-1)Q(n)
Q(n+1) = (   1)Q(n+1) + ( 0)Q(n)

第二个方程似乎很愚蠢，但它使我们可以编写以下矩阵方程:

That second equation seems silly, but it allows us to write the following matrix equation:

[ Q(n+2) ]  = [ 10/3  -1 ][ Q(n+1) ]
[ Q(n+1) ]  = [    1   0 ][   Q(n) ]

这是像v(n+1) = a*v(n)这样的重复发生的二维类似物，具有简​​单的解决方案v(n) = a^n * v(0).我们可以对矩阵方程应用相同的逻辑来获得:

This is the 2-dimensional analogue of a recurrence like v(n+1) = a*v(n) which has an easy solution v(n) = a^n * v(0). We can apply the same logic to our matrix equation to obtain:

[ Q(n+1) ] = [ 10/3  -1 ]^n [ 1/3 ]
[   Q(n) ] = [    1   0 ]   [   1 ]

让我们将中间的2 x 2矩阵提升为n次幂A.现在我们如何快速计算平方矩阵的幂?当它们对角线化时，这很容易.该2x2矩阵的特征值是其特征多项式的根:

Let's call that 2 x 2 matrix in the middle that we're raising to the nth power, A.Now how do we quickly compute powers of square matrices? When they're diagonalizable, it's easy. The eigenvalues of that 2x2 matrix are the roots of its characteristic polynomial:

det(A - xI) = (10/3 - x)(0 - x) - (1)(-1) = (x - 1/3)(x - 3)

这告诉我们，存在一些可逆的2 x 2矩阵P(由的特征向量组成)，这样:

This tells us that there's some invertible 2 x 2 matrix P (consisting of the eigenvectors of A) such that:

[ Q(n+1) ] = P [ 1/3  0 ]^n P^-1 [ 1/3 ]
[   Q(n) ] =   [   0  3 ]        [   1 ]

等等:

[ Q(n+1) ] = P [ 1/3^n    0 ] P^-1 [ 1/3 ]
[   Q(n) ] =   [     0  3^n ]      [   1 ]

由此我们可以轻松推断出一些常数a和b:

From this we easily deduce that for some constants a and b:

Q(n) = a(1/3^n) + b(3^n)

我们可以通过找到A的特征向量，构造矩阵P和P^-1，将这三个2 x 2矩阵与右边的2 x 1向量相乘，来明确找出它们的含义.从中提取Q(n)的表达式.但是，仅需看一下方程式，便会发现它会产生Q(n) = a(1/3^n) + b(3^n)形式的东西，并且实际上只是通过反替代来求解a和b，这会更容易.

We could explicitly figure out what they are by finding the eigenvectors of A, constructing the matrices P and P^-1, multiplying those three 2 x 2 matrices with the 2 x 1 vector on the right, and actually extracting the expression for Q(n) from that. But it's easier to just look at the equation, realize that it'll result in something of the form Q(n) = a(1/3^n) + b(3^n) and actually just solve for a and b via back-substitution.

这篇关于将递归公式转换回原始的显式公式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！