Numerické metody I - cv. 11 Kateřina Konečná
ITERAČNÍ METODY PRO SYSTÉMY NELINEÁRNÍCH ROVNIC
Řešíme systém m nelineárních rovnic o m neznámých:
f1(x1, x2, . . . , xm) = 0
...
fm(x1, x2, . . . , xm) = 0,
vektorový zápis soustavy: F(x) = 0, x ∈ Rm
, 0 = (0, . . . , 0) ∈ Rm
, řešení: ξ = (ξ1, ξ2, . . . , ξm) ∈ Rm
.
Metoda prosté iterace
Namísto původní úlohy F(x) = 0 řešíme ekvivalentní úlohu x = G(x), x ∈ Rm
, tj. hledáme pevné body zobrazení
G.
Iterační vztah:
xk+1
1 = g1(xk
1, xk
2, . . . , xk
m)
...
xk+1
m = gm(xk
1, xk
2, . . . , xk
m).
Konvergence: max
1≤i≤m
n
j=1
∂gi(x)
∂xj
≤ q < 1 pro každé x ∈ O(ξ), i, j = 1, . . . , m.
Příklad. Pro zadaný systém nalezněte metodou prosté iterace kořen z I. kvadrantu.
x =
8x − 4x2
+ y2
+ 1
8
,
y =
2x − x2
+ 4y − y2
+ 3
4
.
Řešení.
1. počáteční aproximace – úprava rovnic pro nalezení průsečíku
1. rovnice:
8x = 8x − 4x2
+ y2
+ 1
4x2
− y2
= 1 . . . rovnice hyperboly, hledáme průsečíky s osami:
průsečík s osou x: y = 0 −→ x2
= 1
4 −→ x = ±1
2
průsečík s osou y: x = 0 −→ y2
+ 1 = 0 . . . nemá reálný průsečík
2. rovnice:
4y = 2x − x2
+ 4y − y2
+ 3
x2
+ y2
− 2x − 3 = 0
(x − 1)2
+ y2
= 4 . . . rovnice kružnice se středem S = (1, 0) a poloměrem r = 2
⇒ počáteční aproximace: x0
= (1, 2)
1
Numerické metody I - cv. 11 Kateřina Konečná
2. konvergence:
∂g1(x, y)
∂x
= 1 − x,
∂g1(x, y)
∂y
=
1
4
y,
∂g2(x, y)
∂x
=
1
2
−
1
2
x,
∂g2(x, y)
∂y
= 1 −
1
2
y,
∂g1(x)
∂x x=x0
+
∂g1(x)
∂y x=x0
=
1
2
< 1
∂g2(x)
∂x x=x0
+
∂g2(x)
∂y x=x0
= 0 < 1
3. výpočet
x0
= (1, 2)
x1
=
8x0
− 4(x0
)2
+ (y0
)2
+ 1
8
=
9
8
y1
=
2x0
− (x0
)2
+ 4y0
− (y0
)2
+ 3
4
= 2
x1
= (9
8 , 2)
x2
≈ (1.1172, 1.9961)
x3
≈ (1.1162, 1.9966) STOP: ||xk+1
−xk
||
||xk||
< ε = 10−3
Seidelova metoda
Iterační vztah:
xk+1
1 = g1(xk
1, xk
2, . . . , xk
m)
xk+1
2 = g2(xk+1
1 , xk
2, . . . , xk
m)
...
xk+1
m = gm(xk+1
1 , xk+1
2 , . . ., xk+1
m−1, xk
m).
Příklad. Předchozí příklad pomocí Seidelovy metody.
Řešení.
počáteční aproximace: x0
= (1, 2)
1. iterace:
x1
=
9
8
y1
=
2x1
− (x1
)2
+ 4y0
− (y0
)2
+ 3
4
≈ 1.9961
x1
= (9
8 , 1.9961)
x2
≈ (1.1152, 1.9967)
x3
≈ (1.1167, 1.9966) STOP: ||xk+1
−xk
||
||xk||
< ε = 10−3
Newtonova metoda
Zabýváme se řešením úlohy F(x) = 0, uvažujeme ekvivalentní úlohu ve tvaru x = G(x) s iterační maticí
G(x) = x − J−1
F (x)F(x),
kde JF (x) =




∂f1(x)
∂x1
· · · ∂f1(x)
∂xm
...
...
...
∂fm(x)
∂x1
· · · ∂fm(x)
∂xm



 se nazývá Jacobiova matice funkce F.
2
Numerické metody I - cv. 11 Kateřina Konečná
Newtonova iterační metoda pro systém F(x) = 0 za předpokladu, že JF (x) je regulární, se spojitými prvky
v okolí bodu ξ:
xk+1
= xk
− J−1
F (xk
)F(xk
), k = 0, 1, 2, . . . .
Postup pro výpočet:
1. označme ∆k
= xk+1
− xk
2. JF (xk
)∆k
= −F(xk
) −→ výpočet ∆k
3. dosazení do iteračního vztahu: xk+1
= xk
+ ∆k
Příklad. Vypočítejte první dva kroky Newtonovy metody pro za daný systém rovnic
f1 : x2
− x + y −
1
2
= 0
f2 : x2
− 5xy − y = 0
a počáteční aproximaci x0
=
x0
y0 =
1
0
.
Řešení. Výpočet parciálních derivací a sestavení Jacobiho matice:
∂f1(x, y)
∂x
= 2x − 1,
∂f1(x, y)
∂y
= 1,
∂f2(x, y)
∂x
= 2x − 5y,
∂f2(x, y)
∂y
= −5x − 1,
−→ Jacobiho matice: JF (x) =
2x − 1 1
2x − 5y −5x − 1
.
Označme ∆ =
∆x
∆y
a počítejme soustavu JF (x0
)∆0
= −F(x0
), kde
JF (x0
) =
2x0
− 1 1
2x0
− 5y0
−5x0
− 1
=
1 1
2 −6
a − F(x0
) =
1
2
−1
.
Dostáváme soustavu
1 1
2 −6
·
∆x
∆y
=
1
2
−1
,
kterou vyřešíme (Gaussova eliminační metoda):
1 1 1
2
2 −6 −1
∼
1 0 1
4
0 1 1
4
⇒ ∆0
=
1
4
1
4
.
1. krok:
x1
= x0
+ ∆0
=
1
0
+
1
4
1
4
=
5
4
1
4
.
Výpočet ∆1
: řešíme soustavu JF (x1
)∆1
= −F(x1
)
3
2 1
5
4 −29
4
·
∆x
∆y
=
− 1
16
1
4
⇒ ∆1
=
− 13
776
− 29
776
,
2. krok:
x2
= x1
+ ∆1
=
5
4
1
4
+
− 13
776
− 29
776
≈
1.2332
0.2126
.
3