Metoda Newtona

Jeśli f ∈ C^2 [a, b] tworzę ciąg typu

Procedura trwa do momentu aż dla zadanej dokładności δ

Kod programu w C++:

#include<iostream>

#include<cmath>

using namespace std;

double fun(double x)

{

return exp(x)*log(x)-x*x;

}

double fun1(double x)

{

return exp(x)*log(x)+exp(x)*(1./x)-2.*x;

}

int main()

{

double a=1.0;

double b=2.0;

double ab=b-a;

double delta=0.001;

double x0=(a+b)/2.;

double x1;

while( fabs(ab) > delta)

{

x1=x0-fun(x0)/fun1(x0);

ab=x1-x0;

x0=x1;

cout<<x1<<endl;

}

return 0;

}

Otrzymujemy w kolejnych krokach miejsc zerowe:1.7398; 1.69657; 1.6946; 1.6946

A oto film stworzony na zajęciach.

Witam na moim blogu.

Będzie on poświęcony metodom numerycznym, a dokładnie wybranym zagadnieniom z tego działu.

Blog ten tworzony jest na potrzeby przedmiotu "Metody numeryczne". Prowadzącym jest profesor Ihor Ohirko (zdjęcie poniżej).

Co to są metody numeryczne? 

Metody numeryczne to dziedzina wiedzy zajmująca się problemami obliczeniowymi i konstrukcją algorytmów rozwiązywania zadań matematycznych. Najczęściej, zadania obliczeniowe postawione są w dziedzinie rzeczywistej (lub zespolonej) i dlatego mówimy o zadaniach obliczeniowych matematyki ciągłej (w odróżnieniu od matematyki dyskretnej).

Metody numeryczne wykorzystywane są wówczas, gdy badany problem nie ma w ogóle rozwiązania analitycznego (danego wzorami) lub korzystanie z takich rozwiązań jest uciążliwe ze względu na ich złożoność.

W szczególności dotyczy to:

• całkowania;
• znajdowania miejsc zerowych wielomianów stopnia większego niż 2 (korzystanie ze wzorów na dokładne wartości pierwiastków równań stopnia 3 i stopnia 4 jest niepraktyczne, dla równań stopnia wyższego niż 4 wzorów już nie ma);
• rozwiązywania układów równań liniowych w przypadku większej liczby równań i niewiadomych;
• rozwiązywania równań różniczkowych i układów takich równań;
• znajdowania wartości i wektorów własnych (zob. równanie własne);
• aproksymacji, czyli przybliżaniu nieznanych funkcji (np. pomiarów zjawisk fizycznych).

Niektóre metody numeryczne

• Interpolacja liniowa
• Interpolacja wielomianowa
• FFT
• metoda Monte Carlo
• metody Newtona-Cotesa
• wzór parabol Simpsona
• wzór trapezów
• metoda równego podziału
• Kwadratury Gaussa

Interpolacja liniowa – szczególny przypadek aproksymacji za pomocą funkcji liniowej.

Aproksymacja (łac. approximare – przybliżać) – proces określania rozwiązań przybliżonych na podstawie rozwiązań znanych, które są bliskie rozwiązaniom dokładnym w ściśle sprecyzowanym sensie. Zazwyczaj aproksymuje się byty (np. funkcje) skomplikowane bytami prostszymi. Często stosowana w przypadku szukania rozwiązań dla danych uzyskanych metodami empirycznymi, które mogą być obarczone błędami.

Jeśli x określa wartość z przedziału x0 < x < x1, a y0 = f(x0) i y1 = f(x1) tablicę wartości danej funkcji, oraz h = x1 - x0 odstęp pomiędzy argumentami, wówczas liniową interpolację wartości L(x) funkcji f otrzymuje się jako:

Interpolacja liniowa

Interpolacja wielomianowa, nazywana też interpolacją Lagrange'a, od nazwiska pioniera badań nad interpolacją Josepha Lagrange'a, lub po prostu interpolacją jest metodą numeryczną przybliżania funkcji tzw. wielomianem Lagrange'a stopnia n przyjmującym w n+1 punktach, zwanych węzłami interpolacji, wartości takie same jak przybliżana funkcja.

Interpolacja jest często stosowana w naukach doświadczalnych, gdzie dysponuje się zazwyczaj skończoną liczbą danych do określenia zależności między wielkościami.

Zgodnie z twierdzeniem Weierstrassa dowolną funkcję y=f(x), ciągłą na przedziale domkniętym, można dowolnie przybliżyć za pomocą wielomianu odpowiednio wysokiego stopnia.

Metoda interpolacji polega na:

1. wybraniu n+1 punktów x0,x1,...,xn należących do dziedziny f, dla których znane są wartości
   
   
   
2. znalezieniu wielomianu W(x) stopnia co najwyżej n takiego, że
   
   

Interpretacja geometryczna – dla danych n+1 punktów na wykresie szuka się wielomianu stopnia co najwyżej n, którego wykres przechodzi przez dane punkty.

Znajdowanie odpowiedniego wielomianu

Wielomian przyjmujący zadane wartości w konkretnych punktach można zbudować w ten sposób:

1. Dla pierwszego węzła o wartości f(x0) znajduje się wielomian, który w tym punkcie przyjmuje wartość f(x0), a w pozostałych węzłach x1,x2,...,xn wartość zero.
2. Dla kolejnego węzła znajduje się podobny wielomian, który w drugim węźle przyjmuje wartość f(x1), a w pozostałych węzłach x0,x2,...,xn wartość zero.
3. Dodaje się wartość ostatnio obliczonego wielomianu do wartości poprzedniego.
4. Dla każdego z pozostałych węzłów znajduje się podobny wielomian, za każdym razem dodając go do wielomianu wynikowego.
5. Wielomian będący sumą wielomianów obliczonych dla poszczególnych węzłów jest wielomianem interpolującym.

Dowód ostatniego punktu i dokładny sposób tworzenia poszczególnych wielomianów opisany jest poniżej w dowodzie istnienia wielomianu interpolującego będącego podstawą algorytmu odnajdowania tego wielomianu.

Wielomian Lagrange'a

Postać Lagrange'a wielomianu to jedna z metod przedstawiania wielomianu, wykorzystywana często w zagadnieniach interpolacji. Dla wielomianu stopnia n wybiera się n+1 punktów – x0,x1,...,xn i wielomian ma postać:

Ponieważ
     jest równy 1 dla x równego xi (licznik i mianownik są równe), 0 zaś dla wszystkich innych xj (licznik jest równy zero), można łatwo za pomocą postaci Lagrange'a interpolować dowolną funkcję:

Wielomian ten będzie się zgadzał z funkcją f we wszystkich punktach xi.

Szybka transformacja Fouriera

Szybka transformacja Fouriera (ang. fast Fourier transform, FFT) – algorytm liczenia dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej.

Czasem używana jest też forma szybka transformata Fouriera w odniesieniu do tej metody. Ściśle jednak transformacja jest przekształceniem, a transformata wynikiem tego przekształcenia.

Niech x0, ...., xN-1 będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem:

Obliczanie tych sum za pomocą powyższego wzoru zajęłoby O(N2) operacji.

Algorytmy (jak algorytm Cooleya-Tukeya) obliczające szybką transformację Fouriera bazują na metodzie dziel i zwyciężaj, rekurencyjnie dzieląc transformatę wielkości N = N1N2 na transformaty wielkości N1 i N2 z wykorzystaniem O(N) operacji mnożenia.

Najpopularniejszą wersją FFT jest FFT o podstawie 2. Jest to bardzo efektywna operacja, jednak wektor próbek wejściowych (spróbkowany sygnał) musi mieć długość N=2^k, gdzie k to pewna liczba naturalna. Wynik otrzymuje się na drodze schematycznych przekształceń, opartych o tak zwane struktury motylkowe.

Złożoność obliczeniowa Szybkiej transformacji Fouriera wynosi O(N \log_2 N), zamiast O(N^2) algorytmu wynikającego wprost ze wzoru określającego dyskretną transformatę Fouriera. Dzięki istnieniu takiego algorytmu praktycznie możliwe stało się cyfrowe przetwarzanie sygnałów (DSP), a także zastosowanie dyskretnych transformat kosinusowych (DCT) (JPEG, MP3 itd.) do kompresji.

WAŻNE LINKI:

http://wazniak.mimuw.edu.pl/index.php?title=Metody_numeryczne

https://pl.wikipedia.org/wiki/Metoda_numeryczna

https://www.youtube.com/watch?v=uxu004QjtuU

https://www.youtube.com/watch?v=R-z1KXTXUWc

https://www.youtube.com/watch?v=N8fbW_B19ew

https://www.youtube.com/watch?v=e-luonb2VoM

METODY NUMERYCZNE Metoda Newtona Cotesa - WSB Radom Ohirko Ighor

https://pl.wikipedia.org/wiki/Metoda_numeryczna

http://wazniak.mimuw.edu.pl/index.php?title=Metody_numeryczne

https://www.youtube.com/watch?v=C7fPZtWKJ1Y