دورهمی طرح و حل مساله ریاضی/ریشه‌های درون دایره واحد

راوی: فرحان معرفت

راجع به این موضوع در یک جلسه صحبت شد: یکشنبه، ۴ آذر ۱۴۰۳

گزارشی از مطالب کلاس

در کلاس درس پیرو سوالی که توسط یکی از دانشجویان مطرح شد، این بحث به میان آمد که فرمول یا الگوریتمی که بر حسب ضرایب یک چندجمله‌ای مختلط مشخص کند توزیع ریشه های آن نسبت به درون دایره واحد چگونه است. در ادامه‌ی گزارش الگوریتمی برای محاسبه‌ی این امر آورده می‌شود.

الگوریتم Schur-Cohn

این الگوریتم به ما اجازه می‌دهد تا توزیع ریشه‌های یک چندجمله‌ای مختلط را نسبت به دایره واحد در صفحه مختلط پیدا کنیم. برای یک چندجمله‌ای مختلط $p$ از درجه $n$، چندجمله‌ای reciprocal adjoint ،$p^{*}$ به صورت زیر تعریف می‌شود: $p^{*}(z)=z^n\overline{p({\overline{z}}^{-1})}$ و تبدیل Schur ، $Tp$ به صورت زیر تعریف می‌شود:

$Tp=\overline{p(0)}p-\overline{p^{*}(0)}{p}^{*}$

(خط روی نماد ها همان مزدوج مختلط است)

بنابراین، اگر $p(z)=a_n{z}^n+\cdots +a_{1}z+a_0$ با $a_n\ne 0$، آنگاه $p^{*}(z)={\overline{a}}_0{z}^n+{\overline{a}}_1{z}^{n-1}+\cdots +{\overline{a}}_n$، (با حذف جملات صفر پیشرو در صورت وجود). بنابراین ضریب‌های چندجمله‌ای $Tp$ می‌تواند به‌طور مستقیم در ضریب‌های $p$ بیان شود و از آنجا که یکی یا چند ضریب راس لغو می‌شوند، $Tp$ درجه کمتری نسبت به $p$ دارد. ریشه‌های $p$ ، $p^{*}$ و $Tp$ به صورت زیر مرتبط هستند.

لم

فرض کنید $p$ یک چندجمله‌ای مختلط باشد و $\delta =(Tp)(0)$.

• ریشه‌های $p^{*}$، (با در نظر گرفتن تکررشان)، تصاویر تحت inversion (نگاشت هایی که دایره را به خط می‌برند) در دایره واحد از ریشه‌های غیرصفر $p$ هستند.
• اگر $\delta \ne 0$، آنگاه $p,p^{*}$ و $Tp$ دارای ریشه‌هایی مشترک (همراه با تکررشان) در دایره واحد هستند.
• اگر $\delta >0$، آنگاه $p$ و $Tp$ دارای تعداد ریشه یکسان درون دایره واحد هستند.
• اگر $\delta <0$، آنگاه $p^{*}$ و $Tp$ دارای تعداد ریشه یکسان درون دایره واحد هستند.

اثبات

برای $z\ne 0$ داریم $p^{*}(z)=z^n\overline{p(z/|z{|}^2)}$ و به‌ویژه، $|p^{*}(z)|=|p(z)|$ برای $|z|=1$. همچنین $\delta \ne 0$ به معنای $|p(0)|\ne |p^{*}(0)|$ است. از این و تعاریف فوق، دو گزاره‌ی اول لم نتیجه می‌شوند. دو گزاره‌ی دیگر دیگر نتیجه قضیه روشه است که بر روی دایره واحد به توابع $\overline{p(0)}p(z)/r(z)$ و $-\overline{p^{*}(0)}{p}^{*}(z)/r(z)$ اعمال می‌شود، که در آن $r$ یک چندجمله‌ای است که ریشه‌های آن ریشه‌های $p$ در دایره واحد است، با همان تکرارها.

• برای بیان قابل‌فهم‌تر لم،

مفروض بدارید $n_p^{-},n_p^0$ و $n_p^{+}$ به ترتیب تعداد ریشه‌های $p$ را درون، بر روی و خارج از دایره واحد نشان دهند و نیز با نمادگذاری مشابه برای $Tp$. علاوه بر این، فرض کنید $d$ تفاوت درجه های $p$ و $Tp$ باشد. بنابراین لم نشان می‌دهد که $(n_p^{-},n_p^0,n_p^{+})=(n_{Tp}^{-},n_{Tp}^0,n_{Tp}^{+}+d)$ اگر $\delta >0$ و $(n_p^{-},n_p^0,n_p^{+})=(n_{Tp}^{+}+d,n_{Tp}^0,n_{Tp}^{-})$ اگر $\delta <0$ (توجه کنید که علائم مثبت و منفی رو نماد ها می‌توانند جابجا شوند.)

اکنون دنباله‌ی چندجمله‌ای‌های $T^{k}p$ $(k=0,1,\dots )$ را در نظر بگیرید، که در آن $T^{0}p=p$ و $T^{k+1}p=T(T^{k}p)$. اعمال موارد فوق به هر جفت از اعضای متوالی این دنباله نتیجه زیر را می‌دهد.

آزمون Schur-Cohn

فرض کنید $p$ یک چندجمله‌ای مختلط باشد با $Tp\ne 0$ و و نیز فرض کنید $K$ کوچک‌ترین عددی باشد که $T^{K+1}p=0$. علاوه بر این، فرض کنید ${\delta }_k=(T^{k}p)(0)$ برای $k=1,\dots ,K$ و $d_k=\mathrm{deg}{T}^{k}p$ برای $k=0,\dots ,K$.

• همه ریشه‌های $p$ درون دایره واحد قرار دارند اگر و تنها اگر

${\delta }_1<0$، ${\delta }_k>0$ برای $k=2,\dots ,K$، و $d_K=0$.

• همه ریشه‌های $p$ خارج از دایره واحد قرار دارند اگر و تنها اگر

${\delta }_k>0$ برای $k=1,\dots ,K$ و $d_K=0$.

• اگر $d_K=0$ و اگر ${\delta }_k<0$ برای $k=k_0,k_1\dots k_m$ (به ترتیب صعودی) و ${\delta }_k>0$ ، آنگاه $p$ ریشه‌ای در دایره واحد ندارد و تعداد ریشه‌های $p$ درون دایره واحد به صورت زیر است:

$\sum _{i=0}^m(-1{)}^i{d}_{k_i-1}$.

به‌طور کلی‌تر، توزیع ریشه‌های یک چندجمله‌ای $p$ نسبت به یک دایره دلخواه در صفحه مختلط، مثلاً دایره‌ای با مرکز $c$ و شعاع $\rho$، می‌تواند با استفاده از آزمون شُر-کوهن بر روی چندجمله‌ای «انتقال و Scale داده شده‌ی» $q$ که به صورت $q(z)=p(c+\rho z)$ تعریف شده است، پیدا شود.

با این حال، هر فاکتور scaling مجاز نیست، زیرا آزمون شُر-کوهن تنها زمانی می‌تواند به چندجمله‌ای $q$ اعمال شود که هیچ‌یک از برابری‌های زیر اتفاق نیفتد: $T^{k}q(0)=0$ برای برخی $k=1,\dots K$ یا $T^{K+1}q=0$ در حالی که $d_K>0$. اکنون، ضریب‌های چندجمله‌ای $T^{k}q$ چندجمله‌ای‌هایی در $\rho$ هستند و این برابری‌ها منجر به معادلات چندجمله‌ای برای $\rho$ می‌شوند، که بنابراین تنها برای تعداد محدودی از مقادیر $\rho$ برقرارند. بنابراین یک عامل scaling مناسب حتی به مقدار دلخواه نزدیک به $1$، همیشه می‌تواند پیدا شود.

مطالب تکمیلی

روش Lehmer

برای یک چندجمله‌ای مختلط $p$، با آزمون شُر-کوهن می‌توان یک دیسک دایره‌ای بزرگ پیدا کرد که تمام ریشه‌های $p$ را در بر بگیرد. سپس این دیسک می‌تواند با مجموعه‌ای از دیسک‌های کوچکتر که همپوشانی دارند، پوشش داده شود، که یکی از آن‌ها به‌طور هم‌مرکز قرار داده شده و بقیه به‌طور یکنواخت بر روی ناحیه حلقوی که هنوز باید پوشش داده شود، پخش شده‌اند. از این مجموعه، با استفاده از آزمون مجدد، دیسک‌هایی که حاوی هیچ ریشه‌ای از $p$ نیستند، می‌توانند حذف شوند. با هر یک از دیسک‌های باقی‌مانده، این روند پوشش‌دهی و حذف می‌تواند تکرار شود و این کار می‌تواند به هر تعداد دفعات انجام شود، که منجر به مجموعه‌ای از دیسک‌های به‌طور دلخواه کوچک می‌شود که به‌طور جمعی تمام ریشه‌های $p$ را در بر می‌گیرند.

مزایای این روش این است که شامل تکرار یک فرآیند واحد است و همه ریشه‌ها به طور همزمان پیدا می‌شوند، خواه واقعی باشند یا مختلط. همچنین، کاهش، یعنی حذف ریشه‌های پیدا شده، ضروری نیست و هر آزمون با چندجمله‌ای اصلی و با دقت کامل آغاز می‌شود. و به‌طرز شگفت‌انگیزی، این چندجمله‌ای هرگز نیازی به ارزیابی ندارد.

با این حال، هرچه دیسک‌ها کوچکتر شوند، ضریب‌های چندجمله‌ای‌های ' scale شده' مربوطه بیشتر در اندازه نسبی تفاوت خواهند داشت. این ممکن است باعث افزایش یا کاهش بیش از حد محاسبات کامپیوتری شود و در نتیجه شعاع دیسک‌ها را از پایین محدود کرده و دقت ریشه‌های محاسبه شده را کاهش دهد. برای جلوگیری از scaling شدید، یا برای صرفه‌جویی در کارایی، می‌توان با آزمودن تعدادی دیسک هم‌مرکز برای تعداد ریشه‌های مشمول شروع کرد و بنابراین ناحیه‌ای که ریشه‌ها در آن قرار دارند را به تعدادی ناحیه حلقوی باریک و هم‌مرکز کاهش داد. با تکرار این فرآیند با یک مرکز دیگر و ترکیب نتایج، ناحیه مذکور به اجتماع تقاطع‌های چنین ناحیه‌های حلقوی تبدیل می‌شود. در نهایت، زمانی که یک دیسک کوچک پیدا می‌شود که حاوی یک ریشه منفرد است، آن ریشه می‌تواند با استفاده از روش‌های دیگر، مانند روش نیوتن، بیشتر تقریب زده شود.

مطالعه بیش‌تر

دسترسی به برخی از این مقالات فقط با پرداخت وجه امکان‌پذیر است، هر چند می‌توان با روش‌هایی به صورت رایگان به آن‌ها دسترسی پیدا کرد:

https://ieeexplore.ieee.org/abstract/document/1100253/ (آزمون شر-کوهن ساده شده)
https://www.sciencedirect.com/science/article/pii/S0885064X99905289 (ورژن تسریع شده‌ای از الگوریتم شر-کوهن)
https://ieeexplore.ieee.org/abstract/document/1084319/ (آزمون شر-کوهن از نقطه نظری دیگر)
https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/schurcohn-theorem-for-matrix-polynomials/5AB9F1B5788EC10C3C510CB2218B26FE (آزمون شر-کوهن برای معادلات ماتریسی)