25 Mayıs 2017 Perşembe

Ey Edip Adana'da Pide Ye veyahut dokuzuncu dereceden bir palindromik polinomun kökleri cebirsel yöntemlerle hesaplanabilir

Ey Edip Adana'da pide ye! Bu emir cümlesini tersinden okuduğunuzda da yine aynı ifadeyle karşılaşıyorsunuz. Bu tip hem düz hem de ters okunuşu aynı olan ifadelere literatürde palindrom deniyor. Buradan hareketle cebirde palindromik polinomlar şöyle tanımlanıyor:

Tanım: Derecesi $n$ olan bir $P(x):=a_{n}x^{n}+\cdots+a_{0}$ polinomunun katsayıları $a_{i}=a_{n-i}$ şartını sağlıyorsa, o polinoma palindrom ya da palindromik polinom denir.
Örneğin $1+x$, $1+4x+x^{2}$, $2+11x+11x^{2}+2x^{3}$ ve $5+26x+66x^{2}+26x^{3}+5x^{4}$ hep palindromik polinomlar. Basitçe yerine koyarak derecesi $n$ olan bütün palindromların aşağıdaki denklemi sağladığı gösterilebilir. \begin{equation*} x^{n} P\left( \frac{1}{x} \right) = P(x) \ \ \ \ldots \ \ \ (1) \end{equation*} Hatta bu denklem palindromik polinomun tanımı olarak da addedilebilir.

Cebirsel bir özdeşliği asla hafife alma! (Never underestimate an algebraic identity!) özdeyişini uygulayıp bu denklemden hemen üç sonuç çıkartacağız.

Lemma 1: Derecesi tek olan bütün palindromların $x=-1$ noktasında bir kökü vardır.
İspat: (1) nolu denklemde $x=-1$ ve $n=2k+1$ koyduğumuzda denklem $-P(-1)=P(-1)$ ya da $2P(-1)=0$ haline indirgenir. QED

Lemma 2: Birbirini tam bölen iki palindromun bölümü de palindromdur.
İspat: $m < n$ olmak üzere, $\deg (P) = n$, $\deg (Q) = m$ ve $\deg (R) = n-m$ olsun. $P(x)=Q(x)R(x)$ eşitliğinde, $x$ yerine $\frac{1}{x}$ yazıp daha sonra her iki tarafı $x^{n}$ ile çarpalım: $x^{n}P\left( \frac{1}{x} \right) = x^{m} Q\left( \frac{1}{x} \right) x^{n-m} R\left( \frac{1}{x} \right)$. Hipotez gereği $P$ ve $Q$ palindrom olduklarından her ikisi de (1) nolu denklemi sağlar. O zaman $P(x)=Q(x) x^{n-m} R\left( \frac{1}{x} \right)$ ya da $x^{n-m} R\left( \frac{1}{x} \right) = \frac{P(x)}{Q(x)} = R(x)$ yazabiliriz. QED

Lemma 3: Derecesi $2n+1$ olan bir palindromun kök bulma problemi, derecesi $2n$ olan bir palindromun kök bulma problemine indirgenebilir.
İspat: $\deg (P) = 2n+1$ olan bir palindrom olsun. Lemma (1) uyarınca $x=-1$ bu polinomun bir köküdür ya da $(x+1)$ bu polinomu böler. O zaman $P(x) = (x+1)Q(x)$ yazabiliriz. $x+1$ bir palindrom olduğundan, Lemma (2) uyarınca $Q(x)$ de bir palindromdur. QED

Ödev 1: İki palindromun çarpımının da bir palindrom olduğunu gösteriniz.

Postanın başlığındaki Adanalı Edip şamatasını geçtiğinizde bir iddia var: 9. dereceden bir palindromun köklerini cebirsel yöntemlerle hesaplayabileceğimiz öne sürülmüş. Bu ilk bakışta meşhur Abel-Ruffini teoremini ihlal ediyor görünse de palindromların kök yapısını kurcaladığımızda aslında makul olduğunu görebiliriz. Öncelikle bir gözlemde bulunalım. $P(z)=0$ ise, o zaman (1) nolu denklem uyarınca $P\left( \frac{1}{z} \right) = 0$ olmalıdır. Diğer bir deyişle bir palindromun kökleri $\ldots, z_{i},z_{i}^{-1}, \ldots $ şeklinde kendini göstermektedir. Hem $x-z_{i}$ hem de $x-z_{i}^{-1}$, ilgili palindromu böldüklerinden bu kök çiftinden oluşan ikinci dereceden polinom da palindromu böler: \begin{equation*} (x-z_{i}) \left( x - \frac{1}{z_{i}} \right) = x^{2} - \left( z_{i} + \frac{1}{z_{i}} \right)x + 1 \end{equation*} Ama bu ikinci dereceden polinomun da bizzat bir palindrom olduğuna dikkat ediniz. Bu çıkarsamanın problematik olduğu, daha doğrusu bize yeni kök vermediği iki nokta var: $\pm 1$. Zira $z= \pm 1$ için $z=z^{-1}$ sağlanıyor. Bu da Acaba bu noktalarda çift katlı kök mü olmalı? sorusunu gündeme getiriyor. Eğer mümkünse $1,z_{1},z_{1}^{-1},\ldots,z_{n},z_{n}^{-1}$ bir palindromun kökleri olsun. O zaman cebirin temel teoremi uyarınca (ve genelliği kaybetmeden polinomun monik olduğunu varsayarak) \begin{eqnarray} \nonumber P(x) &=& (x-1) (x-z_{1}) \left( x - \frac{1}{z_{1}} \right) \cdots (x-z_{n}) \left( x - \frac{1}{z_{n}} \right) \\ \nonumber &=& (x-1) \left( x^{2} - \left( z_{1} + \frac{1}{z_{1}} \right)x + 1 \right) \cdots \left( x^{2} - \left( z_{n} + \frac{1}{z_{n}} \right)x + 1 \right) \end{eqnarray} olmaktadır. İkinci satırda bütün kuadratik terimler palindromdur. Dolayısıyla $P(x)$ polinomunu sırasıyla bu kuadratik palindromlara böldüğümüzde, Lemma (2) uyarınca bölüm yine bir palindrom olmalıdır. Ama bu sürecin sonunda elimizde kala kala $x-1$ kalır ve bu bir palindrom değildir. Dolayısıyla, evet, $x=1$ noktasındaki kök iki veya çift sayıda katlı olmalıdır, zira $(x-1)^{2} = x^{2}-2x+1$ de bir kuadratik palindromdur. Öte yandan $x+1$ bir palindrom olduğundan, $x=-1$ noktasındaki kök çift katlı olmak zorunda değildir. Bu paragrafta palindrom köklerinin yapısına dair eriştiğimiz sonuçları bir teoremde toparlayalım.

Teorem 1: $z$ bir palindromun kökü ise, $z^{-1}$ de aynı palindromun köküdür. Ayrıca palindromun eğer varsa $z=1$ noktasındaki kökü çift sayıda tekrarlanır.

Bunca ön hazırlıktan sonra postanın başlığındaki önermemizi ispatlayabiliriz artık. $D(x)$ dokuzuncu dereceden bir palindrom olsun. Bu palindromun derecesi tek olduğundan Lemma (1) uyarınca $x=-1$ noktasında bir kökü vardır ve $D(x) = (x+1)S(x)$ yazabiliriz. $S(x)$ sekizinci dereceden bir polinomdur ve Lemma (2) uyarınca o da bir palindromdur. Problemi sekizinci dereceye indirgedik. Teorem (1) uyarınca $S$ polinomunun kök yapısı $z_{1},z_{1}^{-1},\ldots , z_{4},z_{4}^{-1}$ şeklinde olur. Genelliği kaybetmeden $D$ ve dolayısıyla $S$ polinomlarının monik olduğunu varsayarak cebirin temel teoremini uygulayalım. İşlemleri sadeleştirmek için $z_{i}+z_{i}^{-1} =: \zeta_{i}$ tanımını kullanacağız. \begin{eqnarray} \nonumber S(x) &=& x^{8} + a_{1}x^{7} + a_{2}x^{6} + a_{3}x^{5} + a_{4}x^{4} + a_{3}x^{3} + a_{2}x^{2} + a_{1}x +1 \\ \nonumber &=& (x^{2} - \zeta_{1}x + 1) (x^{2} - \zeta_{2}x + 1) (x^{2} - \zeta_{3}x + 1) (x^{2} - \zeta_{4}x + 1) \\ \nonumber &=& x^{8} - (\zeta_{1}+\zeta_{2}+\zeta_{3}+\zeta_{4})x^{7} +(4+\zeta_{1}\zeta_{2}+\zeta_{1}\zeta_{3}+\zeta_{1}\zeta_{4}+\zeta_{2}\zeta_{3}+\zeta_{2}\zeta_{4}+\zeta_{3}\zeta_{4})x^{6} \\ \nonumber &\ & -(3(\zeta_{1}+\zeta_{2}+\zeta_{3}+\zeta_{4}) +\zeta_{1}\zeta_{2}\zeta_{3}+\zeta_{1}\zeta_{2}\zeta_{4}+\zeta_{1}\zeta_{3}\zeta_{4}+\zeta_{2}\zeta_{3}\zeta_{4})x^{5} \\ \nonumber &\ & +(6+2(\zeta_{1}\zeta_{2}+\zeta_{1}\zeta_{3}+\zeta_{1}\zeta_{4}+\zeta_{2}\zeta_{3}+\zeta_{2}\zeta_{4}+\zeta_{3}\zeta_{4})+ \zeta_{1}\zeta_{2}\zeta_{3}\zeta_{4})x^{4} \\ \nonumber &\ & -(3(\zeta_{1}+\zeta_{2}+\zeta_{3}+\zeta_{4}) +\zeta_{1}\zeta_{2}\zeta_{3}+\zeta_{1}\zeta_{2}\zeta_{4}+\zeta_{1}\zeta_{3}\zeta_{4}+\zeta_{2}\zeta_{3}\zeta_{4})x^{3} \\ \nonumber &\ & +(4+\zeta_{1}\zeta_{2}+\zeta_{1}\zeta_{3}+\zeta_{1}\zeta_{4}+\zeta_{2}\zeta_{3}+\zeta_{2}\zeta_{4}+\zeta_{3}\zeta_{4})x^{2} - (\zeta_{1}+\zeta_{2}+\zeta_{3}+\zeta_{4})x +1 \end{eqnarray} Bu büyük denklemde Viète-Girard simetrik fonksiyonlarını görmemek mümkün değil. Hemen tanımlayalım. \begin{eqnarray} \nonumber e_{1} &:=& \zeta_{1}+\zeta_{2}+\zeta_{3}+\zeta_{4} \\ \nonumber e_{2} &:=& \zeta_{1}\zeta_{2}+\zeta_{1}\zeta_{3}+\zeta_{1}\zeta_{4}+\zeta_{2}\zeta_{3}+\zeta_{2}\zeta_{4}+\zeta_{3}\zeta_{4} \\ \nonumber e_{3} &:=& \zeta_{1}\zeta_{2}\zeta_{3}+\zeta_{1}\zeta_{2}\zeta_{4}+\zeta_{1}\zeta_{3}\zeta_{4}+\zeta_{2}\zeta_{3}\zeta_{4} \\ \nonumber e_{4} &:=& \zeta_{1}\zeta_{2}\zeta_{3}\zeta_{4} \end{eqnarray} Böylelikle, katsayıları eşitleyerek \begin{eqnarray}\nonumber e_{1} &=& -a_{1} \\ \nonumber e_{2} &=& a_{2}-4 \\ \nonumber e_{3} &=& -3e_{1}-a_{3} = 3a_{1}-a_{3} \\ \nonumber e_{4} &=& a_{4} - 6 - 2e_{2} = a_{4}-2a_{2}+2 \end{eqnarray} ifadelerine ulaşabiliriz.

Şimdi, kökleri $\zeta_{1}, \zeta_{2}, \zeta_{3}$ ve $\zeta_{4}$ olan, kuartik bir denklemimiz olsaydı, aşağıdaki gibi olacaktı. \begin{equation*} x^{4} - e_{1}x^{3} + e_{2}x^{2} - e_{3}x + e_{4} = 0 \end{equation*} Bir önceki paragrafta yaptığımız çalışma uyarınca biz bu denklemi şöyle de ifade edebiliriz: \begin{equation*} x^{4} + a_{1}x^{3} + (a_{2}-4)x^{2} + (a_{3}-3a_{1})x + a_{4}-2a_{2}+2 = 0 . \end{equation*} Ama daha önce kuartik denklemleri yerölçüsünde Ferrari yöntemiyle çözmüştük. Dolayısıyla katsayılarını da bildiğimiz bu denklemi çözebilir ve $\zeta_{i}$ değerlerini bulabiliriz! Son olarak $\zeta_{i}=z_{i}+z_{i}^{-1}$ eşitliği yeniden düzenlendiğinde aşağıdaki kuadratik denkleme indirgenmektedir. \begin{equation*} z_{i}^{2} - \zeta_{i} z_{i} + 1 = 0 \end{equation*} Bu denklem ise kolayca çözülerek $z_{i}$ kökleri hesaplanır.

Evet, Abel-Ruffini teoremi genel olarak derecesi 5 ya da daha büyük olan polinomların köklerinin cebirsel yöntemlerle hesaplanamayacağını söylüyor. Öte yandan polinom eğer palindromik ise, kökleri 9. dereceye kadar cebirsel yöntemlerle muamele edilebiliyor. Bu bir çelişki değil. Zira palindromların katsayılarındaki simetri onların herhangi bir genelliği yakalamasını engelliyor.

22 Mayıs 2017 Pazartesi

Strelitz algoritmasıyla Routh-Hurwitz kararlılık probleminin çözümü

Motivasyon

Fen bilimlerinde ve mühendislik uygulamalarında pek çok problem aşağıdaki lineer başlangıç değer problemine kadar indirgenebilir. \begin{equation*} c_{n} \frac{{\rm d}y^{n}(t)}{{\rm d}t^{n}} + \cdots + c_{1} \frac{{\rm d}y(t)}{{\rm d}t} + c_{0}y(t) = f(t) \end{equation*} Burada $y(t)$ çalıştığımız sistemi tarif eden bir durum değişkeni ve $c_{n},\ldots,c_{0}$ ise sabit değerli (ve genellikle gerçel) katsayılardır. $f(t)$ ise sistemin davranışını yönlendirmeye çalışan ve dışarıdan uygulanan bir çeşit itici güç (driving force) olarak adlandırılır ve genellikle amaç sistemin bu itici güce verdiği tepkiyi (response) $y$ niceliği kanalıyla hesaplamaktır. Örneğin, ne kadar karmaşık olursa olsun, pasif, lineer devre elemanlarıyla kurulan ve sözgelimi sinusoidal bir güç kaynağı ile tahrik edilen bütün analog devrelerin dinamiği bu şablona uyar. $f$, her $t$ için sıfır değerini aldığında bu denklemin homojen olduğu söylenir ve çözümü $y_{\rm h}(t)=\exp(\lambda t)$ şablonunda fonksiyonlarla aranır. İlgili homojen denkleme bu deneme fonksiyonunu koyup gerekli sadeleştirmeleri yaptığımızda karşımıza cebirsel bir denklem çıkar. \begin{equation*} c_{n}\lambda^{n} + \cdots + c_{1} \lambda + c_{0} = 0 \end{equation*} Demek ki aradığımız deneme fonksiyonlarındaki $\lambda$ değerleri, derecesi $n$ olan cebirsel bir denklemin kökleriymiş. Buraya kadar her şey son derece tek düze giderken, özellikle kararlılık analizi aşamasında $t \to \infty$ asimptotiğinde $|y_{\rm h}| < y_{\rm max} < \infty$ olmasını hatta $|y_{\rm h}| \to 0$ olmasını isteriz. Sistem tasarımcılarının en büyük kabusu $t \to \infty$ asimptotiğinde $|y| \to \infty$ davranışına rastlamaktır. (Devre elemanından sonsuz akım geçmesi o devrenin -eğer patlamazsa- aşırı ısınıp buharlaşması anlamına gelir.) $t \to \infty$ asimptotiğinde kararlı bir davranış elde etmemizin, deneme fonksiyonlarının şablonuna bakıldığında $\Re [\lambda_{i}] < 0$ şartında düğümlendiği barizdir. Burada $\Re[z]$ ile karmaşık bir sayının gerçel kısmını simgeliyoruz. Bu ve benzeri endişeler Routh-Hurwitz kararlılık problemini tanımlar.

Routh-Hurwitz problemi: Katsayıları gerçel bir polinomun tüm köklerinin gerçel kısımlarının negatif olması için gerekli ve yeterli şartları bulunuz.

Strelitz çözümü

Routh-Hurwitz problemi, cebirsel kök tasnifi (root classification) konusunun abecesini oluşturur ve bu alanda öğrencinin ilk rastladığı konulardan birisidir. Bu problem 19. yy'da ortaya atılmış ve Sturm teoremi kullanılarak çözülmüştür. 20. yy'da ise Strelitz tarafından Sturm teoremini kullanmadan, daha düşük cebirsel işlem hammaliyesiyle başka bir çözüm önerilmiştir. Biz bu postada Strelitz'in çözümünü orijinal makalesini takip ve yer yer şerh ederek sunmaya çalışacağız.

Polinomun kökleri, polinomdaki bütün katsayıları baş katsayıya böldüğümüzde değişmeyeceğinden, genelliği kaybetmeden, aşağıdaki monik polinomu ele alıyoruz. \begin{equation} P(z) := z^{n} + a_{1}z^{n-1} + \cdots + a_{n} \ \ \ \ \ (1) \end{equation} Katsayı indisleri ile terimlerin dereceleri arasındaki zıt yönlerde artışa dikkat ediniz. (Literatürdeki çoğu formül maalesef bizim burada uyguladığımız konvansiyonu takip etmiyor ama yazarla paralel gidebilmek için biz bu konvansiyonu tercih etmek zorunda kaldık.) Strelitz bu noktada bariz olduğunu düşünerek ispatsız şöyle bir argüman sunuyor:

(1) nolu denklemdeki katsayıların gerçel olmaları şartının zaruri olmadığı barizdir, zira eğer karmaşık katsayılı bir $P_{0}(z)$ polinomunun bütün köklerinin gerçel kısımları negatif ise, o zaman $P_{0}(z)\overline{P_{0}(\overline{z})}$ polinomunun tüm köklerinin gerçel kısımları da negatiftir.
(Burada $\overline{z}$ ile $z$ sayısının karmaşık eşleniği kastediliyor.) Bu önermeyi ispatlayalım. Monik $P_{0}$ polinomunun derecesi $k$, kökleri ise $z_{1},\ldots,z_{k}$ olsun. O zaman cebirin temel teoremi uyarınca $P_{0}(z) = (z-z_{1}) \cdots (z-z_{k})$ yazabiliriz. Yine benzer şekilde $P_{0}(z)\overline{P_{0}(\overline{z})}$ polinomunun köklerinin de $z_{1},\overline{z_{1}}, \ldots , z_{k}, \overline{z_{k}}$ olması gerektiği barizdir. Dolayısıyla cebirin temel teoremini kullanarak \begin{eqnarray}\nonumber P_{0}(z)\overline{P_{0}(\overline{z})} &=& (z-z_{1}) (z-\overline{z_{1}}) \cdots (z-z_{k}) (z-\overline{z_{k}}) \\ \nonumber &=& (z^{2} - 2 \Re [z_{1}]z + |z_{1}|^{2}) \cdots (z^{2} - 2 \Re [z_{k}]z + |z_{k}|^{2}) \end{eqnarray} sonucunu elde ederiz. Bu denklemin sağ tarafının sadece gerçel katsayılardan oluştuğu barizdir. Uzun lafın kısası Strelitz şunu demeye çalışıyor: Eğer $P_{0}$ polinomunun katsayıları karmaşık ise, o zaman bu polinomun Routh-Hurwitz sorgusu yerine katsayıları tamamen gerçel olan $P_{0}(z)\overline{P_{0}(\overline{z})}$ polinomunun Routh-Hurwitz sorgusuna bakabiliriz. Her iki polinomun da köklerinin gerçel kısımları aynı olduğundan, Routh-Hurwitz sorguları da aynı sonucu verecektir.

(1) nolu denklemde verilen polinoma ek olarak ikinci bir polinom tanımlıyoruz. \begin{equation} Q(z) := z^{m} + b_{1}z^{m-1} + \cdots + b_{m}, \ \ \ m := \frac{n(n-1)}{2} \ \ \ \ \ (2) \end{equation} (Strelitz'in makalesinde bu polinomun baş teriminin derecesi yazılırken baskı hatası yapılmış, yanlışlıkla $n$ konulmuş.) $P$ polinomun kökleri $z_{k}$ (ve $k=1,\ldots,n$) ise, o zaman $Q$, kökleri \begin{equation*} z_{i}+z_{j}; \ \ \ i < j, \ \ \ i,j=1,\ldots,n \end{equation*} ile verilen polinom olacak şekilde tanımlanıyor. Makalenin ilerleyen bölümlerinde, $P$'nin köklerini hesaplamadan $Q$ polinomunu türetmenin yollarını gösteriyor yazar. Ayrıca $n$ adet kökten seçilebilecek ikili çiftlerin sayısı da $m = n(n-1)/2$ eşitliğini izah etmektedir. Bu ön hazırlıktan sonra Routh-Hurwitz probleminin kesin çözümünü verebiliriz.

Teorem: Katsayıları gerçel $P(z)$ polinomunun tüm köklerinin karmaşık düzlemin sol yarısında kalması için gerek ve yeter şart hem $P(z)$ hem de $Q(z)$ polinomlarının katsayılarının pozitif olmasıdır. Diğer bir deyişle \begin{eqnarray} \nonumber &&a_{j}>0, \ \ \ j=1,\ldots, n; \\ \nonumber &&b_{k}>0, \ \ \ k=1,\ldots, m; \ \ \ m = n(n-1)/2. \end{eqnarray} İspat: (Strelitz) Gereklilik. $P$'nin bütün köklerinin gerçel kısmı karmaşık düzlemin sol tarafında yer alsın. Bu köklere $z_{1},\ldots,z_{n}$ diyelim. Söz konusu polinomun katsayıları gerçel olduğundan $P(z_{i})=0 \iff P(\overline{z_{i}})=0$ olduğu barizdir. $z_{p}=\alpha+\beta i$ olsun. (Hipotez gereği $\alpha < 0$ olduğunu unutmayınız.) O zaman \begin{equation*} (z-z_{p})(z-\overline{z_{p}}) = z^{2} - 2\alpha z + \alpha^{2} +\beta^{2} \ \ \ \ \ (3) \end{equation*} ifadesindeki bütün katsayılar pozitif olur. $z_{q}$ gerçel bir kök olsun. Yine hipotez gereği $z_{q}<0$ olması gerektiğinden, $(z-z_{q})$ ifadesindeki bütün katsayılar yine pozitif olacaktır. $k=1,\ldots,s$ için $\alpha_{k}+i\beta_{k}$ ve $\alpha_{k}-i\beta_{k}$, $P$ polinomunun tüm karmaşık köklerini temsil ederken, $j=1,\ldots,t=n-2s$ için $\gamma_{j}$ aynı polinomun gerçel köklerini temsil etsin. O zaman \begin{equation*} P(z) = \prod_{k=1}^{n} (z-z_{k}) = \prod_{k=1}^{s} (z^{2} - 2\alpha _{k} z + \alpha _{k}^{2} +\beta _{k}^{2}) \prod_{l=1}^{t} (z-\gamma_{l}) \ \ \ \ \ (4) \end{equation*} yazabiliriz. (4) nolu denklemdeki ifadeleri çarptıktan sonra $-\alpha_{k}$ ve $-\gamma_{k}$ değerlerinin negatifliğine ilişkin yukarıdaki mülahazalar muvacehesinde, (1) nolu denklemdeki bütün katsayıların pozitif olduğu sonucuna varabiliriz: $a_{i} > 0$.

Ayrıca, $k=1,2,\ldots, n$ için $\Re [z_{k}] < 0$ olması halinde, o zaman $Q(z)$ polinomunun bütün kökleri karmaşık düzlemin sol tarafında kalır ve böylece $k=1,2,\ldots,m$ için $b_{k} > 0$ olduğunu da göstermiş oluruz.

Yeterlilik. $\alpha \pm i \beta$, $P(z)$ polinomunun $\alpha$ ve $\beta$ sıfırdan farklı olacak şekilde iki kökü olsun. O zaman $2\alpha$ da $Q(z)$ polinomunun bir köküdür: $Q(2\alpha) = 0$. Ancak, $Q(z)$ polinomunun bütün katsayıları, $b_{k}$, pozitif olduğundan, $Q(z)=0$ denkleminin tüm gerçel kökleri negatiftir ve sonuç itibariyle $P(z)=0$ denkleminin tüm karmaşık kökleri karmaşık düzlemin sol yarısına düşer. Ayrıca, $P(z)$ polinomunun da tüm gerçel kökleri gerçel eksenin sol tarafındadır, zira $j=1,2,\ldots,n$ için $a_{j} > 0$.

Teoremin ispatı burada bitmiştir.

Strelitz algoritması

Yukarıdaki ispat güzel ama işe yarayabilmesi için $Q(z)$ polinomunun katsayılarını, $P(z)$ polinomunun köklerini hesaplamadan, hızlı bir biçimde hesaplayacak bir yönteme ihtiyacımız var. Makalenin geri kalan kısmında Strelitz ilgili katsayıları hesaplamak için Newton toplamlarına dayanan bir algoritma kurmakla uğraşıyor. Bu amaçla $k=1,\ldots,n$ olmak üzere $P(z)$ polinomunun köklerine $z_{k}$ diyelim ve \begin{equation*} \sigma_{j} := \sum_{k=1}^{n} z_{k}^{j}; \ \ \ s_{j} := \sum_{p=1}^{n-1} \sum_{q=p+1}^{n} (z_{p}+z_{q})^{j}, \ \ \ j=0,1,2,3,\ldots \end{equation*} niceliklerini tanımlayalım. Bu tanımların her ikisi de bildiğiniz Newton toplamı: ilki $P$, ikincisi $Q$ polinomlarının kökleriyle hesaplanmış. $j \geq n$ için Newton toplamını ilk $n-1$ Newton toplamı verilmişse hesaplamak çok kolay. Zira $0=P(z_{k})=z_{k}^{n}+a_{1}z_{k}^{n-1}+\cdots+a_{n}$ eşitliğinde her iki tarafı da önce $z_{k}^{j-n}$ ile çarpıp, sonra bütün kökler üzerinden toplama yaparsak \begin{equation*} \sigma_{j} + a_{1}\sigma_{j-1} + \cdots + a_{n}\sigma_{j-n} = 0, \ \ \ j \geq n, \ \ \ (5a) \end{equation*} denklemine ulaşıyoruz. (Strelitz'in makalesinde yine bir baskı hatası var. Bu denklemdeki $a_{n}$ terimi unutulmuş. bak. 544. sayfadaki ilk denklem.) Bu denklem sayesinde kendisinden önceki $n$ Newton toplamının verilmesi halinde bir sonraki Newton toplamının da sadece çarpma ve toplama işlemlerini kullanarak hesaplanabileceğini gözleyiniz. $j < n$ için Newton toplamlarının nasıl hesaplanılacağı konusunda biraz düşünmek gerekiyor. Gerçi temel cebirsel özdeşlikler kanalıyla $\sigma_{0}=n$ ve $\sigma_{1}=-a_{1}$ (basitçe kökler toplamı) olduğu kolayca ortaya çıksa da diğer Newton toplamları o kadar kolay değil. Biz ispatını daha sonra yapmak üzere sadece bu durum için Newton toplamlarının formülünü vermekle yetineceğiz. \begin{equation*} \sigma_{j} + a_{1}\sigma_{j-1} + \cdots + a_{j-1}\sigma_{1} + j a_{j} = 0, \ \ \ j < n, \ \ \ (5b) \end{equation*}

Algoritmanın ikinci aşamasında $s_{j}$ niceliklerini $\sigma_{j}$ cinsinden ifade etmeye çalışacağız. Bu amaçla \begin{equation*} \left( \sum_{k=1}^{n} e^{z_{k}t} \right)^{2} = e^{2z_{1}t}+e^{2z_{2}t}+ \cdots +e^{2z_{n}t} + 2 \sum_{p=1}^{n-1}\sum_{q=p+1}^{n} e^{(z_{p}+z_{q})t} \end{equation*} özdeşliğinin her iki tarafını da Taylor serilerini kullanarak açacağız. (Strelitz'in makalesinde yine bir baskı hatası var. 544. sayfada yukarıdan dördüncü satırda yer alan bu denklemde $e^{2z_{n}t}$ terimi yerine $e^{2z_{k}t}$ yazılmış.) Sol tarafı açtığımızda \begin{eqnarray}\nonumber \left( \sum_{k=1}^{n} e^{z_{k}t} \right)^{2} &=& \left( \sum_{j=0}^{\infty} \sum_{k=1}^{n} z_{k}^{j} \frac{t^{j}}{j!} \right)^{2} = \left( \sum_{j=0}^{\infty} \sigma_{j} \frac{t^{j}}{j!} \right)^{2} = \sum_{j=0}^{\infty}\sum_{i=0}^{\infty} \sigma_{j}\sigma_{i} \frac{t^{i+j}}{i!j!} \\ \nonumber &=& \frac{\sigma_{0}\sigma_{0}}{0!0!} + \left( \frac{\sigma_{1}\sigma_{0}}{1!0!} + \frac{\sigma_{0}\sigma_{1}}{0!1!} \right) t + \left( \frac{\sigma_{2}\sigma_{0}}{2!0!} + \frac{\sigma_{1}\sigma_{1}}{1!1!} + \frac{\sigma_{0}\sigma_{2}}{0!2!}\right) t^{2} + \cdots \\ \nonumber &=& \sum_{j=0}^{\infty} \left( \sum_{i=0}^{j} \frac{\sigma_{i}\sigma_{j-i}}{i!(j-i)!} \right) t^{j} \end{eqnarray} eşitliği elde ediliyor. Aynı özdeşliğin sağ tarafını açtığımızda ise \begin{eqnarray}\nonumber \sum_{k=1}^{n} e^{2z_{k}t} + 2 \sum_{p=1}^{n-1}\sum_{q=p+1}^{n} e^{(z_{p}+z_{q})t} &=& \sum_{j=0}^{\infty}\sum_{k=1}^{n} z_{k}^{j} \frac{2^{j}t^{j}}{j!} + 2 \sum_{j=0}^{\infty} \sum_{p=1}^{n-1}\sum_{q=p+1}^{n} (z_{p}+z_{q})^{j} \frac{t^{j}}{j!} \\ \nonumber &=& \sum_{j=0}^{\infty} \sigma_{j} \frac{2^{j}t^{j}}{j!} + 2 \sum_{j=0}^{\infty} s_{j} \frac{t^{j}}{j!} \end{eqnarray} sonucunu elde ediyoruz. Matematikte iş bu aşamaya geldiğinde genellikle denklemin sol ve sağ tarafında yer alan aynı kuvvetteki terimlerin ($t^{j}$) katsayıları eşitlenir. (Neden?) Yeniden düzenleme yaptığımızda $Q$ polinomunun Newton toplamlarını $P$ polinomunun Newton toplamlarına bağlayan özdeşliği elde etmiş oluyoruz. \begin{equation*} s_{j} = -2^{j-1}\sigma_{j} + \frac{1}{2} \sum_{i=0}^{j} \frac{j!}{i!(j-i)!} \sigma_{i}\sigma_{j-i} \end{equation*} (Sterlitz'in makalesinde bu denklemle ilgili yine bir işlem hatası var. Onun verdiği formülü uyguladığınızda $s_{0}=n(2n-1)/4$ çıkıyor. Bu sonuç yanlış. Bizim burada verdiğimiz formül kullanıldığında $s_{0}=n(n-1)/2$ elde ediliyor, olması gerektiği gibi. Zira derecesi sıfır olan Newton toplamı her zaman polinomun derecesine eşittir.)

Algoritmanın üçüncü ve son aşamasında $Q$ polinomunun katsayılarını elde etmek var. Bu ise çok kolay. Öncelikle $b_{0}=1$ olduğunu not edelim. Sonra (5) nolu denklemler kanalıyla, bu denklemlerde $a$ yerine $b$, $\sigma$ yerine $s$ ve $n$ yerine $m$ koyarak, önce $s_{1} + b_{1} = 0$ ilişkisinden $b_{1}=-s_{1}$ hesaplanabileceğini gözleyelim. Ardından $s_{2} + b_{1}s_{1} + 2b_{2}=0$ denkleminin bize $b_{2}$ değerini vereceğini. Böyle devam ettiğimizde bütün $b_{j}$ katsayılarının hesaplanacağı da barizdir.

10 Mayıs 2017 Çarşamba

Kübik ve kuartik fiyakalı formül arayışı

Soru: $(n-m)^{a}+\cdots +(n-1)^{a}+n^{a}=(n+1)^{a}+\cdots+(n+m)^{a}$ denkleminin $a=3,4$ için hiçbir $n$ ve $m$ pozitif tam sayılarıyla sağlanmadığını ispatlayınız.

$a=3$ için söz konusu denklem aşağıdaki gibi yeniden düzenlenebilir. \begin{eqnarray} \nonumber n^{3} &=& \sum_{k=1}^{m} (n+k)^{3}-(n-k)^{3} \\ \nonumber &=& \sum_{k=1}^{m}((n+k)-(n-k))((n+k)^{2}+(n+k)(n-k)+(n-k)^{2}) \\ \nonumber &=& \sum_{k=1}^{m} 2k (3n^{2}+k^{2}) \\ \nonumber &=& 6n^{2} \sum_{k=1}^{m} k + 2\sum_{k=1}^{m} k^{3} \\ \nonumber &=& 3 m(m+1) n^{2} + \frac{m^{2}(m+1)^{2}}{2} \end{eqnarray} Burada cebirde çok iyi bilinen iki küp farkını $a^{3}-b^{3}=(a-b)(a^{2}+ab+b^{2})$ ve $\sum_{k=1}^{m} k = m(m+1)/2$ ile $\sum_{k=1}^{m} k^{3} = m^{2}(m+1)^{2}/4$ özdeşliklerini kullandık. Özellikle son iki özdeşliğin ispatını bilmiyorsanız mutlaka ispatlamaya çalışmalısınız. Bu ifadeyi yeniden düzenlediğimizde $n$ için üçüncü $m$ için dördüncü dereceden bir Diaphantos denklemi elde ediyoruz. \begin{equation*} n^{3} - 3m(m+1)n^{2} - \frac{m^{2}(m+1)^{2}}{2} = 0 \end{equation*} Bu denklemin hiç negatif kökü olmadığını $n \to -n$ koyarak kolayca görebilirsiniz. Descartes'in işaret kuralı uyarınca sadece bir tane pozitif kök olduğu da aşikardır. Dolayısıyla verilen bir $m$ tam değerine tekabül eden $n$ tam sayısı (eğer varsa) biriciktir.

$n$ tam sayısı (eğer varsa) çift olmalıdır. Zira ardışık iki sayıdan bir tanesinin kesinlikle çift olması sebebiyle, $m(m+1) =: 2X$ yazabiliriz. O zaman $\frac{m^{2}(m+1)^{2}}{2} = 2X^{2}$ olur. Dolayısıyla çalıştığımız denklem $n^{3} - 6Xn^{2} - 2X^{2} = 0$ formunda da ifade edilebilir. Bu ifadede ikinci ve üçüncü terimler çift olduklarından, ilk terim de çift olur.

Genelliği kaybetmeden $n=:2N$ ve daha önce olduğu üzere $m(m+1)=2X$ yazalım. Böylesi bir dönüşümle çalıştığımız denklem \begin{equation*} X^{2} + 12 N^{2} X - 4N^{3} = 0 \end{equation*} halini alır. $X$ bilinmeyen olarak addedildiğinde ikinci dereceden cebirsel denklemler için geçerli çözüm aşağıdaki gibi olur. \begin{equation*} X = 2N \sqrt{9N^{2}+N} - 6N^{2} \end{equation*} $X$ herşeyden önce bir tam sayı olduğu için diskriminanttan gelen köklü ifadenin de bir tam sayı olması gerekir. Ama bunun için gerekli ve yeterli şart $9N^{2}+N=:M^{2}$ bir tam karenin varlığıdır. Şimdi bu denklemi yeniden düzenlediğimizde $N = (M-3N)(M+3N)$ olduğunu görüyoruz. Demek ki $M+3N$, $N$ sayısının bir çarpanıymış. Ama $M+3N>N$ olduğundan böylesi bir durum absurddür. O zaman hiçbir $N$ değeri için $X$ ya da $m(m+1)$ ya da $m$ tam sayı değeri alamazlar. Bu da $a=3$ için ispatı tamamlar.

Ödev

$a=4$ için de ispatı yukarıdaki basamakları taklit ederek kendiniz yapınız.


Sorunun hikayesi

Sosyal medyada sağdan soldan bulduğu şeyleri yeniden paylaşan popüler bir hesapta şöyle fiyakalı bir denklem gördüm: $36^{2}+37^{2}+38^{2}+39^{2}+40^{2}=41^{2}+42^{2}+43^{2}+44^{2}$. Maksat fiyaka yapmak olduğundan denklemin altında yatan formül verilmemişti. Kendim daha sonra aynı denklemin meşhur $3^{2}+4^{2}=5^{2}$ Pisagor üçlüsünün bir genelleştirilmesi olduğunu fark ettim ve başka eşitliklere de uzandım: $10^{2}+11^{2}+12^{2}=13^{2}+14^{2}$ ve $21^{2}+22^{2}+23^{2}+24^{2}=25^{2}+26^{2}+27^{2}$ gibi. Ardından bu formülün kübik ve kuartik versiyonlarını da aramaya başlayınca bu posta hasıl oldu.

Ödev

Yukarıdaki soruda $a=2$ durumunda çözümün $n=2m(m+1)$ ile her zaman mümkün olduğunu gösteriniz.