Metoda Laguerre'a może i by była dobra gdyby nie konieczność korzystania z arytmetyki zespolonej nawet gdy wielomian ma współczynniki rzeczywiste (Wtedy zespolone pierwiastki można połączyć we wzajemnie sprzężone pary i nie ma konieczności korzystania z arytmetyki zespolonej) Ponadto metoda Laguerre'a nie jest niezawodna bo widziałem przykład w którym mianownik się zerował

Thanks for the comment. The parameter u varies from -pi to pi, while v varies from 0 to 14 pi. Here is an explicit Sagemath code to plot the shell (without coloring): var("u,v") # parameters aa = 2 bb = 2.5 cc = 0.15 dd = 4.15 ee = -2 vv = v + (v + ee)^2/16 s = exp(-cc*vv) r = s*aa + s*bb*cos(u) x = r*cos(vv) y = dd*(1-s) + s*bb*sin(u) z = r*sin(vv) parametric_plot3d( (x,z,y), (u, -pi, pi), (v, 0, 14*pi), plot_points = (100, 400) )

@@pkoprowski much appreciated ! I'm preparing kind of a show for elementary school kids <10. y.o mixing art & maths. I find your example good to add to my library. The objective is to make them loving and understanding that Maths as also beautiful.

Algorytmów aproksymacji pierwiastków wielomianów jest multum. Pewnie setki. Niektóre są dobrze znane (jak wymieniony w komentarzu Bairstow, czy wspominany pobieżnie na tym wykładzie Laguerre). Inne (jak Newton) są *bardzo* dobrze znane. Jeszcze inne są trochę mniej znane (jak omawiany na wykładzie QIR Abbotta). Tak jak pisałem w odpowiedzi do komentarza pod innym wykładem - istotne jest aby znać jak najwięcej narzędzi. Wtedy w danej sytuacji można wybrać najbardziej optymalną metodę. Przykładowo - wspomniana metoda Laguerre'a też znajduje pierwiastki zespolone i jest asymptotycznie szybsza od metody Bairstowa, ale bywa "kapryśna". Przy źle wybranym elemencie początkowym (ang. initial guess) ciąg może być rozbieżny. Albo nawet zbieżny, ale wyjątkowo wolno. Bairstow zresztą też w pewnych sytuacjach miewa "narowy". Z kolei QIR jest asymptotycznie równie szybki jak Newton,a przy tym zawsze zbieżny, ale nadaje się tylko do pierwiastków rzeczywistych. Dlatego właśnie warto znać różne algorytmy. Można je też nawet łączyć ze sobą, np. użyć QIR (lub AQIR jeśli współczynniki są zmiennoprzecinkowe) aby wychwycić pierwiastki rzeczywiste, a potem Bairstowa, aby wyznaczyć pary pierwiastków zespolonych. Co do pierwiastków wielokrotnych, jeżeli współczynniki wielomianu są dokładne (np. całkowitoliczbowe, wymierne albo wyrażone za pomocą dokładnej reprezentacji liczb algebraicznych), to problem można łatwo rozwiązać wyznaczając rozkład bezkwadratowy wielomianu (albo przynajmniej radykał). Jeżeli jednak współczynniki są zmiennoprzecinkowe, to rozkład bezkwadratowy nie zadziała.

@@pkoprowski No tak ale zdaje się że metoda Laguerra wymaga arytmetyki zespolonej a metoda Bairstowa już nie Czy planuje Pan omówić metody znajdowania wartości własnych ? Od metod potęgowych które pozwalają obliczyć pojedynczą parę własną (wartość własna i odpowiadający jej wektor własny) Metoda potęgowa znajduje największą co do modułu wartość własną i odpowiadający jej wektor własny Odwrotna metoda potęgowa znajduje najmniejszą co do modułu wartość własną i odpowiadający jej wektor własny Po zastosowaniu przesunięcia znajduje parę własną najbliższą przesunięciu Aby znaleźć zespoloną parę własną wymagana jest arytmetyka zespolona Dla wielokrotnej wartości własnej podobno tylko jeden wektor własny jest możliwy do znalezienia (bez dodatkowej informacji o klatkach Jordana - Z Fortuna, B Macukow, J Wąsowski Metody numeryczne) Metoda QR A_{k} = Q_{k}R_{k} A_{k+1} = R_{k}Q_{k} Nietrudno pokazać że wszystkie macierze w tak utworzonym ciągu będą do siebie podobne Metoda QR z przesunięciem A_{k} - sI = Q_{k}R_{k} A_{k+1} = R_{k}Q_{k}+sI Co do usprawnień to redukcja przez podobieństwo macierzy A do postaci Hessenberga przyśpieszy rozkład QR (Macierz w postaci Hessenberga to macierz w postaci U + T, gdzie U to macierz trójkątna górna a T to macierz trójdiagonalna ) Mnie udało się napisać redukcję z użyciem eliminacji Gaussa bo była ona dobrze opisana w książce Z Fortuna, B Macukow, J Wąsowski Metody numeryczne ale wolałbym redukcję z użyciem odbić Householdera Co do samego rozkładu QR to rozpisałem sobie zarówno lewostronne jak i prawostronne mnożenie przez macierze obrotów i okazało się że lewostronne mnożenie modyfikuje tylko dwa wiersze a prawostronne mnożenie modyfikuje tylko dwie kolumny W przypadku macierzy w postaci Hessenberga nie widzę jakiejś przewagi metody odbić Householdera nad metodą mnożenia przez macierze obrotów a mnożenie przez macierze obrotów łatwiej rozpisać Odpowiedni dobór przesunięcia powinien przyśpieszyć metodę iteracyjną i zmniejszyć potrzebną liczbę iteracji Jak dobrać przesunięcie ? Iloraz Rayleigha nie gwarantuje zbieżności , wektor dla którego liczymy ten iloraz powinien dążyć do wektora własnego , obliczenie tego ilorazu wymaga O(n^2) operacji chyba że możliwe są jakieś optymalizacje Przesunięcie Wilkinsona - to chyba zadziała dla macierzy symetrycznych Podwójne przesunięcie - w jednej iteracji zastosować dwa przesunięcia w przypadku zespolonych wartości własnych użyć pary sprzężonych wartości własnych tylko jak to zrealizować i czy nie popsujemy sobie w ten sposób postaci Hessenberga Jak zrealizować deflację ? Najlepiej aby zrobić to w miejscu bez allokacji dodatkowej pamięci i tak aby nie popsuć sobie postaci Hessenberga Jeżeli wartości własnych potrzebujemy do znalezienia przybliżonych pierwiastków wielomianu to macierz stowarzyszona jest już na wejściu w postaci Hessenberga Jeszcze jeszcze metoda dziel i rządź ale podobno jest ona dopracowana tylko dla macierzy symetrycznych Ogólnie rzecz biorąc zagadnienie znajdowania wartości własnych jest lepiej uwarunkowane dla macierzy symetrycznych

@@pkoprowski Bairstow zresztą też w pewnych sytuacjach miewa "narowy" Czy aby te "narowy" Bairstowa nie są spowodowane tym że korzysta z metody Newtona ? Czy dałoby się podczas rozwiązywania tego układu równań z metody Bairstowa zastąpić metodę Newtona jakąś inną metodą albo przynajmniej zmodyfikować metodę Newtona tak aby zagwarantować jej zbieżność globalną przy zachowaniu jej tempa zbieżności Gdybym miał na wejściu współczynniki zespolone oraz arytmetyka zespolona nie byłaby przeszkodą to pewnie wybrałbym metodę Laguerre'a tylko co gdy metoda Laguerre'a da ciąg rozbieżny ?

To czy warto, czy też nie warto tego algorytmu użyć, zależy od konkretnych zastosowań i konkretnej architektury, na której pracujemy. Na pewno warto ten algorytm (a raczej algorytm Coppersmith-Winograd, o którym na wykładzie wspominam po algorytmie Strassena) znać. Bo tylko znając go możemy podjąć racjonalną decyzję, czy w naszej konkretnej sytuacji użycie danego algorytmu jest opłacalne.

Żeby w ogóle mówić o stabilności numerycznej, musimy mieć do czynienia z reprezentacja przybliżoną (liczbami zmiennoprzecinkowymi). Na tym wykładzie jest mowa o wielomianach, których współczynniki są reprezentowane dokładnie, jako liczby całkowite czy wymierne. Dla wielomianów o współczynnikach zmiennoprzecinkowych omawia tu narzędzia w ogóle nie mają matematycznego sensu. Jak na przykład zdefiniować zawartość wielomianu, czy część pierwotną, jeśli jego współczynniki są liczbami zmiennoprzecinkowymi? To się nie da. Podobnie, dla wielomianów o współczynnikach zmiennoprzecinkowych, nie ma sensu mówić o pseudo-dzieleniu. Jeżeli współczynniki wielomianu są liczbami zmiennoprzecinkowymi używa się kompletnie innych metod. Na przykład w pierwszej kolejności wyznacza się *przewidywany* stopień GCD, obliczając (numerycznie) rząd macierzy Sylwestera lub (lepiej) Bezout, a potem dopiero konstruuje przybliżony NWD dla wyznaczonego stopnia. Wiecej na ten temat można poczytać na przykład w pracach: - Paola Boito (2011), Structured matrix based methods for approximate polynomial GCD, - Tateaki Sasaki, Mutsuko Sasaki (1997), Polynomial remainder sequence and approximate gcd - Matu-Tarow Noda, Tateaki Sasaki (1991). Approximate {GCD} and its application to ill-conditioned algebraic equations. (Jest tego pewnie więcej, ale akurat te prace znam.) Na tym wykładzie jednak przybliżonego, numerycznego NWD nie omawiam. Tak samo jak nie omawiam powiedzmy szybkich, sub-kwadratowych algorytmów typu half-GCD. Nie dlatego, że te algorytmy są nieważne i nieistotne (wręcz przeciwnie), tylko ponieważ coś trzeba wybrać. I to coś musi pasować to kontekstu całego kursu.

@@pkoprowski a to ok , z tym że jest niestabilny numerycznie to wyczytałem to w pomocy do funkcji Octave czy tam do funkcji z jakiejś paczki do Pythona No tak miałem na myśli dzielenie wielomianów z resztą gdzie współczynniki wielomianów są liczbami zmiennoprzecinkowymi (algorytm ten sam co przy dzieleniu pisemnym)

Niestety mój program nie działa poprawnie dla każdego wielomianu Chyba głównym problemem jest u mnie odpowiedni dobór przesunięć w metodzie QR Napisanie metody QR blokowo mogłoby wprowadzić dodatkowy warunek stopu inny niż maksymalna liczba iteracji W obecnej postaci program nie zawsze daje ciąg macierzy zbieżny do macierzy Schura a nawet jeśli daje to dość często zbieżność tego ciągu dość wolna Redukcję do postaci Hessenberga znalazłem dobrze opisaną ale tylko za pomocę eliminacji Gaussa (Dla zachowania podobieństwa macierzy wykonujemy operacje elementarne zarówno na wierszach jak i na kolumnach) Wolałbym jednak tej redukcji dokonać za pomocą odbić Householdera Jeżeli chodzi o rozkład QR macierzy Hessenberga to dla mnie obojętnre jest czy wykonamy go za pomocą odbić czy za pomocą obrotów Dla mnie wygodniej jes6t rozpisać mnożenie przez macierze obrotów Mój program nie jest też optymalny jeśli chodzi o złożoność pamięciową Może jakieś wideo o metodach obliczania wartości własnych i ich zastosowaniu np do znajdowania przybliżonych pierwiastków równania wielomianowego

Tak