Twierdzenie Budana

W matematyce twierdzenie Budana jest twierdzeniem służącym do ograniczania liczby pierwiastków rzeczywistych wielomianu w przedziale i obliczania parzystości tej liczby. Została ona opublikowana w 1807 roku przez François Budan de Boislaurent .

Podobne twierdzenie zostało niezależnie opublikowane przez Josepha Fouriera w 1820 r. Każde z tych twierdzeń jest następstwem drugiego. Stwierdzenie Fouriera pojawia się częściej w literaturze XIX wieku i jest określane jako twierdzenie Fouriera , Budana – Fouriera , Fouriera – Budana , a nawet twierdzenie Budana

Oryginalna formuła Budana jest używana w szybkich nowoczesnych algorytmach izolacji wielomianów z pierwiastkiem rzeczywistym .

Odmiana znaku

Niech $\ displaystyle c_ {0}, c_ {1}, c_ {2}, \ ldots c_ {k}}$ będzie skończoną sekwencją liczb rzeczywistych do Odmianą znaku lub zmianą znaku w sekwencji jest para indeksów $ja < j$ taka, że do ${\ Displaystyle c_ {i} c_ {j}<0,}$ ${\ Displaystyle c_ {k} = 0}$ j $= ja + 1$ lub dla wszystkich $k$ takich, że $ja < k < j$ .

Innymi słowy, zmiana znaku występuje w sekwencji w każdym miejscu, w którym znaki się zmieniają, przy ignorowaniu zer.

Do badania pierwiastków rzeczywistych wielomianu można użyć liczby odmian znaku kilku ciągów. W przypadku twierdzenia Budana jest to sekwencja współczynników. Dla twierdzenia Budana-Fouriera jest to ciąg wartości kolejnych pochodnych w punkcie. Dla twierdzenia Sturma jest to ciąg wartości w punkcie ciągu Sturma .

Reguła znaków Kartezjusza

Wszystkie wyniki opisane w tym artykule są oparte na zasadzie znaków Kartezjusza.

Jeżeli $p (x)$ jest wielomianem jednowymiarowym o rzeczywistych współczynnikach, oznaczmy przez $# + (p)$ liczbę jego dodatnich pierwiastków rzeczywistych, liczoną z ich krotnością, a przez $v (p)$ liczbę zmian znaku w ciągu jego współczynniki. Potwierdza to reguła znaków Kartezjusza

v (p) - # + (p)

jest nieujemną parzystą liczbą całkowitą.

W szczególności, jeśli $v (p) \leq 1$ , to mamy $# + (p) = v (p)$ .

oświadczenie Budana

Mając jednowymiarowy wielomian $p (x)$ o rzeczywistych współczynnikach, oznaczmy przez $# (ℓ, r] (p)$ liczbę pierwiastków rzeczywistych, liczoną ich wielokrotnościami, z $p$ w przedziale półotwartym $(ℓ, r]$ ( gdzie $ℓ < r$ liczb rzeczywistych). Oznaczmy także przez $v h (p)$ liczbę zmian znaku w ciągu współczynników wielomianu $p h (x) = p (x + h)$ . W szczególności mamy $0 v (p) = v (p)$ z zapisem z poprzedniej sekcji.

Twierdzenie Budana jest następujące:

{\ Displaystyle v _ {\ ell} (p) -v_ {r} (p) - \ # _ {(\ ell, r]}}

jest nieujemną parzystą liczbą całkowitą.

Ponieważ ${\ Displaystyle \ # _ {(\ ell, r]}}$ nie jest ujemne, implikuje to $\ Displaystyle v _ {\ ell} (p )\geq v_{r}(p).}$

Jest to uogólnienie reguły znaków Kartezjusza, ponieważ jeśli wybierzemy $r$ wystarczająco duże, jest ono większe niż wszystkie rzeczywiste pierwiastki $p$ i wszystkie współczynniki ${\ displaystyle p_ {r} (x) }$ są dodatnie, to znaczy ${\ displaystyle v_ {r} (p) = 0.}$ Zatem ${\ displaystyle v_ { 0} (p) = v_ {0} (p) -v_ {r} (p)}$ i ${\ Displaystyle \ #_ {+} = \ # _ {(0, r)},}$ , co sprawia, że reguła znaków Kartezjusza jest szczególnym przypadkiem twierdzenia Budana.

Jeśli chodzi o regułę znaków Kartezjusza, jeśli ma się ${\ Displaystyle \ # _ {(\ ell, r]} = v _ {\ ell} (p) -v_ {r} (p). }$ ${\ Displaystyle v_ {\ ell} (p) -v_ {r} (p) \ równoważnik 1}$ Oznacza to, że jeśli ${\ Displaystyle v_ {\ ell} (p) -v_ {r} (p) \ równoważnik 1}$ jeden ma „test pierwiastka zerowego ” i „test jednego korzenia”.

Przykłady

1. Biorąc pod uwagę wielomian ${\ Displaystyle p (x) = x ^ {3} -7x + 7,}$ i przedział otwarty ${\ Displaystyle (0 ,2)}$ , jeden ma

{\ Displaystyle {\ rozpocząć {wyrównane} p (x + 0) i = p (x) = x ^ {3} -7x + 7 \\ p (x + 2) i = (x + 2) ^ {3} -7(x+2)+7=x^{3}+6x^{2}+5x+1\end{wyrównane}}.}

Zatem ${\ Displaystyle v_ {0} (p) -v_ {2} (p) = 2-0 = 2,}$ i twierdzenie Budana stwierdza, że wielomian $rzeczywistych w$ przedziale ${\ Displaystyle (0,2).}$

2. Z tym samym wielomianem ma się ${\ Displaystyle p (x) = x ^ {3} -7x + 7}$

{\ Displaystyle p (x + 1) = (x + 1) ^{3}-7(x+1)+7=x^{3}+3x^{2}-4x+1.}

Zatem ${\ Displaystyle v_ {0} (p) -v_ {1} (p) = 2-2 = 0,}$ i twierdzenie Budana stwierdza, że wielomian nie ma rzeczywistego pierwiastka w otwartym przedziale ${\ displaystyle (0,1).}$ ${\ displaystyle p (x)}$ To jest przykład użycia twierdzenia Budana jako testu pierwiastka zerowego.

stwierdzenie Fouriera

Twierdzenie Fouriera o wielomianowych pierwiastkach rzeczywistych , zwane także twierdzeniem Fouriera – Budana lub twierdzeniem Budana – Fouriera (czasami po prostu twierdzeniem Budana ) jest dokładnie takie samo jak twierdzenie Budana, z wyjątkiem tego, że dla $h = l$ i $r$ sekwencja współczynników $p (x + h)$ jest zastępowane przez sekwencję pochodnych $p$ w $h$ .

Każde twierdzenie jest następstwem drugiego. Wynika to z rozwinięcia Taylora

{\ Displaystyle p (x) = \ suma _ {i = 0} ^ {\ stopień p} {\ Frac {p ^ {(i)} (h)} {i!}} (xh )^{i}}

wielomianu $p$ w $h$ $_$ $że_$ współczynnik $x ja$ w $p (x + h)$ jest ilorazem , liczba dodatnia. Zatem ciągi rozważane w twierdzeniu Fouriera iw twierdzeniu Budana mają taką samą liczbę wariacji znaku.

Ten silny związek między tymi dwoma twierdzeniami może wyjaśniać kontrowersje dotyczące pierwszeństwa, które miały miejsce w XIX wieku, oraz użycie kilku nazw dla tego samego twierdzenia. We współczesnym użyciu do obliczeń komputerowych twierdzenie Budana jest ogólnie preferowane, ponieważ ciągi mają znacznie większe współczynniki w twierdzeniu Fouriera niż w twierdzeniu Budana, ze względu na czynnik silni.

Dowód

Ponieważ każde twierdzenie jest następstwem drugiego, wystarczy udowodnić twierdzenie Fouriera.

Rozważmy więc wielomian $p (x)$ i przedział $(l, r)$ . Gdy wartość $x$ rośnie od $l$ do $r$ , liczba zmian znaku w ciągu pochodnych $p$ może się zmienić tylko wtedy, gdy wartość $x$ przechodzi przez pierwiastek z $p$ lub jedną z jego pochodnych.

Oznaczmy przez $f$ wielomian $p$ lub dowolną jego pochodną. Dla dowolnego pierwiastka $m$ $z$ krotności $f$ , jest $przybliżony$ $pobliżu$ h $przez$ pewną stałą Ponadto, dla $i = 1, ..., m$ , jego $i-$ ta pochodna jest przybliżona przez ${\ Displaystyle \ textstyle a (xh) ^ {mi} \ prod _ {j = 1} ^ {i} (mj + 1).} Wynika z tego, że w sekwencji$ utworzonej przez $f$ i jego $m$ pierwsze pochodne, istnieje $m$ odmian znaku dla $x < h$ i zero dla $x \geq h$ .

Pokazuje to, że gdy $x$ rośnie i przechodzi przez pierwiastek z krotności $m$ $,$ to liczba zmian znaku w sekwencji pochodnej maleje o $m$ .

Teraz, dla $ja > 0$ , niech $h$ będzie pierwiastkiem z $i$ -tej pochodnej ${\ Displaystyle f = p ^ {(i)}}$ z $p$ , który nie jest pierwiastkiem z ${\ displaystyle p ^ {(i-1)}.}$ Należy rozważyć dwa przypadki. Jeśli krotność $m$ pierwiastka $h$ jest parzysta, to ${\ Displaystyle f = p ^ {(i)}}$ i ${\ Displaystyle p ^ {(i-1)} }$ zachowaj stały znak, gdy $x$ przechodzi przez $h$ . Oznacza to, że liczba znaków zmienności w ciągu pochodnych zmniejsza się o liczbę parzystą $m$ . Z drugiej strony, jeśli $m jest$ $zmiany$ , znaku w $h$ , podczas gdy $-1)}}$ $p ^ {($ nie. Istnieje zatem $m + 1$ odmian znaku.

Podsumowując, liczba odmian znaku maleje o $m$ , jeśli $m$ jest parzyste, i o $m + 1,$ jeśli $m$ jest nieparzyste, a parzyste liczby w obu przypadkach.

Historia

Problem liczenia i lokalizowania pierwiastków rzeczywistych wielomianu zaczął być systematycznie badany dopiero na początku XIX wieku.

W 1807 roku François Budan de Boislaurent odkrył metodę rozszerzenia reguły znaków Kartezjusza — ważnej dla przedziału $(0, + \infty)$ — na dowolny przedział.

Joseph Fourier opublikował podobne twierdzenie w 1820 roku, nad którym pracował przez ponad dwadzieścia lat.

Ze względu na podobieństwo między tymi dwoma twierdzeniami istniała kontrowersja dotycząca pierwszeństwa, pomimo faktu, że oba twierdzenia zostały odkryte niezależnie. Ogólnie rzecz biorąc, sformułowanie i dowód Fouriera były używane w XIX wieku w podręcznikach teorii równań .

Używany w XIX wieku

Twierdzenia Budana i Fouriera wkrótce uznano za bardzo ważne, chociaż nie rozwiązują one całkowicie problemu obliczania liczby pierwiastków rzeczywistych wielomianu w przedziale. Problem ten został całkowicie rozwiązany w 1827 roku przez Sturma .

Chociaż twierdzenie Sturma nie jest oparte na regułach znaków Kartezjusza , twierdzenia Sturma i Fouriera są powiązane nie tylko przez użycie liczby wariacji znaku ciągu liczb, ale także przez podobne podejście do problemu. Sturm sam przyznał, że inspirował się metodami Fouriera: „C'est en m'appuyant sur les principes qu'il a posés, et en imitant ses demonstrations, que j'ai trouvé les nouveaux théorèmes que je vais énoncer. » co przekłada się na « Opierając się na zasadach, które przedstawił i naśladując jego dowody, znalazłem nowe twierdzenia, które mam zamiar przedstawić. »

Z tego powodu w XIX wieku twierdzenia Fouriera i Sturma pojawiły się razem w prawie wszystkich książkach o teorii równań.

Fourier i Budan pozostawili otwartą kwestię zmniejszenia wielkości przedziałów, w których przeszukiwane są pierwiastki w taki sposób, aby ostatecznie różnica między liczbą odmian znaku wynosiła co najwyżej jeden, co pozwala stwierdzić, że końcowe przedziały zawierają co najwyżej jeden pierwiastek każdy. Problem ten rozwiązał w 1834 roku Alexandre Joseph Hidulph Vincent. Z grubsza mówiąc, twierdzenie Vincenta polega na użyciu ułamków ciągłych do zastąpienia liniowych transformacji zmiennej Budana przez transformacje Möbiusa .

Twierdzenia Budana, Fouriera i Vincenta popadły w zapomnienie pod koniec XIX wieku. Ostatnim autorem wymieniającym te twierdzenia przed drugą połową XX wieku jest Joseph Alfred Serret . Zostały one ponownie wprowadzone w 1976 roku przez Collinsa i Akritasa za dostarczenie w algebrze komputerowej wydajnego algorytmu do izolacji pierwiastków rzeczywistych na komputerach.

Zobacz też

Linki zewnętrzne

O'Connor, John J.; Robertson, Edmund F. , „Budan de Boislaurent” , archiwum MacTutor History of Mathematics , University of St Andrews