Numerische Methoden

Aleksandar Tuzlak ¹
ETH Zürich, D-ITET

Abstract

Dieses Dokument enthält eine Zusammenfassung und Codesnippets der Vorlesung Numerische Methoden 401-0654-00L FS25. Falls du an der Webseite mitwirken willst oder Feedback geben möchtest, kannst du mir gerne eine Mail schreiben.

[↓]

Python/Numpy/CodeExpert/Misc.

Plots in CodeExpert speichern: plt.savefig("./cx_out/img.png")


'''
    Annotations don't effectively change anything, 
    just intended for better readability,
    unless using mypy for static analysis.
'''
def func(arg1: int, arg2: float) -> float:
    return 0

    
        '''
        Array indexing
        f[start : stop : step] : general case
        '''
        
        fx[1:-1:2]  # Odd indices (midpoints)
        fx[2:-2:2]  # Even indices (excluding first and last)


'''
    inline for loops, zip
'''

list1 = [1, 2, 3, 4]
list2 = [10, 20, 30, 40]

squared_sums = [(x + y) ** 2 for x, y in zip(list1, list2)]

print(squared_sums)  # Output: [121, 484, 1089, 1936]

Quadratur Fehler: $$E(n) = \lvert \int\limits_a^b f(x) dx - Q_n(f; a, b) \rvert \stackrel{\stackrel{!}{n\to\infty}}{\to}0$$ Konvergenz:
alg.: $E(n) = O(\frac{1}{n^p}), p > 0$
exp.: $E(n) = O(q^n), q\in[0, 1)$

Ordnung $n + 1$ falls Poly. vom Grad n (Genauigkeitsgrad) $(p\in\mathbb{R}[x]_n)$ ($n + 1$ Koeff.) exakt integriert ($I = Q$) $\leadsto x^{n + 1}$ erstes falsches Ergebnis, (für symm: ord. $\in 2\mathbb{N}$), Ordnung von QF herausfinden $\to$ ausprobieren (loop bis nicht mehr stimmt)

auf $[-1, 1]$ mit $c_1,\dots, c_n, \omega_1,\dots,\omega_n$ symm. falls: $$\omega_i = \omega_{n+1-i}, c_i = -c_{n+1-i}$$
Gewichte $\omega_i^n$, Knoten $c_i^n\in [a, b]$ $$\int\limits_a^b f(x) dx \approx Q_n(f; a, b) := \sum\limits_{i=1}^n w_i^n f(c_i^n) $$

Summierte QF
Schrittweite $h = \frac{b - a}{N}, x_0 = a, x_i = x_0 + ih, x_N = b$ $$\int\limits_a^b f(x)dx = \sum\limits_{i = 0}^{N - 1}\int\limits_{x_i}^{x_{i + 1}}f(x) dx \approx \sum\limits_{i = 0}^{N - 1}Q_n(f; x_i, x_{i + 1})$$

MR, TR, SR (äquidistante Stützstellen)

Summierte Mittelpkt-Regel: (symm, offene QF, Endpkt. des Intervalls nie Knoten)
$$I(f; a, b) \approx \sum\limits_{i = 0}^{N - 1}hf\left( \frac{x_i + x_{i + 1}}{2} \right)$$

                                        
# summed MR
def summMR(f, a: float, b: float, N: int) -> float:
    """
    Approximates the definite integral of f(x)
    from a to b using the summed mid-point rule.

    Args:
        f: function to be integrated. 
        takes 1d np.array as input and returns a same dimensional array.
        a (float): left integration limit
        b (float): right integration limit
        N (int): number of subintervals

    Returns:
        float: approximation of the integral
    """

    # x: Vector [x_0, x_1, ..., x_N] with x_0 = a and x_N = b
    # h: Subinterval width
    x, h = np.linspace(a, b, N + 1, retstep=True)

    # mid-pts.
    x_i = (x[:-1] + x[1:]) / 2

    fx = f(x_i)  # Evaluate f at x_i 
    # Summed mid-point rule
    Q = h * np.sum(fx[:-1])

    return Q

Summierte Trapez-Regel:
$$I(f; a, b) \approx \sum\limits_{i = 0}^{N - 1}\frac{h}{2}\left( f(x_i) + f(x_{i + 1}) \right) = \frac{h}{2}\left( f(a) + 2\sum\limits_{i = 1}^{N - 1}f(x_i) + f(b) \right)$$

                                        
# summed TR
def summtrapezregel(f, a: float, b: float, N: int) -> float:
    """
    Approximates the definite integral of f(x)
    from a to b using the summed trapezoidal rule.

    Args:
        f: function to be integrated. 
        takes 1d np.array as input and returns a same dimensional array.
        a (float): left integration limit
        b (float): right integration limit
        N (int): number of subintervals

    Returns:
        float: approximation of the integral
    """

    # x: Vector [x_0, x_1, ..., x_N] with x_0 = a and x_N = b
    # h: Subinterval width
    x, h = np.linspace(a, b, N + 1, retstep=True)

    fx = f(x)  # Evaluate f at x
    # Summed trapezoidal rule
    Q = h / 2 * (fx[0] + 2 * np.sum(fx[1:-1]) + fx[-1])

    return Q

Summierte Simpson-Regel: (symm.)
$$ \begin{split} I(f; a, b) &\approx \sum\limits_{i = 0}^{N - 1}\frac{h}{6} \left( f(x_i) + 4f\left( \frac{x_i + x_{i + 1}}{2}\right) + f(x_{i+1}) \right) \\ & = \frac{h}{6} \left( f(a) + 2\sum\limits_{i = 1}^{N - 1}f(x_i) + 4\sum\limits_{i = 1}^{N}f\left( \frac{x_{i-1} + x_i}{2} \right) + f(b) \right) \\ & = \frac{\tilde{h}}{3}\left( f(\tilde{x}_0) + 2 \sum\limits_{i = 1}^{N - 1}f(\tilde{x}_{2i} + 4\sum\limits_{i = 1}^{N}f(\tilde{x}_{2i - 1}) + f(\tilde{x}_{2N})) \right) \end{split} $$ $ \tilde{h} = \frac{h}{2}, \tilde{x}_{2i} = x_i, \tilde{x}_{2i-1} = \frac{x_{i - 1} + x_i}{2} $

                                        
# summed SR
def summsimpsonregel2(f, a: float, b: float, N: int) -> float:
    """
    Approximates the definite integral of f(x) 
    from a to b using the summed Simpson rule.
    
    Args:
        f: function to be integrated. 
        takes 1d np.array as input and returns a same dimensional array.
        a (float): left integration limit
        b (float): right integration limit
        N (int): number of subintervals

    Returns:
        float: approximation of the integral
    """

    # Vector [x_0, x_1, ..., x_N] with x_0 = a and x_N = b
    x, h = np.linspace(a, b, 2*N+1, retstep=True)
    
    # Sum rule of Simpson
    fx = f(x)  # Evaluate f at x
    '''
        fx[1:-1:2]  : Odd indices (midpoints)
        fx[2:-2:2]  : Even indices (excluding first and last)
    '''
    Q = h / 3 * np.sum(f(x[:-2:2]) + 4*f(x[1:-1:2]) + f(x[2::2]))

    # x = np.linspace(a, b, 2*N+1)
    # h = (b - a) / N
    # Q = h / 6 * (fx[0] + 2 * np.sum(fx[2:-2:2]) + 4 * np.sum(fx[1:-1:2]) + fx[-1])

    return Q

Gauss Quad. (nicht äquidist. Stuützstellen)

Adaptive Quad.

Referenzintervall $[-1, 1]$:
$$\int\limits_a^b f(t) dt = \frac{(b - a)}{2}\int\limits_{-1}^1 f(\frac{1}{2}(1 - \tau)a + \frac{1}{2}(\tau + 1)b) d\tau$$

[↑]

1. atuzlak(ät)ethz.ch