Algorytmy Numeryczne - Podsumowanie i Analiza

Poniższy dokument zawiera zestawienie podstawowych algorytmów numerycznych wraz z kodem źródłowym oraz wyjaśnieniem ich działania. Na końcu znajduje się sekcja z zadaniami analitycznymi.

1. Algorytm Newtona-Raphsona (Obliczanie pierwiastka kwadratowego)

Wyznacza wartość pierwiastka kwadratowego z liczby nieujemnej.

Dane:

P : R, P >= 0 - liczba podpierwiastkowa

E : R, E >= 0 - dokładność obliczeń

L : C, L > 0 - ilość iteracji

Wyniki:

a : R - przybliżona wartość pierwiastka kwadratowego

Kod algorytmu:

#include <cmath>

double pierwiastek(double p, int L, double E) {
    if (p < 0) return -1; 
    if (p == 0) return 0; 
    
    double a = p; 
    int i = 0;
    
    while (i < L && std::abs(a - p / a) >= E) {
        a = (a + p / a) / 2.0;
        i++;
    }
    return a;
}

Zasada działania krok po kroku:

  1. Zaczynamy od pierwszego przybliżenia a, równego podanej liczbie p.
  2. Sprawdzamy, czy różnica między przybliżeniami jest większa niż wymagana precyzja E oraz czy nie przekroczyliśmy limitu kroków L.
  3. Jeśli warunki są spełnione, obliczamy nowe, dokładniejsze przybliżenie ze wzoru średniej arytmetycznej: $$a = \frac{a + \frac{p}{a}}{2}$$
  4. Powtarzamy proces, aż wynik będzie wystarczająco dokładny.

2. Metoda połowienia (Bisekcji)

Znajduje przybliżoną wartość miejsca zerowego funkcji ciągłej w podanym przedziale.

Dane:

f(t) - funkcja

p, q - początek i koniec przedziału, p < q

E : R - dokładność obliczeń, 0,00001

L : C - ilość iteracji

Kryteria zakończenia:

q - p <= E

Maksymalna ilość iteracji

Kod algorytmu:

#include <cmath>

double f(double x) {
    return x * x - 4.0; // Przykładowa funkcja
}

double bisekcja(double p, double q, double E, int L) {
    double sr = p;
    int i = 0;
    
    while ((q - p) >= E && i < L) {
        sr = (p + q) / 2.0; 
        
        if (f(sr) == 0.0) break; 
        
        if (f(p) * f(sr) < 0) {
            q = sr; 
        } else {
            p = sr; 
        }
        i++;
    }
    return sr;
}

Zasada działania krok po kroku:

  1. Bierzemy przedział od p do q. Funkcja na jego krańcach musi przyjmować wartości o przeciwnych znakach.
  2. Znajdujemy dokładny środek przedziału: $sr = \frac{p + q}{2}$.
  3. Sprawdzamy, po której stronie od środka sr wartości funkcji zmieniają znak. Tam, gdzie znak się zmienia, na pewno znajduje się miejsce zerowe.
  4. Zawężamy przedział o połowę, zastępując jeden z jego brzegów punktem sr, i powtarzamy proces, aż przedział będzie mniejszy niż ustalony błąd E.

3. Całkowanie numeryczne - Metoda prostokątów (punktu środkowego)

  1. Metoda prostokątów

Dane: f(x) - funkcja

n : C - ilość prostokątów

p, q - początek i koniec przedziału

Przybliża pole pod wykresem funkcji poprzez podział obszaru na prostokąty.

Kod algorytmu:

double obliczPoleProstokaty(double p, double q, int n) {
    double dl = (q - p) / n; 
    double s = 0.0;
    
    for (int i = 0; i < n; i++) {
        s += f(p + i * dl + dl / 2.0); 
    }
    
    return s * dl; 
}

Zasada działania krok po kroku:

  1. Dzielimy cały przedział (od p do q) na n równych fragmentów. Szerokość każdego z nich to dl.
  2. Przechodzimy przez każdy fragment, znajdując jego środek.
  3. Obliczamy wartość funkcji w tym środkowym punkcie - to staje się wysokością naszego prostokąta. Sumujemy wszystkie te wysokości.
  4. Mnożymy sumę wysokości przez szerokość podstawy dl, otrzymując łączne pole.

4. Całkowanie numeryczne - Metoda trapezów

Przybliża pole pod wykresem funkcji za pomocą sumy pól trapezów.

  1. Metoda prostokątów

Dane: f(x) - funkcja

n : C - ilość trapezów

p, q - początek i koniec przedziału

Kod algorytmu:

double obliczPoleTrapezy(double p, double q, int n) {
    double dl = (q - p) / n; 
    double s = 0.0;
    
    for (int i = 1; i < n; i++) {
        s += f(p + i * dl);
    }
    
    return (dl / 2.0) * (f(p) + f(q) + 2.0 * s);
}

Zasada działania krok po kroku:

  1. Dzielimy przedział na n równych części o szerokości dl (pełniącej rolę wysokości trapezu).
  2. Sumujemy wartości funkcji w punktach styku wewnętrznych krawędzi trapezów (od i = 1 do n - 1). Te wartości liczą się podwójnie, bo każdy punkt należy do dwóch trapezów.
  3. Wartości na skrajnych punktach przedziału f(p) i f(q) bierzemy tylko raz.
  4. Stosujemy uproszczony wzór sumaryczny, dodając wszystkie elementy.

5. Zadania do analizy (Praca samodzielna)

Zadanie 1: Śledzenie iteracji w algorytmie Newtona-Raphsona Chcemy obliczyć pierwiastek kwadratowy z liczby $p = 16$. Przyjmujemy pierwsze przybliżenie $a = 16$.

Zadanie 2: Ręczna bisekcja przedziału Dana jest funkcja $f(x) = x^2 - 9$. Szukamy jej miejsca zerowego w przedziale od $p = 0$ do $q = 5$.

Zadanie 3: Porównanie metod całkowania Mamy bardzo prostą funkcję liniową $f(x) = 2x$. Chcemy obliczyć pole pod wykresem na przedziale od $p = 0$ do $q = 2$.