Direkt zum Inhalt

Lexikon der Mathematik: Krawczyk-Verfahren

Verfahren der Intervallrechnung zum Nachweis der Existenz und Eindeutigkeit bzw. der Nichtexistenz einer Nullstelle x in einem Intervallvektor x(0)D bei einer stetig differenzierbaren Funktion f : D ⊆ ℝn → ℝn.

Ist f′(x) die Intervallauswertung der Funktionalmatrix f ′ von f über xx(0), C eine reelle (n × n)-Matrix und \(\tilde{x}\in \bf x\) so heißt \begin{eqnarray}{\bf K}(\tilde{x},{\bf x})=\tilde{x}-Cf(\tilde{x})+(I-C{\bf f}^{\prime}({\bf x}))({\bf x}-\tilde{x})\end{eqnarray}

Krawczyk-Operator, und die Iteration \begin{eqnarray}{\bf x}^{(k+1)}={\bf K}({\tilde{x}}^{(k)},{\bf x}^{(k)})\cap {\bf x}^{(k)},k=0,1,\ldots,\end{eqnarray}

Krawczyk-Verfahren. Dabei ist das Verfahren abzubrechen, wenn der Durchschnitt leer ist. Häufig wählt man \(\tilde{x}\) als Mittelpunkt von x und C als Näherungsinverse des Mittelpunkts von f′(x). Für ein Intervallgleichungssystem Ax = b definiert man \begin{eqnarray}{\bf K}(\tilde{x},{\bf x})=\tilde{x}-C({\bf b}-{\bf A}\tilde{x})+(I-C{\bf A})({\bf x}-\tilde{x})\end{eqnarray}

und iteriert analog.

Bezeichnen ϱ(·) den Spektralradius und |·| den Betrag Einer Intervallgröße, so kann man mit der Beziehung B =|ICf′(x(0))| folgende Aussagen beweisen:

  1. a) Gilt \({\bf K}(\tilde{x},{\bf x})\subseteq \bf x\)für ein xx(0), und ist C regulär, so besitzt f in x mindestens eine Nullstelle.
  2. b) Gilt \(({\bf K}(\tilde{x},{\bf x}))_i \subset {\bf x}_i\), i = 1, …, n, für ein x = (xi) ⊆ x(0), so besitzt f in x eine Nullstelle, die in x(0)eindeutig ist, und es folgt ϱ(B) < 1.
  3. c) Wird der Durchschnitt in (1) nach endlich vielen Schritten leer, so besitzt f in x(0)keine Nullstelle. Falls ϱ(B) < 1 ist, und \({\tilde{\bf x}}^{(k)}\)den Mittelpunkt von x(k)bezeichnet, folgt auch die Umkehrung.
  4. d) Gilt ϱ(B) < 1, und besitzt f in x(0) eine Nullstelle x, so ist diese dort eindeutig, der Durchschnitt in (1) wird nie leer, die Iterierten x(k)sind für jedes k ∈ ℕ0definiert und konvergieren bzgl. des Hausdorff-Abstands q gegen x, sofern man für \({\tilde{x}}^{(k)}\)den Mittelpunkt von x(k)wählt.

Man beachte, daß aus ϱ(B) < 1 stets die Regularität von C und f′(x) folgt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos