WikiDer > Абрамовтар алгоритмі - Википедия

Abramovs algorithm - Wikipedia

Математикада, атап айтқанда компьютер алгебрасы, Абрамовтың алгоритмі бәрін есептейді рационалды а шешімдері полиномдық коэффициенттермен сызықтық қайталану теңдеуі. Алгоритмді 1989 жылы Сергей Абрамов жариялады.^[1]^[2]

Әмбебап бөлгіш

Абрамовтың алгоритміндегі негізгі түсінік - әмбебап бөлгіш. Келіңіздер ${ textstyle mathbb {K}}$ болуы а өріс туралы сипаттамалық нөл. The дисперсия ${ 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 } кубок {- 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} (n-r), p_ {0} (n))}

және

{ displaystyle u (n) = gcd ([p_ {0} (n + D)] ^ { асты {D + 1}}, [p_ {r} (nr)] ^ { асты {D + 1) }})}

қайда

{ textstyle [p (n)] ^ { астын сызу {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) n) ell (n).}

Ретінде

{ textstyle u (n + k)}

жою - бұл белгісіз көпмүшелік шешім үшін шешуге болатын көпмүшелік коэффициенттері бар сызықтық қайталану теңдеуі

{ textstyle z (n)}

. Сонда полиномдық шешімдерді табудың алгоритмдері. Шешімдері

{ textstyle z (n)}

рационалды шешімдерді есептеу үшін қайтадан қолдануға болады

{ textstyle y (n) = z (n) / u (n)}

. ^[2]

алгоритм рационалды_шешімдер болып табылады    енгізу: Сызықтық қайталану теңдеуі  ${ 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} (n-r), p_ {0} (n))}$      ${ textstyle u (n) = gcd ([p_ {0} (n + D)] ^ { асты {D + 1}}, [p_ {r} (nr)] ^ { асты {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)] ^ { асты сызылған {2}}, [p_ {r} (n-1)] ^ { асты сызылған {2}} ) = (n-1) n}

және

{ displaystyle ell (n) = оператордың аты {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}}

.

Әдебиеттер тізімі

^ Абрамов, Сергей А. (1989). «Полиномдық коэффициенттері бар сызықтық дифференциалдық және айырымдық теңдеулердің рационалды шешімдері». КСРО есептеу математикасы және математикалық физика. 29 (6): 7–12. дои:10.1016 / s0041-5553 (89) 80002-3. ISSN 0041-5553.
^ ^а ^б Абрамов, Сергей А. (1995). Полиномдық коэффициенттері бар сызықтық айырмашылық пен q-айырымдық теңдеулердің ұтымды шешімдері. ISSAC '95 1995 жылғы символдық және алгебралық есептеу бойынша халықаралық симпозиум материалдары. 285–289 бб. дои:10.1145/220346.220383. ISBN 978-0897916998.
^ Адам, Иу-Квонг; Райт, Фрэнсис Дж. (1994). Жылдам полиномдық дисперсияны есептеу және оны шексіз қосындыға қолдану. ISSAC '94 Халықаралық символикалық және алгебралық есептеу симпозиумының жинағы. 175-180 бет. дои:10.1145/190347.190413. ISBN 978-0897916387.
^ Герхард, Юрген (2005). Символдық жиынтықтағы және символдық интегралдағы модульдік алгоритмдер. Информатика пәнінен дәрістер. 3218. дои:10.1007 / b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743.
^ Чен, Уильям Ю. С .; Паул, Питер; Саад, Хусам Л. (2007). «Госпер алгоритміне көшу». arXiv:0711.3386 [математика].

Математика WikiProject Wikidata-да

[1] Абрамов, Сергей А. (1989). «Полиномдық коэффициенттері бар сызықтық дифференциалдық және айырымдық теңдеулердің рационалды шешімдері». КСРО есептеу математикасы және математикалық физика. 29 (6): 7–12. дои:10.1016 / s0041-5553 (89) 80002-3. ISSN 0041-5553.

[Abramov_1995-2] а ^б Абрамов, Сергей А. (1995). Полиномдық коэффициенттері бар сызықтық айырмашылық пен q-айырымдық теңдеулердің ұтымды шешімдері. ISSAC '95 1995 жылғы символдық және алгебралық есептеу бойынша халықаралық симпозиум материалдары. 285–289 бб. дои:10.1145/220346.220383. ISBN 978-0897916998.

[3] Адам, Иу-Квонг; Райт, Фрэнсис Дж. (1994). Жылдам полиномдық дисперсияны есептеу және оны шексіз қосындыға қолдану. ISSAC '94 Халықаралық символикалық және алгебралық есептеу симпозиумының жинағы. 175-180 бет. дои:10.1145/190347.190413. ISBN 978-0897916387.

[4] Герхард, Юрген (2005). Символдық жиынтықтағы және символдық интегралдағы модульдік алгоритмдер. Информатика пәнінен дәрістер. 3218. дои:10.1007 / b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743.

[5] Чен, Уильям Ю. С .; Паул, Питер; Саад, Хусам Л. (2007). «Госпер алгоритміне көшу». arXiv:0711.3386 [математика].

[1]

[2]

[3]

[4]

[5]

Navigation

Navigation

Themenportale

WikiDer > Абрамовтар алгоритмі - Википедия

Мазмұны

Әмбебап бөлгіш

Алгоритм

Мысал

Әдебиеттер тізімі