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.