خوارزمية أبراموف

في الرياضيات، وتحديداً في الجبر الحاسوبي ، تحسب خوارزمية أبراموف جميع الحلول النسبية لمعادلة تكرارية خطية ذات معاملات متعددة الحدود . وقد نشر سيرجي أ. أبراموف هذه الخوارزمية عام 1989. ^{[ 1 ] [ 2 ]}

المفهوم الرئيسي في خوارزمية أبراموف هو المقام العام. ليكن${\textstyle \mathbb {K} }$ليكن حقلاً ذا خاصية صفرية. التشتت${\textstyle \operatorname {dis} (p,q)}$من كثيرتي حدود${\textstyle p,q\in \mathbb {K} [n]}$يُعرَّف بأنه$${\displaystyle \operatorname {dis} (p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\gcd(p(n),q(n+k)))\geq 1\}\cup \{-1\},}$$أين${\textstyle \mathbb {N} }$يرمز إلى مجموعة الأعداد الصحيحة غير السالبة. وبالتالي، يكون التشتت هو الحد الأقصى.${\textstyle k\in \mathbb {N} }$بحيث تكون متعددة الحدود${\textstyle p}$و${\textstyle k}$متعدد الحدود المزاح مرات${\displaystyle q}$يوجد بينهما عامل مشترك. وهو${\textstyle -1}$إذا كان هذا${\textstyle k}$غير موجود. يمكن حساب التشتت على أنه أكبر جذر صحيح غير سالب للناتج${\textstyle \operatorname {res} _{n}(p(n),q(n+k))\in \mathbb {K} [k]}$[ ^{3 ] [ 4 ]} ليكن^​${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$لتكن معادلة تكرارية من الرتبة${\textstyle r}$بمعاملات متعددة الحدود${\displaystyle p_{k}\in \mathbb {K} [n]}$، الطرف الأيمن لكثير الحدود${\textstyle f\in \mathbb {K} [n]}$وحل المتسلسلة المنطقية ${\textstyle y(n)\in \mathbb {K} (n)}$من الممكن كتابة${\textstyle y(n)=p(n)/q(n)}$لكثيرتي حدود أوليتين نسبياً${\textstyle p,q\in \mathbb {K} [n]}$. يترك${\textstyle D=\اسم المشغل {dis} (p_{r}(nr),p_{0}(n))}$و$${\displaystyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(nr)]^{\underline {D+1}})}$$أين${\textstyle [p(n)]^{\underline {k}}=p(n)p(n-1)\cdots p(n-k+1)}$يرمز إلى مضروب الدالة المتناقص . ثم${\textstyle q(n)}$يقسم${\textstyle u(n)}$إذن، متعددة الحدود${\textstyle u(n)}$يمكن استخدامه كمقام لجميع الحلول النسبية${\textstyle y(n)}$ولذا يُطلق عليه اسم المقام العالمي. ^{[ 5 ]}

دع مرة أخرى${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$لتكن معادلة تكرارية بمعاملات متعددة الحدود و${\textstyle u(n)}$مقام عام. بعد التعويض${\textstyle y(n)=z(n)/u(n)}$لكثير الحدود المجهول${\textstyle z(n)\in \mathbb {K} [n]}$والضبط${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}$معادلة التكرار مكافئة لـ$${\displaystyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n).}$$بصفتنا${\textstyle u(n+k)}$هذه معادلة تكرارية خطية ذات معاملات متعددة الحدود، ويمكن حلها لإيجاد حل متعدد الحدود غير معروف.${\textstyle z(n)}$توجد خوارزميات لإيجاد حلول متعددة الحدود . حلول لـ${\textstyle z(n)}$ويمكن بعد ذلك استخدامها مرة أخرى لحساب الحلول النسبية${\textstyle y(n)=z(n)/u(n)}$[ ^{2 ]​}

الخوارزمية rational_solutions هي المدخلات: معادلة تكرارية خطية${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n),p_{k},f\in \mathbb {K} [n],p_{0},p_{r}\neq 0}$الناتج: الحل العقلاني العام${\textstyle y}$إذا كانت هناك أي حلول، وإلا فالإجابة خاطئة. ${\textstyle D=\اسم المشغل {disp} (p_{r}(nr),p_{0}(n))}$${\textstyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})}$${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}$ يحل${\textstyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n)}$لإيجاد الحل العام لكثير الحدود${\textstyle z(n)}$إذا كان الحل${\textstyle z(n)}$إذا وُجد حل عام، فقم بإرجاع الحل العام.${\textstyle y(n)=z(n)/u(n)}$وإلا، فأرجع خطأ .

معادلة التكرار المتجانسة من الرتبة${\textstyle 1}$$${\displaystyle (n-1)\,y(n)+(-n-1)\,y(n+1)=0}$$زيادة${\textstyle \mathbb {Q} }$للمعادلة حل منطقي. ويمكن حسابه من خلال النظر في التشتت.$${\displaystyle D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1.}$$وهذا ينتج عنه المقام العام التالي:$${\displaystyle u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n}$$و$${\displaystyle \ell (n)=\operatorname {lcm} (u(n),u(n+1))=(n-1)n(n+1).}$$بضرب معادلة التكرار الأصلية في${\textstyle \ell (n)}$واستبدال${\textstyle y(n)=z(n)/u(n)}$يؤدي إلى$${\displaystyle (n-1)(n+1)\,z(n)+(-n-1)(n-1)\,z(n+1)=0.}$$لهذه المعادلة حل متعدد الحدود${\textstyle z(n)=c}$لثابت اختياري${\textstyle c\in \mathbb {Q} }$. استخدام${\textstyle y(n)=z(n)/u(n)}$الحل العقلاني العام هو$${\displaystyle y(n)={\frac {c}{(n-1)n}}}$$لأي${\textstyle c\in \mathbb {Q} }$.