حلقه چندجملهای: تفاوت میان نسخهها
بدون خلاصۀ ویرایش برچسب: افزودن تگهای خالی |
بدون خلاصۀ ویرایش |
||
خط ۳۷: | خط ۳۷: | ||
:<math>s_i = p_0 q_i + p_1 q_{i-1} + \cdots + p_i q_0.</math> |
:<math>s_i = p_0 q_i + p_1 q_{i-1} + \cdots + p_i q_0.</math> |
||
در فرمول های فوق، می توان با افزودن "جملات ساختگی" با ضرایب صفر، چندجمله ای های <math>p</math> و <math>q</math> را توسعه داد به گونه ای که <math>p_i</math> و <math>q_i</math> های ظاهر شده در این عبارت تعریف شده باشند. بخصوص وقتی که <math>m<n</math> باشد برای هر <math>i</math> که <math>m<i\leq n</math> خواهیم داشت <math>p_i=0</math>. ضرب اسکالر حالت خاصی از همان ضرب عمومی است که در آن <math>p=p_0</math> به ''جمله ثابت'' (جمله ای که مستقل از <math>X</math> است) کاهش یافته است؛ یعنی: |
|||
== ضرب چندجملهای با استفاده از تبدیل فوریه == |
|||
=== تعریف فرم فوریه === |
|||
برای نمایش [[توابع|تابع]] راههای گوناگونی وجود دارد، بهطور مثال میتوان یک تابع را با مجموعه اعضا (برای توابع با دامنهٔ محدود)، ضابطهٔ کلی تابع، یک سری مانند [[بسط تیلور]] یا بسط فوریه و ... نمایش داد. |
|||
یک فرم که در انجام محاسبات بسیار کاراست، را در این جا توضیح می دهیم. می دانیم که در صفحه میتوان هرچندجملهای از درجه n را با دقیقاً n+1 نقطه از آن بهطور یکتا مشخص کرد. مثلاً هر خط راست را میتوان با دو نقطه از آن بهطور یکتا مشخص کرد و برعکس. یا این که هر سه نقطه یک [[سهمی]] را بهطور یکتا تعیین میکنند. پس یک روش نمایش چندجمله ایهای درجه n، نگهداری n+1 نقطهٔ آن است. دقت کنید که این نقاط به دلخواه از دامنهٔ [[تابع انتخاب]] میشوند. بهطور دقیق تر: |
|||
{{سخ}} |
|||
<center> |
|||
<math> |
|||
FFT\left ( P_n \right ) = \left \{ \left ( x_i, P_n\left ( x_i \right ) \right ) | x_i \in \mathbb{C} , \forall i\neq j : x_i\neq x_j \right \} |
|||
</math> |
|||
</center> |
|||
:<math>p_0\left(q_0 + q_1 X + \dots + q_n X^n\right) = p_0 q_0 + \left(p_0 q_1\right)X + \cdots + \left(p_0 q_n\right)X^n</math> |
|||
=== ویژگیهای فرم فوریه === |
|||
نکتهٔ جالب در مورد فرم فوریه برای نمایش چندجملهای ها، سادگی انجام برخی محاسبات روی آن است. بهطور مثال اگر بخواهیم دو چندجملهای را جمع/ضرب کنیم، کافی است آن دو را با یک سری مقادیر x یکسان به فرم فوریه تبدیل کنیم و سپس مقادیر متناظر هر نقطه از آن دو تابع را با هم جمع/ضرب کنیم. دیده میشود که در این فرم اعمالی مانند ضرب یا تقسیم بسیار آسان تر از صورت ضابطهای قابل انجاماند. در حقیقت جمع و تفریق و ضرب و تقسیم چندجملههای به این فرم با <math>\Theta \left (n \right )</math> امکانپذیر است. در ادامه به بررسی جزییات پیادهسازی ضرب چندجمله ایها می پردازیم. |
|||
می توان به راحتی بررسی کرد که سه عملیات بالا در اصول موضوعه جبر جابجایی روی میدان <math>K</math> صدق می کنند. ازینرو، به حلقه های چند جمله ای، ''جبرهای چندجمله ای'' نیز گفته می شود. |
|||
=== ضرب چندجملهای با تبدیل سریع فوریه === |
|||
می توان دید که اگر دو چندجملهای داشته باشیم میتوان ابتدا آنها را در تعدادی نقطهٔ مشترک مقداریابی کرد و پس از آن فرم فوریهٔ ضرب آنها را از ضرب مؤلفههای دوم زوج مرتبهای بدست آمده پیدا کرد. باید توجه کرد که حاصل ضرب، یعنی <math>P \cdot Q</math> دارای درجهای برابر <math>m+n</math> است پس باید برای نمایش آن به تعداد <math>m+n+1</math> [[زوج مرتب]] از آن را داشته باشیم، به همین منظور میتوان از ابتدا هر دو چندجملهای را به فرم فوریهٔ گسترش یافته با <math>m+n+1</math> نقطه تبدیل کرد، و سپس این نقاط را [[نظیر به نظیر]] ضرب کرد و حاصل ضرب را در فرم فوریه بدست آورد. برای یافتن جواب کافی است آن را از فرم فوریه به فرم ضابطهای تبدیل کنیم. |
|||
اغلب تعریف معادل دیگری که شهود کمتری دارد ترجیه داده می شود، چون راحت تر میشود آن را ساخت. به این صورت که چند جمله ای ها به صورت دنباله بی نهایت <math>(a_0, a_1, a_2, \cdots)</math> از عناصر <math>K</math> دیده می شوند که تنها تعداد متناهی از آن ها ناصفرند، یه با طور معادل، دنباله ای که از جایی به بعد اعضای آن صفر هستند. در این حالت، <math>a_0</math> و <math>X</math> را به ترتیب به عنوان نمادهای جایگزین برای دنباله های <math>(a_0, 0, \cdots)</math> و <math>(0, 1, 0, \cdots)</math> در نظر می گیرند. آنگاه با کمی دقت می توان فهمید که با این تعریف یک چندجمله ای چون: |
|||
برای این که بتوانیم این فرایند را در زمانی سریع تر زمان الگوریتم بدیهی ضرب انجام دهیم از [[تبدیل فوریه گسسته]] استفاده می کنیم. در این الگوریتم با انتخاب ریشههای n ام واحد (که مختلط هستند) و محاسبهٔ مقدار چندجملهای در این نقاط چندجملهای را به فرم فوریه تبدیل می کنیم. این کار را برای هر دو چندجملهای عمولوند ضرب انجام می دهیم. میتوان طوری الگوریتم را نوشت که این کار را به سرعت بتوان انجام داد. س÷س دو چندجملهای را که اکنون در فرم فوریه هستند به راحتی در هم ضرب می کنیم و در ÷ایان دوباره حاصل ضرب را از فرم فوریه به فرم ضابطهای متداول تبدیل می کنیم. این فرایند بهطور طرح وار در شکل زیر آمدهاست:{{سخ}}<center> |
|||
[[پرونده:FFT_Multiply.gif]] |
|||
<math>a_0 + a_1X + a_2X^2 + \cdots + a_mX^m</math> |
|||
</center>{{سخ}} |
|||
برای توضیحات دقیق تر و نحوهٔ انجام هر یک از مرحلههای گفته شده به [[تبدیل فوریه گسسته]] رجوع کنید. |
|||
را می توان به این صورت نمایش داد: |
|||
<math>(a_0, a_1, a_2, \cdots, p_m, 0, 0, \cdots)</math> |
|||
===واژه شناسی=== |
|||
فرض کنید: |
|||
:<math>p = p_0 + p_1 X + p_2 X^2 + \cdots + p_{m - 1} X^{m - 1} + p_m X^m,</math> |
|||
یک چندجمله ای ناصفر باشد که در آن <math>p_m\neq 0</math> |
|||
<math>p_0</math> ''جمله ثابت'' چندجمله ای <math>p</math> است. در چند جمله ای های صفر این ثابت صفر است (البته ممکن است در حالت های دیگر هم صفر باشد). |
|||
''درجه'' ی <math>p</math> که به صورت <math>\deg(p)</math> نوشته می شود <math>m</math> است. این مقدار برابر بزرگترین <math>k</math> یی است که ضریب <math>X^k</math> صفر نباشد.<ref>Herstein p. 154</ref> |
|||
''ضریب پیشرو'' ی <math>p</math>، برابر <math>p_m</math> است.<ref>Lang p.100</ref> |
|||
در حالت خاص چندجمله ای های صفر که تمام ضرایب آن صفر است، چندجمله ای پیشرو تعریف نشده و درجه را اغلب تعریف نشده<ref>{{citation|title=Calculus Single Variable|first1=Howard|last1=Anton|first2=Irl C.|last2=Bivens|first3=Stephen|last3=Davis|publisher=John Wiley & Sons|year=2012|isbn=9780470647707|page=31|url=https://books.google.com/books?id=U2uv84cpJHQC&pg=RA1-PA31}}.</ref>، برابر -1<ref>{{citation|title=Rational Algebraic Curves: A Computer Algebra Approach|volume=22|series=Algorithms and Computation in Mathematics|first1=J. Rafael|last1=Sendra|first2=Franz|last2=Winkler|first3=Sonia|last3=Pérez-Diaz|publisher=Springer|year=2007|isbn=9783540737247|page=250|url=https://books.google.com/books?id=puWxs7KG2D0C&pg=PA250}}.</ref> یا برابر <math>-\inf</math><ref>{{citation|title=Elementary Matrix Theory|publisher=Dover|first=Howard Whitley|last=Eves|author-link=Howard Eves|year=1980|isbn=9780486150277|page=183|url=https://books.google.com/books?id=ayVxeUNbZRAC&pg=PA183}}.</ref> تعریف می کنند. |
|||
یک ''چندجمله ای ثابت''، یا چندجمله ای صفر است، یا چندجمله ای از درجه صفر. |
|||
یک چندجمله ای صفر تکین است اگر ضریب پیشروی آن 1 باشد. |
|||
اگر دو چندجمله ای <math>p</math> و <math>q</math> داده شده باشند خواهیم داشت: |
|||
<math>\deg(p+q)\leq max(\deg(p), \deg(q)),</math> |
|||
و بر روی یک میدان یا به طور کلی تر یک حوزه صحیح داریم<ref>Herstein p.155, 162</ref>: |
|||
<math>\deg(pq) = \deg(p) + \deg(q).</math> |
|||
سریعاً نتیجه می شود که اگر <math>K</math> یک حوزه صحیح باشد آنگاه <math>K[X]</math> نیز حوزه صحیح است.<ref>Herstein p.162</ref> |
|||
در نتیجه اگر <math>K</math> یک حوزه صحیح باشد، یک چندجمله ای دارای معکوس ضربی است اگر و تنها اگر ثابت باشند، و آن ثابت در <math>K</math> معکوس ضربی داشته باشد. |
|||
دو چندجمله ای با هم مرتبط {{به انگلیسی|Associated}} هستند اگر برای هرکدام از آن ها یک عضو معکوس پذیر {{به انگلیسی|Unit}} وجود داشته باشد که با ضرب در آن به دیگری تبدیل شود. |
|||
هر چندجمله ای ناصفر بر روی یک میدان مرتبط با یک چندجمله ای منحصر به فرد است. |
|||
اگر دو چندجمله <math>p</math> و <math>q</math> داده شده باشد، می گویند <math>p</math> مقسوم علیه <math>q</math> است، یا <math>p</math> چندجمله ای <math>q</math> را تقسیم می کند یا <math>q</math> ضریبی از <math>p</math> است اگر چندجمله ای <math>r</math> وجود داشته باشد به گونه ای که <math>q=pr</math>. |
|||
یک چندجمله ای تحویل ناپذیر است اگر نتوان آن را به صورت ضرب دو چندجمله ای غیرثابت نوشت، یا به طور معادل، اگر مقسوم علیه های آن یا چندجمله ای های ثابت باشند یا درجه برابر با چندجمله ای اصلی داشته باشند. |
|||
== ضرب چندجمله ایهای تنک == |
== ضرب چندجمله ایهای تنک == |
نسخهٔ ۱۶ ژانویهٔ ۲۰۲۱، ساعت ۰۷:۱۹
در ریاضیات، بخصوص در شاخه جبر، یک حلقه چند جمله ای یا جبر حلقه ای، حلقه ایست (که همزمان یک جبر جابجایی هم می باشد) که توسط مجموعه ای از چند جمله ای های یک متغیره یا چند متغیره تشکیل شده که ضرایبشان در حلقه ای دیگر قرار دارد. حلقه ضرایب چند جمله ای معمولاً یک میدان است.
حلقه چند جمله ای ها در شاخه های مختلفی از ریاضیات ظهور پیدا می کنند، همچون نظریه اعداد، جبر جابجایی، نظریه حلقه ها و هندسه جبری. دسته جات مختلفی از حلقه ها چون دامنه تجزیه یکتا، حلقه های منظم، حلقه های گروهی، حلقه های سری های توانی سوری، چند جمله ای های Ore و حلقه های مدرج را برای تعمیم برخی از خواص حلقه ها معرفی کرده اند.
حلقه توابع چند جمله ای روی یک فضای برداری، و به طور کلی تر حلقه توابع منظم روی یک واریته جبری، با حلقه چند جمله ای ها ارتباط نزدیکی دارند.
تعریف (حالت تک متغیره)
حلقه چند جمله ای ، بر حسب روی میدان (می توان به جای میدان از یک حلقه جابجایی هم استفاده کرد.). (تعاریف معادل دیگری هم برای حلقه چند جمله ای وجود دارند که می توان از آن ها نیز استفاده کرد) را می توان به صورت مجموعه ای از عبارات، به نام چند جمله ای ها بر حسب به صورت زیر تعریف کرد:[۱]
که در آن ضرایب و عضوی از میدان می باشند، به گونه ای که برای هر داریم و نماد هایی هستند که به عنوان "توان" شناخته شده و از همان قواعد معمول به توان رساندن تبعیت می کنند: و و به طوری که برای هر عدد صحیح نامنفی و داریم: . نماد را نامعین[۲] یا متغیر[۳] می نامند (لغت "متغیر" از واژه شناسی توابع چند جمله ای می آید. با این حال در اینجا هیچ مقداری اختیار نمی کند، و نمی تواند تغییر کند و با یک ثابت آن را جایگزین نمود.)
دو چند جمله ای زمانی با هم برابر اند که ضرایب متناظر با هرکدام از ها در هردو با هم برابر باشند.
جور دیگری هم می توان به حلقه چند جمله ای نگاه کرد، اینگونه که به میدان ، عضو جدید خارج از میدان را به میدان اضافه می کنیم که به گونه ای که عضو جدید با تمام اعضای قبلی جابجا شده و خاصیت ویژه دیگری هم ندارد (از همین می توان به عنوان تعریف دیگری از حلقه چند جمله ای بهره جست.).
حلقه چند جمله ای بر حسب که روی تعریف شده است، مجهز به جمع، ضرب و ضرب اسکال است که آن را تبدیل به یک جبر جابجایی می کند. این عملیات بر اساس قواعد معمولی عبارات جبری تعریف می شود. به طور خاص اگر:
و:
آنگاه:
و:
که در آن و و:
در فرمول های فوق، می توان با افزودن "جملات ساختگی" با ضرایب صفر، چندجمله ای های و را توسعه داد به گونه ای که و های ظاهر شده در این عبارت تعریف شده باشند. بخصوص وقتی که باشد برای هر که خواهیم داشت . ضرب اسکالر حالت خاصی از همان ضرب عمومی است که در آن به جمله ثابت (جمله ای که مستقل از است) کاهش یافته است؛ یعنی:
می توان به راحتی بررسی کرد که سه عملیات بالا در اصول موضوعه جبر جابجایی روی میدان صدق می کنند. ازینرو، به حلقه های چند جمله ای، جبرهای چندجمله ای نیز گفته می شود.
اغلب تعریف معادل دیگری که شهود کمتری دارد ترجیه داده می شود، چون راحت تر میشود آن را ساخت. به این صورت که چند جمله ای ها به صورت دنباله بی نهایت از عناصر دیده می شوند که تنها تعداد متناهی از آن ها ناصفرند، یه با طور معادل، دنباله ای که از جایی به بعد اعضای آن صفر هستند. در این حالت، و را به ترتیب به عنوان نمادهای جایگزین برای دنباله های و در نظر می گیرند. آنگاه با کمی دقت می توان فهمید که با این تعریف یک چندجمله ای چون:
را می توان به این صورت نمایش داد:
واژه شناسی
فرض کنید:
یک چندجمله ای ناصفر باشد که در آن جمله ثابت چندجمله ای است. در چند جمله ای های صفر این ثابت صفر است (البته ممکن است در حالت های دیگر هم صفر باشد). درجه ی که به صورت نوشته می شود است. این مقدار برابر بزرگترین یی است که ضریب صفر نباشد.[۴] ضریب پیشرو ی ، برابر است.[۵] در حالت خاص چندجمله ای های صفر که تمام ضرایب آن صفر است، چندجمله ای پیشرو تعریف نشده و درجه را اغلب تعریف نشده[۶]، برابر -1[۷] یا برابر [۸] تعریف می کنند.
یک چندجمله ای ثابت، یا چندجمله ای صفر است، یا چندجمله ای از درجه صفر.
یک چندجمله ای صفر تکین است اگر ضریب پیشروی آن 1 باشد.
اگر دو چندجمله ای و داده شده باشند خواهیم داشت:
و بر روی یک میدان یا به طور کلی تر یک حوزه صحیح داریم[۹]:
سریعاً نتیجه می شود که اگر یک حوزه صحیح باشد آنگاه نیز حوزه صحیح است.[۱۰]
در نتیجه اگر یک حوزه صحیح باشد، یک چندجمله ای دارای معکوس ضربی است اگر و تنها اگر ثابت باشند، و آن ثابت در معکوس ضربی داشته باشد.
دو چندجمله ای با هم مرتبط (به انگلیسی: Associated) هستند اگر برای هرکدام از آن ها یک عضو معکوس پذیر (به انگلیسی: Unit) وجود داشته باشد که با ضرب در آن به دیگری تبدیل شود.
هر چندجمله ای ناصفر بر روی یک میدان مرتبط با یک چندجمله ای منحصر به فرد است.
اگر دو چندجمله و داده شده باشد، می گویند مقسوم علیه است، یا چندجمله ای را تقسیم می کند یا ضریبی از است اگر چندجمله ای وجود داشته باشد به گونه ای که .
یک چندجمله ای تحویل ناپذیر است اگر نتوان آن را به صورت ضرب دو چندجمله ای غیرثابت نوشت، یا به طور معادل، اگر مقسوم علیه های آن یا چندجمله ای های ثابت باشند یا درجه برابر با چندجمله ای اصلی داشته باشند.
ضرب چندجمله ایهای تنک
تعریف و نمایش
در بسیاری از کاربردها پیش میآید که مجبور به نگهداری چندجملهایهایی هستیم که با این که درجهٔ بزرگی دارند ولی تعداد بسیاری از ضرایب آنها صفر میباشد. که استفاده از فرمت نگهداری فرض شده در ابتدای این نوشته برای چنین چند جملههایی بسیار ناکاراست. به چنین چندجملهای هایی، تنک می گوییم و برای اعمال روی آنها الگوریتمهای بسیاری پیشنهد شده که از ارزش بالایی هم برخوردارند. یک مثال از چنین چندجملهایهایی در زیر آمدهاست:
به همین دلیل به جای استفاده از آرایه برای نمایش این چندجملهایها از لیست پیوندی استفاده میشود. به این صورت که هر تک جمله را با یک واحد زبان برنامه نویسی که شامل درجه و ضریب آن باشد نمایش می دهیم و به آن گره می گوییم (مثلاً یک struct یا record) و این گرهها را در یک لیست پیوندی که به ترتیب درجه آنها ار کوچک به بزرگ مرتب شدهاست، نگه می داریم. برای مثال بالا، استفاده از آرایه به حدود 101 واحد حافظه نیاز دارد در حالی با نمایش اخیر میتوان آن را با تنها 16 واحد حافظه (حداکثر) نمایش داد زیرا که هر گره در لیست پیوندی اگر شامل توان و ضریب و دو اشاره جلو و عقب باشد به اندازهٔ 4 واحد فضا مصرف میکند و با سه گره نیز چندجملهای فوق قابل نمایش است به علاوهٔ یک گره احتمالی برای سرلیست.
الگوریتمهای چندجمله ایهای تنک
در مورد این طرز نمایش چندجمله ای، نمی توان الکوریتمهای معمول را به کار برد زیرا بسیاری از الگوریتمها فرض میکنند که دسترسی تصادفی سریع به هر یک از ضرایب دارند. مثلاً نمی توان از تبدیل فوریه آن طور که اینجا مطرح شد برای ضرب چندجمله ایهای تنک استفاده کنیم.
با این حال الکوریتم استراسن که در بالا بحث شد را میتوان با تغییر جزئی برای چنین نمایشی نیز به کار برد زیرا در طی آن تنها نیاز است که با یک بار عبور از روی چندجمله ای، وسط آن را پیدا کرد و سپس آن را به دو بخش تقسیم کرد و الگوریتم را بهطور بازگشتی ادامه داد. واضح است که چنین تقسیمی به زمان اجرای الگوریتم نمیافزاید (از لحاظ تحلیل مجانبی) ولی برخی مسائل جدید در پیادهسازی را پیش می کشد مانند حالات تهی یا نصف تهی. که در بدترین حالت با افزودن تعداد ثابتی گره با ضریب صفر و اضاه کردن حالات پایه برای زمانی که چلیست پیوندی نمایش دهندهٔ چندجملهای تهی است، به راحتی میتوان این الگوریتم را روی چندجمله ایهای تنک نیز اجرا کرد.
الگوریتمهای پیشرفته تر برای ضرب چندجملههای تنک که سریع تر نیز عمل میکنند و مثلاً در برخی از آنها از داده ساختار هیپ برای نگهداری چندجمله ایها و نمایش آنها استفاده میشود، نیز وجود دارند ولی در این جا به جزییات بیشتری از آنها نمیپردازیم.
جستارهای وابسته
منابع
- ↑ Herstein p. 153
- ↑ Herstein, Hall p. 73
- ↑ Lang p. 97
- ↑ Herstein p. 154
- ↑ Lang p.100
- ↑ Anton, Howard; Bivens, Irl C.; Davis, Stephen (2012), Calculus Single Variable, John Wiley & Sons, p. 31, ISBN 9780470647707.
- ↑ Sendra, J. Rafael; Winkler, Franz; Pérez-Diaz, Sonia (2007), Rational Algebraic Curves: A Computer Algebra Approach, Algorithms and Computation in Mathematics, vol. 22, Springer, p. 250, ISBN 9783540737247.
- ↑ Eves, Howard Whitley (1980), Elementary Matrix Theory, Dover, p. 183, ISBN 9780486150277.
- ↑ Herstein p.155, 162
- ↑ Herstein p.162
- [۱] Strassen+algorithm+for+polynomial+multiplication
- Cormen, Thomas H. (2001). "Chapter 30: Polynomials and the FFT". مقدمهای بر الگوریتمها (Second ed.). MIT Press and McGraw-Hill. pp. 822–848. ISBN 0-262-03293-7.
{{cite book}}
: Unknown parameter|coauthors=
ignored (|author=
suggested) (help) esp. section 30.2: The DFT and FFT, pp. 830–838.