ˇ
SISTEMI NELINEARNIH JEDNACINA
April, 2013
Numeriˇ
cka analiza
Razni zapisi sistema
Skalarni oblik:
f1 (x1 , . . . , xn ) = 0
..
.
(1)
fn (x1 , . . . , xn ) = 0
Vektorski oblik:


f1
 .. 
F =  . ,
fn
F(x) = 0,


x1


x =  ...  ,
xn
(2)


0
 .. 
0 =  . .
0
Numeriˇ
cka analiza
Definicije i oznake
Definicija: Preslikavanje F : D ⊆ Rn → D je kontrakcija na D ako
postoji konstanta q, 0 ≤ q < 1 takva da je
kF(x) − F(y)k ≤ qkx − yk,
∀x, y ∈ D.
Konstanta q naziva se koeficijent kontrakcije.
Jakobijeva matrica preslikavanja F u tachki x ∈ D:
 ∂f1

∂f1
∂x1 (x) · · ·
∂xn (x)


..
..
..
JF (x) = 
.
.
.
.
∂fn
∂fn
∂x1 (x) · · ·
∂xn (x)
Numeriˇ
cka analiza
Metoda iteracije
Hesijanova matrica preslikavanja
 ∂2f
2 (x)
 ∂x1.
..
Hf (x) = 

2
∂ f
∂xn ∂x1 (x)
f : Rn → R:
···
..
.
···
∂2f
∂x1 ∂xn (x)

..
.
∂2f
(x)
∂x 2



n
Metoda iteracije
f1 (x1 , . . . , xn ) = 0
x1 = g1 (x1 , . . . , xn )
..
..
⇔
.
.
fn (x1 , . . . , xn ) = 0
xn = gn (x1 , . . . , xn ),
(3)
x = G(x),
(4)
ili
Numeriˇ
cka analiza

 

g1 (x)
g1 (x1 , . . . , xn )

 

..
G(x) =  ...  = 

.
gn (x)
gn (x1 , . . . , xn )
Iterativni proces:
xn = G(xn−1 ),
n = 1, 2, . . .
(5)
Teorema (dovoljan uslov konvergencije): Neka su ispunjeni
uslovi:
(i) preslikavanje G je definisano na zatvorenoj lopti
S = S(x0 , r ) = {x ∈ Rn : kx − x0 k ≤ r }
ˇciji je centar poˇcetna aproksimacija x0 , a polupreˇcnik jednak r ;
(ii) G je kontrakcija na S sa koeficijentom kontrakcije q,
kG(x) − G(y)k ≤ qkx − yk,
0 ≤ q < 1,
∀x, y ∈ S;
(iii) za poˇcetnu aproksimaciju x0 vaˇzi
kG(x0 ) − x0 k ≤ (1 − q)r .
Numeriˇ
cka analiza
(6)
Dovoljan uslov konvergencije
Tada:
1
svi ˇclanovi niza (5) pripadaju lopti S;
2
niz (5) konvergira taˇcki x ∈ S,
lim xn = x;
n→∞
3
x je jedinstvena nepokretna taˇcka preslikavanja G;
4
za aproksimaciju xn vaˇzi ocena
kxn − xk ≤
qn
kx1 − x0 k.
1−q
Dokaz:
1
Matematiˇckom indukcijom dokazujemo da
xn ∈ S(x0 , r )
za n = 0, 1, . . .
Numeriˇ
cka analiza
(7)
kx1 − x0 k = kG(x0 ) − x0 k ≤ (1 − q)r < r ⇒ x1 ∈ S(x0 , r )
Pretpostavimo da xi ∈ S(x0 , r ) za i = 1, . . . , k, gde je k ∈ N
Tada je
kxk+1 − xk k = kG(xk ) − G(xk−1 )k ≤ qkxk − xk−1 k ≤ · · ·
≤ q k kx1 − x0 k ≤ q k (1 − q)r ,
pa je
kxk+1 − x0 k = kxk+1 − xk + xk − xk−1 + · · · + x1 − x0 k
≤ kxk+1 − xk k + kxk − xk−1 k + · · · + kx1 − x0 k
≤ q k (1 − q)r + q k−1 (1 − q)r + · · · + (1 − q)r
= (1 − q)r (1 + q + · · · + q k ) = (1 − q)r
= (1 − q k+1 )r < r ⇒ xk+1 ∈ S(x0 , r ).
Numeriˇ
cka analiza
1 − q k+1
1−q
2. Neka je m > n. Tada je
kxm − xn k ≤ kxm − xm−1 k + kxm−1 − xm−2 k + · · · + kxn+1 − xn k
≤ q m−1 (1 − q)r + q m−2 (1 − q)r + · · · + q n (1 − q)r
= (1 − q)rq n (1 + q + q 2 + · · · + q m−n−1 )
< (1 − q)rq n (1 + q + q 2 + · · · ) = (1 − q)rq n
1
1−q
= rq n → 0 kada n → ∞.
Niz (xn ) je Koˇsijev, pa konvergira u Rn . Neka je
x = lim xn .
n→∞
S obzirom da je x taˇcka nagomilavanja niza (xn ) ˇciji ˇclanovi
pripadaju zatvorenom skupu S(x0 , r ), to i x ∈ S(x0 , r ).
Numeriˇ
cka analiza
3. G je kontrakcija na S(x0 , r ), pa je
kG(xn ) − G(x)k ≤ qkxn − xk.
Kako kxn − xk → 0 kada n → ∞, to je
lim G(xn ) = G(x).
(8)
lim G(xn ) = lim xn+1 = x,
(9)
n→∞
S druge strane je
n→∞
n→∞
Iz (8) i (9) sledi da je x = G(x), tj. x je nepokretna taˇcka
preslikavanja G.
Pretpostavimo da postoje dve nepokretne taˇcke, x i y. Tada iz
kx − yk = kG(x) − G(y)k ≤ qkx − yk
sledi (1 − q)kx − yk ≤ 0, ˇsto je mogu´ce samo ako je
kx − yk = 0, odnosno x = y.
Numeriˇ
cka analiza
4. Imamo
kxn − xk = kG(xn−1 ) − G(x)k ≤ qkxn−1 − xk ≤ · · ·
≤ q n kx0 − xk.
(10)
Za n = 1 nejednakost (10) ima oblik
kx1 − xk ≤ qkx0 − xk.
(11)
S druge strane, koriˇs´cenjem (11), dobijamo
kx0 − xk = kx0 − x1 + x1 − xk ≤ kx0 − x1 k + kx1 − xk
≤ kx1 − x0 k + qkx0 − xk,
odakle sledi
kx0 − xk ≤
kx1 − x0 k
.
1−q
Ocena (7) proizilazi iz relacija (10) i (12).
Numeriˇ
cka analiza
(12)
Dovoljan uslov za kontrakciju
Teorema (dovoljan uslov kontraktibilnosti): Neka su funkcije
gi , i = 1, . . . , n neprekidno diferencijabilne na zatvorenoj lopti
S(x0 , r ) = {x ∈ Rn : kx − x0 k ≤ r }
i neka je
max kJG (s)k ≤ q < 1,
s∈S(x0 ,r )
gde je k · k bilo koja matriˇcna norma saglasna sa uvedenom
vektorskom normom. Tada je G kontrakcija na S(x0 , r ).
Dokaz: u knjizi!
Numeriˇ
cka analiza
(13)
Metoda Njutn-Kantoroviˇca
Metoda Njutn-Kantoroviˇ
ca
Ideja: Reˇsavanje sistema nelinearnih jednaˇcina
f1 (x1 , . . . , xn ) = 0
..
⇔ F(x) = 0.
.
fn (x1 , . . . , xn ) = 0
(14)
svodi se na reˇsavanje niza sistema linearnih jednaˇcina.
Oznake:
x = (x1 , . . . , xn )T
- taˇcno reˇsenje sistema (14)
(0)
(0) T
x0 = (x1 , . . . , xn ) - poˇcetna aproksimacija reˇsenja sistema
ε0 = x − x 0
Tada je
F(x0 + ε0 ) = 0,
(15)
odnosno
fi (x0 + ε0 ) = 0
za i = 1, . . . , n.
Numeriˇ
cka analiza
Ako su funkcije fi neprekidno diferencijabilne u nekoj okolini taˇcke
x0 , vaˇze Tejlorovi razvoji
n
X
∂fi
(0)
fi (x0 ) +
(x0 )εj + · · · = 0
∂xj
za i = 1, . . . , n,
(16)
j=1
(0)
gde je εj
(0)
= xj − xj . Ako u razvoju (16) izostavimo nelinearne
(0)
ˇclanove u odnosu na εj , dobijamo sistem jednaˇcina
n
X
∂fi
(0)
fi (x0 ) +
(x0 )εj = 0,
∂xj
i = 1, . . . , n
j=1
(0)
koji je linearan u odnosu na εj . Matriˇcna forma ovog sistema je
F(x0 ) + JF (x0 )ε0 = 0.
Numeriˇ
cka analiza
(17)
Ako je JF (x0 ) regularna matrica, iz (17) sledi da je
ε0 = −(JF (x0 ))−1 F(x0 ).
Zbog izostavljanja nelinearnih ˇclanova u (16), zbir x0 + ε0
nije jednak taˇcnom reshenju x. Taj zbir uzimamo za narednu
aproksimaciju taˇcnog reˇsenja,
x1 = x0 + ε0 = x0 − (JF (x0 ))−1 F(x0 ).
Analogno,
x2 = x1 − (JF (x1 ))−1 F(x1 ), . . .
Iterativni proces metode Njutn-Kantoroviˇca:
xn+1 = xn − (JF (xn ))−1 F(xn ) n = 0, 1, . . .
Numeriˇ
cka analiza
(18)
Primer: Sistem jednaˇcina
ex − y = 0
xy − e x = 0
ima jedinstveno reˇsenje (1, e). Numeriˇcki rezultati sa poˇcetnom
aproksimacijom (x0 , y0 ) = (0.5, 2.0) ukazuju na konvergenciju
iterativnog procesa taˇcnom reˇsenju.
8
ex−y=0
k
0
1
2
3
4
xy−ex=0
7
6
y
5
4
3
2
1
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
xk
0.500000
1.201202
1.008660
0.999891
1.000000
2
x
Numeriˇ
cka analiza
yk
2.000000
2.804808
2.684080
2.717880
2.718282
Dovoljni uslovi konvergencije
Teorema (dovoljni uslovi konvergencije ): Neka su ispunjeni
slede´ci uslovi:
(i) funkcije fi , i = 1, . . . , n su dva puta neprekidno diferencijabilne
na zatvorenoj lopti
S(x0 , r ) = {x ∈ Rn : kx − x0 k ≤ r }
i pri tome je za i = 1, . . . , n
kHfi (x)k ≤ K ,
∀x ∈ S;
(ii) Jakobijeva matrica JF (x0 ) ima inverznu matricu za koju je
k(JF (x0 ))−1 k ≤ B;
(iii) poˇcetna aproksimacija x0 zadovoljava uslov
kF (x0 )k ≤ η;
Numeriˇ
cka analiza
(iv )
1
h = B 2K η ≤ ;
2
(v )
1−
√
1 − 2h
Bη ≤ r .
h
(19)
Tada:
1
sistem (14) ima reˇsenje x koje pripada lopti S;
2
svi ˇclanovi niza (xn ) pripadaju lopti S i niz (xn ) konvergira
reˇsenju x,
lim xn = x;
n→∞
3
vaˇzi ocena
kx − xn k ≤ t ∗ − tn ,
Numeriˇ
cka analiza
(20)
gde je t ∗ = (1 −
√
1 − 2h)Bη/h manji koren jednaˇcine
1 2
1
Kt − t + η = 0,
2
B
(21)
a tn , n = 0, 1, . . . su uzastopne aproksimacije korena t ∗ dobijene
Njutnovom metodom za t0 = 0.
Numeriˇ
cka analiza
Download

SISTEMI NELINEARNIH JEDNACINA