Wątek przeniesiony 2021-01-14 21:51 z Algorytmy i struktury danych przez Shalom.
Jak zastosować całki do rozwiązywania równań?
Mam na myśli coś takiego:
szukamy rozwiązania równania: f(x) = 0
i tradycyjnie są tu rozmaite metody z pochodnymi (Newtona i dalsze), ale nigdy z całkami - dlaczego?
przecież mając informację: F(x) = int f(x)dx, w granicach x0 do x1 można to chyba jakoś wykorzystać do wyliczenia zera - nie?
Przede wszystkim dlatego, że liczenie pochodnych jest mechaniczne, a liczenie całek — potworne.
Co jest potworne w liczeniu całek?
Np. dla liczenia pierwiastków mamy funkcję: f(x) = x^2 - a;
z tego wyliczamy pierwiastek: x= sqrt(a),
np. Newtonem:
x+ = x - f(x)/f'(x) = x - (x^2-a)/2x
jak widać figuruje tu pochodna: f' = 2x;
no, ale co to za problem użyć tu całki, którą można wyliczyć z marszu:
int fdx = x^3/3 - ax = x/3 (x^2 - 3a)
jest to jakaś informacja, czy nie?
z pewnością, zatem można to wykorzystać w szukaniu zera - jak?
https://en.wikipedia.org/wiki/Root-finding_algorithms
Nie ma ani jednej metody opartej na całkowaniu. Może dlatego, że pochodna funkcji daje styczną do wykresu, ta styczna przecina oś x i można to wykorzystać do znajdowania pierwiastka; a całka to pole pod wykresem, za bardzo nie widać jakby się miała przydać przy liczeniu pierwiastka.
Przede wszystkim potworne jest to, że nikt nie obiecuje, że wynik będzie jakąś „normalną” funkcją, a nie potworkiem. A wszystkie metody, które mi przychodzą do głowy, wymagają analizy symbolicznej rozwiązania w poszukiwaniu jakichś obiecujących cech.
@lion137: dlatego pytam - gdzie są metody z całkami?
Tylko że to niewiele nam daje, bo o ile pochodna daje nam gradient, tzn mówi nam o "kierunku wzrostu/spadku" funkcji o tyle w przypadki całki takiej informacji nie mamy. Wiemy tylko coś na temat "całego całkowanego obszaru". Dla jakiejś monotonicznej funkcji to można by ten trik wykorzystać może, ale to raczej średnio pomocne. Wydaje mi się że w ogólnym przypadku informacja o całce zwyczajnie nie pomaga w szukaniu pierwiastka i tyle.
@kwalifika: Odpowiedział @Shalom, poza tym, artykuł na wiki odpowiada; biorąc pod uwagę, jak zagadnienie jest rozlegle badane, brak choćby tam wzmianki o całkowaniu jest odpowiedzią.
@kwalifika: Wybrał(a|e)ś sobie akurat funkcję którą całkuje się prosto. Tutaj możesz poczytać o tym, dlaczego liczenie całek jest trudne a liczenie pochodnych już nie aż takie:
https://math.stackexchange.com/questions/20578/why-is-integration-so-much-harder-than-differentiation
Zapominacie że moim celem jest wykorzystanie informacji całkowej w rozwiązywaniu równań.
Twierdzenia w stylu: 'całki są trudne' bo 'styczne są łatwe', są zwyczajnym wymigiwaniem się od odpowiedzi.
I tak samo odrzucam tezy typu: pochodna to styczna, a całka to pole.
Druga pochodna, trzecia, itd. - co to jest?
Pierwsza całka to pole pod krzywą - tak?, a druga całka czym jest?
to jest to samo: całki są także pochodnymi, ale ujemnego rzędu!
pierwsza pochodna: df/dx;
zerowa pochodna: f
pierwsza ujemna pochodna: f^-1 = int fdx
... 5, 4, 3, 2, 1, 0, -1, -2, -3, ...
Twierdzenia w stylu: 'całki są trudne' bo 'styczne są łatwe', są zwyczajnym wymigiwaniem się od odpowiedzi
Bez demagogii proszę, jeśli Masz jakiś efektywny algorytm do znajdywania miejsc zerowych, używający całek, to go pokaż.
@kwalifika polecam wybrać się na jakieś matematyka.pl ;) Jeśli pytasz na forum dla programistów to oczekuj odpowiedzi praktycznych z punktu widzenia komputera.
Twierdzenia w stylu: 'całki są trudne' bo 'styczne są łatwe', są zwyczajnym wymigiwaniem się od odpowiedzi.
To jak najbardziej dobra odpowiedź. Całki komputer liczy słabo a pochodne liczy dobrze. W efekcie z punktu widzenia algorytmiki jedne są interesujące a drugie nie są.
Jeśli chodzi o samą kwestię liczenia pierwiastków z użyciem potęg to ja osobiście nie widzę w jaki sposób całki miałyby w czymkolwiek pomóc, ale tez matematykiem nie jestem. Niemniej nie rozumiem twojego przeświadczenia ze jakoś musi się dać. Jest wiele innych operacji matematycznych które też się nie przydadzą do szukania pierwiastków, więc czemu akurat ta wg ciebie powinna? o_O Argument z pochodnymi jest zupełnie chybiony, bo rzadko kiedy operacje przeciwne wykorzystuje się w tym samym celu.
To trochę jakby twierdzić że skoro można szukać liczb pierwszych za pomocą dzielenia to musi się też dać za pomocą mnożenia.
Generalnie można sobie produkować metody dowolnego rzędu - za pomocą kolejnych pochodnych, co jest bardzo łatwe.
To jest po prostu zwyczajne odwracanie funkcji:
f(x) = y
i szukamy f(x0) = y = 0, czyli y = 0;
odwracamy to, czyli: f^-1 = x(y)
i teraz wystarczy podstawić y = 0 i wyliczyć to: x(0).
Przykładem jest metoda Newtona - co to jest?
To jest przybliżenie I-go rzędu funkcji odwrotnej w zerze y:
x(y=0) = x0 - y/y'
Drugie przybliżenie dla metodę III-go rzędu:
x(y) = x0 - y/y' - 1/2 y'' y^2/y'^3
i to jest już full metoda III-go rzędu (można sobie wypróbować i porównać, np. wyliczyć pierwiastek: f = x^2 - a)
itd. można wprowadzać kolejne pochodne, czyli coraz lepsze aproksymacje funkcji odwrotnej.
No, ale mnie interesuje odwrotna droga: całki zamiast pochodnych!
Dostał(a/e)ś już odpowiedź, nawet dwie — liczenie symboliczne całek jest zagadnieniem trudniejszym od rozważanego (więc nie prowadzi do użytecznych rozwiązań), a wartość numeryczna całki oznaczonej nie mówi nic specjalnie użytecznego o rozważanej funkcji.
Jak masz jakieś mocno zawężone rodziny rozważanych funkcji, to coś by się udało pewnie urodzić. Np. jak się ograniczasz do funkcji ściśle monotonicznych. Tyle że dalej liczenie numeryczne całek oznaczonych wymaga sporo więcej obliczeń niż liczenie numeryczne pochodnych, a o liczeniu symbolicznym całkiem zapomnij.
Ogólnie w metodach numerycznych chodzi o to, żeby uzyskać przy użyciu czegoś łatwego obliczeniowo przybliżenie czegoś trudnego obliczeniowo. A liczenie całek jest trudniejsze obliczeniowo od znajdowania punktu zerowego.
Nie słyszałem żeby liczenie całek z wielomianów było specjalnie trudne:
np.:
f(x) = x^5 + 2x +1
masz problem z wyliczeniem całki z tej funkcji?
A teraz spróbuj wyliczyć zero, x0: f(x0) = 0.
@kwalifika: trochę źle myślisz. Istnieją takie metody, po prostu przydają się na tyle rzadko, że raczej tego nie uczą.
Słynne całkowanie przez podstawienie, może być zapisane tak:
h(x)*g(x) = INT(h(x)*g'(x)) + INT(h'(x)*g(x))
W rezultacie rozbijając sobie dowolną funkcję, np. b(x) na iloczyn dwóch funkcji w niektórych przypadkach możesz sobie bardzo uprościć analizę funkcji - albo i odwrotnie, jeśli tylko zauważysz, że łatwo funkcję na takie dwa iloczyny rozbić to uprości ci się analiza funkcji.
Natomiast całka jako taka po prostu nadaje się do tego dużo mniej niż pochodna, zwłaszcza w przypadkach ogólnych.
@wartek01: Wiem że istnieją takie metody, i dlatego pytam - jak to wygląda faktycznie i jakie daje możliwości?
Z literatury wiem, że dodanie informacji całkowej do tradycyjnej metody (bazującej na pochodnych) rzędu n, zwiększa rząd aż o 2!
Np. w przypadku Newtona, która jest rzędu 2, po wprowadzeniu kolejnej pochodnej,
czyli 2-giej, otrzymamy metodę rzędu 3, natomiast po wprowadzeniu całki otrzymamy od razu metodę rzędu 4 - od razu!
No i dlatego pytam: jak konkretnie wygląda taka metoda, jaki wzór tam figuruje:
x(i+1) = Newton + korekta z inf. całkowej.
Próba uzasadnienia - dlaczego informacja całkowa podnosi rząd o 2 a nie o tylko 1?
To prawdopodobnie wynika wprost z liczby danych w interpolacji.
informacja typu: y, y', y'', ... jest jednopunktowa,
natomiast całkowa wymaga minimum 2 punktów: int_a^b fdx = F(b) - F(a); ewidentnie mamy tu dwa punkty: x=a i x=b, i stąd wzrost rzędu o 2.
Można to łatwo uzasadnić na przykładzie metody Newtona:
w każdym kroku używamy tu y(x1) i y'(x1), czyli dwóch wartości w jednym punkcie - dlatego rząd = 2.
Ale przecież można użyć stare - wcześniejsze obliczenia, z innego punktu: y(x0) i y'(x0);
i teraz w sumie mamy aż 4 parametry, zatem rząd będzie 4, nie 2!
Procedura szukania zera w zadanym przedziale [a,b] z użyciem: y i y':
daje nam informację typu: y(a), y'(a), y(b), y'(b) w każdym kroku => rząd 4 na 100%!
Całka pracuje na przedziałach, więc można to przedefiniować odpowiednio,
i w ten sposób otrzymamy metodę rzędu 4 z całką y, y i y', bo to będzie oparte na 4 parametrach tak czy siak!!! :)
moze napisz rownanie jakie chcesz rozwiazac ?
@krzychu82a: metoda nie zależy od równania.
Jako zadanie proponuję stworzyć metodę rzędu 4, do obliczenia zera w przedziale [a,b],
opartą na informacji typu: y(a), y'(a), y(b), y'(b);
Będzie to naturalne rozszerzenie tradycyjnej metody Newtona,
i zerowym kosztem, bo w kolejnych krokach używamy poprzednio wyliczanych wartości!
Metoda rzędu 2 podwaja liczbę poprawnych cyfr w każdym kroku,
zatem metoda 4... co robi? :)
2x2x2x2 = 16; 4 kroki
4x4 = 16; dwa
@kwalifika: naprawdę nie wiem co ci napisać. Na początku zakładałem, że masz wiedzę o tym, co piszesz ale po tej serii postów straciłem nadzieję.
Tak na koniec - masz tutaj kilka rzeczywistych przykładów, kiedy całkowanie funkcji ułatwia jej analizę:
Drobna dygresja odnośnie obliczeń numerycznych.
Chcemy obliczyć całkę w przedziale [a,b] z dowolnej funkcji: y = f(x),
ale za pomocą tylko wartości samej funkcji i pierwszych pochodnych, czyli mamy jedynie: y(a), y'(a), y(b) i y'(b);
Nie ma takiej możliwości i błąd jest inf. Prosty przykład takiej funkcji:
weźmy funkcje która w punktach a i b ma ekstrema lokalne (więc pochodna wynosi 0) i dodatkowo a i b to miejsca zerowe tejże funkcji np. wielomian 4go stopnia: k*((x-a)^2 * (x-b)^2).
Wiemy że a i b to miejsca zerowe, plus wiemy że pierwiastki są podwójne, więc funkcja ma tam ekstremum i się "odbija". Wygląda to np. tak https://www.desmos.com/calculator/omxxo0dx4f (dla a=1, b=-1 i k=10)
Nie trudno zauważyć że f(a)=f(b)=f'(a)=f'(b)=0 a jednak w zależności od a,b i k całka na przedziale a,b może wynosić -inf,+inf. QED.
Mylisz się.
Błąd takiej metody byłby 4-go rzędu, czyli proporcjonalny do 4-tej pochodnej (dlatego to jest metoda 4-go rzędu).
Jak rozwiązać równanie za pomocą 4 danych: dwóch wartości y(a) i y(b), oraz dwóch pochodnych y'(a) i y'(b)?
szukamy zera y, czyli x0 który spełnia warunek: y(x0) = 0
Proste: za pomocą interpolacji odwrotnej.
kwalifika napisał(a):
Mylisz się.
Błąd takiej metody byłby 4-go rzędu, czyli proporcjonalny do 4-tej pochodnej (dlatego to jest metoda 4-go rzędu).
Jak rozwiązać równanie za pomocą 4 danych: dwóch wartości y(a) i y(b), oraz dwóch pochodnych y'(a) i y'(b)?
szukamy zera y, czyli x0 który spełnia warunek: y(x0) = 0Proste: za pomocą interpolacji odwrotnej.
Kolego, chcesz podyskutować, to zdefiniuj porządnie zagadnienie, a nie jakieś pierdoły wypisujesz o całkowaniu dowolne funkcji i używaniu informacji całkowej (którą to raz uznajesz za pochodne, a innym razem obstajesz przy ujemnych rzędach). To, że funkcja jest całkowalna nie oznacza, że jest różniczkowalna.
Dla prostej funkcji zdefiniowanej na zbiorze licz rzeczywistych:
f(x) = 0 dla x wymiernego, 1 dla niewymiernego.
Całkowalna?
Różniczkowalna?
Co Ci da Twoja interpolacja odwrotna?
Nie mówię o dziwolągach nieanalitycznych, lecz o zwyczajnych funkcjach - ciągłych, gładkich i do tego odwracalnych!
zadaniem jest wyznaczanie zera:
y(x0) = 0
odwrotna funkcja:
x(y=0) = x0
i tak to należy rozpatrywać!
co znaczy że szukamy zera: funkcji monotonicznej!
Przykładem błędnego zastosowania wzorów jest próba liczenia zera
za pomocą metody Newtona, lub pokrewnych opartych na odwracaniu!, funkcji niemonotonicznej.
Nie istnieje funkcja odwrotna do funkcji.. niejednoznacznej - jasne!
przykład:
y = x^3 - 3x - 1
odwrotna:
x(y) = ?
nie istnieje taka funkcja, niestety.
Wciąż czekam na odpowiedzi: jak wykorzystać informację całkową w rozwiązywaniu równań nieliniowych?
@kwalifika: Czyli nagle z "dowolnej funkcji" robi się, różniczkowalna, gładka, a dodatkowo monotoniczna ;) Jeszcze trochę i zredukujemy to do funkcji liniowych ;)
Ten Twój przykład: x^3 - 3x -1 nie jest monotoniczny.
Dla monotonicznych programista zapewne weźmie brute forcem (połowienie przedziału).
Nie rozumiesz o co w tym chodzi.
Metoda Newtona jaki i te dalsze - z wyższymi pochodnymi, są po prostu aproksymacjami funkcji odwrotnej!
Zatem jaki z tego wniosek należy wyciągnąć?
Gdy szukamy zera funkcji niemonotonicznej, wtedy należy podzielić taką funkcję na przedziały - monotoniczne!,
i dopiero wtedy stosować te metody - bo one pracują tylko na odwrotnych funkcjach!
Przykład: szukamy zera x^3 - 3x - 1, ale tylko jednego naraz - jasne?
widzimy że zero jest w okolicach x= 2, oraz drugie -0.4m -1.6, więc możemy sobie spokojnie zrobić odwrotną w przedziale np.: [1.5, 2.5], i tam szukać zera;
nie możemy stworzyć odwrotnej 0 do 3 - bo taka funkcja nie istnieje!
Gdy szukamy wszystkich zer wtedy robimy to kolejno - przedziałami, bo naraz nie da rady.
kwalifika napisał(a):
Nie rozumiesz o co w tym chodzi.
Możliwe, dlatego zadaję pytania by zrozumieć ;)
Metoda Newtona jaki i te dalsze - z wyższymi pochodnymi, są po prostu aproksymacjami funkcji odwrotnej!
Zatem jaki z tego wniosek należy wyciągnąć?
No właśnie czekam w napięciu na te wnioski.
Gdy szukamy zera funkcji niemonotonicznej, wtedy należy podzielić taką funkcję na przedziały - monotoniczne!,
i dopiero wtedy stosować te metody - bo one pracują tylko na odwrotnych funkcjach!
A niby jak będziesz dzielił na przedziały monotoniczne? Na wejście dostajesz funkcję, np. sin(1/x) - pewnie złą wybrałem, bo ma nieciągłość w 0, ale chyba 1 punkt nie robi aż takiej różnicy?
