Линейные рекуррентные уравнения однородные и неоднородные с постоянными коэффициентами


Определение: Уравнение L(x(k)) = x(k+n) + a1(k)x(k+n+1) + … + an(k)x(k) = {0, F(k)}, причём
0 – (R0) однородное уравнение.
F(k) – R1 неоднородное уравнение.
где ai(k) – функция в N→R, i = 1…n и F(k)≠0 (тривиально) – неизвестная функция, x(k) – неизвестная функция называются линейными рекуррентными уравнениями (ЛРУ) однородными и неоднородными соответственно с постоянными коэффициентами.

Замечание: Такие уравнения R0 и R1 называют стационарными ЛРУ или СЛРУ однородными и неоднородными соответственно.

Определение: Выражение L(y) = λn + a1λn-1 + … + an-1λ + an есть характеристический компонент для однородного СЛРУ R0 (Равно как и для неоднородного СЛРУ R1).

Теорема: Если:
λ1, … , λp – вещественные кокни характеристического уравнения
l1, … , lp – их кратности
μ1, … , μs – группа комплексных корней
μj = αjj, j=1, … ,s
μ1*, … , μs* — группа комплексно сопряженных корней.

μj = αj — iβj, j = 1, …, s

r1, …, rs – их кратность
pjφj — модуль и аргумент для комплексного числа μj, то функции:
xj(k) = kmjj)k , j=1,…,p; mj=0,…,lj-1
yj = kmjj)kcos(φjk), j=1,…,sj; mj=0,…,rj-1
zj = kmjj)ksin(φjk), j=1,…,sj; mj=0,…,rj-1
составляют решение для однородной СЛРУ(r0).

Замечание:. Если x1(k),…, xn(k) есть ФСР для однородного СРЛУ (r0), то его общее решение xoo(k)=C1x1(k)+…+ Cnxn(k), где произвольные постоянные пробегают множество вещественных чисел R – независимо друг от друга.

Если xчн есть какое либо частное неоднородное решение СЛРУ(r1), то если xон=xчн+ xoo(k)=C1x1(k)+…+ Cnxn(k)

Нахождение частного решения часто бывает непростой задачей, но для некоторых специальных правых частей R1, такое решение может быть найдено, например, если правая часть R1 есть квазиполином.
f(k)=Pm(k), то функция xчн может быть найдена в виде xчн=krQm(k)λk,где r есть кратность корня характеристического уравнения, а Qm(k) – есть полином степени m, неизвестные коэффициенты которого: a0,a1,…,am – подлежат определению.

Замечание: СЛРУ, определена на элементах групп, широко используемых в криптографии.


Комментарии запрещены.




Статистика