递推关系与差分方程 |
您所在的位置:网站首页 › 差分方程与微分方程在解法上有何异同 › 递推关系与差分方程 |
递推关系与差分方程¶
数列的递推关系(Recurrence relation),就是一个数列的第\(n\)项和前\(n-1\)项的等式。这个等式也叫差分方程(Difference equation)。 差分方程的概念¶在差分方程中,一个很重要的任务就是从递推关系求解出数列的通项公式,这个过程称为解差分方程。 和数列的求和一样,求解递推关系(差分方程)也没有通用的方法。不过,下面我们会介绍一些常用的解法,能解决一部分常见的差分方程。 Tip 并不是所有的差分方程都可以给出初等解或者解析解。一个很显然的例子就是阶乘:定义数列\(a_0 = 1\),\(a_{n+1} = na_n\),那么这个数列就是阶乘数列\(a_n = n!\),但阶乘并不是初等函数(阶乘在实数上的延拓是 Gamma 函数,但 Gamma 函数并非初等函数)。 如果将数列的求和类比成积分,那么差分方程就应该对应微积分的微分方程。很多微分方程和差分方程都无法用解析解表示。 通解与特解¶一个差分方程往往不止一个解,差分方程的所有解的集合称为通解。而其中一个特定的解,称为差分方程的特解。 初值条件¶差分方程的求解过程中,往往需要伴随某些已知的条件,例如已知某一项的具体值。这些条件称为初值条件(initial condition)。 这个条件的作用之一就是从通解得出满足给定条件的特解。 最常见的初值条件就是已知前几项 \(a_1, \dots, a_k\) 的值。 一些典型的差分方程¶ 等差数列¶等差数列的定义式是: \[ a_n - a_{n-1} = d; \]这是一个典型的差分方程,在第一节中我们已经用数学归纳法证明了等差数列的通项为 \(a_n = a_1 + d(n-1)\)。 这里我们用 \(a_1\) 表示了通项,实际上暗含了 \(a_1\) 已知的假设。也就是说,\(a_1\) 是这个方程的初值条件。 等比数列¶ \[ \frac{a_{n+1}}{a_n} = q; \] 阶乘¶数列递推与编程递归 递推与递归(recursive)具有一定的相似性。 在数学上,递归指的是将一个问题分解为已经解决的问题,如用数学归纳法证明问题。类似地,编程上的递归也是将一个问题分解为它的子问题。 以下我们便可以用一个递推方法编写一个阶乘函数: #include int factorial(int n){ return n * factorial(n-1); } void main(){ scanf("%d", &n); printf("%d", factorial(n)); } def Factorial(n : int) -> int: return n * Factorial(n-1) n = input() print(Factorial(n)) 差分方程与求和¶数列的求和也是一类特殊的差分方程。求数列 \(\{a_n\}\) 的前 \(n\) 项和 \(S_n\),也即相当于求出差分方程 \(S_n = S_{n - 1} + a_n\) 在初值条件 \(S_1 = a_1\) 下的特解。 这是一类最特殊的差分方程。如同我们学习微分方程前会先学习不定积分,学习差分方程之前也应先掌握多种数列求和技巧,然后将差分方程的求解化归到求和。 高中常见的差分方程解法¶这些方法大多数在高中已经涉及,大家可以通过下面的内容进行温习。 如果没见过也没关系,我们会给出尽量详细的推导。 累加法¶累加法就是将差分方程转化为一个数列的求和问题。 累加法主要适用于 \[ a_n = f(n) + a_{n-1} \]型的方程。 累乘法¶和累加法类似,累乘法解决的是 \[ {a_{n+1}} = f(n) a_n \]型的方程,将数列通项转化为\(f(n)\)的前\(n\)项积的计算问题。 转化法¶转化法是将一个数列通过平移、加项等方法,变换成熟悉的数列。 最经典的例子是\(a_n = k a_{n-1} + f(n)\)型的数列(可以称为一阶线性非齐次递推关系式),我们以这个数列举例: Example 已知\(a_n = 2 a_{n-1} + 1, a_1 = 1\),求\(a_n\)的通项。Solution 这道题有多种方法: Method 1 两边加上一个数,尝试将它配凑成等比数列的格式。经过尝试,加上1之后刚好成倍数: \[ a_n + 1 = 2(a_{n+1} + 1). \]于是令\(b_n = a_n + 1\),则数列\(\{ b_n \}\)构成等比数列,于是有 \[ b_n = b_1 2^{n-1} = 2^n. \]这样,就得到了\(a_n = 2^n - 1\)。 Method 2 方程两边除以\(2^n\),得到: \[ \frac{a_n}{2^n} = \frac{a_{n-1}}{2^{n-1}} + \left(\frac{1}{2}\right)^n; \]这样,令\(c_n = a_n / 2^n\),这样\(\{ c_n \}\)就可以用累加法进行计算。 对于二阶线性常系数递推关系式,我们也可以尝试将其转化,降次为一阶的常系数递推(等比数列): Example 设数列\(\{ x_n \}\)满足: \[ x_n = (\alpha + \beta) x_{n-1} - \alpha \beta x_{n-2} \](其中\(\alpha,\beta\)为常数),求数列的通项公式。 Solution我们可以将方程变形为: \[ x_n - \beta x_{n-1} = \alpha (x_{n-1} - \beta x_{n-2}), \]令\(y_n = x_n - \beta x_{n-1}\),则有: \[ y_n = \alpha y_{n-1}, \]这说明\(\{ y_n \}\)是等比数列,得到: \[ y_n = C \alpha^n \](其中\(C\)为任意常数)。这说明: \[ x_n - \beta x_{n-1} = C \alpha^n, \]这是上面提到的一阶线性非齐次递推关系,我们通过两边除以\(\beta^n\)得到: \[ \frac{x_n}{\beta^n} - \frac{x_{n-1}}{\beta^{n-1}} = C \left( \frac{\alpha}{\beta} \right)^n, \]于是,\(\{ x_n/\beta^n \}\)构成一个等比数列,可以得到: \[ \frac{x_n}{\beta^n} = C' \frac{1 - C \left( \frac{\alpha}{\beta} \right)^n}{1 - C \left( \frac{\alpha}{\beta} \right)} \]整理得到: \[ x_n = A \alpha^n + B \beta^n. \]其中\(A, B\)为常数,由初值条件确定。 取倒数法¶这是一种特殊的转化法,通过取倒数转化为已知递推数列。 取对数法¶这也是一种特殊的转化法,通过取对数来转化。 不动点法¶不动点法最常见的应用是针对分式型递推数列,也即形如: \[ x_{n+1} = \frac{A x_n + B}{C x_n + D} \]型的数列。 不动点¶一个函数 \(f(x)\) 的不动点指的是满足 \(f(x) = x\) 的数 \(x\)。对于一阶递推关系 \(x_n = f(x_{n - 1})\),可以定义其不动点为 \(f(x)\) 的不动点。 直观上看,“不动点”就是经过函数 \(f\) 作用之后不改变位置的点,对于数列也就是递推中不变的点。 不动点与数列极限如果 \(f\) 为连续函数,递推关系 \(x_n = f(x_{n - 1})\) 所确定的数列 \(\{ x_n \}\) 收敛,则其极限必定为不动点。 这一性质是显然的,设 \(x\) 为极限值,对 \(x_n = f(x_{n - 1})\) 两边取极限就得到 \(x = f(x)\),因此 \(x\) 是不动点。 利用这一性质,我们可以先用单调有界法、压缩法、Cauchy 收敛原理等方法证明数列收敛,然后再利用不动点求出数列的极限。 不动点法解差分方程¶(待补充) 线性常系数递推·特征方程法¶ 线性常系数递推的概念¶一般地,设\(k\)是一个固定的正整数,那么线性常系数齐次差分方程(Linear homogeneous difference equation with constant coefficients)或线性常系数齐次递推关系(Linear homogeneous recurrence with constant coefficients),指的是满足以下条件的方程: \[ a_n = c_1 a_{n-1} + a_2 a_{n-2} + \cdots + c_k a_{n-k}. \tag{1} \](其中\(c_1, \dots, c_k\)为常数) 这个递推关系中的每一项只与其前\(k\)项有关,我们将\(k\)称为这个递推关系式的阶(degree)。 而如果方程的右边还有一个固定的非零项\(g(n)\),也即: \[ a_n = c_1 a_{n-1} + a_2 a_{n-2} + \cdots + c_k a_{n-k} + g(n); \]则称该方程为线性常系数非齐次差分方程(Linear nonhomogeneous diffence equation with constant coefficients) Notation 这类差分方程的名字中,“线性”指的是两个该形式的递推关系相加,或者与一个数(实数或复数)相乘后,仍然满足该形式;“常系数”指的是\(a_{n-1},\dots,a_{n-k}\)的系数均为常数,而不是某个关于\(n\)的函数;“齐次”指的是方程的右边只包含\(a_{n-1},\dots,a_{n-k}\)这些项的组合,不再包含一个非零项\(g(n)\)。 因此,简单说,可以把\(a_n\)表示为\(a_{n-1}, \dots, a_{n-k}\)的线性组合的递推关系,称为线性常系数齐次递推关系。 方程解法的推导¶我们可以发现,等比数列\(x_n = r^n\)在任取倍数作差之后,仍然为等比数列: \[ x_n - k x_{n-1} = r\cdot r^{n-1} - k r^{n-1} = (r-k) r^{n-1}; \]所以我们可以猜出,等比数列很可能满足这类方程。我们将等比数列\(a_n = r^n\)代入定义式\((1)\)得到: |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |