Numeryczne znajdowanie pierwiastków wielomianu Mariusz: Chciałem tutaj skupić się na dwóch podejściach 1. Metoda QR dla wartości własnych macierzy stowarzyszonej z wielomianem 2. Metoda Bairstowa (deflacja czynnikiem kwadratowym) 1. Metoda QR dla wartości własnych macierzy stowarzyszonej z wielomianem Przypuśćmy że równanie wielomianowe które chcemy rozwiązać jest zapisane w postaci λⁿ=a_n−1λⁿ⁻¹+a_n−2λⁿ⁻²+...+a₁λ+a₀ Tworzymy macierz stowarzyszoną (Umieszczamy jedynki tuż pod główną przekątną, Mamy cztery możliwości co do umieszczenia współczynników wielomianu pierwszy wiersz albo ostatni wiersz albo pierwsza kolumna albo ostatnia kolumna, pozostałe elementy są zerowe) Macierz górna Hessenberga to macierz w postaci T+U gdzie T macierz trójdiagonalna a macierz U to macierz górnotrójkątna Macierz stowarzyszona jest więc w takiej postaci Jeżeli chodzi o rozkład QR macierzy A_mn = Q_mmR_mn to rozpisałem sobie mnożenie przez macierze obrotów (Mnożąc lewostronnie macierz A przez macierze obrotów G otrzymujemy macierz R Mnożąc prawostronnie macierz I przez macierze obrotów G^T otrzymujemy macierz I) Lewostronne mnożenie przez macierze obrotów G modyfikuje tylko dwa wiersze macierzy A Prawostronne mnożenie przez macierze obrotów G^T modyfikuje tylko dwie kolumny macierzy A Aby znaleźć macierz obrotu należałoby rozwiązać układ równań −sa_ii+ca_ji=0 // To równanie otrzymujemy z pomnożenia macierzy A przez macierz obrotu G c²+s²=1 //To równanie pochodzi z jedynki trygonometrycznej Co do rozkładu QR to czy mógłby ktoś opisać metodę odbić Householdera ale w taki sposób aby łatwo było ją zapisać w ulubionym języku programowania Metoda QR wygląda następująco A_i = Q_iR_i A_i+1 = R_iQ_i Tutaj można pokazać że metoda QR tworzy ciąg macierzy podobnych do macierzy A Ta metoda po każdej iteracji zachowuje postać Hessenberga Metoda ta jest zbliżona do metod potęgowych Można by przyspieszyć zbieżność metody QR stosując przesunięcia Metoda QR wyglądałaby następująco A_i −s_iI = Q_iR_i A_i+1 = R_iQ_i + s_iI Problem w tym że nie znalazłem jak dobrać odpowiednie przesunięcie Jak zrealizować deflację ? Da się to zrobić w miejscu a jeśli tak to w jaki sposób 2. Metoda Bairstowa (deflacja czynnikiem kwadratowym) Jeżeli wielomian o współczynnikach rzeczywistych posiada pierwiastki zespolone to są one parami sprzężone Każdy wielomian stopnia większego od zera posiada co najmniej jeden pierwiastek zespolony (Stosując to twierdzenie indukcyjnie doprowadzi to nas do wniosku że każdy wielomian stopnia większego od zera posiada dokładnie tyle pierwiastków zespolonych ile wynosi jego stopień) Jeżeli wyjściowy wielomian miał współczynniki rzeczywiste to możemy czynniki liniowe tak pogrupować aby czynniki kwadratowe miały współczynniki rzeczywiste W(x)=Q(x)(x²−px−r)+a(p,r)x+b(p,r) Prowadzi to nas do układu równań nieliniowych a(p,r) = 0 b(p,r) = 0 Metoda Bairstowa zakłada rozwiązanie tego układu równań metodą Newtona Metoda Newtona nie gwarantuje nam jednak zbieżności Jeżeli wiemy że metoda ta jest zbieżna to jej zbieżność jest dość dobra Czy dałoby się metodę Newtona zastąpić taką metodą która zagwarantowałaby nam zbieżność Dlaczego wybrałem te metody ? Otóż stosując te metody możemy uniknąć arytmetyki zespolonej mając dany wielomian o współczynnikach rzeczywistych