\section*{Eigenwerte} Sei $A \in \C^{n \times n}$. Ein $\lambda \in \C$ ist \emph{Eigenwert} von $A$, wenn $\exists v \in \C^n\setminus\{0\} : Av = \lambda v$. \subsection*{Satz von Gerschgorin} \[ \mathcal{K}_i := \left\{ z \in \C \middle| |z-a_{i,i}| \leq \sum_{k=1, k\neq i}^n |a_{i,k}| =: r_i \right\}, \ 1 \leq i \leq n \] Die Vereinigung der Kreisscheiben $\mathcal{K}_i$ enthält alle Eigenwerte von $A \in \C^{n \times n}$: $\sigma(A) \subset \bigcup_{i=1}^n \mathcal{K}_i$ \spacing Ist $M_1 = \bigcup_{j=1}^k \mathcal{K}_{i_j}$ disjunkt von der Vereinigung $M_2$ der übrigen Kreise, so enthält $M_1$ genau $k$ und $M_2$ genau $n-k$ Eigenwerte gezählt entsprechend der algebraischen Vielfachheit. \subsection*{Störung des Eigenwertproblems} Sei $A$ diagonalisierbar mit $A= TDT^{-1}$, $\Delta A \in \C^{n \times n}$ beliebig: $\forall \lambda(A+\Delta A) \in \sigma(A+\Delta A) \ \exists \lambda(A) \in \sigma(A) : |\lambda(A+\Delta A) - \lambda(A)| \leq \kappa_p(T) \|\Delta A\|_p$ mit $1 \leq p \leq \infty$. \spacing Entsprechend lautet die Kondition der Bestimmung von Eigenwerten $\lambda \neq 0$ bzgl. der $p$-Norm: \[ \kappa_p(\lambda) \leq \frac{\|A\|_p}{|\lambda|} \kappa_p(T) \] \subsection*{Mögliche Eigenwertlöser} Das Eigenwertproblem ist äquivalent zur Bestimmung der Nullstellen des char. Polynoms. Nach dem \emph{Satz von Abel} existiert für Polynome von Grad $\geq 5$ bzw. Matrizen von Dimension $\geq 5\times5$ kein exakt arbeitender Eigenwertlöser welcher in endlicher Zeit die Eigenwerte bestimmt. d.h. alle Eigenwertlöser sind iterativ. \subsection*{Potenzmethode} In $A^k$ dominiert der betragsgrößte Eigenwert und diese Dominanz nimmt mit $k$ zu. Somit ist an $A^k v$ der betragsgrößte Eigenwert ablesbar. Für $k = 1, 2, \dots$ und Startvektor $x^0 \in \C^n$: \vspace*{-2mm} \[ z^k := Ax^{k-1}, \ x^k := \frac{z^k}{\|z^k\|} \] Der approx. betragsgrößte Eigenwert ergibt sich: \vspace*{-2mm} \[ \tilde\lambda = \langle Ax^k,x^k \rangle_2 \] Potenzmethode konvergiert nicht zwingend gegen einen EV des betragsgrößten EW sondern hat Häufungspunkte welche EV zu diesem EW sind. \subsubsection*{Inverse Potenzmethode} Die Konvergenzgeschwindigkeit der Potenzmethode hängt von $|\frac{\lambda_{r+1}}{\lambda_1}|$, also dem Quotienten des ersten nicht betragsmaximalen Eigenwerts und des betragsmaximalen Eigenwertes ab. Langsame Konvergenz liegt bei $|\frac{\lambda_{r+1}}{\lambda_1}| \approx 1$ vor. \spacing Sei $\tilde\lambda$ Schätzwert für $\lambda_i \in \sigma(A)$ d.h. $|\tilde\lambda - \lambda_i| < |\tilde\lambda - \lambda_j|, \ j \neq i$. Die inverse Potenzmethode: \vspace*{-2mm} \[ (A-\tilde\lambda Id_n)z^k = x^{k-1}, \ x^k = \frac{z^k}{\|z^k\|_2} \] Zur Lösung des linearen Systems wird die LR-Zerlegung von $A- \tilde\lambda Id_n$ bestimmt. Konvergenz: \vspace*{-2mm} \[ \lim_{k\to\infty} \langle Ax^k,x^k \rangle_2 = \lambda_i \] Wird die Approximation $\tilde\lambda$ in jedem Iterationsschritt durch die gefundene Approx. verbessert, so approx. das Verfahren einen EV zum EW $\lambda_i$. \subsection*{Hessenberg- / Tridiagonalgestalt} Eigenwertlöser beginnen i.A. mit der Äquivalenz-umformung von $A \in \C^{n \times n}$ in obere Hessenberg- bzw. Tridiagonalgestalt $\mathcal{H}$. Danach wird $\mathcal{H}$ in eine obere Dreiecks- bzw. Diagonalmatrix äquivalent umgeformt. Die Hauptdiagonale einer solchen Matrix besteht dann aus den Eigenwerten von $A$. \subsection*{QR-Algorithmus} Sei $A = QR$ eine QR-Zerlegung von $A \in \R^{n \times n}$. Eine \emph{QR-Transformation} ist $A \mapsto A':=RQ$. \spacing $A'$ ist orthogonalähnlich zu $A$ und $\sigma(A) = \sigma(A')$. Ist $A$ eine obere Hessenberg- oder symmetrische Tridiagonalmatrix, so hat $A'$ dieselbe Struktur. \spacing Transformiere $A$ in obere Hessenberg- bzw. symmetrische Tridiagonalgestalt. Setze dann $A_0 := A$ und iteriere: $A_k =: Q_kR_k, \ A_{k+1} := R_kQ_k$ für $k = 0,1,2,\dots$. \subsubsection*{QR-Identitäten} Sei $A \in \R^{n \times n}$. Dann gelten für $\{A_k\}_k$: \begin{enumerate}[label=(\alph*)] \item $A_{k+1} = Q_k^T A_k Q_k$ \item $A_{k+1} = Q_{k+1}^T A Q_{k+1}$ mit $Q_{k+1} := Q_0 \cdots Q_k$ \item $A^{k+1} = Q_{k+1} R_{k+1}$ mit $R_{k+1} := R_k \cdots R_0$ \end{enumerate} Diese begründen den Zusammenhang von QR-Algorithmus und Potenzmethode. \subsubsection*{QR mit Spektralverschiebung} Der ursprüngliche QR-Algorithmus konvergiert langsam. Dies lässt sich mit Anwendung auf $\tilde A = A - \mu I_n$ (Shift / Spektralverschiebung) verbessern. \spacing Transformiere $A$ in obere Hessenberg- bzw. symmetrische Tridiagonalgestalt. Setze dann $A_0 := A$ und iteriere: $A_k - \mu_k I_n =: Q_kR_k, \ A_{k+1} := R_kQ_k + \mu_k I_n$ für $k = 0,1,2,\dots$. \spacing Bewährte Shift-Strategie: $\mu_k := (A_k)_{nn}$ $|(A_{k+1})_{n,n-1}| \leq c |(A_k)_{n,n-1}|^2$ (quadratische Konv.) \subsubsection*{Bestimmung der Eigenvektoren} Auf die obere Hessenberg-Form $A_0 = P^T A P$ lässt sich die inverse Potenzmethode mit den berechneten Eigenwertnäherungen als Schätzwert anwenden. Das auftretende LGS $A_0 - \tilde\lambda I_n$ lässt sich effizient mit $n-1$ Givens-Rotationen lösen. \section*{Nichtlineare Gleichungssysteme} Die Berechnung von Nullstellen von nichtlinearer $F : D \subset \R^n \to \R^n$ kann i.A. nur iterativ erfolgen. \subsection*{Konvergenzordnung} Sei $\{x^k\}_{k\in\N_0} \subset \R^n$ gegen $\xi \in \R^n$ konv. Folge. Die Folge ist von Ordnung $p \geq 1$, wenn: $\exists C > 0 : \| x^{k+1}-\xi \| \leq C\|x^k-\xi\|^p$ für $k = 0,1,\dots$ Falls $p=1$ sei zusätzlich $C < 1$. \vspace*{-4mm} \begin{align*} p=1 \ (C<1) & \text{\ \ \emph{lineare Konvergenz}} \\ p\in(1,2) & \text{\ \ \emph{superlineare Konvergenz}} \\ p=2 & \text{\ \ \emph{quadratische Konvergenz}} \\ p=3 & \text{\ \ \emph{kubische Konvergenz}} \end{align*} \subsection*{Lokale Konvergenz} Ein Iterationsverfahren $x^{k+1} = \Phi_k(x^k)$ mit $\Phi_k : D \subset \R^n \to \R^n$ ist \emph{lokal konvergent} gegen $\xi \in \R^n$, wenn: $\exists \text{ Umgebung } U \subset D \text{ von } \xi \ \forall x^0 \in U : \{x^k\}_{k\in\N_0}$ konvergiert gegen $\xi$. Ist $U = D$ so konvergiert das Verfahren global. \subsection*{Nullstellen einer Veränderlichen} Sei $f : [a,b] \to \R$ stetig mit $a < b \in \R$. \subsubsection*{Bisektionsverfahren} Sei $f(a)f(b) < 0$. Dann garantiert der Zwischenwertsatz die Existenz einer Nullstelle $\xi \in (a,b)$. Intervallhalbierung approximiert eine Nullstelle. \vspace*{-4mm} \begin{align*} x_k &:= \frac{b_k+a_0}{2} \\ f(x_k)f(a_k) \leq 0 &\rightsquigarrow a_{k+1} := a_k, \ b_{k+1} := x_k \\ f(x_k)f(a_k) > 0 &\rightsquigarrow a_{k+1} := x_k, \ b_{k+1} := b_k \end{align*} Das Bisektionsverfahren konvergiert mit Abbruchbedingung $|f(x_k)| < \tau$ für bel. $\tau > 0$ in endlich vielen Schritten. Falls $f$ Hölder-stetig mit Ordnung $\alpha \in (0,1]$ ist, konvergiert das Verfahren nach maximal $\left\lceil\log_2((b-a)(\frac{L}{\tau})^{1/\alpha})\right\rceil$ Schritten. \subsubsection*{Sekantenverfahren} Zwei Approximationen $x_{k-1}$ und $x_k$ ergeben neue Approximation $x_{k+1}$ als Nullstelle der Sekante $S_f(x;x_k;x_{k-1}) = f(x_k)+\frac{f(x_{k-1})-f(x_k)}{x_{k-1}-x_k} (x-x_k)$. Rekursion: \vspace*{-4mm} \[ x_{k+1} := x_k - \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}f(x_k) \] \spacing Sei $f \in C^2(a,b)$, $\exists \xi \in (a,b) : f'(\xi), f''(\xi) \neq 0$. Dann konvergiert das Sekantenverfahren lokal superlinear mit Ordnung $(\sqrt{5}+1)/2 \approx 1.618$. \subsubsection*{Newton-Verfahren} Ersetzen von $\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}$ im Sekantenverfahren mit dem Kehrwert der Tangentensteigung $\frac{1}{f'(x_k)}$ ergibt das \emph{Newton-Verfahren}: \vspace*{-2mm} \[ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \] $x_{k+1}$ ist Nullstelle der Tangente an $f$ in $x_k$. \spacing Sei $f \in C^2(a,b), \exists \xi \in (a,b) : f'(\xi) \neq 0$. Dann konv. das Newton-Verfahren lokal mit Ordnung $2$. \subsection*{Banachscher Fixpunktsatz} Sei $D \subset \R^n$ abgeschlossen, $\Phi : D \to D$ Kontraktion bzgl. $\|\cdot\|$ mit Kontraktionszahl $q \in [0,1)$. Dann hat $\Phi$ genau einen Fixpunkt $x^\star \in D$. Die Fixpunktiteration $x^{k+1} := \Phi(x^k)$ mit $x^0 \in D$ konv. Es gilt die Fehlerabschätzung: \vspace*{-6mm} \[ \forall 0 \leq l \leq k - 1 : \|x^\star - x^k\| \leq \frac{q^{k-l}}{1-q} \|x^{l+1} - x^l\| \] Für $l=0$ ergibt sich die a priori-Abschätzung: \vspace*{-2mm} \[ \|x^\star - x^k\| \leq \frac{q^k}{1-q} \|x^1 - x^0\| \] Für $l=k-1$ die a posteriori-Abschätzung: \vspace*{-2mm} \[ \|x^\star - x^k\| \leq \frac{q}{1-q} \|x^k - x^{k-1}\| \] \subsubsection*{Lokaler Konvergenzsatz} Sei $\Phi : D \subset \R^n \to \R^n$ stetig differenzierbare Fkt., $D$ offen, $\exists x^\star \in D : f(x^\star)=x^\star$ und $\|\Phi'(x^\star)\| < 1$. \vspace*{1mm} Dann ex. abgeschlossene Umgebung $U \subset D$ von $x^\star$ s.d. $\Phi$ in ihr Kontraktion und Selbstabbildung $\Phi(U) \subset U$ ist sowie die Fixpunktiteration konv. \subsection*{Newton-Verfahren in $\R^n$} Sei $F : D \subset \R^n \to \R^n$ eine nichtlineare Funktion. Zu finden ist ein $x^\star \in D$ mit $F(x^\star) = 0$. \spacing Sei $\Phi(x) := x + G(x,F(x))$ mit $G(x,F(x)) = T(x)F(x)$ wobei $T : D \subset \R^n \to \text{GL}_n(\R)$. Das Nullstellenproblem ein Fixpunktproblem: \vspace*{-2mm} \[ \Phi(x^\star) = x^\star \iff F(x^\star) = 0 \] Es ergibt sich das \emph{Newton-Verfahren} für $x^0 \in D$: $x^{k+1} := x^k + s^k, \ F'(x^k)s^k = -F(x^k), \ k = 0,1,2,\dots$ \vspace*{1mm} $s^k$ ist der \emph{$k$-te Newton-Schritt oder Korrektur}. \spacing Für Konvergenzuntersuchungen formuliert: $x^{k+1} = \Phi(x^k)$ mit $\Phi(x) = x - F'(x)^{-1}F(x)$ \subsubsection*{Wohldefiniertheit des Newton-Verfahrens} Sei $x^\star \in D$ Lösung des Nullstellenproblems, $F : D \subset \R^n \to \R^n$ stetig diffbar. mit regulärer $F'(x^\star)$: \begin{enumerate}[label=(\alph*)] \item $\exists$ Umgebung $U$ mit $x^\star \in U \ \forall x^0 \in U : $ Newton-Verfahren ist wohldefiniert und mindestens linear konvergent gegen $x^\star$ \item Ist $F' : D \to \R^{n \times n}$ Hölder-stetig in $U$ mit Ordnung $\alpha \in (0,1]$ dann: \\ $\|x^{k+1}-x^\star\| \leq C_N \|x^k-x^\star\|^{1+\alpha}$ mit $C_N > 0$ \\ Verfahren konv. superlinear mit Ordnung $1+\alpha$ für $\alpha \in (0,1)$ und quadratisch für $\alpha = 1$ \end{enumerate} \subsubsection*{Konvergenzüberprüfung} Eine wichtige Invarianzeigenschaft des Newton-Verfahrens ist, dass $F(\cdot)$ und $G(\cdot) = AF(\cdot)$ für $A \in \text{GL}_n(\R)$ dieselben Nullstellen haben, dass Verfahren sich also auf $F$ oder $G$ anwenden lässt. Der \emph{Monotonietest} $\|F(x^{k+1})\| \leq \vartheta\|F(x^k)\|, \ \vartheta \in (0,1)$ spiegelt dies nicht wieder. Er ist nicht affin-invariant, im Gegensatz zum Newton-Verfahren und dem Nullstellenproblem. \vspace*{1mm} Der \emph{affin-invariante natürliche Monotonietest}: \vspace{-2mm} \[ \|F'(x^k)^{-1}F(x^{k+1})\| \leq \vartheta\|F'(x^k)^{-1}F(x^k)\| \] Praktisch wird das Newton-Verfahren bei Verletzung des Tests mit $\vartheta = \frac{1}{2}$ als divergent gestoppt. \subsubsection*{Stoppstrategie} Ein $x^{k+1}$ wird als Approximation an $x^\star$ aktzeptiert, wenn $\|s^k\| \leq \tau$ mit $s^k := F'(x^k)^{-1}F(x^k)$ ist. $\tau > 0$ ist die gewählte Toleranz. \subsection*{Satz von Kantorowitsch} Sei $F : D \subset \R^n \to \R^n$ Funktion mit Eigenschaften: $\exists \beta, \gamma, \eta > 0 : \beta\gamma\eta \leq \frac{1}{2}$ und $\ x^0 \in D$ s.d.: \begin{enumerate}[label=(\roman*)] \item $F$ ist in $x^0$ diffbar. mit $\|F'(x^0)^{-1}\| \leq \beta$ und $\|F'(x^0)^{-1}F(x^0)\| \leq \eta$ \item $F'$ ist Lipschitz-stetig mit $\gamma$ in abg. Kugel $\overline{B_{\overline r}(x^0)} \subset D$ mit Radius $\overline r \geq r_- := \frac{1-\sqrt{1-2\beta\gamma\eta}}{\beta\gamma}$ \end{enumerate} Dann ex. eine eind. Nst. $x^\star$ von $F$ in $\overline{B_{r_-}(x^0)}$ und das Newton-Verfahren mit $x^0 \in D$ ist wohldef. Weiter gilt: $\|x^k-x^\star\| \leq t_k := \frac{(2\beta\gamma\eta)^{2^k}}{2^k\beta\gamma}$ Zusätzlich ist $x^\star$ die eind. Nst. in offener Kugel $B_R(x^0)$ mit $R=\min\{\overline r,r_+\}$ und $r_+ := \frac{1+\sqrt{1-2\beta\gamma\eta}}{\beta\gamma}$. \subsection*{Inexakte Newton-Verfahren} Hier wird der Newton-Schritt $s^k$ zu Beginn nur grob approximiert und nur in der Nähe der Nullstelle präzise berechnet. Dies dient der Reduktion der Rechenzeit bei Beibehaltung der quadratischen Konvergenz. Für $x^0 \in D, k = 0,1,2,\dots$: \vspace*{-4mm} \[ x^{k+1} := x^k + s^k, \ \|F'(x^k)s^k + F(x^k)\| \leq \eta_k \|F(x^k)\| \] Hierbei ist $\{\eta_k\}_k \subset [0,1)$ die Toleranz. Der inexakte Schritt wird aus $F'(x^k)s^k = -F(x^k)$ bestimmt, s.d. das relative Residuum kleiner gleich $\eta_k$ ist. Dies ist über frühes Stoppen von iterativen Lösern wie GMRES zu erreichen. \section*{Nichtlineare Ausgleichsprobleme} Sei $F : D \subset \R^n \to \R^m$ mit $n \neq m$. \vspace*{1mm} Finde die Lösung einer Minimierungsaufgabe: $x^\star \in D : g(x^\star) = \min_{x \in D}g(x)$ mit $g(x) := \|F(x)\|^2$. \vspace*{1mm} $\|\cdot\|$ sei die Euklidische Norm $\|\cdot\|_2$. \subsection*{Gauß-Newton-Verfahren} Ziel ist die Bestimmung von $n$ Parametern $x$ einer Modellfunktion $\varphi$ mit Hilfe von $m$ Messungen. Sei $\{(t_i,b_i) : 1 \leq i \leq \ell\} \subset \R^d \times \R^p$ Meßdatensatz mit Meßpunkten $t_i \in \R^d$ und Meßwerten $b_i \in \R^p$. \columnbreak Modell $\varphi(t_i;x) = b_i$ wird identifiziert mit: \vspace*{-2mm} \[ F(x) := \begin{pmatrix} \varphi(t_1;x) - b_1 \\ \vdots \\ \varphi(t_\ell;x) - b_\ell \end{pmatrix} \in \R^m, \ m=\ell p \] Konkret gelößt wird das lokale Minima $x^\star$ von $g$ mit $\nabla g(x^\star) = 0$ und $\mathcal{H}g(x^\star)$ positiv definit. \vspace*{-4mm} \begin{align*} \nabla g(x) &= 2F(x)^T F'(x) \\ G(x^\star) :&= \frac{1}{2} \nabla g(x^\star)^T = F'(x^\star)^T F(x^\star) = 0 \end{align*} Nullstelle wird mit Newton-Verfahren bestimmt. \vspace*{-2mm} \[ G'(x) \approx F'(x)^T F'(x) \] Für $x$ in der Nähe eines Minimums von $g$. Das konkrete \emph{Gauß-Newton-Verfahren}: \vspace{-4mm} \[ x^{k+1} := x^k + s^k, \ s^k := -F'(x^k)^+ F(x^k), \ k = 0,1,2,\dots \] Wobei $F'(x)^+ = (F'(x)^T F'(x))^{-1} F'(x)^T$. \subsubsection*{Konvergenz des Gauß-Newton-Verfahrens} Sei $F : D \subset \R^n \to \R^m$ stetig differenzierbar, $m \geq n$ und habe Lösung $x^\star$ s.d. $F'$ Maximalrang hat: $F'(x^\star)$ ist injektiv. Weiter gelte für $\kappa \in [0,1)$ $\|F'(x)^+ F(x^\star)\| \leq \kappa \|x-x^\star\|$ lokal um $x^\star$. Dann: \begin{enumerate}[label=(\alph*)] \item Das Gauß-Newton-Verfahren konvergiert lokal mindestens linear gegen $x^\star$ \item Ist $F'$ Hölder-stetig mit Ordnung $\alpha \in (0,1]$ in der Nähe von $x^\star$ so gilt: \\ $\|x^{k+1}-x^\star\| \leq C_{GN}\|x^k-x^\star\|^{1+\alpha} + \kappa\|x^k-x^\star\|$ Falls $F(x^\star) = 0$ gilt, ist die Konvergenz superlinear von Ordnung $1+\alpha$. Sonst linear. \end{enumerate} \section*{Numerische Integration} Numerische Auswertung des Riemann-Integrals: \vspace*{-2mm} \[ I(f) = I_a^b(f) = \int_a^b f(t) \ \text{d}t \] Die Integralabbildung $I : \mathcal{C}([a,b]) \to \R, f \mapsto I(f)$ ist additive, positive Linearform. \subsection*{Kondition der Quadraturaufgabe} Die Kondition der Aufgabe $(I,f)$ bezüglich der $\text{L}^1$-Norm $\|f\|_1 := \int_a^b |f(t)| \text{d}t$ ist: $\kappa(f) = \frac{I(|f|)}{|I(f)|}$ Gute Konditionierung ist bei vorzeichenwechsellosen $f$ gegeben, oszillierde $f$ haben $\kappa(f) \gg 1$. \subsection*{Quadraturformeln} Eine \emph{Quadraturformel} $\widehat I(f)$ ist def. als: \vspace*{-2mm} \[ \widehat I(f) := (b-a)\sum_{i=0}^n \lambda_i f(t_i) \] Mit $n+1$ ansteigenden Knoten $t_i$ sowie Gewichten $\lambda_i$ s.d. $\sum_{i=0}^n \lambda_i = 1$. \subsubsection*{Trapezsumme} \[ \widehat I_n := \sum_{i=1}^n T_i = \sum_{i=1}^n \frac{t_i - t_{i-1}}{2}(f(t_{i-1})+f(t_i)) \] \subsubsection*{Konstruktion von Quadraturformeln} $f$ werde durch Linearkombination einfach integrierbarer Funktionen $p_i$ approximiert: \vspace*{-2mm} \[ \widehat I(f) := I(\tilde f) = \sum_{i=0}^n f(t_i) I(p_i) \] Wobei $\tilde f(t) := \sum_{i=0}^n f(t_i) p_i(t)$ \subsubsection*{Newton-Cotes-Formeln} $f$ wird mit Polynomen, z.B. \emph{Lagrange-Polynomen} $L_{n,i}$ aus Numerik 1 approximiert. \vspace*{-4mm} \begin{align*} \widehat I_n(f) :&= \int_a^b P(f|t_0,\dots,t_n)(t)\text{d}t \\ &= (b-a) \sum_{i=0}^n \frac{1}{b-a} \int_a^b L_{n,i}(t)\text{d}t f(t_i) \end{align*} Die Gewichte $\lambda_{n,i}$ hängen von der Knotenwahl ab. $\widehat I_n$ ist exakt für Polynome bis Grad $n$. Zu $n+1$ verschiedenen Knoten gibt es genau eine Quadraturformel die für alle $Q \in \Pi_n$ exakt ist. \spacing Sind die Knoten äquidistant mit $t_i = a + ih, \ h=\frac{b-a}{n}$, heißen die Quadraturformeln \emph{Newton-Cotes-Formeln} mit Gewichten: \vspace*{-2mm} \[ \lambda_{n,i} = \frac{1}{b-a} \int_a^b \prod_{j=0,j\neq i}^n \frac{t-t_j}{t_i-t_j} \text{d}t \] { \def\arraystretch{1.6} \begin{tabular}{ l | l | l | l } $n$ & Gewichte & Fehler & Regel \\ \hline 1 & $\frac{1}{2}$, $\frac{1}{2}$ & $\frac{h^3}{12}f''(\tau)$ & Trapez \\ 2 & $\frac{1}{6}$, $\frac{4}{6}$, $\frac{1}{6}$ & $\frac{h^5}{90}f^{(4)}(\tau)$ & Simpson \\ 3 & $\frac{1}{8}$, $\frac{3}{8}$, $\frac{3}{8}$, $\frac{1}{8}$ & $\frac{3h^5}{80}f^{(4)}(\tau)$ & $3/8$ \\ 4 & $\frac{7}{90}$, $\frac{32}{90}$, $\frac{12}{90}$, $\frac{32}{90}$, $\frac{7}{90}$ & $\frac{8h^7}{945}f^{(6)}(\tau)$ & Milne \end{tabular} } \subsection*{Romberg-Quadratur} Die \emph{Romberg-Quadratur} wertet die Trapezsumme bzgl. einer Folge von Gittern aus und extrapoliert aus den Integralen eine bessere Approximation. \spacing Konkret wird ein interpolierendes Polynom durch Stützwerte $(h_0^2,T(h_0)),\ (h_1^2,T(h_1)),\dots,(h_m^2,T(h_m))$ gelegt und an der Null ausgewertet: \vspace*{-2mm} \[ P(T|h_0^2,\dots,h_m^2)(0) \approx I(f) \] Da das interpolierende Polynom nur in $0$ ausgewertet wird, bietet sich das \emph{Schema von Neville} an. \vspace*{-4mm} \begin{align*} T_{i,0} &= P(T|h_i^2) = T(h_1) \\ T_{i,k} :&= P(T|h_{i-k}^2,h_{i-k+1}^2,\dots,h_i^2)(0) &0 \leq k \leq i \leq m \\ &= T_{i,k-1} + \frac{T_{i,k-1}-T_{i-1,k-1}}{\frac{h_{i-k}^2}{h_i^2}-1} &1\leq k\leq i\leq m \end{align*} \subsubsection*{Verkleinerung des Gitters} Folgen zur Verkleinerung der Grundschrittweite: $h_j = \frac{h_{j-1}}{2} = \frac{h}{2^j}$ mit $n_j = 2^j$ ist die \emph{Romberg-Folge}. \vspace*{1mm} $h_1 = \frac{h}{2},h_2=\frac{h}{3},h_3=\frac{h}{4},h_j=\frac{h}{n_j},\ j=4,5,\dots$ mit $n_j = 2n_{j-2}$ für $j \geq 4$ ist die \emph{Bulirsch-Folge}. \vspace*{1mm} Vorteil der Bulirsch-Folge ist, dass sie mit weitaus weniger Auswertungen der Funktion auskommt.