Własności geometryczne pierwiastków wielomianowych

Aby uzyskać informacje na temat obliczania pierwiastków wielomianowych, zobacz Algorytmy wyszukiwania pierwiastków wielomianowych .

W matematyce jednowymiarowy wielomian stopnia n o rzeczywistych lub zespolonych współczynnikach ma n pierwiastków zespolonych , licząc ich krotności . Tworzą multizbiór n punktów na płaszczyźnie zespolonej . Artykuł dotyczy geometrii tych punktów, czyli informacji o ich położeniu na płaszczyźnie zespolonej, jakie można wywnioskować ze stopnia i współczynników wielomianu.

Niektóre z tych właściwości geometrycznych są związane z pojedynczym wielomianem, na przykład górne granice wartości bezwzględnych pierwiastków, które definiują dysk zawierający wszystkie pierwiastki, lub dolne granice odległości między dwoma pierwiastkami. Takie granice są szeroko stosowane w algorytmach znajdowania pierwiastków dla wielomianów, albo do ich dostrajania, albo do obliczania ich złożoności obliczeniowej .

Niektóre inne właściwości są probabilistyczne, na przykład oczekiwana liczba pierwiastków rzeczywistych losowego wielomianu stopnia n o rzeczywistych współczynnikach, która jest mniejsza niż ${\ Displaystyle 1 + {\ Frac {2} \pi }}\ln(n)}$ dla n wystarczająco dużych.

W tym artykule rozważany wielomian jest zawsze oznaczony

${\ Displaystyle p (x) = a_ {0} + a_ {1} x + \ cdots + a_ {n} x ^ {n},}$

gdzie $\ Displaystyle a_ {0}, \ kropki, a_ {n}}$ są liczbami rzeczywistymi lub zespolonymi i ${\ Displaystyle a_ {n} \ neq 0}$ ; zatem n jest stopniem wielomianu.

Ciągła zależność od współczynników

N pierwiastków wielomianu stopnia n zależy w sposób ciągły od współczynników. W przypadku pierwiastków prostych wynika to bezpośrednio z twierdzenia o funkcji uwikłanej . Dotyczy to również wielu pierwiastków, ale dowód wymaga pewnej uwagi.

Niewielka zmiana współczynników może wywołać dramatyczną zmianę pierwiastków, w tym zmianę pierwiastka rzeczywistego na pierwiastek złożony z dość dużą częścią urojoną (patrz wielomian Wilkinsona ). Konsekwencją jest to, że w przypadku klasycznych numerycznych algorytmów wyszukiwania pierwiastków problem aproksymacji pierwiastków przy danych współczynnikach jest źle uwarunkowany dla wielu danych wejściowych.

Koniugacja

Twierdzenie o złożonym pierwiastku sprzężonym stwierdza, że ​​jeśli współczynniki wielomianu są rzeczywiste, to pierwiastki nierzeczywiste występują parami postaci ( a + ib , a – ib ) .

Wynika z tego, że pierwiastki wielomianu o rzeczywistych współczynnikach są lustrzanie symetryczne względem osi rzeczywistej.

Można to rozszerzyć na koniugację algebraiczną : pierwiastki wielomianu o współczynnikach wymiernych są sprzężone (to znaczy niezmienne) pod działaniem grupy Galois wielomianu. Jednak ta symetria rzadko może być interpretowana geometrycznie.

Granice na wszystkich korzeniach

Górne granice wartości bezwzględnych pierwiastków wielomianowych są szeroko stosowane w algorytmach wyszukiwania pierwiastków, albo do ograniczania regionów, w których należy szukać pierwiastków, albo do obliczania złożoności obliczeniowej tych algorytmów.

Podano wiele takich granic, a ostrzejsze zależy generalnie od określonej sekwencji rozważanych współczynników. Większość granic jest większa lub równa jedności, a zatem nie jest ostra dla wielomianu, który ma tylko pierwiastki o wartościach bezwzględnych mniejszych od jedności. Jednak takie wielomiany są bardzo rzadkie, jak pokazano poniżej.

Każda górna granica wartości bezwzględnych pierwiastków zapewnia odpowiednią dolną granicę. $W$ rzeczywistości, jeśli jest górną granicą pierwiastków

${\ Displaystyle a_ {0} + a_ {1} x + \ cdots + a_ {n} x ^ {n},}$

wtedy 1/ U jest dolną granicą bezwzględnych wartości pierwiastków

${\ Displaystyle a_ {n} + a_ {n-1} x + \ cdots + a_ {0} x ^ {n},}$

ponieważ pierwiastki jednego wielomianu są multiplikatywnymi odwrotnościami pierwiastków drugiego. Dlatego w dalszej części artykułu dolne granice nie będą podawane wprost .

Granice Lagrange'a i Cauchy'ego

Lagrange i Cauchy jako pierwsi podali górne granice wszystkich pierwiastków złożonych. Granica Lagrange'a wynosi

${\ Displaystyle \ max \ lewo \ {1, \ suma _ {i = 0} ^ {n-1} \ lewo | {\ Frac {a_ {i}} {a_ {n}}} \ prawo |\ Prawidłowy\},}$

a granica Cauchy'ego to

${\ Displaystyle 1+ \ max \ lewo \ {\ lewo | {\ Frac {a_ {n-1}} {a_ {n}}} \ prawo |, \ lewo | {\ Frac {a_ {n-2} }{a_{n}}}\right|,\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|\right\}}$

Granica Lagrange'a jest ostrzejsza (mniejsza) niż granica Cauchy'ego tylko wtedy, gdy 1 jest większe niż suma wszystkich ${\ Displaystyle \ lewo | {\ Frac {a_ {i}} {a_ {n}}} \ prawo |},$ ale największy. Jest to stosunkowo rzadkie w praktyce i wyjaśnia, dlaczego granica Cauchy'ego jest szerzej stosowana niż granica Lagrange'a.

Oba ograniczenia wynikają z twierdzenia Gershgorina o okręgu zastosowanego do macierzy towarzyszącej wielomianu i jego transpozycji . Można je również udowodnić metodami elementarnymi.

Dowód granic Lagrange'a i Cauchy'ego

Jeśli z jest pierwiastkiem wielomianu, a | z | ≥ 1 ma ${\ Displaystyle | a_ {n} | | z ^ {n} | = \ lewo | \ suma _ {i = 0} ^ {n-1} a_ {i} z ^ {i} \ prawo | \ równoważnik \ suma _{i=0}^{n-1}|a_{i}z^{i}|\równik \suma _{i=0}^{n-1}|a_{i}||z|^{ n-1}.}$ Dzielenie przez ${\ Displaystyle | a_ {n}|| z | ^ {n-1},}$ dostaje się ${\ Displaystyle | z | \ równoważnik \ suma _ {i = 0} ^ {n-1} {\ Frac {| a_ {i} |} {| a_ {n} |}}$ co jest granicą Lagrange'a, gdy istnieje co najmniej jeden pierwiastek o wartości bezwzględnej większej niż 1. W przeciwnym razie 1 jest granicą pierwiastków i nie jest większa niż granica Lagrange'a. Podobnie, dla ograniczenia Cauchy'ego, mamy, jeśli | z | ≥ 1 , ${\ Displaystyle | a_ {n} | | z ^ {n} | = \ lewo | \ suma _ {i = 0} ^ {n-1} a_ {i} z ^ {i} \ prawo | \ równoważnik \ suma _{i=0}^{n-1}|a_{i}z^{i}|\równik \max |a_{i}|\suma _{i=0}^{n-1}|z| ^{i}={\frac {|z|^{n}-1}{|z|-1}}\max |a_{i}|\leq {\frac {|z|^{n}}{ |z|-1}}\max |a_{i}|.}$ Zatem ${\ Displaystyle | a_ {n} | (| z | -1) \ równoważnik \ maks | a_ {i} |.}$ Rozwiązywanie w | z | , otrzymujemy granicę Cauchy'ego, jeśli istnieje pierwiastek o wartości bezwzględnej większej niż 1. W przeciwnym razie granica jest również poprawna, ponieważ granica Cauchy'ego jest większa niż 1.

Te granice nie są niezmienne przez skalowanie. Oznacza to, że pierwiastki wielomianu p ( sx ) są ilorazem pierwiastka p przez s , a granice podane dla pierwiastków p ( sx ) nie są ilorazem granic p . W ten sposób można uzyskać ostrzejsze granice, minimalizując możliwe skalowania. To daje

${\ Displaystyle \ min _ {s \ w \ mathbb {R} _ {+} }\left(\max \left\{s,\suma _{i=0}^{n-1}\left|{\frac {a_{i}}{a_{n}}}\right|s^ {i-n+1}\prawo\}\prawo),}$

I

${\ Displaystyle \ min _ {s \ w \ mathbb {R} _ {+} }\left(s+\max _{0\leq i\leq n-1}\left(\left|{\frac {a_{i}}{a_{n}}}\right|s^{i-n +1}\prawo)\prawo),}$

odpowiednio dla granic Lagrange'a i Cauchy'ego.

Innym ograniczeniem, pierwotnie nadanym przez Lagrange'a, ale przypisanym Zassenhausowi przez Donalda Knutha , jest

${\ Displaystyle 2 \ max \ lewo \ {\ lewo | {\ Frac {a_ {n-1}}} {a_ {n}}} \ prawo |, \ lewo | {\ Frac {a_ {n-2}}} a_{n}}}\right|^{1/2},\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|^{1/n}\right\ }.}$

Ta granica jest niezmienna przez skalowanie.

Dowód poprzedniej granicy

Niech A będzie największym ${\ Displaystyle \ lewo | {\ Frac {a_ {i}} {a_ {n}}} \ prawo | ^ {\ Frac {1} {ni}}} dla$ for 0 ≤ i < n. Thus one has ${\ Displaystyle {\ Frac {| a_ {i} |} {| a_ {n} |}} \ równoważnik A ^ {ni}}$ dla ${\ Displaystyle 0 \ równoważnik i <n.}$ Jeśli z jest pierwiastkiem z p , jeden ma ${\ Displaystyle -a_ {n} z ^ {n} = \ suma _ {i = 0} ^ {n-1} a_ {i} z ^{i},}$ a więc po podzieleniu przez ${\ displaystyle a_ {n},}$ ${\ Displaystyle {\ rozpocząć {wyrównane} | z | ^ {n} i \ równoważnik \ suma _ {i = 0} ^ {n-1} A ^ {ni} | z | ^ {i} \\& = A {\frac {|z|^{n}-A^{n}}{|z|-A}}.\end{wyrównane}}}$ Jak chcemy udowodnić | z | ≤ 2 A , możemy założyć, że | z | > A (inaczej nie ma czego udowadniać). Zatem ${\ Displaystyle | z | ^ {n} \ równoważnik A {\ Frac {| z | ^ {n}} {| z | -A}}}$ co daje wynik, ponieważ ${\ Displaystyle | z|> A.}$

Lagrange poprawił to ostatnie związane z sumą dwóch największych wartości (prawdopodobnie równych) w sekwencji

${\ Displaystyle \ lewo [\ lewo | {\ Frac {a_ {n-1}} {a_ {n}}} \ prawo |, \ lewo | {\ Frac {a_ {n-2}} {a_ {n} }}\right|^{1/2},\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|^{1/n}\right].}$

Lagrange dostarczył również oprawę

$\ Displaystyle \ suma _ {i} \ lewo | {\ Frac {a_ {i}} {a_ {i + 1}}} \ prawo |,}$

gdzie $oznacza i$ ty niezerowy współczynnik , gdy wyrazy wielomianów są sortowane według rosnących stopni

Korzystanie z nierówności Höldera

Nierówność Höldera pozwala na rozszerzenie granic Lagrange'a i Cauchy'ego na każdą h -normę . Norma h sekwencji

${\ Displaystyle s = (a_ {0}, \ ldots, a_ {n})}$

Jest

$\ Displaystyle \ | s \ | _ {h} = \ lewo (\ suma _ {i = 1} ^ {n} | a_{i}|^{h}\right)^{1/h},}$

dla dowolnej liczby rzeczywistej h ≥ 1 i

${\ Displaystyle \|s \|_ {\ infty} = \ textstyle {\ max _ {i = 1} ^ {n}} | a_ {i} |.}$

Jeśli ${\ Displaystyle {\ Frac {1} {h}} + {\ Frac {1} {k}} = 1}$ z 1 ≤ h , k ≤ ∞ i 1 / ∞ = 0 , górna granica wartości bezwzględnych pierwiastków p wynosi

${\ Displaystyle {\ Frac {1} {| a_ {n} |}} \ lewo \ | (| a_ {n} |, \ lewo \ | (| a_ {n-1} |, \ ldots, | a_ { 0}|\right)\|_{h}\right)\|_{k}.}$

Dla k = 1 i k = ∞ otrzymujemy odpowiednio granice Cauchy'ego i Lagrange'a.

Dla h = k = 2 mamy granicę

${\ Displaystyle {\ Frac {1} {| a_ {n} |}} {\ sqrt {| a_ {n} | ^ {2} + | a_ {n-1} | ^ {2} + \ cdots + | a_{0}|^{2}}}.}$

Jest to nie tylko ograniczenie wartości bezwzględnych pierwiastków, ale także ograniczenie iloczynu ich wartości bezwzględnych większych niż 1; patrz § Nierówność Landaua poniżej.

Dowód

Niech z będzie pierwiastkiem wielomianu ${\ Displaystyle p (x) = a ^ {n} + a_ {n-1} x ^ {n-1} + \ cdots + a_ {1} x + a_ {0}.}$ Ustawienie ${\ Displaystyle A = \ lewo ({\ Frac {| a_ {n -1}|}{|a_{n}|}},\ldots ,{\frac {|a_{1}|}{|a_{n}|}},{\frac {|a_{0}|} {|a_{n}|}}\prawo),}$ musimy udowodnić, że każdy pierwiastek z p spełnia ${\ Displaystyle z \ równoważnik \ lewo \ | (1, \ lewo \ | A \ prawo \ | _ {h} \ prawo) \ | _ {k}.}$ Jeśli ${\ Displaystyle | z | \ równoważnik 1,}$ nierówność jest prawdziwa; więc można przypuszczać ${\ displaystyle | z|> 1}$ dla pozostałej części dowodu. Zapisz równanie jako ${\ Displaystyle -z ^ {n} = {\ Frac {a_ {n-1}}} {a_ {n }}}z^{n-1}+\cdots +{\frac {a_{1}}{a_{n}}}z+a_{0},}$ Nierówność Höldera implikuje ${\ Displaystyle | z | ^ {n} \ równoważnik \| A \ | _ {h} \ cdot \ lewo \ | (z ^ {n-1}, \ ldots, z, 1) \ prawo \ | _ {k }.}$ Jeśli k = 1 , to tak ${\ Displaystyle | z | ^ {n} \ równoważnik \| A \ |_ {1} \ max \ lewo \ {| z | ^ {n-1}, \ ldots, | z |, 1 \ prawo \} = \|A\|_{1}|z|^{n-1}.}$ Zatem ${\ Displaystyle | z | \ równoważnik \ max \ {1, \ | A \ | _ {1} \}.}$ W przypadku 1 < k ≤ ∞ , wzór na sumowanie postępu geometrycznego daje ${\ Displaystyle | z | ^ {n} \ równoważnik \| A \ | _ {h} \ lewo (| z | ^ {k (n-1)} + \ cdots + | z | ^ {k} + 1 \ prawo)^{\frac {1}{k}}=\|A\|_{h}\left({\frac {|z|^{kn}-1}{|z|^{k}-1 }}\right)^{\frac {1}{k}}\leq \|A\|_{h}\left({\frac {|z|^{kn}}{|z|^{k} -1}}\right)^{\frac {1}{k}}.}$ Zatem ${\ Displaystyle | z | ^ {kn} \ równoważnik \ lewo (\| A \ | _ {h} \ prawej) ^ {k} {\ Frac {| z | ^ {kn}} {| z |^{k}-1}},}$ co upraszcza ${\ Displaystyle | z | ^ {k} \ równoważnik 1 + \ lewo (\| A \ | _ {h} \ prawo) ^ {k}.}$ A więc we wszystkich przypadkach ${\ Displaystyle | z | \ równoważnik \ lewo \ | \ lewo (1, \ | A \ | _ {h} \ prawo) \ prawo \ | _ {k} ,}$ co kończy dowód.

Inne granice

Podano wiele innych górnych granic wielkości wszystkich pierwiastków.

Fujiwara jest związana

${\ Displaystyle 2 \, \ max \ lewo \ {\ lewo | {\ Frac {a_ {n-1}} {a_ {n}}} \ prawo |, \ lewo | {\ Frac {a_ { n-2}}{a_{n}}}\right|^{\frac {1}{2}},\ldots ,\left|{\frac {a_{1}}{a_{n}}}\ prawo|^{\frac {1}{n-1}},\lewo|{\frac {a_{0}}{2a_{n}}}\prawo|^{\frac {1}{n}}\ Prawidłowy\},}$ 

nieznacznie poprawia granicę podaną powyżej, dzieląc ostatni argument maksimum przez dwa.

Granica Kojimy to

${\ Displaystyle 2 \, \ max \ lewo \ {\ lewo | {\ Frac {a_ {n-1}} {a_ {n}}} \ prawo |, \ lewo | {\ Frac {a_ {n- 2}}{a_{n-1}}}\prawo|,\ldots ,\lewo|{\frac {a_{0}}{2a_{1}}}\prawo|\prawo\},}$

gdzie $oznacza i$ ty niezerowy współczynnik , gdy wyrazy wielomianów są sortowane według rosnących stopni Jeśli wszystkie współczynniki są niezerowe, granica Fujiwary jest ostrzejsza, ponieważ każdy element w granicy Fujiwary jest średnią geometryczną pierwszych elementów w granicy Kojimy.

Sun i Hsieh uzyskali kolejną poprawę na granicy Cauchy'ego. Załóżmy, że wielomian jest moniczny z wyrazem ogólnym a _i x ⁱ . Sun i Hsieh wykazali, że górne granice 1 + d ₁ i 1 + d ₂ można otrzymać z następujących równań.

${\ Displaystyle d_ {1} = {\ tfrac {1} {2}} \ lewo ((| a_ {n-1} | -1) + {\ sqrt {(| a_ {n-1} | -1) ^{2}+4a}}\right),\qquad a=\max\{|a_{i}|\}.}$

d ₂ jest dodatnim pierwiastkiem równania sześciennego

${\ Displaystyle Q (x) = x ^ {3} + (2- | a_ {n-1} |) x ^ {2} + (1- | a_ {n-1} | - | a_ {n- 2}|)xa,\qquad a=\max\{|a_{i}|\}}$

Zauważyli również, że d ₂ ≤ d ₁ .

Nierówność Landaua

Poprzednie granice są górnymi granicami dla każdego korzenia osobno. Nierówność Landaua zapewnia górną granicę wartości bezwzględnych iloczynu pierwiastków, które mają wartość bezwzględną większą niż jeden. Ta nierówność, odkryta w 1905 roku przez Edmunda Landaua , została zapomniana i ponownie odkryta co najmniej trzy razy w XX wieku.

Ta granica iloczynu pierwiastków jest niewiele większa niż najlepsze poprzednie granice każdego pierwiastka z osobna. Niech ${\ displaystyle z_ {1}, \ ldots, z_ {n}}$ będzie n pierwiastkami wielomianu p . Jeśli

${\ Displaystyle M (p) = | a_ {n} | \ prod _ {j = 1} ^ {n} \ max (1, | z_ {j} |)}$

jest zatem miarą Mahlera p

${\ Displaystyle M (p) \ równoważnik {\ sqrt {\ suma _ {k = 0} ^ {n} | a_ {k} | ^ {2}}}.}$

Co zaskakujące, ta granica iloczynu wartości bezwzględnych większych niż 1 pierwiastków jest niewiele większa niż najlepsze granice jednego pierwiastka podane powyżej dla pojedynczego pierwiastka. Ta granica jest nawet dokładnie równa jednej z granic uzyskanych za pomocą nierówności Höldera .

To ograniczenie jest również przydatne do wiązania współczynników dzielnika wielomianu ze współczynnikami całkowitymi: jeśli

${\ Displaystyle q = \ suma _ {k = 0} ^ {m} b_ {k} x ^ {k}}$

zatem dzielnikiem p

${\ Displaystyle | b_ {m} |\ równoważnik | a_ {n} |,}$

i według wzorów Viety ,

$\ Displaystyle {\ Frac {| b_ {i} |} {| b_ {m} |}} \ równoważnik {\ binom {m} {i}} {\ Frac {M (p)} {| a_ {n }|}},}$

dla ja = 0, ..., m , gdzie ${\ Displaystyle {\ binom {m} {i}}}$ jest współczynnikiem dwumianowym . Zatem

${\ Displaystyle | b_ {i} | \ równoważnik {\ binom {m} {i}} M (p) \ równoważnik {\ binom {m} {i}}} {\ sqrt {\ suma _ {k = 0 }^{n}|a_{k}|^{2}}},}$

I

${\ Displaystyle \ suma _ {i = 0} ^ {m} | b_ {k} | \ równoważnik 2 ^ {m} M (p) \ równoważnik 2 ^ {m} {\ sqrt {\ suma _ {k = 0 }^{n}|a_{k}|^{2}}}.}$

Dyski zawierające niektóre korzenie

Z twierdzenia Rouchégo

Twierdzenie Rouchégo pozwala na zdefiniowanie dysków o środku w punkcie zerowym i zawierających określoną liczbę pierwiastków. Dokładniej, jeśli istnieje dodatnia liczba rzeczywista R i liczba całkowita 0 ≤ k ≤ n taka, że

${\ Displaystyle | a_ {k} | R ^ {k}> | a_ {0} | + \ cdots + | a_ {k-1} | R ^ {k-1} + | a_ {k + 1 }|R^{k+1}+\cdots +|a_{n}|R^{n},}$

wtedy jest dokładnie k pierwiastków, liczonych z krotnością, o wartości bezwzględnej mniejszej niż R .

Dowód

Jeśli ${\ Displaystyle | z | = R,}$ wtedy ${\ Displaystyle {\ rozpocząć {wyrównane} | a_ {0} & + \ cdots + a_ {k-1} z ^ {k-1} + a_ {k + 1} z ^ {k + 1} + \ cdots + a_{n}z^{n}|\\&\równoważnik |a_{0}|+\cdots +|a_{k-1}|R^{k-1}+|a_{k+1}|R ^{k+1}+\cdots +|a_{n}|R^{n}\\&\równoważnik |a_{k}|R^{k}\równik |a_{k}z^{k}| .\end{wyrównane}}}$ Z twierdzenia Rouché wynika to bezpośrednio, że $i$ mają $taką$ samą liczbę pierwiastków o wartościach bezwzględnych liczonych krotnościami Ponieważ ta liczba to k , wynik jest udowodniony.

Powyższy wynik można zastosować, jeśli wielomian

${\ Displaystyle h_ {k} (x) = | a_ {0} | + \ cdots + | a_ {k-1} | x ^ {k-1} - | a_ {k} | x ^ {k} + | a_{k+1}|x^{k+1}+\cdots +|a_{n}|x^{n}.}$

przyjmuje wartość ujemną dla pewnej dodatniej wartości rzeczywistej x .

W dalszej części sekcji załóżmy, że ₀ a ≠ 0 . Jeśli tak nie jest, zero jest pierwiastkiem, a lokalizację innych pierwiastków można zbadać, dzieląc wielomian przez potęgę nieokreśloności, uzyskując wielomian o niezerowym stałym składniku.

Dla k = 0 i k = n reguła znaków Kartezjusza pokazuje , że wielomian ma dokładnie jeden dodatni pierwiastek rzeczywisty. Jeśli i ${0}}$$R_ {0}}$ i są tymi , powyższy wynik pokazuje, że wszystkie pierwiastki spełniają R {\ displaystyle

${\ Displaystyle R_ {0} \ równoważnik | z | \ równoważnik R_ {1}.}$

$i$ te nierówności dotyczą również $sekwencją wartości$ te ich współczynników. Są więc ostrzejsze niż wszystkie granice podane w poprzednich sekcjach.

Dla 0 < k < n , reguła znaków Kartezjusza implikuje, że $każdej$ dwa dodatnie pierwiastki rzeczywiste, które nie są wielokrotnością, albo jest nieujemna x . Tak więc powyższy wynik można zastosować tylko w pierwszym przypadku. R ${\ Displaystyle R_ {k, 1}<R_ {k, 2}} to te dwa pierwiastki$ powyższy wynik implikuje, że

${\ Displaystyle | z | \ równoważnik R_ {k, 1}}$

dla k pierwiastków z p i tyle

${\ Displaystyle | z | \ geq R_ {k, 2}}$

dla n – k innych pierwiastków.

Zamiast jawnego obliczania i $R_ {k,$${\ Displaystyle$ wystarczy obliczyć wartość ${\ Displaystyle R_ {$ takie, że ${\ Displaystyle h_ {k} (R_ {k}) <0}$ (koniecznie ${\ Displaystyle R_ {k, 1 <R_{k<R_{k,2}}$ ). Te mają właściwość oddzielania pierwiastków pod względem ich wartości bezwzględnych: jeśli dla h < k $jak$ zarówno ${\ displaystyle R_ {h}},$ R $\ displaystyle R_ {} k}}$ istnieje, istnieje dokładnie k – h pierwiastków z takich, że ${\ Displaystyle R_ {h}<| z | <R_ {k}.}$

Do obliczeń można $}$ fakt, że R $\ Displaystyle$ { funkcja (jej druga pochodna jest dodatnia). Tak więc $istnieje$ i tylko wtedy $gdy$ unikalnym Do obliczenia tego minimum można użyć dowolnej metody optymalizacji lub alternatywnie metody Newtona do obliczenia unikalnego dodatniego zera pochodnej ${\ Displaystyle {\ Frac {h (x)}} {x ^ { k}}}}$ (jest szybko zbieżny, ponieważ pochodna jest funkcją monotoniczną ).

Można zwiększyć liczbę istniejących, $iteracji$ operację pierwiastka kwadratowego – Graeffe . Jeśli pierwiastki mają różne wartości bezwzględne, można ostatecznie całkowicie oddzielić pierwiastki pod względem ich wartości bezwzględnych, to znaczy obliczyć n + 1 liczb dodatnich ${\ Displaystyle R_ {0}< R_ { 1}<\ kropki <R_ {n}}$ taki, że istnieje dokładnie jeden pierwiastek o wartości bezwzględnej w przedziale otwartym ${\ Displaystyle (R_ {k-1}, R_ {k} ),}$ dla k = 1, ..., n .

Z twierdzenia Gershgorina o okręgu

Twierdzenie Gershgorina o okręgu stosuje towarzyszącą macierz wielomianu na podstawie związanej z interpolacją Lagrange'a w celu zdefiniowania dysków wyśrodkowanych w punktach interpolacji, z których każdy zawiera pierwiastek wielomianu; szczegółowe informacje można znaleźć w metodzie Duranda – Kernera § Inkluzja korzenia przez kręgi Gerschgorina .

Jeśli punkty interpolacji znajdują się blisko pierwiastków pierwiastków wielomianu, promienie dysków są małe i jest to kluczowy składnik metody Duranda-Kernera do obliczania pierwiastków wielomianu.

Granice rzeczywistych korzeni

W przypadku wielomianów o rzeczywistych współczynnikach często przydatne jest ograniczenie tylko rzeczywistych pierwiastków. Wystarczy związać pierwiastki dodatnie, gdyż pierwiastki ujemne p ( x ) są pierwiastkami dodatnimi p ( – x ) .

Oczywiście, każde ograniczenie wszystkich pierwiastków stosuje się również do pierwiastków rzeczywistych. Ale w niektórych kontekstach przydatne są ściślejsze granice rzeczywistych korzeni. Na przykład skuteczność metody ułamków ciągłych do izolacji pierwiastków rzeczywistych silnie zależy od szczelności wiązania pierwiastków dodatnich. Doprowadziło to do ustanowienia nowych granic, które są ściślejsze niż ogólne granice wszystkich korzeni. Granice te są na ogół wyrażane nie tylko w wartościach bezwzględnych współczynników, ale także w postaci ich znaków.

Inne ograniczenia dotyczą tylko wielomianów, których wszystkie pierwiastki są liczbami rzeczywistymi (patrz poniżej).

Granice dodatnich pierwiastków rzeczywistych

Aby podać granicę dodatnich pierwiastków, można założyć $zmiana$ znaków wszystkich współczynników nie zmienia pierwiastków

Każda górna granica dodatnich pierwiastków

${\ Displaystyle q (x) = a_ {n} x ^ {n} + \ suma _ {i = 0} ^{n-1}\min(0,a_{i})x^{i}}$

jest również granicą rzeczywistych zer

$\ Displaystyle p (x) = \ suma _ {i = 0} ^ {n} a_ {i} x ^ {i}}$ .

W rzeczywistości, jeśli B jest takim ograniczeniem, dla wszystkich x > B , jeden ma p ( x ) ≥ q ( x ) > 0 .

Zastosowane do granicy Cauchy'ego daje to górną granicę

${\ Displaystyle 1 + {\ textstyle \ max _ {i = 0} ^ {n-1}} {\ Frac {-a_ {i}}} {a_ {n }}}}$

dla rzeczywistych pierwiastków wielomianu o rzeczywistych współczynnikach. Jeśli ta granica jest nie większa niż 1 , oznacza to, że wszystkie niezerowe współczynniki mają ten sam znak i że nie ma dodatniego pierwiastka.

Podobnie jest z inną górną granicą dodatnich pierwiastków

${\ Displaystyle 2 \, {\ max _ {a_ {i} a_ {n}<0}} \ lewo ({\ Frac {-a_ {i}} {a_ {n}}} \ prawej) ^ {\ frac {1}{ni}}.}$

Jeśli wszystkie niezerowe współczynniki mają ten sam znak, nie ma dodatniego pierwiastka, a maksimum musi wynosić zero.

Ostatnio opracowano inne ograniczenia, głównie dla metody ułamków ciągłych do izolacji pierwiastków rzeczywistych .

Wielomiany, których wszystkie pierwiastki są rzeczywiste

Jeśli wszystkie pierwiastki wielomianu są rzeczywiste, Laguerre udowodnił następujące dolne i górne granice pierwiastków, używając czegoś, co obecnie nazywa się nierównością Samuelsona .

Niech ${\ Displaystyle \ suma _ {k = 0} ^ {n} a_ {k} x ^ {k}}$ będzie wielomianem ze wszystkimi pierwiastkami rzeczywistymi. Wtedy jego pierwiastki znajdują się w przedziale z punktami końcowymi

${\ Displaystyle - {\ Frac {a_ {n-1}} {na_ {n}}} \ pm {\ Frac {n-1} {na_ {n}}} {\ sqrt {a_ {n-1} ^ {2}-{\frac {2n}{n-1}}a_{n}a_{n-2}}}.}$

Na przykład pierwiastki wielomianu ${\ Displaystyle x ^ { 4}+5x^{3}+5x^{2}-5x-6=(x+3)(x+2)(x+1)(x-1)}$ spełnia

${\ Displaystyle -3,8118 <- {\ Frac {5} {4}} - {\ Frac {3} {4}}} {\ sqrt {\ Frac {35} {3}}} \ równoważnik x \ równoważnik - {\ frac {5}{4}}+{\frac {3}{4}}{\sqrt {\frac {35}{3}}}<1.3118.}$

Separacja korzeni

Separacja pierwiastków wielomianu to minimalna odległość między dwoma pierwiastkami, czyli minimum bezwzględnych wartości różnicy dwóch pierwiastków:

${\ Displaystyle \ nazwa operatora {sep} (p) = \ min \ {| \ alfa - \ beta | \;; \; \ alfa \ neq \ beta { \text{ i }}p(\alpha)=p(\beta)=0\}}$

Separacja pierwiastków jest podstawowym parametrem złożoności obliczeniowej algorytmów znajdowania pierwiastków dla wielomianów. W rzeczywistości separacja pierwiastków określa precyzję reprezentacji liczb, która jest potrzebna, aby mieć pewność rozróżnienia różnych pierwiastków. Ponadto w przypadku izolacji pierwiastków rzeczywistych umożliwia to ograniczenie liczby podziałów interwałów potrzebnych do wyizolowania wszystkich pierwiastków.

W przypadku wielomianów o współczynnikach rzeczywistych lub zespolonych nie jest możliwe wyrażenie dolnej granicy separacji pierwiastków wyłącznie w kategoriach stopnia i wartości bezwzględnych współczynników, ponieważ niewielka zmiana pojedynczego współczynnika przekształca wielomian z wieloma pierwiastkami w wielomian bezkwadratowy z małą separacją pierwiastków i zasadniczo tymi samymi bezwzględnymi wartościami współczynnika. Jednak uwzględnienie dyskryminatora wielomianu pozwala na dolną granicę.

W przypadku wielomianów bezkwadratowych o współczynnikach całkowitych wyróżnikiem jest liczba całkowita, a zatem ma wartość bezwzględną nie mniejszą niż 1 . Pozwala to na dolne granice separacji korzeni, które są niezależne od dyskryminatora.

Granica separacji Mignotte'a to

${\ Displaystyle \ operatorname {sep} (p)> {\ Frac {\ sqrt {3 | \ Delta (p) |}} {n ^ {(n+1)/2}(\|p\|_{2})^{n-1}}},}$

gdzie ${\ Displaystyle \ Delta (p)}$ jest wyróżnikiem i ${\ Displaystyle \ textstyle \| p \ |_ {2} = {\ sqrt {a_ {0} ^ {2} + a_ {1} ^ {2} + \ kropki + a_ {n} ^ {2}}} .}$

W przypadku wielomianu swobodnego do kwadratu ze współczynnikami całkowitymi oznacza to

${\ Displaystyle \ operatorname {sep} (p)> {\ Frac {\ sqrt {3} }{n^{n/2+1}(\|p\|_{2})^{n-1}}}>{\frac {1}{2^{2s^{2}}}}, }$

gdzie s jest rozmiarem bitowym p , czyli sumą rozmiaru bitowego jego współczynników.

Twierdzenie Gaussa-Lucasa

Główny artykuł: twierdzenie Gaussa – Lucasa

Twierdzenie Gaussa-Lucasa stwierdza, że ​​wypukła otoczka pierwiastków wielomianu zawiera pierwiastki pochodnej wielomianu .

Czasami przydatnym wnioskiem jest to, że jeśli wszystkie pierwiastki wielomianu mają dodatnią część rzeczywistą, to tak samo pierwiastki wszystkich pochodnych wielomianu.

Powiązanym wynikiem jest nierówność Bernsteina . Stwierdza, że ​​dla wielomianu P stopnia n z pochodną P′ mamy

${\ Displaystyle \ max _ {| z | \ równoważnik 1} {\ duży |} P' (z) {\ duży |} \ równoważnik n \ max _ {| z | \ równoważnik 1} {\ duży |} P ( z) {\duży |}.}$

Rozkład statystyczny korzeni

Jeśli współczynniki a _i losowego wielomianu mają niezależny i identyczny rozkład ze średnią równą zero, najbardziej złożone pierwiastki znajdują się na okręgu jednostkowym lub blisko niego. W szczególności pierwiastki rzeczywiste znajdują się najczęściej w pobliżu ±1 , a ponadto ich oczekiwana liczba jest w dużym stopniu mniejsza od logarytmu naturalnego stopnia.

Jeśli współczynniki mają rozkład Gaussa ze średnią zerową i wariancją σ , to średnia gęstość pierwiastków rzeczywistych jest określona wzorem Kac

${\ Displaystyle m (x) = {\ Frac {\ sqrt {A (x) C (x) -B ( x)^{2}}}{\pi A(x)}}}$

Gdzie

${\ Displaystyle {\ rozpocząć {wyrównane} A (x) & = \ sigma \ suma _ {i = 0} ^ {2n-1} x ^ {i} = \ sigma {\ Frac {x ^ {2n} -1 }{x-1}},\\B(x)&={\frac {1}{2}}{\frac {d}{dx}}A(x),\\C(x)&={ \frac {1}{4}}{\frac {d^{2}}{dx^{2}}}A(x)+{\frac {1}{4x}}{\frac {d}{dx }}A(x).\end{wyrównane}}}$

Gdy współczynniki mają rozkład Gaussa z niezerową średnią i wariancją σ , znany jest podobny, ale bardziej złożony wzór.

Prawdziwe korzenie

Dla dużego n średnia gęstość rzeczywistych pierwiastków w pobliżu x jest asymptotyczna

${\ Displaystyle m (x) = {\ Frac {1} {\ pi | 1-x ^ {2} |}}}$

jeśli ${\ Displaystyle x ^ {2} -1 \ neq 0,}$ i

${\ Displaystyle m (\ pm 1) = {\ Frac {1} {\ pi}} {\ sqrt {\ Frac {n ^ {2} -1} 12}}}}$

Wynika z tego, że oczekiwana liczba rzeczywistych pierwiastków wynosi, używając notacji dużego O

${\ Displaystyle N_ {n} = {\ Frac {2} {\ pi}} \ ln n + C + {\ Frac {2 }{\pi n}}+O(n^{-2})}$

gdzie C jest stałą w przybliżeniu równą 0,625 735 8072 .

Innymi słowy, oczekiwana liczba rzeczywistych pierwiastków losowego wielomianu wysokiego stopnia jest mniejsza niż logarytm naturalny stopnia .

Kac, Erdős i inni wykazali, że wyniki te są niewrażliwe na rozkład współczynników, jeśli są one niezależne i mają ten sam rozkład ze średnią zerową. Jeśli jednak wariancja i- tego współczynnika jest równa ${\ displaystyle {\ binom {n} {i}}},$ oczekiwana liczba pierwiastków rzeczywistych wynosi ${\ displaystyle {\ sqrt {n}}.}$

Geometria wielu korzeni

Wielomian można zapisać w postaci ${\ displaystyle p}$

${\ Displaystyle p (x) = a (xz_ {1}) ^ {m_ {1}} \ cdots ( x-z_{k})^{m_{k}}}$

z różnymi pierwiastkami $m_ {k$ odpowiednimi krotnościami $ldots$ . Korzeń ${\ Displaystyle z_ {j}}$ jest prostym pierwiastkiem , jeśli ${\ Displaystyle m_ {j} = 1}$ lub wielokrotnym pierwiastkiem , jeśli ${\ Displaystyle m_ {j} \ geq 2 }$ . Proste pierwiastki są ciągłe Lipschitza pod względem współczynników, ale pierwiastki wielokrotne nie są. Innymi słowy, pierwiastki proste mają ograniczoną czułość, ale pierwiastki wielokrotne są nieskończenie czułe, jeśli współczynniki są dowolnie zaburzane. W rezultacie większość algorytmów wyszukiwania pierwiastków cierpi na znaczną utratę dokładności wielu pierwiastków w obliczeniach numerycznych.

W 1972 roku William Kahan udowodnił, że istnieje wrodzona stabilność wielu korzeni. Kahan odkrył, że wielomiany o określonym zbiorze wielokrotności tworzą coś, co nazwał rozmaitością pejoratywną, i udowodnił, że pierwiastek wielokrotny jest ciągły Lipschitza , jeśli zaburzenie zachowuje swoją wielość.

Ta geometryczna właściwość wielu pierwiastków jest kluczowa w obliczeniach numerycznych wielu pierwiastków .

Zobacz też

• Reguła znaków Kartezjusza - Związek między liczbą dodatnich pierwiastków wielomianu a znakami jego współczynników
• Twierdzenie Mardena - O zerach pochodnych wielomianów sześciennych
• Tożsamości Newtona – Relacje między sumami mocy a elementarnymi funkcjami symetrycznymi
• Funkcja kwadratowa # Górna granica wielkości pierwiastków
• Izolacja pierwiastków rzeczywistych - Metody lokalizowania pierwiastków rzeczywistych wielomianu
• Znajdowanie pierwiastków wielomianów - Algorytmy znajdowania zer wielomianów
• Wielomian bez kwadratów - wielomian bez powtarzającego się pierwiastka
• Wzory Viety – Powiązanie współczynników i pierwiastków wielomianu

Notatki

•    Rahman, QI; Schmeisser, G. (2002). Analityczna teoria wielomianów . Monografie Londyńskiego Towarzystwa Matematycznego. Nowa seria. Tom. 26. Oksford: Oxford University Press . ISBN 0-19-853493-0 . Zbl 1072.30006 .
•   Yap, Chee-Keng (2000). Podstawowe problemy algebry algorytmicznej (PDF) . Oxford University Press . ISBN 978-0195125160 . .

Linki zewnętrzne

• Piękno pierwiastków , wizualizacja rozkładu wszystkich pierwiastków wszystkich wielomianów ze współczynnikami stopni i całkowitymi w pewnym zakresie.