Szybkie mnożenie wielomianów

Własności wielomianów; pierwiastki, współczynniki. Dzielenie wielomianów. Wzory Viete'a. RÓWNANIA I NIERÓWNOŚCI wielomianowe (wyższych stopni). Rozkład na czynniki.
PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Szybkie mnożenie wielomianów

Post autor: PAV38 »

Czy mógłby ktoś podać przykład mnożenia dwóch wielomianów przy użyciu transformaty Fouriera (algorytm szybkiego mnożenia wielomianów)? Byłbym bardzo wdzięczny, bo w internecie znalazłem samą teorię i niewiele mi ona mówi...
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Szybkie mnożenie wielomianów

Post autor: Kartezjusz »

Weźmy
\(\displaystyle{ W(x)=x^{2}-3x+2}\)
\(\displaystyle{ V(x)=x^{2}+2x+1}\)
Policz transormaty dla obu wielomianów
Potem policz wartości transformat w tych punktach i wzajemnie pomnóż
Potem użyj teransformaty odwrotnej
... grafii.pdf

A o samej transformacie
... a_Fouriera

Najlepiej jak wybierzesz punkty 1,2,3 Wybieraj tak,abyś liczył jak najprościej te punkty węzłowe...
PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Szybkie mnożenie wielomianów

Post autor: PAV38 »

A dałoby rade rozpisać to tak całkiem, od początku do końca? W sumie o to mi przede wszystim chodziło

Pod ten link już zdążyłem zajrzeć.
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Szybkie mnożenie wielomianów

Post autor: Kartezjusz »

Liczenie tych transformat mi się nie uśmiecha powiem szczerze.
Powiem tylko kroki
1.Wypisz współczynniki
\(\displaystyle{ N}\)-liczba współczynnika (u ciebie) \(\displaystyle{ 3}\)
\(\displaystyle{ n}\)-numer \(\displaystyle{ (a_{0}=2 / a_{1}=-3 / a_{2}=2}\)
2.liczysz \(\displaystyle{ e^{-{\frac2/pi nk}{N}}=\cos (-{{\frac2/pi nk}{N}})+i \sin (-{{\frac2/pi nk}{N}})}\) dla każdego \(\displaystyle{ n=0,1,2...,N-1}\)
3.jak pomnożysz sklalarnie wektor tych liczb sprzed dwóch linijek podniesionych do \(\displaystyle{ i}\)-tej,a \(\displaystyle{ i=0,1,2,..N-1}\) potęgi ( masz ich w sumie trzy) i z wektorem współczynników otrzymasz \(\displaystyle{ i}\)-tą harmonatę. Tworzy ci się wielomian o współczynnikach z hamonaty
4.Powtarzasz 2 i 3 dla wielomianu b
5.liczysz wartości obu wielomianów w trzech punktach ( takich samych ) i mnożysz je przez siebie.
6.Następnie otrzymane współczynniki trawisz przez transformatę odwrotną
To samo co zwykłe,tyle,że współczynnikami są harmonaty nowego wielomianu,a minusy sprzed exp znikają.
Ostatnio zmieniony 6 kwie 2012, o 12:51 przez loitzl9006, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
PAV38
Użytkownik
Użytkownik
Posty: 149
Rejestracja: 24 paź 2010, o 09:50
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 18 razy
Pomógł: 2 razy

Szybkie mnożenie wielomianów

Post autor: PAV38 »

Nie rozumiem tego trochę...
Mam wypisać współczynniki tych wielomianów ustawić je w ciąg i przekształcić te ciągi przez transformatę?
Załóżmy, że wyszły mi przykładowo- nie liczyłem (!) takie wyniki:

\(\displaystyle{ \left\{ 1,-3,2\right\} \rightarrow \left\{ 1,1-5i,1+i\right\} \\
\left\{ 1,2,1\right\} \rightarrow \left\{ 1,5-4i,6+2i\right\}}\)


Co mam z tym teraz zrobić?

Skąd mam wziąć te punkty? Mam je dowolnie wybrać? I gdzie je należy podstawić potem? Pomocy!
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Szybkie mnożenie wielomianów

Post autor: Kartezjusz »

Tak możesz je dowolnie wybrać,byle były równe. Otwórz wielomian zespolony o współczynnikach z tej prawej strony:)
ODPOWIEDZ