Metody numeryczne Marina : Witam! Czy umiałby i zechciałby ktoś z Państwa "rozwiązać" następujące zadanie z metod numerycznych w języku C++? Znajdź wielomian interpolacyjny dla funkcji f(x)=1/x i węzłów x₀=2, x₁=2.75 i x₂=4. Znajdź wartość wielomianu dla x=3. Oszacuj błąd dla x należącego do przedziału [2, 4]. Z góry dziękuję i pozdrawiam! 🙂

Mariusz: x₀ = 2 ,x₁ = 2.75 , x₂ = 4 y₀ = 0.5 , y₁ = 0.3636, y₂ = 0.25 Jeżeli chodzi o wielomian interpolacyjny to się tym bawiłem https://pastebin.com/CEEss5WS Wartość wielomianu jest zwracana przez funkcję horner której użyłem także do dzielenia przez dwumian

Maciess: Mariusz a implementowałeś kiedyś algorytm Remeza do znajdowania wielomianów optymalnych w sensie aproksymacji jednostajnej? Mam kod w Pythonie a chciałem porównać o ile lepiej radzi sobie to w czymś niższego poziomu.

Mariusz: Maciess nie . Ten kod co tutaj napisałem można by napisać lepiej bo w pewnym momencie mamy trzy zagnieżdżone pętle a to mogliby uznać za podejście zbyt kosztowne czasowo Aby zmniejszyć złożoność czasową tego algorytmu należałoby odwrócić schemat Hornera (Schemat Hornera jest tutaj użyty do dzielenia przez dwumian ale gdyby go odwrócić to mógłby być użyty do mnożenia przez dwumian)

Maciess: A po ci w ogóle dzielenie przez dwumian w tym algorytmie? W jakiej bazie konstruujesz ten wielomian?

Mariusz: To jest interpolacja Lagrange więc skoro policzyłem iloczyn wszystkich czynników x−x_i to muszę podzielić aby dostać to co we wzorze , tylko że nie trzeba w każdej iteracji liczyć iloczynu wszystkich czynników x−x_i

Maciess: @Marina Podejrzewam, że chodziło o konstrukcje wielomianu w bazie Newtona przy użyciu ilorazów różnicowych. Metoda której uzył Mariusz nadaje się do rozważan teoretycznych, ale raczej nie powinno jej używać się w praktyce numerycznej.

Mariusz: A w tej swojej ulubionej metodzie też dzielisz , dodatkowo jest ona bardziej złożona pamięciowo niż interpolacja Lagrange a daje te same wyniki

Mariusz: Maciess a ten algorytm Remeza to sam napisałeś czy skądś ściągnąłeś

Maciess: @15:58 Tak, zwiększamy nieznacznie złożonosc pamięciową, ale przecież to i tak niewielki koszt względem tego co zyskujemy. Jakbyś potem chciał rysować wykresy, albo po prostu obliczyć wartości w dużej ilości różnych punktów, to lepiej jak to umiemy zrobić przy O(n) a nie O(n²) Nie miał to być żaden przytyk w twoją stronę, robiłem podobny kurs co autorka, więc mniej więcej mam pogląd czego tam sie oczekuje. Ona nie wydaje się już zainteresowana, więc nie ma co ciągnąć tematu. @16:08 Implementowałem samemu, przy czym korzystałem z funkcji bibliotecznych, które robiły sporo za mnie. Interesowało mnie stricte porównanie wyników, liczyłem ze moze kiedys bawiłes sie w cos takiego.

Mariusz: Mam też i interpolację Newtona tyle że dodatkowy koszt pamięciowy to u mnie O(n²) ale podobno da się go zmniejszyć Może zamiast interpolacji Newtona można by napisać interpolację Hermite gdzie dla wielokrotnych węzłów podaje się też wartości pochodnych https://pastebin.com/m49DYgQp Jak widzisz tutaj dodatkowa pamięć jest zwiększona O(n²) Pokazałbyś jak zmniejszyć złożoność pamięciową

Maciess: Zerknij tutaj: https://www.impan.pl/~szczep/AMM1/Kincaid.pdf Strona 314 (wg numeracji skanów). Jest napisane jak to można łatwo usprawnić. Tutaj kod: https://pastebin.com/x78r7ZLJ

Mariusz: Po usprawnieniu kod wygladałby tak https://pastebin.com/nxGvTpA3 Maciess , czytałeś ten pdf O co chodzi z porządkowaniem węzłów Co to daje i jak to zrealizować (Niby w stdlib jest qsort ale mamy dane dwie jednowymiarowe tablice) Nadal nie wiem co zyskujemy stosując różnice dzielone Newtona zamiast interpolacji Lagrange Do obliczenia różnic dzielonych i tak potrzebujemy O(n²) czasu a dodatkowo O(n) pamięci (w wersji naiwnej było to nawet O(n²) pamięci)

Maciess: Z porządkowaniem węzłów to nie da się tak w 3 słowach. Jest takie pojęcie w analizie algorytmów jak numeryczna poprawność. Badamy algorytm pod kątem tego, jak bardzo jego wynik różni się od prawdziwego rozwiązania, uwzględniając fakt, że poruszamy się w arytmetyce zmiennopozycyjnej. No i o algorytmach, które dają wynik "bliski prawdziwemu" dla delikatnie zaburzonych danych mówimy, że są numerycznie poprawne. To tak w dużym skrócie. W tej książce również masz to opisane (rozdział 2.3). Co do twojego pytania, to tak jak mówisz nie ma sensu tego porządkować na starcie − po prostu zrób założenie, że podajesz wezły i wartość uporządkowane. No w notacji asymptotycznej to niby to samo, faktycznie i tak będzie działać szybciej i mniejsza szansa na popełnianie błedów. Tak jak pisałem (i jest również wytłuszczone w PDFie) znając wspolczynniki w bazie Newtona może dokonać ewaluacji w punkcie w czasie liniowym używając wariantu metody Hornera. Nie zrobisz tego (tak łatwo) w postaci Lagranga. Z tego co autorzy podali to są jakieś metody do efektywnego wyliczania wartosci w postaci Lagranga − ja ich nie znam.

Mariusz: Tutaj w tym fragmencie kodu gdzie obliczam różnice dzielone chyba iteruję za dużo (zamiast n powinienem tam wstawić n−1) Gdybym jednak chciał porządkować to porządkować tablicę igreków ? ale jak tak to trzeba by też odpowiednio spermutować tablicę iksów i właśnie zastanawiam się nad tą permutacją tablicy iksów

Mariusz: Maciess odpowiedziałbyś na kilka pytań z metod numerycznych Może nie koniecznie z interpolacji ale po części także związanych z wielomianami Ostatnio bawiłem się metodą QR dla wartości własnych Niby program coś już liczy ale nie zawsze zwraca poprawny wynik

Maciess: Szczerze z metod numerycznych dla algebry liniowej to nie robiłem nic oprócz rozwiązywania układów metoda LU, więc w tym temacie raczej nie będę w stanie szybko pomóc. Na dniach mam obronę i nie mam teraz nazbyt czasu. Może napisz co tam nie działa a ja sobie gdzieś w przyszłym tygodniu odkopie ten wątek i ewentualnie spróbuje pomoc

Mariusz: No to LU byłoby przydatne do odwrotnej metody potęgowej (do wyznaczania pojedynczej pary własnej − wartość własna i odpowiadający jej wektor) Dobrze napiszę co jest nie tak i co chciałbym jeszcze dopisać − ale może już w innym wątku