Benutzer:Stepri2005/Kurs:Optimierung II/Einführung

In diesem Kapitel stellen wir einige Ergebnisse aus der Optimierung I zusammen, wobei wir einige von ihnen auf den Spezialfall der in diesem Kurs behandelten unrestringierten Optimierung einschränken.

1.1 Einleitung

In diesem Kurs werden Algorithmen zur Lösung des unrestringierten (stetigen) Optimierungsproblems

$(P):{\text{ Minimiere }}f(x){\mbox{ über alle }}x\in \mathbb {R} ^{n}$

für eine stetige Zielfunktion $f:\mathbb {R} ^{n}\to \mathbb {R}$ in $n$ Veränderlichen untersucht. Der Einfachheit halber fordern wir im Allgemeinen, dass die in einem Problem vorkommenden Funktionen auf dem ganzen $\mathbb {R} ^{n}$ definiert sind und dort die gewünschten Differenzierbarkeitseigenschaften haben. Es würde in den meisten Fällen reichen, diese Eigenschaften nur auf einer offenen Umgebung der betrachteten lokalen Lösung zu fordern. Das Wort „${\text{Minimiere}}$“, abgekürzt „${\text{Min.}}$“, ist wieder als Aufforderung und nicht als „$\min$“ im mathematischen Sinne von Minimum zu verstehen. Die Aufgabe $(P)$ ist demnach gleichbedeutend mit dem Problem

$\inf _{x\in \mathbb {R} ^{n}}f(x)$

und es nicht unbedingt von Vorneherein klar, ob $f$ auf $\mathbb {R} ^{n}$ einen kleinsten Funktionswert besitzt. Falls $f(x)$ sein Minimum auf $\mathbb {R} ^{n}$ in einem Punkt $x^{*}$ annimmt, dann kann das Problem $(P)$ bekanntlich auch in der Form

$\min _{x\in \mathbb {R} ^{n}}f(x)$

geschrieben werden.

Ein unrestringiertes Maximierungsproblem kann aufgrund der Identität

(1.1) $\sup _{x\in \mathbb {R} ^{n}}f(x)=-\inf _{x\in \mathbb {R} ^{n}}(-f(x))$

in ein Minimierungsproblem umgeschrieben werden, so dass es genügt, nur Minimierungsprobleme zu betrachten. Den Wert

(1.2) $\mu :=\inf _{x\in \mathbb {R} ^{n}}f(x)$

bezeichnen wir wieder als den Minimalwert von Problem $(P)$. Es sei ergänzt, dass man für $Z=\emptyset$ setzt:

$\inf _{x\in Z}f(x):=+\infty ,\quad \sup _{x\in Z}f(x):=-\infty .$

Da es uninteressant ist, eine lineare Funktion über dem ganzen $\mathbb {R} ^{n}$ zu minimieren (warum?), können wir implizit annehmen, dass $f$ nichtlinear ist. Ist $f$ eine konvexe Funktion, so handelt es sich offenbar bei $(P)$ um ein spezielles konvexes Optimierungsproblem. In diesem Zusammenhang wiederholen wir nochmals:

Definition 1.1

Eine Menge $K\subseteq \mathbb {R} ^{n}$ heißt konvex, wenn gilt:

$x,y\in K,\quad t\in [0,1]\Rightarrow tx+(1-t)y\in K.$

Definition 1.2

Sei $f:D\subseteq \mathbb {R} ^{n}\to \mathbb {R}$ eine Funktion und $K\subseteq D$ eine konvexe Menge.

(i) $f$ heißt konvex auf $K$, falls gilt:

(1.3) $x,y\in K,\quad t\in [0,1]\Rightarrow f(tx+(1-t)y)\leq tf(x)+(1-t)f(y).$

(ii) $f$ heißt strikt konvex auf $K$, falls gilt:

$x,y\in K,\quad x\neq y,\quad t\in (0,1)\Rightarrow f(tx+(1-t)y)<tf(x)+(1-t)f(y).$

(iii) $f$ heißt gleichmäßig konvex auf $K$, falls eine Konstante $\beta >0$, genannt (gleichmäßige) Konvexitätskonstante, existiert, so dass gilt:

(1.4) $x,y\in K,\quad t\in [0,1]\Rightarrow {\frac {\beta }{2}}t(1-t)\|x-y\|^{2}+f(tx+(1-t)y)\leq tf(x)+(1-t)f(y).$

(iv) $f$ heißt konkav (strikt konkav, gleichmäßig konkav) auf $K$, wenn $-f$ konvex (strikt konvex, gleichmäßig konvex) auf $K$ ist.

Falls $D=K$ ist, kann in (i) - (iv) der Zusatz „auf $K$“ fortgelassen werden.

Weiter heißt eine reellwertige Funktion der Gestalt

(1.5) $f(x):=a^{T}x+\alpha ,\quad x\in \mathbb {R} ^{n}$

mit $a\in \mathbb {R} ^{n}$ und $\alpha \in \mathbb {R}$ affin oder affn-linear und im Fall $\alpha =0$ auch linear. Der Einfachheit halber sprechen wir häufig auch bei $f(x)$ von einer Funktion, obwohl es sich dabei streng genommen um den Funktionswert einer Funktion $f$ handelt. Affin-lineare Funktionen sind sowohl konvex als auch konkav, aber nicht gleichmäßig konvex.

Wichtig sind noch die Charakterisierungen konvexer Funktionen durch erste und zweite Ableitungen, welche in den folgenden beiden Sätzen zusammengefasst sind:

Satz 1.3

Sei $K\subseteq \mathbb {R} ^{n}$ konvex und $f\in C^{1}(K)$. (Mit $C^{k}(\Omega )$ bezeichnen wir die Menge aller auf einer offenen Obermenge ${\tilde {\Omega }}$ von $\Omega \subseteq \mathbb {R} ^{n}$ $k$-mal stetig differenzierbaren Funktionen $f:{\tilde {\Omega }}\to \mathbb {R}$, wobei ${\tilde {\Omega }}$ von $f$ abhängen darf.) Dann gilt:

(i) $f$ ist auf $K$ genau dann konvex, wenn gilt:

(1.6) $f(y)+\nabla f(y)^{T}(x-y)\leq f(x),\quad x,y\in K.$

(ii) $f$ ist auf $K$ genau dann strikt konvex, wenn gilt:

$f(y)+\nabla f(y)^{T}(x-y)<f(x),\quad x,y\in K,\quad x\neq y.$

(iii) $f$ ist auf $K$ genau dann gleichmäßig konvex mit Konstante $\beta >0$, wenn gilt:

${\frac {\beta }{2}}\|x-y\|^{2}+f(y)+\nabla f(y)^{T}(x-y)\leq f(x),\quad x,y\in K.$

Satz 1.4

Sei $K\subseteq \mathbb {R} ^{n}$ konvex und $f\in C^{2}(K)$. Dann gilt:

(i) Ist $\nabla ^{2}f(x)$ für alle $x\in K$ positiv semidefinit, so ist $f$ konvex auf $K$.

(ii) Ist $\nabla ^{2}f(x)$ für alle $x\in K$ positiv definit, so ist $f$ strikt konvex auf $K$.

(iii) Gibt es eine Konstante $\beta >0$, so dass

(1.7) $h^{T}\nabla ^{2}f(x)h\geq \beta \|h\|^{2},\quad h\in \mathbb {R} ^{n},\quad x\in K$

gilt, so ist $f$ gleichmäßig konvex auf $K$ mit Konstante $\beta$.

(iv) Ist $K$ offen, so gelten auch die Umkehrungen von (i) und (iii).

Mit

${\mathcal {U}}_{\varepsilon }(x^{*}):=\{x\in \mathbb {R} ^{n}{\big |}\|x^{*}-x\|<\varepsilon \}$

für ein $\varepsilon >0$ bezeichnen wir die offene $\varepsilon$-Umgebung von $x^{*}$. Weiter verwenden wir die folgenden Definitionen.

Definition 1.5

(i) $x^{*}$ heißt globale Lösung von Problem $(P)$, falls

$f(x^{*})\leq f(x),\quad x\in \mathbb {R} ^{n}$

gilt und strikt globale Lösung im Fall

$f(x^{*})<f(x),\quad x\in \mathbb {R} ^{n},\quad x\neq x^{*}.$

(ii) $x^{*}$ heißt lokale Lösung von Problem $(P)$, falls ein $\varepsilon >0$ existiert, so dass

(1.8) $f(x^{*})\leq f(x),\quad x\in {\mathcal {U}}_{\varepsilon }(x^{*})$

gilt und strikt lokale Lösung im Fall

$f(x^{*})<f(x),\quad x\in {\mathcal {U}}_{\varepsilon }(x^{*}),\quad x\neq x^{*}.$

Statt von einer Lösung spricht man auch von einem Minimalpunkt oder einem Minimierer.

Im Fall, dass $x^{*}$ eine lokale oder globale Lösung von Problem $(P)$ ist, sagt man auch, dass $f$ bzw. $f(x)$ sein lokales bzw. globales Minimum in $x^{*}$ annimmt. Wir unterscheiden hier also zwischen einem Minimierer von $f$, einem Punkt, und einem Minimum von $f(x)$, d. h. dem zugehörigen Funktionswert.

Jede globale Lösung von Problem $(P)$ ist gemäß Definition 1.5 auch eine lokale Lösung des Problems. Konvexe Probleme besitzen die wichtige Eigenschaft, dass für sie umgekehrt auch jede lokale Lösung eine globale Lösung ist:

Satz 1.6

Es sei $f\in C(\mathbb {R} ^{n})$ eine konvexe Funktion. Dann gilt:

(i) Jede (strikt) lokale Lösung von Problem $(P)$ ist auch (strikt) globale Lösung.

(ii) Ist $f$ strikt konvex, dann besitzt Problem $(P)$ höchstens eine globale Lösung.

(iii) Die Menge aller globalen Lösungen von Problem $(P)$ ist konvex und abgeschlossen.

Im konvexen Fall brauchen wir also nicht zwischen lokalen und globalen Lösungen von Problem $(P)$ zu unterscheiden und sprechen wir daher oft auch nur von Lösungen. Man denke jedoch daran, dass eine auf dem $\mathbb {R} ^{n}$ strikt konvexe Funktion keinen Minimalpunkt haben muss (z. B. $f(x):=e^{x}=\exp(x)$). Wenn eine stetige, strikt konvexe Funktion aber einen Minimalpunkt besitzt, dann ist er gemäß dem letzten Satz eindeutig.

Für den Nachweis der Existenz eines Minimalpunktes von $f$ im Fall des unrestringierten Optimierungsproblems $(P)$ lässt sich der Satz von Weierstraß nicht anwenden, weil der zulässige Bereich dieses Problems nicht beschränkt und damit nicht kompakt ist. Eine Teilmenge des $\mathbb {R} ^{n}$ ist genau dann kompakt, wenn sie abgeschlossen und beschränkt ist. Bekanntlich genügt es jedoch für den Nachweis der Existenz einer Lösung $(P)$, dass die Niveaumenge

$N(x^{0}):=\left\{x\in \mathbb {R} ^{n}{\big |}f(x)\leq f(x^{0})\right\}$

für ein $x^{0}\in \mathbb {R} ^{n}$ beschränkt ist. Für diese Menge hat man:

Lemma 1.7

Seien $x^{0}\in \mathbb {R} ^{n}$ und $f\in C(\mathbb {R} ^{n})$. Dann gilt:

(i) Es ist $x^{0}\in N(x^{0})$.

(ii) Ist $f$ konvex, so ist $N(x^{0})$ eine konvexe Menge.

(iii) $N(x^{0})$ ist abgeschlossen.

Weiter war in Optimierung I gezeigt worden:

Satz 1.8

Es seien $x^{0}\in \mathbb {R} ^{n}$ und $f\in C(\mathbb {R} ^{n})$. Ist die Niveaumenge $N(x^{0})$ beschränkt, dann besitzt das Problem $(P)$ eine globale Lösung.

Für konvexe Optimierungsprobleme mit einer differenzierbaren, gleichmäßig konvexen Zielfunktion kann die Existenz garantiert werden.

Satz 1.9

Es seien $x^{0}\in \mathbb {R} ^{n}$ und $f\in C^{1}(\mathbb {R} ^{n})$ eine auf $N(x^{0})$ gleichmäßig konvexe Funktion. Dann folgt:

(i) Die Menge $N(x^{0})$ ist kompakt.

(ii) Das Problem $(P)$ besitzt genau eine Lösung.

1.2 Positiv definite Matrizen und quadratische Funktionen

Wenn nichts anderes gesagt ist, meinen wir mit $\|\cdot \|$ die Euklidische Vektornorm bzw. die durch sie induzierte Matrixnorm, die Spektralnorm. Eine symmetrische Matrix $A\in \mathbb {R} ^{n\times n}$ ist genau dann positiv definit, wenn alle ihre Eigenwerte positiv sind und damit ihr kleinster Eigenwert $\lambda _{\min(}A)$ größer als Null ist. Sie ist folglich insbesondere nichtsingulär. Ist $\lambda _{\max(}A)$ ihr größter Eigenwert, so ist weiter $1/\lambda _{\max(}A)$ der kleinste und $1/\lambda _{\min(}A)$ der größte Eigenwert von $A^{-1}$. Demnach ist auch $A^{-1}$ eine symmetrische, positiv definite Matrix. Für die Kondition von $A$ hinsichtlich der Spektralnorm gilt somit

(1.9) $\operatorname {cond} (A)=\|A\|\left\|A^{-1}\right\|={\frac {\lambda _{\max(}A)}{\lambda _{\min(}A)}}.$

Weiter benötigen wir die folgenden Resultate aus der Optimierung I.

Lemma 1.10

Für eine symmetrische Matrix $A\in \mathbb {R} ^{n\times n}$ gilt

(1.10) $\lambda _{\min(}A)\|x\|^{2}\leq x^{T}Ax\leq \lambda _{\max(}A)\|x\|^{2},\quad x\in \mathbb {R} ^{n}.$

Im Fall, dass $A$ positiv definit ist, hat man ferner

(1.11) ${\frac {1}{\lambda _{\max(}A)}}\|x\|^{2}\leq x^{T}A^{-1}x\leq {\frac {1}{\lambda _{\min(}A)}}\|x\|^{2},\quad x\in \mathbb {R} ^{n}.$

Lemma 1.11

Ist $A\in \mathbb {R} ^{n\times n}$ eine symmetrische, positiv semidefinite Matrix und $C\in \mathbb {R} ^{m\times n}$, dann ist die Matrix $CAC^{T}$ symmetrisch und positiv semidefinit. Ist überdies $A$ positiv definit und $\operatorname {Rang} (C)=m$, dann ist auch $CAC^{T}$ positiv definit.

Von zentralem Interesse in der Optimierung sind quadratische Funktionen. Denn jede zweimal stetig differenzierbare Funktion lässt sich nach dem Satz von Taylor durch eine quadratische Funktion lokal annähern.

Definition 1.12

Unter einer quadratischen Funktion versteht man eine Funktion $f:\mathbb {R} ^{n}\to \mathbb {R}$, welche durch

(1.12) $f(x):={\frac {1}{2}}x^{T}Qx+c^{T}x+\alpha$

definiert ist, wobei $\alpha \in \mathbb {R} ,c\in \mathbb {R} ^{n}$ und $Q\in \mathbb {R} ^{n\times n}$ eine symmetrische Matrix ist.

Für die quadratische Funktion in (1.12) hat man

(1.13) $\nabla f(x)=Qx+c,\quad \nabla ^{2}f(x)=Q.$

Der Faktor $1/2$ vor dem quadratischen Term in (1.12) bewirkt also, dass der Gradient und die Hesse-Matrix von $f$ keinen Faktor vor $Q$ enthalten. Für quadratische Funktionen hat man weiter:

Lemma 1.13

Für die quadratische Funktion $f$ in (1.12) gilt:

(i) $f$ ist genau dann konvex, wenn $Q$ positiv semidefinit ist.

(ii) $f$ ist genau dann gleichmäßig konvex, wenn $Q$ positiv definit ist.

(iii) Wenn $f$ gleichmäßig konvex ist, so ist

(1.14) $\beta :=\lambda _{\min(}Q)$

die größtmögliche Konvexitätskonstante für $f$.

1.3 Optimalitätskriterien

Zur Berechnung und Identifizierung einer Lösung ist die von der Anschauung her natürliche Definition 1.5 einer lokalen bzw. globalen Lösung eines Optimierungsproblems im Allgemeinen nicht geeignet. Daher interessieren notwendige und hinreichende Optimalitätskriterien dafür, dass in einem Punkt eine lokale bzw. globale Lösung des gegebenen Problems vorliegt. Für das unrestringierte Optimierungsproblem

$(P):{\text{ Minimiere }}f(x){\mbox{ über alle }}x\in \mathbb {R} ^{n}$

hat man bekanntlich die folgenden Optimalitätskriterien.

Satz 1.14

(i) (Notwendige Optimalitätsbedingung erster Ordnung)
Es sei $x^{*}$ lokale Lösung von Problem $(P)$ und $f\in C^{1}(\mathbb {R} ^{n})$. Dann ist

$\nabla f(x^{*})=0.$

(ii) (Notwendige Optimalitätsbedingungen zweiter Ordnung)
Es sei $x^{*}$ lokale Lösung von Problem $(P)$ und $f\in C^{2}(\mathbb {R} ^{n})$. Dann gilt:

$\nabla f(x^{*})=0,\quad \nabla ^{2}f(x^{*})$ ist positiv semidefinit.

(iii) (Hinreichende Optimalitätsbedingungen zweiter Ordnung)
Es sei $f\in C^{2}(\mathbb {R} ^{n})$ und für $x^{*}$ gelte

$\nabla f(x^{*})=0,\quad \nabla ^{2}f(x^{*})$ ist positiv definit.

Dann ist $x^{*}$ strikt lokale Lösung von Problem $(P)$.

In diesem Zusammenhang definieren wir:

Definition 1.15

Es sei $f\in C^{1}(\mathbb {R} ^{n})$.

(i) Ein Punkt $x^{*}$ mit $\nabla f(x^{*})=0$ heißt stationärer oder kritischer Punkt von $f$ bzw. stationäre oder kritische Lösung von Problem $(P)$.

(ii) Ein stationärer Punkt von $f$, der weder lokaler Minimalpunkt noch lokaler Maximalpunkt von $f$ ist, heißt Sattelpunkt.

Wir geben einige Beispiele kritischer Punkte.

Beispiel 1.16

Wir untersuchen die kritischen Punkte der drei auf $\mathbb {R} ^{2}$ definierten Funktionen

$f(x,y):=x^{2}-y^{2},\quad g(x,y):=x^{3}-y^{2},\quad h(x,y):=x^{4}-y^{2}.$

Die Gradienten dieser Funktionen lauten

$\nabla f(x,y)=(2x,-2y)^{T},\quad \nabla g(x;y)=(3x^{2},-2y)^{T},\quad \nabla h(x,y)=(4x^{3},-2y)^{T}.$

Demnach ist $(x^{*},y^{*})^{T}:=(0,0)^{T}$ in allen drei Fällen der einzige kritische Punkt. Die Hesse-Matrizen der Funktionen in diesem Punkt sind gegeben durch

$\nabla ^{2}f(x^{*},y^{*})={\begin{pmatrix}2&0\\0&-2\end{pmatrix}},\quad \nabla ^{2}g(x^{*},y^{*})=\nabla ^{2}h(x^{*},y^{*})={\begin{pmatrix}0&0\\0&-2\end{pmatrix}}.$

Da $\nabla ^{2}f(x^{*},y^{*})$ Eigenwerte entgegengesetzten Vorzeichens aufweist, können wir durch Anwendung von Satz 1.14 auf $f$ und $-f$ schließen, dass $(x^{*},y^{*})^{T}$ ein Sattelpunkt von $f$ ist. ($f$ nimmt in $(0,0)^{T}$ entlang der $x$-Richtung ein Minimum und entlang der $y$-Richtung ein Maximum an.) Dagegen liefert Satz 1.14 für $g$ und $h$ keine Aussage über $(x^{*},y^{*})^{T}$, denn die Matrizen $\nabla ^{2}g(x^{*},y^{*})$ und $\nabla ^{2}h(x^{*},y^{*})$ sind zwar positiv semidefinit, aber nicht positiv definit. In der Tat hat offenbar $g$ in $(x^{*},y^{*})^{T}$ einen Sattelpunkt und $h$ dort einen Minimalpunkt.

---

Eine Funktion kann natürlich mehrere lokale Minimal- und Maximalpunkte sowie Sattelpunkte besitzen. Für konvexe Probleme können wir aber aus den bisherigen Ergebnissen die folgende wichtige Information ableiten.

Korollar 1.17

Es sei $f\in C^{1}(\mathbb {R} ^{n})$ konvex. Dann ist $x^{*}$ genau dann Lösung von Problem $(P)$, wenn $\nabla f(x^{*})=0$ ist.

Dies folgt aus den Sätzen 1.14 und 1.3, wenn man in (1.6) $y:=x^{*}$ setzt und $\nabla f(x^{*})=0$ berücksichtigt. Aus Korollar 1.17 zusammen mit Satz 1.9 (für $Z:=\mathbb {R} ^{n}$) können wir ferner schließen:

Korollar 1.18

Ist $f\in C^{1}(\mathbb {R} ^{n})$ gleichmäßig konvex auf der Niveaumenge $N(x^{0})$ für ein $x^{0}$, so existiert genau ein $x^{*}$ mit $\nabla f(x^{*})=0$ und $x^{*}$ ist die eindeutige Lösung von Problem $(P)$.

1.4 Konvergenzraten

Zuletzt wollen wir die Definitionen der wichtigsten Konvergenzraten und einige ihrer Eigenschaften wiederholen, wobei $\|\cdot \|$ eine beliebige Norm auf dem $\mathbb {R} ^{n}$ sei. (Konvergenz im $\mathbb {R} ^{n}$ hinsichtlich einer Norm impliziert die Konvergenz hinsichtlich jeder anderen Norm.)

Definition 1.19

Sei $\left\{x^{k}\right\}$ eine Folge im $\mathbb {R} ^{n}$ mit $\lim _{k\to \infty }x^{k}=x^{*}$.

(i) Die Folge $\left\{x^{k}\right\}$ konvergiert von (mindestens) der Ordnung $1$ (gegen $x^{*}$), wenn ein $C\in (0,1)$ und ein $k_{0}\in \mathbb {N}$ existieren, so dass gilt:

(1.15) $\left\|x^{k+1}-x^{*}\right\|\leq C\left\|x^{k}-x^{*}\right\|,\quad k\geq k_{0}.$

(ii) Die Folge $\left\{x^{k}\right\}$ konvergiert von (mindestens) der Ordnung $p>1$ (gegen $x^{*}$), wenn ein $C>0$ und ein $k_{0}\in \mathbb {N}$ existieren, so dass gilt:

(1.16) $\left\|x^{k+1}-x^{*}\right\|\leq C\left\|x^{k}-x^{*}\right\|^{p},\quad k\geq k_{0}.$

(iii) Die Folge $\left\{x^{k}\right\}$ konvergiert superlinear (gegen $x^{*}$), wenn eine Folge $\left\{\varepsilon _{k}\right\}$ von Zahlen $\varepsilon _{k}\geq 0$ mit $\lim _{k\to \infty }\varepsilon _{k}=0$ und ein $k_{0}\in \mathbb {N}$ existieren, so dass gilt:

(1.17) $\left\|x^{k+1}-x^{*}\right\|\leq \varepsilon _{k}\left\|x^{k}-x^{*}\right\|,\quad k\geq k_{0}.$

Im Fall, dass $\left\{x^{k}\right\}$ (mindestens) von der Ordnung 1 konvergiert, spricht man auch von linearer Konvergenz der Folge. Ist die Konvergenzordnung einer Folge (mindestens) $p=2$, so spricht man von quadratischer Konvergenz.

Die Bedingung (1.17) für superlineare Konvergenz kann man auch äquivalent durch die Bedingung

(1.18) $\lim _{k\to \infty }{\frac {\left\|x^{k+1}-x^{*}\right\|}{\left\|x^{k}-x^{*}\right\|}}=0$

ersetzen, sofern $x^{k}\neq x^{*},k\geq k_{1}$ für ein $k_{1}$ ist. (Letzteres kann sicher für die Iteriertenfolge eines numerischen Verfahrens angenommen werden, da dieses abbrechen sollte, wenn $x^{k}=x^{*}$ für ein $k$ ist.) Quadratische Konvergenz impliziert superlineare Konvergenz und diese wiederum lineare Konvergenz.

Lineare Konvergenz mit einer Konstanten $C\approx 1$ kann sehr langsame Konvergenz bedeuten. Man hofft also, dass in der Praxis im Fall der linearen Konvergenz $C\ll 1$ und im Fall der quadratischen Konvergenz $C$ nicht allzu groß ist. Quadratische Konvergenz ist eine für die Praxis ausgesprochen gute Eigenschaft eines Verfahrens. Man beachte aber, dass die schnelle Konvergenz einer quadratisch konvergenten Folge erst für $\left\|x^{k}-x^{*}\right\|<1$, also für alle hinreichend großen $k$ eintritt und die Ungleichung (1.16) mit $p=2$ im Fall $\left\|x^{k}-x^{*}\right\|>1$ uninteressant ist.

Die Eigenschaften der superlinearen und quadratischen Konvergenz einer Folge im $\mathbb {R} ^{n}$ gelten unabhängig von der gerade gewählten Norm, während die Eigenschaft der linearen Konvergenz normabhängig ist. Sofern wir nichts anderes sagen, beziehen wir uns immer auf Konvergenz im Sinne der Euklidischen Norm.

Wenn wir nichts anderes sagen, meinen wir mit den Konvergenzordnungen die oben definierten, die auch als Q-Ordnungen bezeichnet werden. Neben diesen werden gelegentlich auch die etwas schwächeren R-Ordnungen verwendet.

Definition 1.20

Sei $\left\{x^{k}\right\}$ eine Folge im $\mathbb {R} ^{n}$ mit $\lim _{k\to \infty }x^{k}=x^{*}$. Dann konvergiert $\left\{x^{k}\right\}$ R-linear (R-superlinear, R-quadratisch) gegen $x^{*}$, wenn es eine Folge $\left\{\nu _{k}\right\}$ von Zahlen $\nu _{k}\geq 0$ gibt, welche Q-linear (Q-superlinear, Q-quadratisch) gegen 0 konvergiert und für die mit einem $k_{0}\in \mathbb {N}$ gilt:

(1.19) $\left\|x^{k}-x^{*}\right\|\leq \nu _{k},\quad k\geq k_{0}.$