<<

. 16
( 31 .)



>>

min si ’ xk fk (ti )
x∈IRn+1
i=1 k=0


also zu einem Problem der Form (3.37) mit
« 
f0 (t1 ) · · · fn (t1 )
¬ ·
. .
¬ ·
. .
C= . . 
f0 (tm ) · · · fn (tm )

und x = (x0 , . . . , xn )T , s = (s1 , . . . , sm )T . Fur die Basisfunktionen fk (t) =
¨
k
t, k = 0, . . . , n, ist
« 
1 t1 t2 . . . tn
1 1
¬. . .·
.
C=¬ . . .·
.
. . . .
1 tm t2 . . . t n
m m


die Vandermonde“Matrix, fur die gilt:
¨

rang(C) = n + 1, falls ti = tj fur i = j.
¨

Also ist C T C positiv de¬nit und die L¨sunge x ist eindeutig bestimmt.
o
Lineare Ausgleichsrechnung 67
s


f=x0+x1t
x
x
x
x
x x
x
x
x (ti,s i)
xxx




t




Abbildung 3.6: Ausgleichsgrade.


Beispiel 3.44. Der Fall n = 1: (Ausgleichsgerade)
Die Normalgleichungen fur das Problem
¨
m
(si ’ (x0 + x1 ti ))2
min
x0 ,x1
i=1

lauten m m
x0 m + x1 ti = si
i=1 i=1
m m m
t2
x0 ti + x1 = si ti
i
i=1 i=1 i=1

und k¨nnen explizit nach x0 , x1 aufgel¨st werden. In der Statistik spricht man
o o
dabei von Regressionsrechnung.

Beispiel 3.45. Der Fall n = 2: (Ausgleichsparabel)
Zu den Meßpunkten:

i 1 2 3 4 5 6 7
ti 0.04 0.32 0.51 0.73 1.03 1.42 1.60
si 2.63 1.18 1.16 1.54 2.65 5.41 7.67
erh¨lt man die Ausgleichsparabel (Schwarz, S.288)
a

f (t) = x0 + x1 t + x2 t2 ,
x0 = 2.749198
x1 = ’5.954657
x2 = 5.607247
68 Lineare Gleichungssysteme




f(t) x



5
x




x
x

x
1 x
x



1.5
0.5 1.0 t



Abbildung 3.7: Ausgleichsparabel.
Kapitel 4

Nichtlineare Gleichungen und
Gleichungssysteme

4.1 Einfuhrung und Aufgabenstellung
¨
Die Berechnung von Nullstellen nichtlinearer Gleichungssysteme bildet eine naturli-
¨
che Erweiterung der LGS aus dem vorhergehenden Kapitel. Nichtlineare Glei-
chungen und Gleichungssysteme mussen in vielen Anwendungen der Mathematik
¨
gel¨st werden. Typischerweise werden die L¨sungen nichtlinearer Gleichungen
o o
uber die Nullstellen einer Funktion f : IRn ’ IRn de¬niert, fur die dann ein
¨ ¨
n

x ∈ IR mit
f (x— ) = 0
(4.1)
gesucht wird.
Beispiel 4.1.
1. Polynome:
f (x) = a0 + a1 x + a2 x2 + . . . + an xn = 0, x ∈ IR
Z.B. sind Eigenwerte von Matrizen Nullstellen des charakteristischen Poly-
noms.

2. Bei der Berechnung der Schwingungen eines Balkens tritt das Problem
f (x) = x ’ tan(x) = 0
auf. In den Intervallen ((k ’ 1/2)π, (k + 1/2)π) liegen Nullstellen.

3. Bei der L¨sung nichtlinearer Optimierungsprobleme.
o

4. Gleichgewichtsl¨sungen chemischer Prozesse.
o

69
70 Nichtlineare Gleichungen und Gleichungssysteme




4.2 Grundlagen
4.2.1 Fixpunkte
Fixpunktgleichungen lassen sich an vielen Stellen leichter analysieren als die Null-
stellen nichtlinearer Funktionen, tatsachlich sind aber beide Problemklassen in-
¨
einander uberfuhrbar.
¨ ¨
Sei D ‚ IR und g : D ’ IRn . Gesucht sind die L¨sungen x ∈ D der Gleichung
n
o

(4.2) x = g(x).

Ein Punkt x— ∈ D heißt Fixpunkt von g, wenn x— = g(x— ) gilt.

Bemerkung 4.2. Durch De¬nition von f (x) := x ’ g(x) wird eine Fixpunktglei-
chung in eine Nullstellenberechnung uberfuhrt. Ist umgekehrt A(x) eine regul¨re
a
¨ ¨
(n, n)“Matrix (z.B. die Einheitsmatrix), x ∈ D, dann ist die Nullstellenbestim-
mung
f (x) = 0
¨quivalent zur Fixpunktgleichung
a

x = g(x) := x + A(x)f (x).


Fur gegebene Startwerte x0 , x1 , . . . , xs , s ≥ 0 werden Fixpunkte mit Iterations-
¨
verfahren der Form

xk+1 = ψ(xk , xk’1 , . . . , xk’s ),
(4.3) k≥s

bestimmt.
ψ heißt Iterationsfunktion und h¨ngt von g ab. Oft kann ψ = g und s = 0 gew¨hlt
a a
werden, so daß die Iteration dann lautet

xk+1 = g(xk ), fur gegebenes x0 ∈ D.
(4.4) k = 1, 2, 3 . . . , ¨

Es stellen sich die folgenden Fragen:

1. Wie ¬ndet man eine passende Iterationsfunktion?

2. Wie ¬ndet man passende Anfangspunkte?

3. Wann konvergiert die Folge gegen einen Fixpunkt?

4. Wie schnell konvergiert die Folge?
Grundlagen 71

y=x

g(x2 )
1
g(x ) y=g(x)
g(x0 )




x0 x1 x2 x*

Abbildung 4.1: Graphische Darstellung eines Fixpunktes.


4.2.2 Konvergenz
Der Begri¬ der Konvergenzordnung erlaubt es, iterative Verfahren auf ihre Kon-
vergenzgeschwindigkeit hin zu untersuchen.

Iterationsverfahren liefern eine Folge {xk } ‚ IRn approximativer L¨sungen, die
o
gegen die exakte L¨sung x— konvergieren. Die Konvergenzordnung gibt an, wie
o
schnell der Fehler xk ’ x— gegen Null konvergiert.

De¬nition 4.3 (Konvergenzordnung). Sei . eine Norm fur IRn und sei
¨
n
{xk } ‚ IR eine aus einem Iterationsverfahren entstandene Folge mit

x— = lim xk .
k’∞

1. Existiert eine Konstante c ∈ (0, 1), so daß

xk+1 ’ x—
(4.5) ¤ c, ∀ k = 0, 1, 2, . . .
xk ’ x—

gilt, so heißt {xk } linear konvergent. Das zugeh¨rige Iterationsverfahren
o
wird linear konvergent oder konvergent von der Ordnung 1 genannt.

<<

. 16
( 31 .)



>>