-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.cyf-kr.edu.pl!news.nask
.pl!news.nask.org.pl!news.unit0.net!news.uni-stuttgart.de!npeer.de.kpn-euroring
s.net!npeer-ng0.de.kpn-eurorings.net!zen.net.uk!dedekind.zen.co.uk!newsfeed.neo
strada.pl!unt-exc-01.news.neostrada.pl!unt-spo-b-01.news.neostrada.pl!news.neos
trada.pl.POSTED!not-for-mail
From: "slawek" <s...@h...pl>
Newsgroups: pl.comp.programming
References: <509ee300$0$26682$65785112@news.neostrada.pl>
<k7olf5$rpm$1@news.task.gda.pl>
In-Reply-To: <k7olf5$rpm$1@news.task.gda.pl>
Subject: Re: Simpson vs. Niski Cotes
Date: Mon, 12 Nov 2012 05:11:01 +0100
MIME-Version: 1.0
Content-Type: text/plain; format=flowed; charset="iso-8859-2"; reply-type=original
Content-Transfer-Encoding: 8bit
X-Priority: 3
X-MSMail-Priority: Normal
Importance: Normal
X-Newsreader: Microsoft Windows Live Mail 14.0.8117.416
X-MimeOLE: Produced By Microsoft MimeOLE V14.0.8117.416
Lines: 77
Message-ID: <50a076d3$0$26703$65785112@news.neostrada.pl>
Organization: Telekomunikacja Polska
NNTP-Posting-Host: 62.69.202.124
X-Trace: 1352693459 unt-rea-a-01.news.neostrada.pl 26703 62.69.202.124:63415
X-Complaints-To: a...@n...neostrada.pl
Xref: news-archive.icm.edu.pl pl.comp.programming:200733
[ ukryj nagłówki ]
Użytkownik "Baranosiu" <r...@w...pl> napisał w wiadomości grup
dyskusyjnych:k7olf5$rpm$...@n...task.gda.pl...
> Akurat w tym przypadku tak, ale weź inny przedział całkowania (na
> przykład -10..10 tak żeby wpływ funkcji wykładniczej był nieco
> bardziej znaczący) i już simpson może wypaść lepiej.
Oczywiście, że dla /pewnych/ przedziałów lub /pewnych/ funkcji może być
tak... albo może tak nie być.
Jednakże mit o wyższości metody Simpsona nad metodą trapezów jest obalony -
nie można a priori założyć, że wyniki otrzymane metodą Simpsona będą
dokładniejsze.
I jeszcze drobiazg - większość ludzi, jak usłyszy "całkowanie", to kojarzy
to z zadaną w postaci w wzoru funkcją podcałkową. W przykładowym programie
taka funkcja, f, była wyłącznie dla niezaśmiecania forum tablicą parunastu
tysięcy wartości. Bo istotą rzeczy jest - w tym do czego mi są potrzebne
całki - że są dane pary (x,y), nie ma jawnie postaci funkcji. Można to sobie
np. wyobrazić jako zapis PCM dźwięku - przy próbkowaniu 44 kHz będzie to
44000 punktów (x,y) na każdą sekundę - i teraz trzeba to scałkować - dane
są - funkcji zapisanej wzorkiem nie ma.
Teraz trochę teorii. Jeżeli jest dość dużo sampli, czyli par (x,y) jest n+1,
a to n+1 wynosi kilkaset tysięcy lub więcej, to nie ma znaczenia, czy urwie
się jeden z sampli gdzieś z przodu lub z tyłu - wartość całki powinna być
/niemal/ taka sama. Stosując wzór Simpsona dla danych "urwanych z przodu"
otrzymuje się zupełnie inne sumowanie niż dla "urwanych z tyłu" (inne
elementy są są wtedy parzyste/nieparzyste). Można potem dodać "urwany"
przedział (ale to nie jest konieczne). Oczywiście dla otrzymania
dokładniejszych wyników można i należy wziąć średnią arytmetyczną wyników
całkowania "urwanego z przodu" i "urwanego z tyłu". Tylko że, surprise,
surprise, dostaje się wtedy po prostu wzór trapezów (kwadraturę
Newtona-Cotesa rzędu 1). Dlaczego tak jest? Między innymi dlatego, że wzór
na całkowanie numeryczne musi mieć "symetrię translacyjną" - tj. zastąpienie
przedziału indeksów [1, n] przez [2, n+1] powinno dawać ten sam wynik z
dokładnością do końcówek [1,2] i [n, n+1]. Tego warunku wzór Simpsona nie
spełnia, a wzór trapezów tak.
Kwadratury Newtona-Cotesa, Gaussa-Czebyszewa itd. powstawały w czasach
"przedkomputerowych". Służyć miały rozwiązaniu problemu: mamy funkcję f i
przedział [a, b] - jak tylko kilkakrotnie ewaluując f obliczyć wartość całki
z f, wiedząc że f jest taka a taka? Kilkakrotnie, tzn. 3-5 razy, bo każde
wyliczenie f trwa długo - papier i ołówek, ew. arytmometr (ale to już raczej
nie czasy Newtona i Gaussa, tylko trochę później).
Jeszcze nieco o całkowaniu metodą Romberga - to nic innego niż zastosowanie
ekstrapolacji Richardsona do całkowania. A ta jest, podobnie jak
ekstrapolacja Aitkena, należy do metod w których rezultaty kilku, coraz
dokładniejszych, obliczeń ekstrapoluje się do wyniku jaki prawdopodobnie
otrzymanoby przy jeszcze większej staranności. Praktycznie, w przypadku
danych stablicowanych oznaczałoby to policzenie metodą trapezów dla co
drugiego punktu (krok 2h) i normalnie (h = x[2] - x[1]), a następnie próbę
odgadnięcia ile to miałoby być dla h/2. Trzeba dodatkowego założenia o
odstępstwie wartości oszacowanych numerycznie od dokładnej. Tymczasem dla
danych stablicowanych takie założenie /może/ nie być prawdziwe - oraz co też
istotne - nie da się obliczyć w razie potrzeby np. wartości f((x[k] +
x[k+1])/2), gdyż formuła dla funkcji f nie jest znana, a interpolacji nie
należy stosować (tzn. można, lecz nie da ona nowych informacji, więc nie ma
sensu robić interpolacji w danych skoro efektywniej jest robić to dla sum).
Praktycznie? W niezłej bibliotece CERNLIB jest TRAPER (D108, Trapezoidal
Rule Integration with an Estimated Error), który - jak pamiętam - wbrew swej
nazwie używa interpolacji parabolicznej pomiędzy dostarczonymi odciętymi.
Lepiej jest używać używać funkcji sklejanych z wielomianów m-tego stopnia,
ale wymaga to rozwiązywania równania trójdiagonalnego, a to przy dużej
ilości danych może prowadzić do dużych błędów z zaokrągleń. Wracamy do
punktu wyjścia - metody Newtona-Cotesa rzędu 1.
Ogólnie sytuacja jest dość nieciekawa i to w tak trywialnie prostych
zagadnieniach, jak obliczanie RMS sygnału audio. Nic lepszego niż trapezy, a
w zasadzie nawet i to nie - bo z wzoru na trapezy wychodzi zwykłe sumowanie
wszystkiego co jest w środku i jeszcze doliczenie tylko połowy końcówek.
slawek
Następne wpisy z tego wątku
- 12.11.12 06:01 slawek
- 12.11.12 06:08 slawek
- 12.11.12 10:46 AK
- 12.11.12 10:48 AK
- 12.11.12 12:53 slawek
- 12.11.12 13:07 slawek
- 12.11.12 13:32 Michoo
- 12.11.12 13:54 slawek
- 12.11.12 14:28 Stachu 'Dozzie' K.
- 12.11.12 14:29 Michoo
- 12.11.12 15:05 R.e.m.e.K
- 12.11.12 15:26 Stregor
- 12.11.12 15:33 R.e.m.e.K
- 12.11.12 15:37 slawek
- 12.11.12 15:40 Baranosiu
Najnowsze wątki z tej grupy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
Najnowsze wątki
- 2025-03-15 China-Kraków => Senior PHP Symfony Developer <=
- 2025-03-15 Wrocław => Konsultant wdrożeniowy Comarch XL (Logistyka, WMS, Produk
- 2025-03-15 Błonie => Analityk Systemów Informatycznych (TMS SPEED) <=
- 2025-03-15 Warszawa => Senior Frontend Developer (React + React Native) <=
- 2025-03-15 Warszawa => Java Full Stack Developer (Angular2+ experience) <=
- 2025-03-15 Warszawa => Java Full Stack Developer (Angular2+) <=
- 2025-03-15 KOMU w RP3 pasuje "Rumuńska łatwość gmerania w wyborach" i dlaczego nie PO-Trzaskanym?
- 2025-03-15 China-Kraków => Key Account Manager IT <=
- 2025-03-14 Spalił się autobus :-)
- 2025-03-14 Policjanci z Piątku
- 2025-03-14 Lublin => JavaScript / Node / Fullstack Developer <=
- 2025-03-14 Warszawa => Account Manager - Sprzedaż Usług Rekrutacyjnych <=
- 2025-03-14 Gliwice => Business Development Manager - Dział Sieci i Bezpieczeńst
- 2025-03-14 VAT-R Umowa najmu na adres zamieszkania
- 2025-03-14 Gliwice => IT Expert (Network Systems area) <=