Lehmer – Schurův algoritmus - Lehmer–Schur algorithm

v matematika, Lehmer – Schurův algoritmus (pojmenoval podle Derrick Henry Lehmer a Issai Schur ) je algoritmus hledání kořenů pro složité polynomy, rozšiřující myšlenku uzavření kořenů jako v jednorozměrném metoda půlení do složité roviny. Využívá Schur-Cohnův test k testování stále menších disků na přítomnost nebo nepřítomnost kořenů.

Schur-Cohnův algoritmus

Tento algoritmus umožňuje najít distribuci kořenů komplexního polynomu vzhledem k jednotkový kruh v komplexní rovině.^[1][2][3] Je založen na dvou pomocných polynomech, které zavedl Schur.^[4]

Pro složitý polynom ${ displaystyle p}$ z stupeň ${ displaystyle n}$ své reciproční adjunktový polynom ${ displaystyle p ^ {*}}$ je definováno ${ displaystyle p ^ {*} (z) = z ^ {n} { overline {p ({ bar {z}} ^ {- 1})}}}$ a jeho Schurtransform ${ displaystyle Tp}$ podle

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

kde sloupec označuje komplexní konjugace.

Takže když ${ displaystyle p (z) = a_ {n} z ^ {n} + cdots + a_ {1} z + a_ {0}}$ s ${ displaystyle a_ {n} neq 0}$, pak${ displaystyle p ^ {*} (z) = { bar {a}} _ {0} z ^ {n} + { bar {a}} _ {1} z ^ {n-1} + cdots + { bar {a}} _ {n}}$,s vedoucí nulové termíny, pokud existují, odstraněny. The koeficienty z ${ displaystyle Tp}$ lze tedy přímo vyjádřit v těch z ${ displaystyle p}$ a protože jeden nebo více hlavních koeficientů se ruší, ${ displaystyle Tp}$ má nižší stupeň než ${ displaystyle p}$. Kořeny ${ displaystyle p}$, ${ displaystyle p ^ {*}}$, a ${ displaystyle Tp}$ souvisí takto.

Lemma

Nechat ${ displaystyle p}$ být složitým polynomem a ${ displaystyle delta = (Tp) (0)}$.

• Kořeny ${ displaystyle p ^ {*}}$, včetně jejich multiplicity, jsou obrázky pod inverze v jednotkovém kruhu nenulových kořenů ${ displaystyle p}$.
• Li ${ displaystyle delta neq 0}$, pak ${ displaystyle p, , p ^ {*}}$, a ${ displaystyle Tp}$ sdílet kořeny na jednotkovém kruhu, včetně jejich multiplicit.
• Li ${ displaystyle delta> 0}$, pak ${ displaystyle p}$ a ${ displaystyle Tp}$ mít stejný počet kořenů uvnitř jednotkového kruhu.
• Li ${ displaystyle delta <0}$, pak ${ displaystyle p ^ {*}}$ a ${ displaystyle Tp}$ mít stejný počet kořenů uvnitř jednotkového kruhu.

Důkaz

Pro ${ displaystyle z neq 0}$ my máme ${ displaystyle p ^ {*} (z) = z ^ {n} { overline {p (z / | z | ^ {2})}}}$ a zejména${ displaystyle | p ^ {*} (z) | = | p (z) |}$ pro ${ displaystyle | z | = 1}$.Taky ${ displaystyle delta neq 0}$ naznačuje ${ displaystyle | p (0) | neq | p ^ {*} (0) |}$. Z toho a z definic výše vyplývají první dva výroky. Další dva výroky jsou důsledkem Rouchéova věta aplikován na kruh jednotek na funkce ${ displaystyle { overline {p (0)}} p (z) / r (z)}$ a ${ displaystyle - { overline {p ^ {*} (0)}} p ^ {*} (z) / r (z)}$ , kde ${ displaystyle r}$ je polynom, jehož kořeny mají kořeny ${ displaystyle p}$ na jednotkové kružnici se stejnou multiplicitou. □

Pro přístupnější reprezentaci lemmatu, let ${ displaystyle n_ {p} ^ {-}, n_ {p} ^ {0}}$, a ${ displaystyle n_ {p} ^ {+}}$ označte počet kořenů ${ displaystyle p}$ uvnitř, na a mimo kruh jednotky a podobně pro ${ displaystyle Tp}$.Navíc nechte ${ displaystyle d}$ být rozdíl ve stupni ${ displaystyle p}$ a ${ displaystyle Tp}$. Potom to lemma naznačuje${ displaystyle (n_ {p} ^ {-}, ; n_ {p} ^ {0}, ; n_ {p} ^ {+}) = (n_ {Tp} ^ {-}, ; n_ { Tp} ^ {0}, ; n_ {Tp} ^ {+} + d)}$ -li ${ displaystyle delta> 0}$ a${ displaystyle (n_ {p} ^ {-}, ; n_ {p} ^ {0}, ; n_ {p} ^ {+}) = (n_ {Tp} ^ {+} + d, ; n_ {Tp} ^ {0}, ; n_ {Tp} ^ {-})}$ -li ${ displaystyle delta <0}$(všimněte si výměny ${ displaystyle ^ {+}}$ a ${ displaystyle ^ {-}}$).

Nyní zvažte posloupnost polynomů ${ displaystyle T ^ {k} p}$ ${ displaystyle (k = 0,1, ldots)}$, kde ${ displaystyle T ^ {0} p = p}$ a ${ displaystyle T ^ {k + 1} p = T (T ^ {k} p)}$. Aplikace výše uvedeného na každou dvojici po sobě jdoucích členů této sekvence dává následující výsledek.

Věta [Schur-Cohnův test]

Nechat ${ displaystyle p}$ být složitý polynom s ${ displaystyle Tp neq 0}$ a nechte ${ displaystyle K}$ být nejmenší takové číslo ${ displaystyle T ^ {K + 1} p = 0}$. Navíc nechte ${ displaystyle delta _ {k} = (T ^ {k} p) (0)}$ pro ${ displaystyle k = 1, ldots, K}$ a ${ displaystyle d_ {k} = deg T ^ {k} p}$ pro ${ displaystyle k = 0, ldots, K}$.

• Všechny kořeny ${ displaystyle p}$ ležet uvnitř kruhu jednotky právě tehdy

${ displaystyle delta _ {1} <0}$, ${ displaystyle delta _ {k}> 0}$ pro ${ displaystyle k = 2, ldots, K}$, a ${ displaystyle d_ {K} = 0}$.

• Všechny kořeny ${ displaystyle p}$ ležet mimo kruh jednotek právě tehdy

${ displaystyle delta _ {k}> 0}$ pro ${ displaystyle k = 1, ldots, K}$ a ${ displaystyle d_ {K} = 0}$.

• Li ${ displaystyle d_ {K} = 0}$ a pokud ${ displaystyle delta _ {k} <0}$ pro ${ displaystyle k = k_ {0}, k_ {1} ldots k_ {m}}$ (ve vzestupném pořadí) a ${ displaystyle delta _ {k}> 0}$ jinak tedy ${ displaystyle p}$ nemá žádné kořeny na jednotkové kružnici a počet kořenů ${ displaystyle p}$ uvnitř jednotkového kruhu je

${ displaystyle sum _ {i = 0} ^ {m} (- 1) ^ {i} d_ {k_ {i} -1}}$.

Obecněji distribuce kořenů polynomu ${ displaystyle p}$ pokud jde o libovolný kruh v komplexní rovině, řekněme jeden se středem ${ displaystyle c}$ a poloměr ${ displaystyle rho}$, lze nalézt aplikací Schur-Cohnova testu na „posunutý a zmenšený“ polynom ${ displaystyle q}$ definován ${ Displaystyle q (z) = p (c + rho , z)}$.

Ne každý faktor škálování je povolen, nicméně u Schur-Cohnova testu lze na polynom použít ${ displaystyle q}$ pouze pokud nenastane žádná z následujících rovností: ${ displaystyle T ^ {k} q (0) = 0}$ pro některé ${ displaystyle k = 1, ldots K}$ nebo ${ displaystyle T ^ {K + 1} q = 0}$ zatímco ${ displaystyle d_ {K}> 0}$. Nyní koeficienty polynomů ${ displaystyle T ^ {k} q}$ jsou polynomy v ${ displaystyle rho}$ a uvedené rovnosti vedou k polynomiálním rovnicím pro ${ displaystyle rho}$, které proto drží pouze konečně mnoho hodnot ${ displaystyle rho}$. Vhodný měřítkový faktor lze tedy vždy najít, dokonce i libovolně blízko ${ displaystyle 1}$.

Lehmerova metoda

Lehmersova metoda je následující.^[5]Pro daný komplexní polynom ${ displaystyle p}$pomocí Schur-Cohnova testu lze najít kruhový disk dostatečně velký, aby obsahoval všechny kořeny ${ displaystyle p}$. Dále může být tento disk zakryt sadou překrývajících se menších disků, z nichž jeden je umístěn soustředně a zbývající jsou rovnoměrně rozprostřeny přes mezikruží, které je ještě třeba zakrýt. Z této sady, při opětovném použití testu, disky neobsahující žádný root z ${ displaystyle p}$ lze odstranit. U každého ze zbývajících disků lze tento postup zakrytí a odebrání opakovat, a tedy libovolněkrát, což má za následek sadu libovolně malých disků, které společně obsahují všechny kořeny ${ displaystyle p}$.

Výhodou metody je, že sestává z opakování jedné procedury a že všechny kořeny jsou nalezeny současně, ať už jsou skutečné nebo složité, jednoduché, vícenásobné nebo seskupené. Také deflace, tj. Odstranění již nalezených kořenů, není nutná a každý test začíná plně přesným původním polynomem. A je pozoruhodné, že tento polynom nikdy nemusel být hodnocen.

Čím menší jsou disky, tím více se budou koeficienty odpovídajících „zmenšených“ polynomů lišit v relativní velikosti. To může způsobit přetečení nebo podtečení počítačových výpočtů, čímž se omezí poloměry disků zespodu a tím přesnost vypočítaných kořenů.^[2].^[6]Aby se zabránilo extrémnímu škálování, nebo jen z důvodu efektivity, je možné začít s testováním řady soustředných disků na počet zahrnutých kořenů a tím zmenšit oblast, kde se kořeny vyskytují, na řadu úzkých, soustředných mezikruží. Opakováním tohoto postupu s dalším centrem a kombinací výsledků se uvedená oblast stává unií křižovatek takových annuli.^[7]Nakonec, když se najde malý disk, který obsahuje jeden kořen, lze tento kořen dále aproximovat pomocí jiných metod, např Newtonova metoda.

Reference