Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Twierdzenie Sturma a pierwiastki wielomianu
102 views
Skip to first unread message
Borneq
Nov 1, 2016, 5:20:39 PM11/1/16
to
Chciałem wyznaczyć wszystkie pierwiastki wielomianu. Najpierw ich
liczbę: w(koniec duzego przedzialu) - w (początek duzego przedzialu)
https://pl.wikipedia.org/wiki/Twierdzenie_Sturma
Jeśli będzie >0 to wtedy znajdę któryś metodą Brenta czy Dekkera.
Ale jak następny?
Wypadało by odczytać wartość w(znaleziony pierwiastek) ale to nie jest
dobra metoda, zwłaszcza gdy pierwiastek jest wielokrotny.
Trzeba by odczytać z miejsc +-epsilon, ale gdy pierwiastek wielokrotny
to nawet obliczenie pochodnej nie pomoże
liczbę: w(koniec duzego przedzialu) - w (początek duzego przedzialu)
https://pl.wikipedia.org/wiki/Twierdzenie_Sturma
Jeśli będzie >0 to wtedy znajdę któryś metodą Brenta czy Dekkera.
Ale jak następny?
Wypadało by odczytać wartość w(znaleziony pierwiastek) ale to nie jest
dobra metoda, zwłaszcza gdy pierwiastek jest wielokrotny.
Trzeba by odczytać z miejsc +-epsilon, ale gdy pierwiastek wielokrotny
to nawet obliczenie pochodnej nie pomoże
bartekltg
Nov 1, 2016, 7:58:33 PM11/1/16
to
On 01.11.2016 22:20, Borneq wrote:
> Chciałem wyznaczyć wszystkie pierwiastki wielomianu. Najpierw ich
> liczbę: w(koniec duzego przedzialu) - w (początek duzego przedzialu)
> https://pl.wikipedia.org/wiki/Twierdzenie_Sturma
> Jeśli będzie >0 to wtedy znajdę któryś metodą Brenta czy Dekkera.
>
> Ale jak następny?
Dzielisz wielomian przez wyliczony pierwiastek.
> Chciałem wyznaczyć wszystkie pierwiastki wielomianu. Najpierw ich
> liczbę: w(koniec duzego przedzialu) - w (początek duzego przedzialu)
> https://pl.wikipedia.org/wiki/Twierdzenie_Sturma
> Jeśli będzie >0 to wtedy znajdę któryś metodą Brenta czy Dekkera.
>
> Ale jak następny?
Dostajesz wielomian o stopień niższy.
Wyznaczasz w nim kolejny pierwiastek.
I teraz bardzo ważny krok: poprawiasz ten pierwiastek
stosując oryginalny, pełny wielomian.
Wtedy niedokładność wyznaczenia poprzednich pierwiastków,
a przez to niedokładność zredukowanego wielomianu,
nie wpływa na dokładność kolejnego pierwiastka,
bo ze zredukowanego dostajemy przyzwoite przybliżęnie,
ale potem poprawiamy na oryginlanym.
BTW, do wielomianóþw raczej nie uzywa sie
Brenta-Dekkera, tylko metod specjalnie przystosowanych
do wielomianów.
Np takie coś:
https://en.wikipedia.org/wiki/Laguerre%27s_method
https://en.wikipedia.org/wiki/Jenkins%E2%80%93Traub_algorithm
Takich metod jest trochę
Tu masz nieco więcej,
http://th-www.if.uj.edu.pl/zfs/gora/metnum13/wyklad10.pdf
Są i metody, które szukają na raz wszystkich pierwiastków.
Diagonalizacja macierzy stowarzyszonej
pzdr
bartekltg
Borneq
Nov 2, 2016, 8:17:05 AM11/2/16
to
W dniu 02.11.2016 o 00:58, bartekltg pisze:
trzeba budować ciąg Sturma. Czy po zmniejszeniu stopnia znowu budujemy
ciąg Sturma, czy dałoby radę od razu wszystkie? Ale problem z
pierwiastkami wielokrotnymi,
Wszystkie pierwiastki mieszczą się w [-M,M] gdzie M = max {1,suma abs
(a_i)}
Co prawda zamiast M mogę policzyć Sturma w minus i plus nieskończoności
- jeszcze łatwiej, wystarczy znak najwyższej potęgi.
Ale to M potrzebne do metod szukających pierwiastka w przedziale.
A jak jest z ograniczaniem najmniejszej odległości między pierwiastkami?
Zwykła funkcja może mieć bardzo blisko np. zagęszczający się sinus, ale
wielomiany to nie.
Jak poprawiać pierwiastek? Jakąś metodą bez zakresów, np. Newtonem?
Przyjrzę się
> https://en.wikipedia.org/wiki/Laguerre%27s_method
> https://en.wikipedia.org/wiki/Jenkins%E2%80%93Traub_algorithm
> http://th-www.if.uj.edu.pl/zfs/gora/metnum13/wyklad10.pdf
> Dzielisz wielomian przez wyliczony pierwiastek.
> Dostajesz wielomian o stopień niższy.
Gdy wielomian ma stopień nieparzysty, na pewno ma pierwiastek, gdy nie,
> Dostajesz wielomian o stopień niższy.
trzeba budować ciąg Sturma. Czy po zmniejszeniu stopnia znowu budujemy
ciąg Sturma, czy dałoby radę od razu wszystkie? Ale problem z
pierwiastkami wielokrotnymi,
Wszystkie pierwiastki mieszczą się w [-M,M] gdzie M = max {1,suma abs
(a_i)}
Co prawda zamiast M mogę policzyć Sturma w minus i plus nieskończoności
- jeszcze łatwiej, wystarczy znak najwyższej potęgi.
Ale to M potrzebne do metod szukających pierwiastka w przedziale.
A jak jest z ograniczaniem najmniejszej odległości między pierwiastkami?
Zwykła funkcja może mieć bardzo blisko np. zagęszczający się sinus, ale
wielomiany to nie.
Jak poprawiać pierwiastek? Jakąś metodą bez zakresów, np. Newtonem?
Przyjrzę się
> https://en.wikipedia.org/wiki/Laguerre%27s_method
> https://en.wikipedia.org/wiki/Jenkins%E2%80%93Traub_algorithm
> http://th-www.if.uj.edu.pl/zfs/gora/metnum13/wyklad10.pdf
bartekltg
Nov 2, 2016, 9:41:35 AM11/2/16
to
On Wednesday, November 2, 2016 at 1:17:05 PM UTC+1, Borneq wrote:
> W dniu 02.11.2016 o 00:58, bartekltg pisze:
> > Dzielisz wielomian przez wyliczony pierwiastek.
> > Dostajesz wielomian o stopień niższy.
>
> Gdy wielomian ma stopień nieparzysty, na pewno ma pierwiastek, gdy nie,
> trzeba budować ciąg Sturma. Czy po zmniejszeniu stopnia znowu budujemy
> ciąg Sturma, czy dałoby radę od razu wszystkie?
A na cholerę. Jeśli wielomian p(x) ma k rzeczywistych pierwiastków,
> W dniu 02.11.2016 o 00:58, bartekltg pisze:
> > Dzielisz wielomian przez wyliczony pierwiastek.
> > Dostajesz wielomian o stopień niższy.
>
> Gdy wielomian ma stopień nieparzysty, na pewno ma pierwiastek, gdy nie,
> trzeba budować ciąg Sturma. Czy po zmniejszeniu stopnia znowu budujemy
> ciąg Sturma, czy dałoby radę od razu wszystkie?
jednym z nich jest x_0, to wielomian p(x)/(x-x0) ma k-1 rzeczywistych
pierwiastków.
BTW, m. Laguerre'a znajduje też zespolone ( co najlepsze, jak masz
jeden zespolony pierwiastek rzeczywistego wielomianu, to masz dwa ;-)
Wtedy dzielisz przez parę sprzeżoną).
Nie trzeba w ogole bawić się w ich zliczanie.
> Ale problem z
> pierwiastkami wielokrotnymi,
Jak x_0 jest pierwiastkiem m krotnym p(x),
to jest pierwiastkeim m-1 krotnym p(x)/(x-x_0).
> Wszystkie pierwiastki mieszczą się w [-M,M] gdzie M = max {1,suma abs
> (a_i)}
> Co prawda zamiast M mogę policzyć Sturma w minus i plus nieskończoności
> - jeszcze łatwiej, wystarczy znak najwyższej potęgi.
> Ale to M potrzebne do metod szukających pierwiastka w przedziale.
> A jak jest z ograniczaniem najmniejszej odległości między pierwiastkami?
> Zwykła funkcja może mieć bardzo blisko np. zagęszczający się sinus, ale
> wielomiany to nie.
x^2 - epslon.
"ale to proste"
To przesuńmu go od zera, przemnóż sobie ten wielomian przez jakiś
wielomian z sufitu.
((x-1)^2 - 0.000001) *(x-1.1)*(x+9) *(x-0.2)=
x^5+5.7 x^4-25.88 x^3+32.64 x^2-15.44 x+1.98
Wcale podejrzanie nie wygląda.
Praktycznie niemożliwe numerycznie jest stwierdzenie z cała pewnością,
czy mamy prawdziwy pierwiastek podwójny, czy parę bardzo
bliskich pierwiastków (bliskich po osi rzeczywistej lub urojonej:)
> Jak poprawiać pierwiastek? Jakąś metodą bez zakresów, np. Newtonem?
pzdr
bartekltg
Borneq
Nov 2, 2016, 9:59:21 AM11/2/16
to
W dniu 02.11.2016 o 00:58, bartekltg pisze:
Uwagi końcowe
1. Jeżeli wyjściowy wielomian Pn(z) ma współczynniki rzeczywiste, wiemy,
ze jego miejsca zerowe są albo rzeczywiste, albo tworzą zespolone pary
sprzężone. Jeżeli zatem za pomocą powyższej strategii znajdziemy jego
wygładzone, zespolone miejsce zerowe zk = xk+iyk
wiemy,ze miejscem zerowym jest także zk+1 = xk − iyk,
a więc możemy obniżyć stopień wielomianu od razu o dwa.
Na dobra, ale granica jest płynna:
może być zk = xk rzeczywiste i nie wiemy czy jednokrotny
a może być zk = xk+i *eps i nie wiemy czy rzeczywisty jeden czy dwa
zespolone.
----
Metoda Metoda Laguerre’a (strona 10-14):
operuje na liczbach zespolonych, poza tym jest pierwiastek; o ile
pierwiastek na liczbach rzeczywistych jest prosty, to jak obliczamy
pierwiastki liczb zespolonych bez przejścia przez funkcje
trygonometryczne? Poza tym pierwiastki zespolone są dwa, który wybrać do
wzoru; oprócz tego że będziemy wybierać, czy mamy dodawać czy odejmować
pierwiastek, to są dwa pierwiastki?
W Wikipedii https://en.wikipedia.org/wiki/Laguerre%27s_method
nie piszą że działa na liczbach zespolonych.
bartekltg
Nov 2, 2016, 10:30:49 AM11/2/16
to
On Wednesday, November 2, 2016 at 2:59:21 PM UTC+1, Borneq wrote:
> W dniu 02.11.2016 o 00:58, bartekltg pisze:
> > Tu masz nieco więcej,
> > http://th-www.if.uj.edu.pl/zfs/gora/metnum13/wyklad10.pdf
>
> Uwagi końcowe
> 1. Jeżeli wyjściowy wielomian Pn(z) ma współczynniki rzeczywiste, wiemy,
> ze jego miejsca zerowe są albo rzeczywiste, albo tworzą zespolone pary
> sprzężone. Jeżeli zatem za pomocą powyższej strategii znajdziemy jego
> wygładzone, zespolone miejsce zerowe zk = xk+iyk
> wiemy,ze miejscem zerowym jest także zk+1 = xk − iyk,
> a więc możemy obniżyć stopień wielomianu od razu o dwa.
>
> Na dobra, ale granica jest płynna:
> może być zk = xk rzeczywiste i nie wiemy czy jednokrotny
Pytam ponownie: I co z tego?!
> W dniu 02.11.2016 o 00:58, bartekltg pisze:
> > Tu masz nieco więcej,
> > http://th-www.if.uj.edu.pl/zfs/gora/metnum13/wyklad10.pdf
>
> Uwagi końcowe
> 1. Jeżeli wyjściowy wielomian Pn(z) ma współczynniki rzeczywiste, wiemy,
> ze jego miejsca zerowe są albo rzeczywiste, albo tworzą zespolone pary
> sprzężone. Jeżeli zatem za pomocą powyższej strategii znajdziemy jego
> wygładzone, zespolone miejsce zerowe zk = xk+iyk
> wiemy,ze miejscem zerowym jest także zk+1 = xk − iyk,
> a więc możemy obniżyć stopień wielomianu od razu o dwa.
>
> Na dobra, ale granica jest płynna:
> może być zk = xk rzeczywiste i nie wiemy czy jednokrotny
Co z tego, że pierwiastek jest wielokrotny.
Dzielisz. Odpalasz procedurę dalej, znajdujesz kolejny, prawdopodobnie
kolejny raz ten sam.
> a może być zk = xk+i *eps i nie wiemy czy rzeczywisty jeden czy dwa
> zespolone.
> ----
> Metoda Metoda Laguerre’a (strona 10-14):
> operuje na liczbach zespolonych, poza tym jest pierwiastek; o ile
> pierwiastek na liczbach rzeczywistych jest prosty, to jak obliczamy
> pierwiastki liczb zespolonych bez przejścia przez funkcje
> trygonometryczne?
Jak ona liczy? To prawdopodobnioe zazależy od implementacji,
w gcc trygonometrii nie uzywa.
> Poza tym pierwiastki zespolone są dwa, który wybrać do
> wzoru;
> oprócz tego że będziemy wybierać, czy mamy dodawać czy odejmować
> pierwiastek, to są dwa pierwiastki?
jak jest + to dodajesz, jak jest - to odejmujesz.
> W Wikipedii https://en.wikipedia.org/wiki/Laguerre%27s_method
> nie piszą że działa na liczbach zespolonych.
Bo ja takiiego zdania tam nie widzę.
Widzą natomiast dokładne instrukcje, który pierwiastek zespolony
użyć, oraaz zdania jak:
"It may even converge to a complex root of the polynomial"
O co więc chodzi, czemu oszukujesz? ;>
pzdr
bartekltg
bartekltg
Nov 2, 2016, 10:45:45 AM11/2/16
to
On Wednesday, November 2, 2016 at 3:30:49 PM UTC+1, bartekltg wrote:
> > Metoda Metoda Laguerre’a (strona 10-14):
> > operuje na liczbach zespolonych, poza tym jest pierwiastek; o ile
> > pierwiastek na liczbach rzeczywistych jest prosty, to jak obliczamy
> > pierwiastki liczb zespolonych bez przejścia przez funkcje
> > trygonometryczne?
>
> Funkcją sqrt()
> Jak ona liczy? To prawdopodobnioe zazależy od implementacji,
> w gcc trygonometrii nie uzywa.
Pewnie tym:
> > Metoda Metoda Laguerre’a (strona 10-14):
> > operuje na liczbach zespolonych, poza tym jest pierwiastek; o ile
> > pierwiastek na liczbach rzeczywistych jest prosty, to jak obliczamy
> > pierwiastki liczb zespolonych bez przejścia przez funkcje
> > trygonometryczne?
>
> Funkcją sqrt()
> Jak ona liczy? To prawdopodobnioe zazależy od implementacji,
> w gcc trygonometrii nie uzywa.
https://en.wikipedia.org/wiki/Square_root#Square_roots_of_negative_and_complex_numbers
[algebraic formula].
Liczy trzy pierwiastki z liczb rzeczywistych.
Może da się lepiej. Poprawiać Newtonem? ;-)
pzdr
bartekltg
To NIE jest do użycia w kodzie. To robi funkcja sqrt.
Borneq
Nov 2, 2016, 12:46:43 PM11/2/16
to
W dniu 02.11.2016 o 14:41, bartekltg pisze:
zespoloną sprzężoną, zwłaszcza że mogę dzielić przez (x-(a+bi)((x-(a-bi)
co mi wyeliminuje liczby urojone. Ale gdy pomylę JEDNOKROTNY pierwiastek
rzeczywisty z parą zespolonych to gorzej bo podzielę dwukrotnie przez
(x-a) a można tylko raz. Rozpoznam po reszcie z dzielenia że jest dużo
większa od zera?
> Pytam ponownie: I co z tego?!
> Co z tego, że pierwiastek jest wielokrotny.
> Dzielisz. Odpalasz procedurę dalej, znajdujesz kolejny, prawdopodobnie
> kolejny raz ten sam.
Tak, gdy użyję Laguerre'a, nie będę musiał używać Sturma. Ale nie mogę
znaleźć gdzie odnosiłeś się do nieodróżnienia jednokrotnego pierwiastka
od pary sprzężonej. Choć nie wiem, czy takie przypadki w ogóle mogą mieć
miejsce.
> Praktycznie niemożliwe numerycznie jest stwierdzenie z cała pewnością,
> czy mamy prawdziwy pierwiastek podwójny, czy parę bardzo
> bliskich pierwiastków (bliskich po osi rzeczywistej lub urojonej:)
Tak, trzeba się z tym zgodzić. Ale nie mogę znaleźć:
> czy mamy prawdziwy pierwiastek podwójny, czy parę bardzo
> bliskich pierwiastków (bliskich po osi rzeczywistej lub urojonej:)
>> a może być zk = xk+i *eps i nie wiemy czy rzeczywisty jeden czy dwa
>> zespolone.
>15 minut temu własnie o tym pisałem:)
Raczej niegroźne gdy pomylę pierwiastek rzeczywisty podwójny z parą
>> zespolone.
>15 minut temu własnie o tym pisałem:)
zespoloną sprzężoną, zwłaszcza że mogę dzielić przez (x-(a+bi)((x-(a-bi)
co mi wyeliminuje liczby urojone. Ale gdy pomylę JEDNOKROTNY pierwiastek
rzeczywisty z parą zespolonych to gorzej bo podzielę dwukrotnie przez
(x-a) a można tylko raz. Rozpoznam po reszcie z dzielenia że jest dużo
większa od zera?
> Pytam ponownie: I co z tego?!
> Co z tego, że pierwiastek jest wielokrotny.
> Dzielisz. Odpalasz procedurę dalej, znajdujesz kolejny, prawdopodobnie
> kolejny raz ten sam.
znaleźć gdzie odnosiłeś się do nieodróżnienia jednokrotnego pierwiastka
od pary sprzężonej. Choć nie wiem, czy takie przypadki w ogóle mogą mieć
miejsce.
Borneq
Nov 2, 2016, 1:03:08 PM11/2/16
to
W dniu 02.11.2016 o 17:46, Borneq pisze:
wielokrotnego? A dla jednokrotnego część urojona zawsze zero? Chyba
zrobię tak, że zawsze zacznę szukać od x rzeczywistego, najpierw szukać
procedurą Laguerre'a dla liczb rzeczywistych, która nie wchodzi w
zespolone, a co najwyżej zwraca NAN. Dopiero gdy mi się nie uda, wtedy
zacznę szukać liczbami zespolonymi, i wtedy przyjmę zawsze sprzężoną
parę. A może po prostu procedura liczb zespolonych nim nie wejdzie w
liczby zespolone będzie miała część urojoną zawsze równą zeru.
> od pary sprzężonej. Choć nie wiem, czy takie przypadki w ogóle mogą mieć
> miejsce.
Może taki przypadek że część urojona = epsilon tylko dla pierwiastka
> miejsce.
wielokrotnego? A dla jednokrotnego część urojona zawsze zero? Chyba
zrobię tak, że zawsze zacznę szukać od x rzeczywistego, najpierw szukać
procedurą Laguerre'a dla liczb rzeczywistych, która nie wchodzi w
zespolone, a co najwyżej zwraca NAN. Dopiero gdy mi się nie uda, wtedy
zacznę szukać liczbami zespolonymi, i wtedy przyjmę zawsze sprzężoną
parę. A może po prostu procedura liczb zespolonych nim nie wejdzie w
liczby zespolone będzie miała część urojoną zawsze równą zeru.
bartekltg
Nov 2, 2016, 4:41:53 PM11/2/16
to
On 02.11.2016 17:46, Borneq wrote:
> W dniu 02.11.2016 o 14:41, bartekltg pisze:
>> Praktycznie niemożliwe numerycznie jest stwierdzenie z cała pewnością,
>> czy mamy prawdziwy pierwiastek podwójny, czy parę bardzo
>> bliskich pierwiastków (bliskich po osi rzeczywistej lub urojonej:)
>
> Tak, trzeba się z tym zgodzić. Ale nie mogę znaleźć:
>>> a może być zk = xk+i *eps i nie wiemy czy rzeczywisty jeden czy dwa
>>> zespolone.
>>15 minut temu własnie o tym pisałem:)
>
> Raczej niegroźne gdy pomylę pierwiastek rzeczywisty podwójny z parą
> zespoloną sprzężoną, zwłaszcza że mogę dzielić przez (x-(a+bi)((x-(a-bi)
> co mi wyeliminuje liczby urojone. Ale gdy pomylę JEDNOKROTNY pierwiastek
> rzeczywisty z parą zespolonych to gorzej bo podzielę dwukrotnie przez
> (x-a) a można tylko raz.
Skoro pomyliłeś, to znaczy, że pomyłka nie była duża i wyjdzie z grubsza
> W dniu 02.11.2016 o 14:41, bartekltg pisze:
>> Praktycznie niemożliwe numerycznie jest stwierdzenie z cała pewnością,
>> czy mamy prawdziwy pierwiastek podwójny, czy parę bardzo
>> bliskich pierwiastków (bliskich po osi rzeczywistej lub urojonej:)
>
> Tak, trzeba się z tym zgodzić. Ale nie mogę znaleźć:
>>> a może być zk = xk+i *eps i nie wiemy czy rzeczywisty jeden czy dwa
>>> zespolone.
>>15 minut temu własnie o tym pisałem:)
>
> Raczej niegroźne gdy pomylę pierwiastek rzeczywisty podwójny z parą
> zespoloną sprzężoną, zwłaszcza że mogę dzielić przez (x-(a+bi)((x-(a-bi)
> co mi wyeliminuje liczby urojone. Ale gdy pomylę JEDNOKROTNY pierwiastek
> rzeczywisty z parą zespolonych to gorzej bo podzielę dwukrotnie przez
> (x-a) a można tylko raz.
na to samo.
podzielenie przez (x^2-eps) przez (x^2+eps) nie na wcale aż tak
wielkiego znaczenia.
>> Pytam ponownie: I co z tego?!
>> Co z tego, że pierwiastek jest wielokrotny.
>> Dzielisz. Odpalasz procedurę dalej, znajdujesz kolejny, prawdopodobnie
>> kolejny raz ten sam.
>
> Tak, gdy użyję Laguerre'a, nie będę musiał używać Sturma. Ale nie mogę
> znaleźć gdzie odnosiłeś się do nieodróżnienia jednokrotnego pierwiastka
> od pary sprzężonej.
> Choć nie wiem, czy takie przypadki w ogóle mogą mieć
> miejsce.
pzdr
bartekltg
Borneq
Nov 2, 2016, 7:19:03 PM11/2/16
to
W dniu 02.11.2016 o 21:41, bartekltg pisze:
Ale to nie taki problem, mam wersję Laguerre dla liczb rzeczywistych
(szybszą), którą najpierw próbuję, jak się nie uda to dla liczb zespolonych.
> podzielenie przez (x^2-eps) przez (x^2+eps) nie na wcale aż tak
> wielkiego znaczenia.
A podzielenie (x-1)(x-2)(x-3) przez (x-2)(x-2)? ;-)
> wielkiego znaczenia.
Ale to nie taki problem, mam wersję Laguerre dla liczb rzeczywistych
(szybszą), którą najpierw próbuję, jak się nie uda to dla liczb zespolonych.
bartekltg
Nov 3, 2016, 6:57:39 AM11/3/16
to
On Thursday, November 3, 2016 at 12:19:03 AM UTC+1, Borneq wrote:
> W dniu 02.11.2016 o 21:41, bartekltg pisze:
> > podzielenie przez (x^2-eps) przez (x^2+eps) nie na wcale aż tak
> > wielkiego znaczenia.
>
> A podzielenie (x-1)(x-2)(x-3) przez (x-2)(x-2)? ;-)
Czyli obawiasz się, że przy pojedyńczym pierwiastku
> W dniu 02.11.2016 o 21:41, bartekltg pisze:
> > podzielenie przez (x^2-eps) przez (x^2+eps) nie na wcale aż tak
> > wielkiego znaczenia.
>
> A podzielenie (x-1)(x-2)(x-3) przez (x-2)(x-2)? ;-)
dostaniesz liczbę zespoloną? Tak nie będzie.
Odlot w zespolopne może wystąpić tylko przy pierwiastku wielokrotnym.
Liczba zespolona może pojawić się, jeśli
(n-1)p(x)'^2 - n p(x)'' p(x) (1)
jest ujemne.
Interesujemy się bliską okolicą takiego podejrzanego pierwiastka
_jednokrotnego_. Co tam się dzieje?
p' jest ograniczone od dołu (jest to pochodna w pierwiastku + mała poprawka)
a p(x) dąży do zera. Zawsze masz więc otoczenie pierwiastka p(x),
w którym powyższe wyrażenie jest dodatnie.
Jeśli dostałeś pierwiastek, i jest on numerycznie niepewnym pierwiastkiem
zespolonym, to znaczy, że to może by c podwójny pierwiastek
zespolony, albo podwojyn pierwiastek rzeczywisty. Nie może*) to
natomiast byc pojedynczy pierwiastek rzeczywisty.
*) Nie wiem, czy ta metoda może wyskoczyć w liczby zespolone, po czym
wrócić dążyć do pierwiastka rzeczywistego.
Można pomyśleć/poszukać/spróbować znaleśc przykład, gdzie się tak dzieje,
ale jeśli może, można się przed tym łatwo zabezpieczyć:
jeśli metoda zbiegła do pierwiastka o podejrzanie małej wartości cześci
urojonej, odpalmy algorytm dla punktu startowego równego cześći rzeczywistej
(możemy to zrobić właściwie za darmo, bo i tak robimy drugie odpalenie
algorytmu dla wyjściowego wielomianu).
Jeśli był to pierwiastek jednokrotny, (1) jest dodatnie i znajdziemy
pierwiastek rzeczywisty.
pzdr
bartekltg
Borneq
Nov 3, 2016, 1:45:00 PM11/3/16
to
W dniu 03.11.2016 o 11:57, bartekltg pisze:
gdy mam sprzężone pierwiastki zespolone i dzielę wielomian przez
wielomian kwadratowy wtedy w wielomianie reszt pozostają jakieś
epsilony, podczas gdy chyba nie gdy dzielę przez (x-a)
Wygładzanie pierwiastków - u mnie jest bez różnicy, za drugim razem
znajduje dokładnie ten sam pierwiastek.
Jedyna różnica to pierwiastek podwójny: za pierwszym razem znajduje
1.9999999963694399 za drugim 1.9999999681825615, jest różnica ale wciąż
nie root=2.
Problem z podwójnymi bo warunek wyjścia z pętli gdy mała wielkość f(x) =
P(x). Wielkość w warunku wyjścia porównuję f(x) z
f'(x)*maszynowy_epsilon, potem dodałem jeszcze czynnik dwa, bo czasami
nie chciał wyjść z pętli. Może drugi warunek wyjścia - gdy x się nie
zmieni, to znaczy a=0?
Jak jest pierwiastek podwójny, nie mówiąc o wielokrotnych, to jego
dokładność jest o połowę cyfr mniejsza niż dokładność maszynowa i nic
się na to nie poradzi bo już w pobliży sqrt(epsilon) wartość wielomianu
jest w granicach błędu maszynowego.
Generowanie testowych wielomianów: gdy generowałem losowe wartości ai od
-10 do 10 zwykle miały tylko jeden pierwiastek rzeczywisty a resztę
zespolonych, czyli nie były reprezentatywne. Może wygenerować wielomian
na podstawie pierwiastków?
> Jeśli dostałeś pierwiastek, i jest on numerycznie niepewnym pierwiastkiem
> zespolonym, to znaczy, że to może by c podwójny pierwiastek
> zespolony, albo podwojyn pierwiastek rzeczywisty. Nie może*) to
> natomiast byc pojedynczy pierwiastek rzeczywisty.
Uwagi dotyczące wyników:
> zespolonym, to znaczy, że to może by c podwójny pierwiastek
> zespolony, albo podwojyn pierwiastek rzeczywisty. Nie może*) to
> natomiast byc pojedynczy pierwiastek rzeczywisty.
gdy mam sprzężone pierwiastki zespolone i dzielę wielomian przez
wielomian kwadratowy wtedy w wielomianie reszt pozostają jakieś
epsilony, podczas gdy chyba nie gdy dzielę przez (x-a)
Wygładzanie pierwiastków - u mnie jest bez różnicy, za drugim razem
znajduje dokładnie ten sam pierwiastek.
Jedyna różnica to pierwiastek podwójny: za pierwszym razem znajduje
1.9999999963694399 za drugim 1.9999999681825615, jest różnica ale wciąż
nie root=2.
Problem z podwójnymi bo warunek wyjścia z pętli gdy mała wielkość f(x) =
P(x). Wielkość w warunku wyjścia porównuję f(x) z
f'(x)*maszynowy_epsilon, potem dodałem jeszcze czynnik dwa, bo czasami
nie chciał wyjść z pętli. Może drugi warunek wyjścia - gdy x się nie
zmieni, to znaczy a=0?
Jak jest pierwiastek podwójny, nie mówiąc o wielokrotnych, to jego
dokładność jest o połowę cyfr mniejsza niż dokładność maszynowa i nic
się na to nie poradzi bo już w pobliży sqrt(epsilon) wartość wielomianu
jest w granicach błędu maszynowego.
Generowanie testowych wielomianów: gdy generowałem losowe wartości ai od
-10 do 10 zwykle miały tylko jeden pierwiastek rzeczywisty a resztę
zespolonych, czyli nie były reprezentatywne. Może wygenerować wielomian
na podstawie pierwiastków?
bartekltg
Nov 3, 2016, 2:43:28 PM11/3/16
to
On 03.11.2016 18:44, Borneq wrote:
> W dniu 03.11.2016 o 11:57, bartekltg pisze:
>> Jeśli dostałeś pierwiastek, i jest on numerycznie niepewnym pierwiastkiem
>> zespolonym, to znaczy, że to może by c podwójny pierwiastek
>> zespolony, albo podwojyn pierwiastek rzeczywisty. Nie może*) to
>> natomiast byc pojedynczy pierwiastek rzeczywisty.
>
> Uwagi dotyczące wyników:
> gdy mam sprzężone pierwiastki zespolone i dzielę wielomian przez
> wielomian kwadratowy wtedy w wielomianie reszt pozostają jakieś
> epsilony, podczas gdy chyba nie gdy dzielę przez (x-a)
Oczywiście, zę się pojawiają.
> W dniu 03.11.2016 o 11:57, bartekltg pisze:
>> Jeśli dostałeś pierwiastek, i jest on numerycznie niepewnym pierwiastkiem
>> zespolonym, to znaczy, że to może by c podwójny pierwiastek
>> zespolony, albo podwojyn pierwiastek rzeczywisty. Nie może*) to
>> natomiast byc pojedynczy pierwiastek rzeczywisty.
>
> Uwagi dotyczące wyników:
> gdy mam sprzężone pierwiastki zespolone i dzielę wielomian przez
> wielomian kwadratowy wtedy w wielomianie reszt pozostają jakieś
> epsilony, podczas gdy chyba nie gdy dzielę przez (x-a)
Jedna liczba. bo z podzieleniu przez x-a resztą jest wielomian stały.
> Wygładzanie pierwiastków - u mnie jest bez różnicy, za drugim razem
> znajduje dokładnie ten sam pierwiastek.
> Jedyna różnica to pierwiastek podwójny: za pierwszym razem znajduje
> 1.9999999963694399 za drugim 1.9999999681825615, jest różnica ale wciąż
> nie root=2.
> Problem z podwójnymi bo warunek wyjścia z pętli gdy mała wielkość f(x) =
> P(x). Wielkość w warunku wyjścia porównuję f(x) z
> f'(x)*maszynowy_epsilon, potem dodałem jeszcze czynnik dwa, bo czasami
> nie chciał wyjść z pętli. Może drugi warunek wyjścia - gdy x się nie
> zmieni, to znaczy a=0?
|a| = |x_{i+1}-x_i| < |x_{i+1}| * epsylon, nie masz sansz się
przesunąć.
Skończyć pewnie można znacznie wcześniej.
BTW, zawsze można pogooglać i odkopać prawdziwe kryteria,
które gwarantują określone |x_i-x|
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4448898/
https://arxiv.org/pdf/1501.02168.pdf
> Jak jest pierwiastek podwójny, nie mówiąc o wielokrotnych, to jego
> dokładność jest o połowę cyfr mniejsza niż dokładność maszynowa i nic
> się na to nie poradzi bo już w pobliży sqrt(epsilon) wartość wielomianu
> jest w granicach błędu maszynowego.
Albo, jak podejrzewasz podwójny, poszukaj zera pochodnej.
Jeśli to jest peirwiastek podwójny, to jest pojedynczym
pierwiastkiem pochodnej.
Jeśli są to dwa osobne, pierwiastek pochodnej jest pomiędzy
nimi, więc też blisko.
pzdr
bartekltg
Borneq
Nov 3, 2016, 5:26:45 PM11/3/16
to
W dniu 03.11.2016 o 19:43, bartekltg pisze:
W funkcji Laguerre mam dwa punkty gdzie sprawdzane są warunki wyjścia:
jeden to f(x) bardzo małe, drugi to x_{i+1}-x_i bardzo małe.
Gdy mam podwójny pierwiastek to wtedy wychodzi w miejscu pierwszym, f(x)
jest rzędu Eps a f'(x) rzędu sqrt(Eps), tu jakoś powinno się sprawdzić
czy w miejscu gdzie pochodna jest równa zeru, jest funkcja równa zero.
Czy drugi raz wołany Laguerre dla pochodnej i liczona zamiast f(x),
pochodnej i drugiej pochodnej - aż do pochodnej trzeciej? A co gdy mamy
potrójny pierwiastek itd? Np (x-1)^20 ?
> To nie patrz na wartości ;-)
>
> Albo, jak podejrzewasz podwójny, poszukaj zera pochodnej.
> Jeśli to jest peirwiastek podwójny, to jest pojedynczym
> pierwiastkiem pochodnej.
> Jeśli są to dwa osobne, pierwiastek pochodnej jest pomiędzy
> nimi, więc też blisko.
Tylko jak to podejrzenie zautomatyzować?
>
> Albo, jak podejrzewasz podwójny, poszukaj zera pochodnej.
> Jeśli to jest peirwiastek podwójny, to jest pojedynczym
> pierwiastkiem pochodnej.
> Jeśli są to dwa osobne, pierwiastek pochodnej jest pomiędzy
> nimi, więc też blisko.
W funkcji Laguerre mam dwa punkty gdzie sprawdzane są warunki wyjścia:
jeden to f(x) bardzo małe, drugi to x_{i+1}-x_i bardzo małe.
Gdy mam podwójny pierwiastek to wtedy wychodzi w miejscu pierwszym, f(x)
jest rzędu Eps a f'(x) rzędu sqrt(Eps), tu jakoś powinno się sprawdzić
czy w miejscu gdzie pochodna jest równa zeru, jest funkcja równa zero.
Czy drugi raz wołany Laguerre dla pochodnej i liczona zamiast f(x),
pochodnej i drugiej pochodnej - aż do pochodnej trzeciej? A co gdy mamy
potrójny pierwiastek itd? Np (x-1)^20 ?
M.M.
Nov 4, 2016, 2:10:38 PM11/4/16
to
On Wednesday, November 2, 2016 at 12:58:33 AM UTC+1, bartekltg wrote:
> Np takie coś:
> https://en.wikipedia.org/wiki/Laguerre%27s_method
> https://en.wikipedia.org/wiki/Jenkins%E2%80%93Traub_algorithm
> Takich metod jest trochę
>
> Tu masz nieco więcej,
> http://th-www.if.uj.edu.pl/zfs/gora/metnum13/wyklad10.pdf
>
> Są i metody, które szukają na raz wszystkich pierwiastków.
> Diagonalizacja macierzy stowarzyszonej
>
Na ile te metody są efektywne i skuteczne? Gdy wielomiany będą miały
> Np takie coś:
> https://en.wikipedia.org/wiki/Laguerre%27s_method
> https://en.wikipedia.org/wiki/Jenkins%E2%80%93Traub_algorithm
> Takich metod jest trochę
>
> Tu masz nieco więcej,
> http://th-www.if.uj.edu.pl/zfs/gora/metnum13/wyklad10.pdf
>
> Są i metody, które szukają na raz wszystkich pierwiastków.
> Diagonalizacja macierzy stowarzyszonej
>
bardzo wysoki stopień (np. 10tys) to też można efektywnie znaleźć
wszystkie miejsca zerowe?
Pozdrawiam
bartekltg
Nov 4, 2016, 2:35:45 PM11/4/16
to
Przynajmniej nie w podwójnej precyzji (chyba, że wielomian bardzo
przyzwoity).
Jeśli miałbym próbować, raczej metodami przez macierz stowarzyszoną.
Coś o wielomianie wiadomo? Np że ma przyzwoicie rozłożone miejsca
zerowe. Albo współczynniki wymierne.
W takich lepszych przypadkach, ludzie faktoryzują wielomiany
o stopniach parę tysięcy.
https://en.wikipedia.org/wiki/Factorization_of_polynomials
Nowadays, modern algorithms and computers can quickly factor univariate
polynomials of degree more than 1000 having coefficients with thousands
of digits.[1]
http://www.math.fsu.edu/~hoeij/papers/issac10/A.pdf
Ale jest to ciut inne zagadnienie;-)
pzdr
bartekltg
bartekltg
Nov 4, 2016, 3:55:05 PM11/4/16
to
On 03.11.2016 22:26, Borneq wrote:
> W dniu 03.11.2016 o 19:43, bartekltg pisze:
Miałeś napisać, jaki to wielomian miał mieć pierwiastek
> W dniu 03.11.2016 o 19:43, bartekltg pisze:
2, a zwracał 1.99999999cośtam.
>> To nie patrz na wartości ;-)
>>
>> Albo, jak podejrzewasz podwójny, poszukaj zera pochodnej.
>> Jeśli to jest peirwiastek podwójny, to jest pojedynczym
>> pierwiastkiem pochodnej.
>> Jeśli są to dwa osobne, pierwiastek pochodnej jest pomiędzy
>> nimi, więc też blisko.
>
> Tylko jak to podejrzenie zautomatyzować?
Z tego co zrtozumiałem, obawiasz się słąbej jakości obliczonych
pierwiastków. Jeśli więc po policzeniu masz taki klaster,
który trzyma się w kupie, jeśli są wszytkie w zadanym promieniu,
możesz je zadeklarować jako będące jednym;-)
I policzyć sobie odpowiednią pochodną i tam dokłądnie pierwiastek.
Tak, jest to uznaniowe.
> W funkcji Laguerre mam dwa punkty gdzie sprawdzane są warunki wyjścia:
> jeden to f(x) bardzo małe, drugi to x_{i+1}-x_i bardzo małe.
> Gdy mam podwójny pierwiastek to wtedy wychodzi w miejscu pierwszym, f(x)
> jest rzędu Eps a f'(x) rzędu sqrt(Eps), tu jakoś powinno się sprawdzić
> czy w miejscu gdzie pochodna jest równa zeru, jest funkcja równa zero.
Ona dziqałały na f i f "numerycznie zaburzonym" przez f'
> Czy drugi raz wołany Laguerre dla pochodnej i liczona zamiast f(x),
> pochodnej i drugiej pochodnej - aż do pochodnej trzeciej? A co gdy mamy
> potrójny pierwiastek itd? Np (x-1)^20 ?
gdy któryś z wyrazów (chyba numer 19) takiego wiuelomianu
lekko zaburzysz. Cuda ;-)
pzdr
bartekltg
Borneq
Nov 4, 2016, 4:05:15 PM11/4/16
to
W dniu 04.11.2016 o 20:55, bartekltg pisze:
ale już poradziłem: gdy x jest blisko dwójki, tak że wartość P(x) rzędu
epsilon choć |x-2| rzędu sqrt(epsilon) przerzucam się na wyliczanie zera
pochodnej itd.
> Miałeś napisać, jaki to wielomian miał mieć pierwiastek
> 2, a zwracał 1.99999999cośtam.
Choćby (x^2 + 3x + 3)(x-1)(x-2)(x-2)(x-3)
> 2, a zwracał 1.99999999cośtam.
ale już poradziłem: gdy x jest blisko dwójki, tak że wartość P(x) rzędu
epsilon choć |x-2| rzędu sqrt(epsilon) przerzucam się na wyliczanie zera
pochodnej itd.
Borneq
Nov 4, 2016, 4:10:06 PM11/4/16
to
W dniu 04.11.2016 o 21:05, Borneq pisze:
Startując np. z 1.9, przy czym metoda dla liczb rzeczywistych sobie nie
radziła, bo nawet gdy znajdował część urojoną równą zero, to w
międzyczasie przechodził przez liczby zespolone, może tak jest tylko dla
wielokrotnych.
radziła, bo nawet gdy znajdował część urojoną równą zero, to w
międzyczasie przechodził przez liczby zespolone, może tak jest tylko dla
wielokrotnych.
Borneq
Nov 4, 2016, 4:48:24 PM11/4/16
to
W dniu 04.11.2016 o 21:10, Borneq pisze:
operacji, gdy już mam wielomian niskiego stopnia
1.0000000000000000 0.0000000000000000
poprawiony 1.0000000000000000 0.0000000000000000
2.0000000000000000 0.0000000000000000
poprawiony 2.0000000000000000 0.0000000000000000
-1.5000000000000000 -0.8660254037844387
poprawiony -1.5000000000000000 -0.8660254037844387
1.9999999999999991 0.0000000000000000
poprawiony 1.9999999999999991 0.0000000000000000
3.0000000000000004 0.0000000000000000
poprawiony 2.9999999999999987 0.0000000000000000
Najpierw był 3+2eps a potem 3-6eps, pogorszyło się trzykrotnie.
Jest tak bo mam wielomian (x^2 + 3·x + 3)(x-1)(x-2)(x-2)(x-3) =
x^6 - 5*x^5 + 2*x^4 + 17*x^3 - 3*x^2 - 48*x + 36
i teraz wychodzę z funkcji gdy |P(x)|<48*epsilon maszynowy, musi być 48
bo w Hornerze są liczby takiego rzędu (max abs z ai), inaczej mógłby być
duży błąd i mógłbym nie wyjść z procedury.
Natomiast gdy podzielę, szukam pierwiastka liniowego x-3, wtedy
max(abs(ai)) = 3, wychodzę z funkcji gdy |P(x)|<3*epsilon maszynowy
Może dlatego że dokładnie działa u mnie funkcja dzielenia wielomianów?
> Startując np. z 1.9, przy czym metoda dla liczb rzeczywistych sobie nie
> radziła, bo nawet gdy znajdował część urojoną równą zero, to w
> międzyczasie przechodził przez liczby zespolone, może tak jest tylko dla
> wielokrotnych.
Ale obecnie wygładzanie wyników tylko mi pogarsza, zwłaszcza pod koniec
> radziła, bo nawet gdy znajdował część urojoną równą zero, to w
> międzyczasie przechodził przez liczby zespolone, może tak jest tylko dla
> wielokrotnych.
operacji, gdy już mam wielomian niskiego stopnia
1.0000000000000000 0.0000000000000000
poprawiony 1.0000000000000000 0.0000000000000000
2.0000000000000000 0.0000000000000000
poprawiony 2.0000000000000000 0.0000000000000000
-1.5000000000000000 -0.8660254037844387
poprawiony -1.5000000000000000 -0.8660254037844387
1.9999999999999991 0.0000000000000000
poprawiony 1.9999999999999991 0.0000000000000000
3.0000000000000004 0.0000000000000000
poprawiony 2.9999999999999987 0.0000000000000000
Najpierw był 3+2eps a potem 3-6eps, pogorszyło się trzykrotnie.
Jest tak bo mam wielomian (x^2 + 3·x + 3)(x-1)(x-2)(x-2)(x-3) =
x^6 - 5*x^5 + 2*x^4 + 17*x^3 - 3*x^2 - 48*x + 36
i teraz wychodzę z funkcji gdy |P(x)|<48*epsilon maszynowy, musi być 48
bo w Hornerze są liczby takiego rzędu (max abs z ai), inaczej mógłby być
duży błąd i mógłbym nie wyjść z procedury.
Natomiast gdy podzielę, szukam pierwiastka liniowego x-3, wtedy
max(abs(ai)) = 3, wychodzę z funkcji gdy |P(x)|<3*epsilon maszynowy
Może dlatego że dokładnie działa u mnie funkcja dzielenia wielomianów?
Borneq
Nov 4, 2016, 5:10:01 PM11/4/16
to
W dniu 04.11.2016 o 21:48, Borneq pisze:
by dobre dla pierwiastków wielokrotnych; teraz przed samym wyjściem
wyliczam zero pochodnej gdy trzeba.
> i teraz wychodzę z funkcji gdy |P(x)|<48*epsilon maszynowy, musi być 48
Mógłbym co prawda wychodzić dopiero gdy |xk-xk-1|<2eps ale to nie było
by dobre dla pierwiastków wielokrotnych; teraz przed samym wyjściem
wyliczam zero pochodnej gdy trzeba.
Borneq
Nov 4, 2016, 5:44:40 PM11/4/16
to
W dniu 04.11.2016 o 21:48, Borneq pisze:
Waha się do 268 eps
> i teraz wychodzę z funkcji gdy |P(x)|<48*epsilon maszynowy, musi być 48
> bo w Hornerze są liczby takiego rzędu (max abs z ai), inaczej mógłby być
Tylko dlaczego mając bliższy punkt nie wychodzi mi od razu z funkcji ?
> bo w Hornerze są liczby takiego rzędu (max abs z ai), inaczej mógłby być
Waha się do 268 eps
M.M.
Nov 5, 2016, 1:55:38 AM11/5/16
to
On Friday, November 4, 2016 at 7:35:45 PM UTC+1, bartekltg wrote:
> >
> > Na ile te metody są efektywne i skuteczne? Gdy wielomiany będą miały
> > bardzo wysoki stopień (np. 10tys) to też można efektywnie znaleźć
> > wszystkie miejsca zerowe?
>
> Obstawiam, że nie.
> Przynajmniej nie w podwójnej precyzji (chyba, że wielomian bardzo
> przyzwoity).
>
> Jeśli miałbym próbować, raczej metodami przez macierz stowarzyszoną.
>
> Coś o wielomianie wiadomo?
Tak ogólnie zapytałem, może na przyszłość się przyda, teraz nie mam
> >
> > Na ile te metody są efektywne i skuteczne? Gdy wielomiany będą miały
> > bardzo wysoki stopień (np. 10tys) to też można efektywnie znaleźć
> > wszystkie miejsca zerowe?
>
> Obstawiam, że nie.
> Przynajmniej nie w podwójnej precyzji (chyba, że wielomian bardzo
> przyzwoity).
>
> Jeśli miałbym próbować, raczej metodami przez macierz stowarzyszoną.
>
> Coś o wielomianie wiadomo?
konkretnych problemów z ogromnymi wielomianami.
> Np że ma przyzwoicie rozłożone miejsca
> zerowe. Albo współczynniki wymierne.
> W takich lepszych przypadkach, ludzie faktoryzują wielomiany
> o stopniach parę tysięcy.
stosuje się szukanie miejsc zerowych dużych wielomianów? Jakie są
ciekawe zastosowania?
Pozdrawiam
peter
Nov 5, 2016, 6:57:48 AM11/5/16
to
M.M. pisze:
> Tak ogólnie zapytałem, może na przyszłość się przyda, teraz nie mam
> konkretnych problemów z ogromnymi wielomianami.
W linku Bartka ( P.Góra) i w dziesiątkach innych miejscach podawany jest przykład wielomianu Wilkinsona
(x+1)(x+2)..(x+19)(x+20) = x^20 + 210 x^19 + 20615 x^18 + ...
Jeżeli zmienimy wartość współczynnika przy x^19 z 210 na 210+1*10^-10 to 4-ty pierwiastek zmienia się z -16
na -16.264012.... Czyli przy błędzie względnym współczynnika o 5*10^-13 mamy zmianę miejsca zerowego o 1.65%.
Żeby uzyskać przyzwoite wyniki współczynniki wielomianu muszą być z dokładnością do 25 miejsc po przecinku a
czas obliczeń gwałtownie wzrasta (O(n^4)). Szukanie pierwiastków wielomianu stopnia 1000 gdy ma 1000
pierwiastków jest niewykonalne.
Gdy pierwiastków rzeczywistych jest jednak znacznie mniej od n to można w miarę 'prosto' znaleźć te pierwiastki.
Sam rozwiązywałem wielomian stopnia 1024, który miał 10 pierwiastki rzeczywiste. Czas obliczeń to, jeżeli
dobrze pamiętam, 10 minut. Dla stopnia 2048 system już padł ( było to już kilka lat temu, więc obecnie może
dałoby radę)
PS. Tylko nie pomyśl, że takie rozwiązywanie równań wysokiego stopnia można uzyskać metodami autora wątku.
--
Peter
>>>
>>> Na ile te metody są efektywne i skuteczne? Gdy wielomiany będą miały
>>> bardzo wysoki stopień (np. 10tys) to też można efektywnie znaleźć
>>> wszystkie miejsca zerowe?
Poniosła cię ułańska fantazja,
>>> Na ile te metody są efektywne i skuteczne? Gdy wielomiany będą miały
>>> bardzo wysoki stopień (np. 10tys) to też można efektywnie znaleźć
>>> wszystkie miejsca zerowe?
> Tak ogólnie zapytałem, może na przyszłość się przyda, teraz nie mam
> konkretnych problemów z ogromnymi wielomianami.
(x+1)(x+2)..(x+19)(x+20) = x^20 + 210 x^19 + 20615 x^18 + ...
Jeżeli zmienimy wartość współczynnika przy x^19 z 210 na 210+1*10^-10 to 4-ty pierwiastek zmienia się z -16
na -16.264012.... Czyli przy błędzie względnym współczynnika o 5*10^-13 mamy zmianę miejsca zerowego o 1.65%.
Żeby uzyskać przyzwoite wyniki współczynniki wielomianu muszą być z dokładnością do 25 miejsc po przecinku a
czas obliczeń gwałtownie wzrasta (O(n^4)). Szukanie pierwiastków wielomianu stopnia 1000 gdy ma 1000
pierwiastków jest niewykonalne.
Gdy pierwiastków rzeczywistych jest jednak znacznie mniej od n to można w miarę 'prosto' znaleźć te pierwiastki.
Sam rozwiązywałem wielomian stopnia 1024, który miał 10 pierwiastki rzeczywiste. Czas obliczeń to, jeżeli
dobrze pamiętam, 10 minut. Dla stopnia 2048 system już padł ( było to już kilka lat temu, więc obecnie może
dałoby radę)
PS. Tylko nie pomyśl, że takie rozwiązywanie równań wysokiego stopnia można uzyskać metodami autora wątku.
--
Peter
M.M.
Nov 5, 2016, 3:46:45 PM11/5/16
to
On Saturday, November 5, 2016 at 11:57:48 AM UTC+1, peter wrote:
> Poniosła cię ułańska fantazja,
Hmmmm.
> Szukanie pierwiastków wielomianu stopnia 1000 gdy ma 1000
> pierwiastków jest niewykonalne.
Czyli nie tylko trudne, ale na przeciętnym sprzęcie, nawet niewykonalne.
> Gdy pierwiastków rzeczywistych jest jednak znacznie mniej od n to
> można w miarę 'prosto' znaleźć te pierwiastki.
Rozumiem.
> Sam rozwiązywałem wielomian stopnia 1024, który miał 10 pierwiastki rzeczywiste. Czas obliczeń to, jeżeli
> dobrze pamiętam, 10 minut. Dla stopnia 2048 system już padł ( było to już kilka lat temu, więc obecnie może
> dałoby radę)
>
> PS. Tylko nie pomyśl, że takie rozwiązywanie równań wysokiego stopnia można uzyskać metodami autora wątku.
Ok, nie pomyślę.
Najważniejsze pytanie, jakie są praktyczne zastosowania dla
szukania miejsc zerowych, może nie ułańskich, ale dużych wielomianów?
Pozdrawiam
> Poniosła cię ułańska fantazja,
Hmmmm.
> Szukanie pierwiastków wielomianu stopnia 1000 gdy ma 1000
> pierwiastków jest niewykonalne.
> Gdy pierwiastków rzeczywistych jest jednak znacznie mniej od n to
> można w miarę 'prosto' znaleźć te pierwiastki.
> Sam rozwiązywałem wielomian stopnia 1024, który miał 10 pierwiastki rzeczywiste. Czas obliczeń to, jeżeli
> dobrze pamiętam, 10 minut. Dla stopnia 2048 system już padł ( było to już kilka lat temu, więc obecnie może
> dałoby radę)
>
> PS. Tylko nie pomyśl, że takie rozwiązywanie równań wysokiego stopnia można uzyskać metodami autora wątku.
Najważniejsze pytanie, jakie są praktyczne zastosowania dla
szukania miejsc zerowych, może nie ułańskich, ale dużych wielomianów?
Pozdrawiam
peter
Nov 5, 2016, 5:10:26 PM11/5/16
to
M.M. pisze:
zastosowaniach.
W moim przypadku, nie wchodząc w szczegóły, równanie kwadratowe było rekurencyjnie 10-krotnie wywoływane i
stąd powstał wielomian stopnia 2^10. Było też wiadome, że będzie 10 lub wielokrotność 10 pierwiastków
rzeczywistych. Obliczenia prowadzone były z opcją poszukiwania wyłącznie pierwiastków rzeczywistych.
--
Peter
>
> Najważniejsze pytanie, jakie są praktyczne zastosowania dla
> szukania miejsc zerowych, może nie ułańskich, ale dużych wielomianów?
>
Miejsca zerowe dla wysokich stopni wielomianów są bardzo rzadko poszukiwane. Zwykle w bardzo specyficznych
> Najważniejsze pytanie, jakie są praktyczne zastosowania dla
> szukania miejsc zerowych, może nie ułańskich, ale dużych wielomianów?
>
zastosowaniach.
W moim przypadku, nie wchodząc w szczegóły, równanie kwadratowe było rekurencyjnie 10-krotnie wywoływane i
stąd powstał wielomian stopnia 2^10. Było też wiadome, że będzie 10 lub wielokrotność 10 pierwiastków
rzeczywistych. Obliczenia prowadzone były z opcją poszukiwania wyłącznie pierwiastków rzeczywistych.
--
Peter
bartekltg
Nov 6, 2016, 4:45:08 AM11/6/16
to
On 05.11.2016 22:10, peter wrote:
> M.M. pisze:
>>
>> Najważniejsze pytanie, jakie są praktyczne zastosowania dla
>> szukania miejsc zerowych, może nie ułańskich, ale dużych wielomianów?
>>
> Miejsca zerowe dla wysokich stopni wielomianów są bardzo rzadko
> poszukiwane. Zwykle w bardzo specyficznych zastosowaniach.
> W moim przypadku, nie wchodząc w szczegóły, równanie kwadratowe było
> rekurencyjnie 10-krotnie wywoływane i stąd powstał wielomian stopnia
> 2^10.
Coś takiego?
> M.M. pisze:
>>
>> Najważniejsze pytanie, jakie są praktyczne zastosowania dla
>> szukania miejsc zerowych, może nie ułańskich, ale dużych wielomianów?
>>
> Miejsca zerowe dla wysokich stopni wielomianów są bardzo rzadko
> poszukiwane. Zwykle w bardzo specyficznych zastosowaniach.
> W moim przypadku, nie wchodząc w szczegóły, równanie kwadratowe było
> rekurencyjnie 10-krotnie wywoływane i stąd powstał wielomian stopnia
> 2^10.
x_1 = a1 x0^2 + b1 x0 + c1
x_2 = a2 x1^2 + b2 x1 + c2
x_3 = a3 x2^2 + b3 x2 + c3
...
x_10 = a10 x9^2 + b10 x9 + c10
I szukamy zer x_10.
> Było też wiadome, że będzie 10 lub wielokrotność 10 pierwiastków
> rzeczywistych. Obliczenia prowadzone były z opcją poszukiwania wyłącznie
> pierwiastków rzeczywistych.
Pewnie bym próbował wyliczyć piewrwiastki
a10 x9^2 + b10 x9 + c10
z tego dostał parę x_9, nastpęnie liczły pierwiastki
(wzgledem x_8)
a9 x8^2 + b9 x8 + c9 - x9 ==0
T tak aż do x0. Może dla 10 kroków zbytnia wynik nie popłynie.
pzdr
bartekltg
Borneq
Nov 6, 2016, 5:44:20 AM11/6/16
to
W dniu 04.11.2016 o 21:48, Borneq pisze:
pogarszać tylko zostawiać ten sam punkt.
Kwestią jest warunek przerwania pętli.
Dokładność wyliczenia funkcji w punkcie składa się z dwóch czynników:
jeden to pochodna, drugi to kumulacja błędów (która będzie przeważać gdy
pochodna mała - pierwiastki wielokrotne)
Doszedłem do procedury obliczającej kumulację:
double estimEps(double x, int n, double *P)
{
if (n<0) return 0;
double value = P[n];
double esterror = 0;
for (int i = n - 1; i >= 0; i--)
{
value *= x;
double esterror1 = esterror*x;
double esterror2 = 0.35* value;
esterror = sqrt(esterror1*esterror1 + esterror2*esterror2);
value += P[i];
esterror = std::max(esterror, fabs(0.35*value));
}
return esterror;
}
Problem, że gdy chcemy prawidłowo obsługiwać warunek wyjścia, należy w
pętli liczyć estimEps (w jednostkach epsilon) a samo liczenie trwa
dłużej niż liczenie wartości Hornerem.
> Ale obecnie wygładzanie wyników tylko mi pogarsza, zwłaszcza pod koniec
> operacji, gdy już mam wielomian niskiego stopnia
> operacji, gdy już mam wielomian niskiego stopnia
> 3.0000000000000004 0.0000000000000000
> poprawiony 2.9999999999999987 0.0000000000000000
Wygładzanie, nawet gdy nie poprawia, nie powinno w żadnym razie
> poprawiony 2.9999999999999987 0.0000000000000000
pogarszać tylko zostawiać ten sam punkt.
Kwestią jest warunek przerwania pętli.
Dokładność wyliczenia funkcji w punkcie składa się z dwóch czynników:
jeden to pochodna, drugi to kumulacja błędów (która będzie przeważać gdy
pochodna mała - pierwiastki wielokrotne)
Doszedłem do procedury obliczającej kumulację:
double estimEps(double x, int n, double *P)
{
if (n<0) return 0;
double value = P[n];
double esterror = 0;
for (int i = n - 1; i >= 0; i--)
{
value *= x;
double esterror1 = esterror*x;
double esterror2 = 0.35* value;
esterror = sqrt(esterror1*esterror1 + esterror2*esterror2);
value += P[i];
esterror = std::max(esterror, fabs(0.35*value));
}
return esterror;
}
Problem, że gdy chcemy prawidłowo obsługiwać warunek wyjścia, należy w
pętli liczyć estimEps (w jednostkach epsilon) a samo liczenie trwa
dłużej niż liczenie wartości Hornerem.
peter
Nov 7, 2016, 11:28:06 AM11/7/16
to
bartekltg pisze:
x(n+1) = a x(n)^2 + b x(n) + c
Dla wielu wartości a,b,c to są szeregi rozbieżne.
Jednak dla niektórych kombinacji a,b,c zbiegają się ( i to zależy jeszcze od wartości startowej).
Najbardziej trywialny sposób zbiegają się do pewnej granicy
W tym przypadku rozwiązujemy równanie ax^2+bx+c = x !
Znacznie trudniej jest znaleźć przypadki, w których wartości szeregu oscylują cyklicznie dookoła kilku wartości np
x(n) x(n+1) x(n+2) x(n+3)->x(n) x(n+4)->x(n+1) x(n+5)->x(n+2)
w tym przypadku granicznym
f = ax^2 + bx +c
f(f(f)) = x rozwiązujemy równanie 8-stopnia i szukamy pierwiastków rzeczywistych.
Podobnie będzie z przypadkiem mającym 10 wartości w cyklu, tylko wielomian będzie stopnia 2^10
Niestety nie umiem podać konkretnego przykładu, bo materiały gdzieś się zawieruszyły w przepastnym archiwum
komputera.
Ad hoc wymyśliłem taki przykład, f = 1/2 x^2 - 5/7 x + 1. Niestety jest to przykład trywialny na pojedynczą
granicę, gdy startujemy tak mniej więcej -1.2 <= x0 <= 2.68
> Jak to rzowiązywałeś?
Już wiele lat temu porządnie rozwinęła się technologia obliczeń numerycznych i symbolicznych. Jest co najmniej
kilka programów łatwiej lub trudniej dostępnych ( czytaj płatnych). Próba a.d. 2016 pisania programów do
obliczeń numerycznych z książek prehistorycznych, jak to czyni autor tego oraz wiele.. wiele innych wątków,
jest jak używanie młotka do naprawy mercedesa.
Nie będę ukrywał, że używałem do do rozwiązania równania stopnia 2^10 mathematiki, do której miałem służbowy
dostęp. Używałem funkcji Solve z opcja Reals. I to wszystko
Pozdrawiam,
--
Peter
> Coś takiego?
>
> x_1 = a1 x0^2 + b1 x0 + c1
> x_2 = a2 x1^2 + b2 x1 + c2
> x_3 = a3 x2^2 + b3 x2 + c3
> ...
> x_10 = a10 x9^2 + b10 x9 + c10
>
Blisko. choć dokładniej tak
>
> x_1 = a1 x0^2 + b1 x0 + c1
> x_2 = a2 x1^2 + b2 x1 + c2
> x_3 = a3 x2^2 + b3 x2 + c3
> ...
> x_10 = a10 x9^2 + b10 x9 + c10
>
x(n+1) = a x(n)^2 + b x(n) + c
Dla wielu wartości a,b,c to są szeregi rozbieżne.
Jednak dla niektórych kombinacji a,b,c zbiegają się ( i to zależy jeszcze od wartości startowej).
Najbardziej trywialny sposób zbiegają się do pewnej granicy
W tym przypadku rozwiązujemy równanie ax^2+bx+c = x !
Znacznie trudniej jest znaleźć przypadki, w których wartości szeregu oscylują cyklicznie dookoła kilku wartości np
x(n) x(n+1) x(n+2) x(n+3)->x(n) x(n+4)->x(n+1) x(n+5)->x(n+2)
w tym przypadku granicznym
f = ax^2 + bx +c
f(f(f)) = x rozwiązujemy równanie 8-stopnia i szukamy pierwiastków rzeczywistych.
Podobnie będzie z przypadkiem mającym 10 wartości w cyklu, tylko wielomian będzie stopnia 2^10
Niestety nie umiem podać konkretnego przykładu, bo materiały gdzieś się zawieruszyły w przepastnym archiwum
komputera.
Ad hoc wymyśliłem taki przykład, f = 1/2 x^2 - 5/7 x + 1. Niestety jest to przykład trywialny na pojedynczą
granicę, gdy startujemy tak mniej więcej -1.2 <= x0 <= 2.68
> Jak to rzowiązywałeś?
Już wiele lat temu porządnie rozwinęła się technologia obliczeń numerycznych i symbolicznych. Jest co najmniej
kilka programów łatwiej lub trudniej dostępnych ( czytaj płatnych). Próba a.d. 2016 pisania programów do
obliczeń numerycznych z książek prehistorycznych, jak to czyni autor tego oraz wiele.. wiele innych wątków,
jest jak używanie młotka do naprawy mercedesa.
Nie będę ukrywał, że używałem do do rozwiązania równania stopnia 2^10 mathematiki, do której miałem służbowy
dostęp. Używałem funkcji Solve z opcja Reals. I to wszystko
Pozdrawiam,
--
Peter
bartekltg
Nov 8, 2016, 1:13:45 PM11/8/16
to
On 07.11.2016 17:27, peter wrote:
> bartekltg pisze:
>> Coś takiego?
>>
>> x_1 = a1 x0^2 + b1 x0 + c1
>> x_2 = a2 x1^2 + b2 x1 + c2
>> x_3 = a3 x2^2 + b3 x2 + c3
>> ...
>> x_10 = a10 x9^2 + b10 x9 + c10
>>
>
> Blisko. choć dokładniej tak
>
> x(n+1) = a x(n)^2 + b x(n) + c
>
> Dla wielu wartości a,b,c to są szeregi rozbieżne.
> Jednak dla niektórych kombinacji a,b,c zbiegają się ( i to zależy
> jeszcze od wartości startowej).
> Najbardziej trywialny sposób zbiegają się do pewnej granicy
> W tym przypadku rozwiązujemy równanie ax^2+bx+c = x !
> Znacznie trudniej jest znaleźć przypadki, w których wartości szeregu
> oscylują cyklicznie dookoła kilku wartości np
> x(n) x(n+1) x(n+2) x(n+3)->x(n) x(n+4)->x(n+1) x(n+5)->x(n+2)
> w tym przypadku granicznym
> f = ax^2 + bx +c
> f(f(f)) = x rozwiązujemy równanie 8-stopnia i szukamy pierwiastków
> rzeczywistych.
Jest tu pewna swoboda. Możemy przeskalować x tak, by pierwiastki
> bartekltg pisze:
>> Coś takiego?
>>
>> x_1 = a1 x0^2 + b1 x0 + c1
>> x_2 = a2 x1^2 + b2 x1 + c2
>> x_3 = a3 x2^2 + b3 x2 + c3
>> ...
>> x_10 = a10 x9^2 + b10 x9 + c10
>>
>
> Blisko. choć dokładniej tak
>
> x(n+1) = a x(n)^2 + b x(n) + c
>
> Dla wielu wartości a,b,c to są szeregi rozbieżne.
> Jednak dla niektórych kombinacji a,b,c zbiegają się ( i to zależy
> jeszcze od wartości startowej).
> Najbardziej trywialny sposób zbiegają się do pewnej granicy
> W tym przypadku rozwiązujemy równanie ax^2+bx+c = x !
> Znacznie trudniej jest znaleźć przypadki, w których wartości szeregu
> oscylują cyklicznie dookoła kilku wartości np
> x(n) x(n+1) x(n+2) x(n+3)->x(n) x(n+4)->x(n+1) x(n+5)->x(n+2)
> w tym przypadku granicznym
> f = ax^2 + bx +c
> f(f(f)) = x rozwiązujemy równanie 8-stopnia i szukamy pierwiastków
> rzeczywistych.
wielomianu były w 0 i 1, wtedy mamy tylko jeden stopień swobody,
a zachowanie jest identyczne
x <- r x(1-x)
gdzie r jest tym naszym parametrem.
> Podobnie będzie z przypadkiem mającym 10 wartości w cyklu, tylko
> wielomian będzie stopnia 2^10
Jeśli będzie jeden, to będzie ich 10, ale skąd przypuszczenie,
że nie będzie większej liczby pierwiastków odpowiadających
dziesiątkom z różnych okresów?
Popatrzma na w pełni chaotyczny wielomian
x <- 4 x (x-1)
f(x) = 4x(1-x)
f^[n](x) == x ma pełne 2^n rozwiązań dla x \in (0,1)
Dobrze to widać patrząc na przekształcenie 'namiocik',
(sprzeżone(*) z logistycznym dla r=4)
https://en.wikipedia.org/wiki/Tent_map#Behaviour
x <- g(x) = 2x dla x<=0.5
2-2x dla x>0.5
Zamiana zmiennych jest pokretna, ale działa(i jest wypisana
wzorkiem w linku.
Wyiterowane n razy g^[n](x) to piła złożona z 2^(n-1)
namiocików. Każdy namiocik przecina się z prostą y=x
dwa razy.
Dla ewentualnych czytelników;)
*) sprzeżenie topologiczne dwóch odwzorowań g(y) -> y
i f(x) ->x (układów dynamicznych) to takie przekształcenie
(odwracalne) h: x->y, że
g(h(x)) = h(f(x))
Albo, inaczej, f = h^-1 (*) g (*) h
(*) - skąłdanie funkcji.
Wtedy widać, że
f^[n] = (h^-1 (*) g (*) h)^n = h^-1 (*) g^[n] (*) h
Więc układy zachowują się tak samo przy iterowaniu.
Mamy przy 10 iteracjach 1024 pierwiastki. I siedzą one w cyklach
nawet po 10 (pewnie mogą odpowiadać krótszym)
Ogolnie (la dowolnego r) chyba jednak nie da się tego tak
zrobić.
> Ad hoc wymyśliłem taki przykład, f = 1/2 x^2 - 5/7 x + 1. Niestety jest
> to przykład trywialny na pojedynczą granicę, gdy startujemy tak mniej
> więcej -1.2 <= x0 <= 2.68
https://en.wikipedia.org/wiki/Logistic_map#Behavior_dependent_on_.7F.27.22.60UNIQ--postMath-00000007-QINU.60.22.27.7F
W ksiąkach do układów dynamicznych mozna znaleść lepszą,
np porządnie opisującą porządek Szarkowskiego:
https://en.wikipedia.org/wiki/Sharkovskii%27s_theorem
>> Jak to rzowiązywałeś?
>
> Już wiele lat temu porządnie rozwinęła się technologia obliczeń
> numerycznych i symbolicznych. Jest co najmniej kilka programów łatwiej
> lub trudniej dostępnych ( czytaj płatnych). Próba a.d. 2016 pisania
> programów do obliczeń numerycznych z książek prehistorycznych, jak to
> czyni autor tego oraz wiele.. wiele innych wątków, jest jak używanie
> młotka do naprawy mercedesa.
>
> Nie będę ukrywał, że używałem do do rozwiązania równania stopnia 2^10
> mathematiki, do której miałem służbowy dostęp. Używałem funkcji Solve z
> opcja Reals. I to wszystko
pzdr
bartekltg
peter
Nov 9, 2016, 11:57:20 AM11/9/16
to
bartekltg pisze:
>> Podobnie będzie z przypadkiem mającym 10 wartości w cyklu, tylko
>> wielomian będzie stopnia 2^10
>
> Skąd pewność, żę pierwiastków będzie tylko 10?
To był błąd mojej pamięci. I nie tylko to.
Znalazłem ten swój stary program pod nazwą chaos ;)
f = -3/2 x^2 + 5/2 x + 2
f(n+1) = f(n)/.x -> f
Jeżeli startujemy przykładowo od x=1 to otrzymamy chaotyczny rozkład wyników w przedziale
(-0.296875,4.08333)
jeżeli wystartujemy z x=0 to otrzymamy cykl złożony z 3 elementów 0,2,4,0,2,4 itd
jeżeli wystartujemy z x=-0.2444519949909373272 to otrzymamy cykl złożony z 9 elementów. Łatwo sprawdzić że
f(1),f(2), f(3) ...są różne a f(10) = f(1)( z małym epsilonem)
Dla cyklu 9-elementowego ( wielomian stopnia 2^9 = 512) było 98 rozwiązań rzeczywistych, w tym 2 odpowiadające
za cykl 1-elementowy oraz 6 za cykl 3-elementowy.
I na tym zakończyłem, bo cykl 10-elementowy ( wielomian 2^10 = 1024) nie dało się rozwiązać w rozsądnym
czasie. Niestety. I tu również pobłądziłem.
--
Peter
>>
>> x(n+1) = a x(n)^2 + b x(n) + c
>>
>> x(n+1) = a x(n)^2 + b x(n) + c
>>
>> x(n) x(n+1) x(n+2) x(n+3)->x(n) x(n+4)->x(n+1) x(n+5)->x(n+2)
>> w tym przypadku granicznym
>> f = ax^2 + bx +c
>> f(f(f)) = x rozwiązujemy równanie 8-stopnia i szukamy pierwiastków
>> rzeczywistych.
> Jest tu pewna swoboda. Możemy przeskalować x tak, by pierwiastki
> wielomianu były w 0 i 1, wtedy mamy tylko jeden stopień swobody,
> a zachowanie jest identyczne
>
> x <- r x(1-x)
?? gdzie tu równanie kwadratowe
>> w tym przypadku granicznym
>> f = ax^2 + bx +c
>> f(f(f)) = x rozwiązujemy równanie 8-stopnia i szukamy pierwiastków
>> rzeczywistych.
> Jest tu pewna swoboda. Możemy przeskalować x tak, by pierwiastki
> wielomianu były w 0 i 1, wtedy mamy tylko jeden stopień swobody,
> a zachowanie jest identyczne
>
> x <- r x(1-x)
>> Podobnie będzie z przypadkiem mającym 10 wartości w cyklu, tylko
>> wielomian będzie stopnia 2^10
>
> Skąd pewność, żę pierwiastków będzie tylko 10?
Znalazłem ten swój stary program pod nazwą chaos ;)
f = -3/2 x^2 + 5/2 x + 2
f(n+1) = f(n)/.x -> f
Jeżeli startujemy przykładowo od x=1 to otrzymamy chaotyczny rozkład wyników w przedziale
(-0.296875,4.08333)
jeżeli wystartujemy z x=0 to otrzymamy cykl złożony z 3 elementów 0,2,4,0,2,4 itd
jeżeli wystartujemy z x=-0.2444519949909373272 to otrzymamy cykl złożony z 9 elementów. Łatwo sprawdzić że
f(1),f(2), f(3) ...są różne a f(10) = f(1)( z małym epsilonem)
Dla cyklu 9-elementowego ( wielomian stopnia 2^9 = 512) było 98 rozwiązań rzeczywistych, w tym 2 odpowiadające
za cykl 1-elementowy oraz 6 za cykl 3-elementowy.
I na tym zakończyłem, bo cykl 10-elementowy ( wielomian 2^10 = 1024) nie dało się rozwiązać w rozsądnym
czasie. Niestety. I tu również pobłądziłem.
--
Peter
bartekltg
Nov 9, 2016, 9:02:57 PM11/9/16
to
On 09.11.2016 17:57, peter wrote:
> bartekltg pisze:
>>>
>>> x(n+1) = a x(n)^2 + b x(n) + c
>>>
>>> x(n) x(n+1) x(n+2) x(n+3)->x(n) x(n+4)->x(n+1) x(n+5)->x(n+2)
>>> w tym przypadku granicznym
>>> f = ax^2 + bx +c
>>> f(f(f)) = x rozwiązujemy równanie 8-stopnia i szukamy pierwiastków
>>> rzeczywistych.
>
>> Jest tu pewna swoboda. Możemy przeskalować x tak, by pierwiastki
>> wielomianu były w 0 i 1, wtedy mamy tylko jeden stopień swobody,
>> a zachowanie jest identyczne
>>
>> x <- r x(1-x)
>
> ?? gdzie tu równanie kwadratowe
r x (1-x)
> bartekltg pisze:
>>>
>>> x(n+1) = a x(n)^2 + b x(n) + c
>>>
>>> x(n) x(n+1) x(n+2) x(n+3)->x(n) x(n+4)->x(n+1) x(n+5)->x(n+2)
>>> w tym przypadku granicznym
>>> f = ax^2 + bx +c
>>> f(f(f)) = x rozwiązujemy równanie 8-stopnia i szukamy pierwiastków
>>> rzeczywistych.
>
>> Jest tu pewna swoboda. Możemy przeskalować x tak, by pierwiastki
>> wielomianu były w 0 i 1, wtedy mamy tylko jeden stopień swobody,
>> a zachowanie jest identyczne
>>
>> x <- r x(1-x)
>
> ?? gdzie tu równanie kwadratowe
Jest kwadratowe.
łatwiej mi napsać to ze strzałeczką niż równanie rekurencyjne
x_{n+1} = r x_n (1-x_n)
>>> Podobnie będzie z przypadkiem mającym 10 wartości w cyklu, tylko
>>> wielomian będzie stopnia 2^10
>>
>> Skąd pewność, żę pierwiastków będzie tylko 10?
>
> To był błąd mojej pamięci. I nie tylko to.
>
> Znalazłem ten swój stary program pod nazwą chaos ;)
>
> f = -3/2 x^2 + 5/2 x + 2
> f(n+1) = f(n)/.x -> f
>
> Jeżeli startujemy przykładowo od x=1 to otrzymamy chaotyczny rozkład
> wyników w przedziale
> (-0.296875,4.08333)
>
> jeżeli wystartujemy z x=0 to otrzymamy cykl złożony z 3 elementów
> 0,2,4,0,2,4 itd
In[174]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
2, x[0] == 1}, x[n], {n, 0, 5}]
Out[174]= {1, 3, -4, -32, -1614, -3911527}
In[176]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
2, x[0] == 0}, x[n], {n, 0, 7}]
Out[176]= {0, 2, 1, 3, -4, -32, -1614, -3911527}
Nie ma literówki w wielomianie?
pzdr
bartekltg
peter
Nov 10, 2016, 8:58:01 AM11/10/16
to
bartekltg pisze:
>> f = -3/2 x^2 + 5/2 x + 2
>> f(n+1) = f(n)/.x -> f
Zamiast RecurrenceTable można użyć takiego schematu
u = x0 = 1
Table[u = f /. x -> u, {10}]
u = x0 = 0
Table[u = f /. x -> u, {10}]
--
Peter
>> f = -3/2 x^2 + 5/2 x + 2
>> f(n+1) = f(n)/.x -> f
>> jeżeli wystartujemy z x=0 to otrzymamy cykl złożony z 3 elementów
>> 0,2,4,0,2,4 itd
>
> Hmm, mi wychodzi inaczej,
> In[174]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
> 2, x[0] == 1}, x[n], {n, 0, 5}]
> Out[174]= {1, 3, -4, -32, -1614, -3911527}
>
> In[176]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
> 2, x[0] == 0}, x[n], {n, 0, 7}]
> Out[176]= {0, 2, 1, 3, -4, -32, -1614, -3911527}
>
> Nie ma literówki w wielomianie?
Niestety jest. Miało być f = -3/4 x^2 + 5/2 x + 2
>> 0,2,4,0,2,4 itd
>
> Hmm, mi wychodzi inaczej,
> In[174]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
> 2, x[0] == 1}, x[n], {n, 0, 5}]
> Out[174]= {1, 3, -4, -32, -1614, -3911527}
>
> In[176]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
> 2, x[0] == 0}, x[n], {n, 0, 7}]
> Out[176]= {0, 2, 1, 3, -4, -32, -1614, -3911527}
>
> Nie ma literówki w wielomianie?
Zamiast RecurrenceTable można użyć takiego schematu
u = x0 = 1
Table[u = f /. x -> u, {10}]
u = x0 = 0
Table[u = f /. x -> u, {10}]
--
Peter
bartekltg
Nov 10, 2016, 10:04:23 AM11/10/16
to
On 10.11.2016 14:57, peter wrote:
> bartekltg pisze:
>
>>> f = -3/2 x^2 + 5/2 x + 2
>>> f(n+1) = f(n)/.x -> f
>>> jeżeli wystartujemy z x=0 to otrzymamy cykl złożony z 3 elementów
>>> 0,2,4,0,2,4 itd
>>
>> Hmm, mi wychodzi inaczej,
>> In[174]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
>> 2, x[0] == 1}, x[n], {n, 0, 5}]
>> Out[174]= {1, 3, -4, -32, -1614, -3911527}
>>
>> In[176]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
>> 2, x[0] == 0}, x[n], {n, 0, 7}]
>> Out[176]= {0, 2, 1, 3, -4, -32, -1614, -3911527}
>>
>> Nie ma literówki w wielomianie?
>
> Niestety jest. Miało być f = -3/4 x^2 + 5/2 x + 2
OK, teraz mi działa:)
> bartekltg pisze:
>
>>> f = -3/2 x^2 + 5/2 x + 2
>>> f(n+1) = f(n)/.x -> f
>>> jeżeli wystartujemy z x=0 to otrzymamy cykl złożony z 3 elementów
>>> 0,2,4,0,2,4 itd
>>
>> Hmm, mi wychodzi inaczej,
>> In[174]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
>> 2, x[0] == 1}, x[n], {n, 0, 5}]
>> Out[174]= {1, 3, -4, -32, -1614, -3911527}
>>
>> In[176]:= RecurrenceTable[{x[n + 1] == -(3/2) (x[n])^2 + (5/2) x[n] +
>> 2, x[0] == 0}, x[n], {n, 0, 7}]
>> Out[176]= {0, 2, 1, 3, -4, -32, -1614, -3911527}
>>
>> Nie ma literówki w wielomianie?
>
> Niestety jest. Miało być f = -3/4 x^2 + 5/2 x + 2
Wielomian odpowiada 'standardowemu' z paremetrem
r = 3.872281323269014329925305734109464659110...
Poprzednio wychodzilo ponad 4, więc trajektrorie powinny sie
rozbiegać...
Przekształcenie (sprzeżenie) szuka się jednak w ciut bardziej
skomplikowany sposób niż poprzednio opisałem, ale nadal
wśród funkcji liniowych ;-)
h = a x + b ;
hInv = Solve[h == y, x];
g = -3/4 x^2 + 5/2 x + 2;
w = (h /. x -> g ) /. hInv[[1]] // FullSimplify;
cc = CoefficientList[w, y];
{cc[[1]] == cc[[2]], cc[[3]] == 0} // FullSimplify
ab = Solve[{cc[[3]] == -cc[[2]], cc[[1]] == 0}, {a, b}]
ww = w /. ab // FullSimplify
N[ww, 40]
pzdr
bartekltg
0 new messages