Idę na kurs obliczeń naukowych i właśnie przekroczyliśmy przybliżenie metodą najmniejszych kwadratów. Moje pytanie dotyczy konkretnie przybliżenia za pomocą wielomianów. Rozumiem, że jeśli masz n + 1 punktów danych, możesz znaleźć unikalny wielomian stopnia n, który opisuje wszystkie te punkty. Ale rozumiem też, dlaczego nie zawsze jest to idealne. Przy takim podejściu można uzyskać dużo hałasu między punktami danych. Przypuszczam, że miło jest uzyskać wielomian niższego stopnia, który wystarczająco dobrze szacuje dane.
Moje pytanie brzmi: jak w praktyce decydujesz, jakiego stopnia wielomianu zamierzasz zastosować? Czy istnieje ogólna zasada, czy zależy to wyłącznie od rodzaju problemu? Czy musimy brać pod uwagę różne kompromisy przy podejmowaniu decyzji między stopniami mniejszymi lub większymi? A może coś tu nie rozumiem?
Z góry dziękuję.
źródło
Odpowiedzi:
Najważniejszym aspektem interpolacji i dopasowania krzywej jest zrozumienie, dlaczego dopasowanie wielomianowe wysokiego rzędu może być problemem i jakie są inne opcje, a następnie zrozumienie, kiedy są / nie są dobrym wyborem.
Kilka problemów z wielomianami wysokiego rzędu:
Wielomiany są naturalnie funkcjami oscylacyjnymi. Wraz ze wzrostem kolejności wielomianu rośnie liczba oscylacji i oscylacje te stają się coraz poważniejsze. Upraszczam tutaj, możliwość wielu i wymyślonych korzeni czyni to nieco bardziej złożonym, ale sprawa jest taka sama.
Wielomiany zbliżają się do +/- nieskończoności z prędkością równą rządowi wielomianu, gdy x idzie do +/- nieskończoności. To często nie jest pożądane zachowanie.
Obliczanie współczynników wielomianowych dla wielomianów wysokiego rzędu jest zwykle źle uwarunkowanym problemem. Oznacza to, że małe błędy (takie jak zaokrąglanie w komputerze) mogą powodować duże zmiany w odpowiedzi. Układ liniowy, który musi zostać rozwiązany, obejmuje Matrycę Vandermonde, którą łatwo można źle warunkować.
Myślę, że być może sednem tego problemu jest rozróżnienie między dopasowaniem krzywej a interpolacją .
Interpolacja jest używana, gdy uważasz, że Twoje dane są bardzo dokładne, więc chcesz, aby funkcja dokładnie odpowiadała punktom danych. Gdy potrzebujesz wartości między punktami danych, zwykle najlepiej jest użyć gładkiej funkcji, która odpowiada lokalnemu trendowi danych. Splajny sześcienne lub hermitowe są często dobrym wyborem dla tego typu problemów, ponieważ są one znacznie mniej wrażliwe na nielokalne (czyli w punktach danych daleko od danego punktu) zmiany lub błędy danych i są mniej oscylacyjne niż wielomian. Rozważ następujący zestaw danych:
Dopasowywanie wielomianowe ma znacznie większe oscylacje, szczególnie w pobliżu krawędzi zestawu danych, niż splajn Hermite.
Z drugiej strony aproksymacja metodą najmniejszych kwadratów to dopasowanie krzywejtechnika. Dopasowanie krzywej jest używane, gdy masz pojęcie o oczekiwanej funkcjonalności danych, ale nie potrzebujesz, aby funkcja dokładnie przechodziła przez wszystkie punkty danych. Jest to typowe, gdy dane mogą zawierać błędy pomiaru lub inne niedokładności lub gdy chcesz wyodrębnić ogólny trend danych. Przybliżenie najmniejszych kwadratów jest najczęściej wprowadzane na kursie przy użyciu wielomianów do dopasowania krzywej, ponieważ daje to układ liniowy, który jest stosunkowo prosty do rozwiązania przy użyciu technik, których prawdopodobnie nauczyłeś się wcześniej na kursie. Jednak techniki najmniejszych kwadratów są znacznie bardziej ogólne niż zwykłe dopasowania wielomianowe i mogą być stosowane do dopasowania dowolnej żądanej funkcji do zbioru danych. Na przykład jeśli spodziewasz się wykładniczego trendu wzrostu w swoim zestawie danych,
Wreszcie wybór odpowiedniej funkcji do danych jest równie ważny, jak prawidłowe wykonanie interpolacji lub obliczeń metodą najmniejszych kwadratów. Takie postępowanie pozwala nawet na (ostrożną) ekstrapolację. Rozważ następującą sytuację. Biorąc pod uwagę dane dotyczące populacji (w milionach osób) dla Stanów Zjednoczonych w latach 2000–2010:
Zastosowanie wykładniczego liniowego dopasowania metodą najmniejszych kwadratów
N(t)=A*exp(B*t)lub interpolantu wielomianowego 10 rzędu daje następujące wyniki:Wzrost populacji w USA nie jest dość gwałtowny, ale pozwolę ci być sędzią w lepszym stanie.
źródło
Bardzo nienaukowe, ale dobrą ogólną zasadą jest to, że wielomiany trzeciego stopnia są zazwyczaj dobrym początkiem, aw praktyce nigdy nie widziałem, aby ktokolwiek używał więcej niż szóstego stopnia, by uzyskać dobre wyniki.
„Idealny” wielomian byłby najniższym rzędem, który reprezentuje bezgłośne dane wystarczająco dobrze dla twojego celu.
Jeśli twoje dane są wystarczająco małe, aby na to pozwolić (zwykle tak jest), możesz po prostu spróbować dopasować wielomiany wyższego rzędu, aż zaczniesz widzieć oscylacje, które zwykle są oznaką „przeregulowania”.
Alternatywą byłoby wygładzenie splajnu , ale w dużym stopniu zależy to od zastosowania. Splajny i wygładzające splajny nadają się tylko do interpolacji. W przypadku zaszumionych danych wolę pasowania wielomianowe niż wygładzanie splajnów, ale dane, z którymi pracuję, są zwykle dobrze przybliżone przez wielomiany.
źródło
Przyzwoicie skutecznym podejściem, którego użyłem przy aproksymacji wielomianu, jest obliczenie wielomianów najmniejszych kwadratów dla różnych stopni (np. Od 1 do 10), a następnie wybranie krzywej, która minimalizuje średni błąd kwadratu w punktach między kolejnymi (gdy posortowane według x) punktów w zbiorze danych. Pomaga to wykluczyć krzywe ze zbyt dużymi oscylacjami.
źródło