シフト作用素さようそと漸化式ぜんかしき

1導入どうにゅう

この講義こうぎでは、差分さぶんdifference、和分わぶんindefinite sum、漸化式ぜんかしきrecurrence relationを、列れつを 1 項こう前進ぜんしんさせるシフト作用素さようそshift operator $E$E によって統一的とういつてきに記述きじゅつする。

差分さぶんはシフト後ごの列れつと元もとの列れつの差さであり、和分わぶんはその逆問題ぎゃくもんだいである。また、定数係数線型漸化式ていすうけいすうせんけいぜんかしきはシフトした列れつの線型結合せんけいけつごうとして表現ひょうげんできる。したがって、中心的ちゅうしんてきな作用素さようそは

である。

この解釈かいしゃくにより、漸化式ぜんかしきは単たんなる項こうの更新規則こうしんきそくではなく、

という線型作用素方程式せんけいさようそほうていしきlinear operator equationになる。

2用語ようごと定義ていぎ

列れつ $a=\left(a_n\right)$a=(a_n) 全体ぜんたいからなる空間くうかんを考かんがえる。必要ひつように応おうじて、両側りょうがわ無限列むげんれつ $(a_n{)}_{n\in \mathbb{Z}}$(a_n)_{n\in\mathbb Z} や片側かたがわ列れつ $(a_n{)}_{n\text{[PARSE ERROR: Undefined("Command("ge")")]}0}$(a_n)_{n\ge0} を使つかう。ここでは、添字そえじが定義ていぎできる範囲はんいで議論ぎろんする。

シフト作用素さようそshift operator $E$E を

で定義ていぎする。

恒等作用素こうとうさようそidentity operator $I$I は

である。

前進差分ぜんしんさぶんforward difference $\mathrm{\Delta }$\Delta は

である。したがって

である。

この規約きやくは Z 変換へんかんの講義こうぎと一致いっちし、両側りょうがわ Z 変換へんかんでは $E$E が $z$z による乗算じょうざんへ対応たいおうする。

3方針ほうしん

この講義こうぎでは、次つぎの順じゅんに確認かくにんする。

1. $E$E が線型作用素せんけいさようそlinear operatorであることを証明しょうめいする。
2. $\mathrm{\Delta }=E-I$\Delta=E-I から差分さぶん公式こうしきを導みちびく。
3. $\mathrm{\Delta }F=f$\Delta F=f を和分わぶん、すなわち差分さぶんの逆問題ぎゃくもんだいとして定式化ていしきかする。
4. 定数ていすう係数けいすう線型せんけい漸化式ぜんかしきを $P\left(E\right)a=b$P(E)a=b と書かく。
5. $r^n$r^n が $E$E の固有列こゆうれつeigen-sequenceであることから、特性とくせい方程式ほうていしきを導みちびく。

この順序じゅんじょにより、各手法かくしゅほうの採用理由さいようりゆうを作用素さようその構造こうぞうから説明せつめいできる。

個別こべつの入試にゅうし型かたや、固定点こていてん・階差かいさ・和わの消去しょうきょ・連立れんりつ化か・帰納法きのうほうへの使つかい分わけは、次つぎの講義こうぎで整理せいりする。

4命題めいだい 1：$E$E は線型作用素せんけいさようそlinear operatorである

4.1主張しゅちょう

列れつ空間上くうかんじょうの $E$E は線型作用素せんけいさようそlinear operatorである。

4.2証明しょうめい

列れつ $a,b$a,b とスカラー $\alpha ,\beta$\alpha,\beta を任意にんいに取とる。このとき

である。これはすべての $n$n で成立せいりつするので

である。したがって $E$E は線型せんけいである。

5差分さぶんは $E-I$E-I である

前進ぜんしん差分さぶんは

である。一方いっぽう、

である。したがって

である。

ここから、$\mathrm{\Delta }$\Delta の線型性せんけいせいlinearityも直ただちに従したがう。$E$E と $I$I が線型せんけいであるため、その差さ $E-I$E-I も線型せんけいである。実際じっさい、

である。

6二項定理にこうていりによる高階差分こうかいさぶん

$\mathrm{\Delta }=E-I$\Delta=E-I であり、$E$E と $I$I は可換かかんである。したがって

に二項定理にこうていりbinomial theoremを適用てきようできる。

である。列れつ $a$a に作用さようさせると

を得える。

この公式こうしきの符号ふごうと添字そえじは、$(E-I{)}^m$(E-I)^m の二項展開にこうてんかいによって決定けっていされる。

7和分わぶんは差分さぶんの逆問題ぎゃくもんだいである

不定和分ふていわぶんindefinite sumの基本きほん問題もんだいは

を満みたす列れつ $F$F を決定けっていすることである。これは

を意味いみする。

$n=a,a+1,\dots ,b-1$n=a,a+1,\ldots,b-1 について両辺りょうへんを加算かさんすると

である。右辺うへんは望遠和ぼうえんわtelescoping sumなので

を得える。

これは連続れんぞくの微積分びせきぶんで

となることの離散りさん版はんである。つまり、和わ分ふんとは $\mathrm{\Delta }$\Delta の逆問題ぎゃくもんだいである。

8積せきの差分さぶんにおけるシフト項こう

連続れんぞく微分びぶんでは積つの微分びぶんが

となる。しかし差分さぶんでは、ずれが残のこる。

実際じっさい、

である。したがって

である。

右辺うへんの $\left(Ev\right)$(Ev) は、前進差分ぜんしんさぶんが 1 項先こうさきの値あたいを含ふくむことを表あらわす。離散計算りさんけいさんでは、このシフトを省略しょうりゃくして連続微分れんぞくびぶんの公式こうしきを適用てきようしてはならない。

9部分和公式ぶぶんわこうしきは離散版りさんばんの部分積分ぶぶんせきぶん

積つの差分さぶん公式こうしき

を変形へんけいすると

である。両辺りょうへんを和わ分ふんすると

という形式けいしきを得える。有限範囲ゆうげんはんいでは

が成立せいりつする。これは連続れんぞくの部分積分ぶぶんせきぶん

の離散りさん版はんである。

ただし、右辺うへんに $v$v ではなく $Ev$Ev が現あらわれる。この一項いっこうの偏移へんいが、差分法さぶんほうでシフト作用素さようそshift operatorを明示めいじする理由りゆうである。

10漸化式ぜんかしきは $P\left(E\right)a=b$P(E)a=b である

定数ていすう係数けいすう線型せんけい漸化式ぜんかしき

を考かんがえる。左辺さへんへ集あつめると

である。$E$E を用もちいると

と書かける。

つまり

である。ただし

である。

この段階だんかいで、漸化式ぜんかしきは一般いっぱんの線型作用素方程式せんけいさようそほうていしきlinear operator equationになっている。したがって

であり、特解とくかい $a_p$a_p が 1 つ存在そんざいすれば

である。

11固有列こゆうれつと特性方程式とくせいほうていしき

両側列りょうがわれつでは $r\ne 0$r\ne0 とし、片側列かたがわれつでは $n\text{[PARSE ERROR: Undefined("Command("ge")")]}0$n\ge0 で $r^n$r^n を定義ていぎする。この幾何列きかれつに対たいして

である。つまり $r^n$r^n は $E$E の固有列こゆうれつeigen-sequenceであり、固有値こゆうちは $r$r である。

したがって

である。よって同次どうじ方程式ほうていしき

に $a_n=r^n$a_n=r^n が解かいとなる条件じょうけんは

である。これが特性方程式とくせいほうていしきcharacteristic equationである。

特性とくせい方程式ほうていしきは、$r^n$r^n が $E$E の固有こゆう列れつであるために現あらわれる。したがって、定数ていすう係数けいすう線型せんけい漸化式ぜんかしきの特性とくせい方程式ほうていしき法ほうは、固有値問題こゆうちもんだいeigenvalue problemの離散りさん版はんである。

12例れい：Fibonacci 型かた漸化式ぜんかしき

漸化式ぜんかしき

は

である。したがって

であり、特性とくせい方程式ほうていしきは

である。根こんは

である。$r_{1^n}$r_1^n と $r_{2^n}$r_2^n はそれぞれ $\ker P\left(E\right)$\ker P(E) に属ぞくする。異ことなる根こんに対応たいおうする 2 列れつは線型独立せんけいどくりつである。また、この二階漸化式にかいぜんかしきの解かいは $f_0,f_1$f_0,f_1 によって一意いちいに決定けっていされるため、解空間かいくうかんは 2 次元じげんである。したがって、これらは解空間かいくうかんの基底きていをなし、一般解いっぱんかいは

を得える。定数ていすう $C_1,C_2$C_1,C_2 は初期条件しょきじょうけんで決きまる。

ここで重要じゅうようなのは、$r^n$r^n を試ためす理由りゆうである。$r^n$r^n は $E$E の固有こゆう列れつであり、$P\left(E\right)$P(E) が $P\left(r\right)$P(r) に落おちるからである。

13定数係数ていすうけいすうと非定数係数ひていすうけいすうの違ちがい

定数ていすう係数けいすうなら、漸化式ぜんかしきは $P\left(E\right)$P(E) の形かたちで書かける。係数けいすうが定数ていすうであるため、$E$E と係数けいすうが可換かかんであり、多項式たこうしきとして扱あつかえる。

しかし係数けいすうが $n$n に依存いぞんすると状況じょうきょうが変かわる。たとえば

を考かんがえる。$M$M を

で定義ていぎされる掛け算作用素ざんさようそmultiplication operatorとすると、この方程式ほうていしきは

の形かたちで書かける。しかし一般いっぱんに

である。実際じっさい、

だが

である。

したがって、非定数係数ひていすうけいすうでは通常つうじょうの多項式たこうしき $P\left(E\right)$P(E) として表現ひょうげんできず、特性方程式法とくせいほうていしきほうは一般いっぱんには成立せいりつしない。定数係数ていすうけいすうという仮定かていは、作用素さようその可換性かかんせいを保証ほしょうする本質的条件ほんしつてきじょうけんである。

14Newton の前進公式ぜんしんこうしき（$n\text{[PARSE ERROR: Undefined("Command("ge")")]}0$n\ge0）

$\mathrm{\Delta }=E-I$\Delta=E-I なので

である。したがって

である。$I$I と $\mathrm{\Delta }$\Delta は可換かかんなので、二項定理にこうていりより

である。

両辺りょうへんを列れつ $f$f の $0$0 番目ばんめに作用さようさせると

を得える。これは初期値しょきちと初期しょき差分さぶんから列れつを復元ふくげんする公式こうしきである。

15成立範囲せいりつはんい

この講義こうぎの $P\left(E\right)$P(E) 表示ひょうじは、主おもに定数係数ていすうけいすうの線型漸化式せんけいぜんかしきに対たいして有効ゆうこうである。非線型漸化式ひせんけいぜんかしきには線型作用素方程式せんけいさようそほうていしきの構造こうぞうがない。非定数係数ひていすうけいすうの線型漸化式せんけいぜんかしきでは、係数作用素けいすうさようそとシフト作用素さようそが一般いっぱんに可換かかんでないため、通常つうじょうの特性方程式法とくせいほうていしきほうは適用てきようできない。

また、片側列かたがわれつでは $E^{-1}$E^{-1} が常つねに自然しぜんに定義ていぎできるとは限かぎらない。後退差分こうたいさぶんや両側りょうがわシフトを扱あつかうときは、列空間れつくうかんをどの添字集合そえじしゅうごう上じょうに置おくかを明示めいじする必要ひつようがある。

16主要公式しゅようこうしき

17要約ようやく

漸化式ぜんかしきrecurrence relationは、シフト作用素さようそshift operator $E$E による線型作用素方程式せんけいさようそほうていしきlinear operator equationであり、特性とくせい方程式ほうていしきは $E$E の固有こゆう列れつ $r^n$r^n から生しょうじる。

18関連かんれんリンク

Shift Operators and Recurrence Relations

1Introduction

This lecture unifies differences, indefinite sums, and recurrences through the forward shift operator

A constant-coefficient linear recurrence then becomes the linear operator equation $P\left(E\right)a=b$P(E)a=b.

2Terminology and Definitions

Work with bilateral sequences indexed by $\mathbb{Z}$\mathbb Z or unilateral sequences indexed by $n\text{[PARSE ERROR: Undefined("Command("ge")")]}0$n\ge0, as specified. Define

and the forward difference

This convention agrees with the Z-transform lecture: the bilateral transform maps $E$E to multiplication by $z$z.

3Program

The development proceeds by proving linearity of $E$E, deriving difference identities from $\mathrm{\Delta }=E-I$\Delta=E-I, treating $\mathrm{\Delta }F=f$\Delta F=f as an inverse problem, expressing recurrences as $P\left(E\right)a=b$P(E)a=b, and deriving the characteristic equation from the eigen-sequence $r^n$r^n.

4Proposition 1: $E$E Is a Linear Operator

4.1Statement

The shift $E$E is linear on the sequence space.

4.2Proof

For sequences $a,b$a,b and scalars $\alpha ,\beta$\alpha,\beta,

The identity holds for every admissible $n$n, hence $E(\alpha a+\beta b)=\alpha Ea+\beta Eb$E(\alpha a+\beta b)=\alpha Ea+\beta Eb. $\mathrm{\square }$\square

5The Difference Is $E-I$E-I

Since

$\mathrm{\Delta }=E-I$\Delta=E-I. Therefore $\mathrm{\Delta }$\Delta is linear as the difference of linear operators:

6Higher Differences from the Binomial Theorem

Because $E$E and $I$I commute,

Consequently,

Thus the signs and indices follow directly from the operator binomial expansion.

7Indefinite Summation as the Inverse Difference Problem

An indefinite sum seeks $F$F satisfying $\mathrm{\Delta }F=f$\Delta F=f, or $F(n+1)-F\left(n\right)=f\left(n\right)$F(n+1)-F(n)=f(n). Summing from $n=a$n=a to $b-1$b-1 telescopes:

This is the discrete counterpart of ${\int }_a^b{F}^{\prime }\left(x\right)dx=F\left(b\right)-F\left(a\right)$\int_a^bF'(x)\,dx=F(b)-F(a).

8The Shift Term in a Product Difference

Direct calculation gives

so

The shift $Ev$Ev cannot be omitted by copying the continuous product rule.

9Summation by Parts Is Discrete Integration by Parts

Rearranging the product rule gives $u\mathrm{\Delta }v=\mathrm{\Delta }\left(uv\right)-\left(Ev\right)\mathrm{\Delta }u$u\Delta v=\Delta(uv)-(Ev)\Delta u. Indefinite summation yields

the discrete counterpart of $\int udv=uv-\int vdu$\int u\,dv=uv-\int v\,du. The one-step shift explains why the shift operator must remain explicit.

On a finite range, the precise boundary formula is

10A Recurrence Is $P\left(E\right)a=b$P(E)a=b

For

define $P\left(t\right)=t^k-c_1{t}^{k-1}-\cdots -c_k$P(t)=t^k-c_1t^{k-1}-\cdots-c_k. Then

The operator equation is solvable exactly when $b\in \mathrm{Im}P\left(E\right)$b\in\operatorname{Im}P(E). If $a_p$a_p is one solution, every solution is

11Eigen-Sequences and the Characteristic Equation

For bilateral sequences assume $r\ne 0$r\ne0; for unilateral sequences define $r^n$r^n on $n\text{[PARSE ERROR: Undefined("Command("ge")")]}0$n\ge0. The geometric sequence satisfies

so it is an eigen-sequence of $E$E with eigenvalue $r$r. Hence

It solves $P\left(E\right)a=0$P(E)a=0 precisely when $P\left(r\right)=0$P(r)=0. The characteristic-equation method is therefore the discrete eigenvalue method for constant-coefficient linear recurrences.

12Example: A Fibonacci-Type Recurrence

The recurrence $f_{n+2}=f_{n+1}+f_n$f_{n+2}=f_{n+1}+f_n is

Its characteristic polynomial is $P\left(t\right)=t^2-t-1$P(t)=t^2-t-1, with roots

The sequences $r_{1^n}$r_1^n and $r_{2^n}$r_2^n are linearly independent. Moreover, a solution of this second-order recurrence is uniquely determined by the two initial values $f_0,f_1$f_0,f_1, so its solution space is two-dimensional. Hence these sequences form a basis and

and initial conditions determine $C_1,C_2$C_1,C_2. The geometric trial sequences are justified because they are eigen-sequences of $E$E.

13Constant and Nonconstant Coefficients

Constant coefficients commute with $E$E, allowing the polynomial $P\left(E\right)$P(E). For the variable-coefficient recurrence $a_{n+1}-n{a}_n=0$a_{n+1}-na_n=0, define $(Ma{)}_n=n{a}_n$(Ma)_n=na_n. The equation is $(E-M)a=0$(E-M)a=0, but

so $EM\ne ME$EM\ne ME. Thus the ordinary polynomial calculus and simple characteristic equation generally fail for nonconstant coefficients. Constancy is an essential commutativity hypothesis.

14Newton's Forward Formula ($n\text{[PARSE ERROR: Undefined("Command("ge")")]}0$n\ge0)

Since $E=I+\mathrm{\Delta }$E=I+\Delta and the operators commute,

Applying both sides to the zeroth entry of $f$f gives

which reconstructs a sequence from its initial forward differences.

15Scope

The representation $P\left(E\right)a=b$P(E)a=b applies primarily to constant-coefficient linear recurrences. Nonlinear recurrences lack this linear operator structure; variable coefficients generally do not commute with $E$E, so the usual characteristic method is unavailable.

On unilateral sequence spaces, $E^{-1}$E^{-1} need not have a natural definition. Any use of backward differences or bilateral shifts must specify the index set of the sequence space.

16Canonical Formulas

17Summary

A recurrence relation is a linear operator equation in the shift $E$E when it is linear with constant coefficients. Its characteristic equation arises from the eigen-sequences $r^n$r^n of $E$E.

18Related Lectures