Решение системы линейных уравнений методом Крамера и с помощью расширенной матрицы

1 Íåëèíåéíûå óðàâíåíèÿ
Ðàññìàòðèâàåòñÿ çàäà÷à íàõîæäåíèÿ çíà÷åíèé ïåðåìåííîé x = x , äëÿ
∗
êîòîðûõ ñïðàâåäëèâî ðàâåíñòâî
f (x) = 0. (1)
 ýòîì óðàâíåíèèè f(x) - íåêîòîðàÿ íåëèíåéíàÿ ôóíêöèÿ x.
Åñëè òàêèå çíà÷åíèÿ ñóùåñòâóþò, òî îíè íàçûâàþòñÿ êîðíÿìè óðàâíå-
íèÿ (1). Êîðåíü íàçûâàåòñÿ ïðîñòûì , åñëè f (x ∗ ) = 0 è êðàòíûì , åñëè
f (k) (x ∗ ) = 0 äëÿ k = 1, . . . , n − 1, à f (n) (x ∗ ) = 0 . Öåëîå n íàçûâåòñÿ êðàò-
íîñòüþ êîðíÿ .
1.1 Îòäåëåíèå êîðíåé
Ïîä îòäåëåíèåì êîðíåé óðàâíåíèÿ (1) ïîíèìàþò îïðåäåëåíèå äîñòàòî÷-
íî óçêîãî èíòåðâàëà (a, b), â êîòîðîì ëåæèò êîðåíü óðàâíåíèÿ. Îñíîâîé
îòäåëåíèÿ êîðíåé ñëóæèò
Òåîðåìà 1 . Ïóñòü ôóíêöèÿ îïðåäåëåíà è íåïðåðûâíà â çàìêíóòîì ïðîìå-
æóòêå [a, b], íà êîíöàõ êîòîðîãî îíà ïðèíèìàåò çíà÷åíèÿ ðàçíûõ çíàêîâ.
Òîãäà ìåæäó a è b íàéäåòñÿ õîòÿ áû îäíà òî÷êà c, â êîòîðîé ôóíêöèÿ
îáðàùàåòñÿ â íóëü:
f (c) = 0, a < c < b.
Åñëè ôóíêöèÿ f(x) ìîíîòîííà â ýòîì èíòåðâàëå, òî âíóòðè åãî ëåæèò
òîëüêî îäèí êîðåíü óðàâíåíèÿ f(x) = 0 .
Àëãîðèòì îòäåëåíèÿ ìîæíî ðåàëèçîâàòü ñëåäóþùèì îáðàçîì
YesDo:=True;
While YesDo do
Input a, b, M ;
h = (b − a)/M; f min := 1.0e20;
x i := a; f i := f (a);
for i:=1 to M do
begin {i}
x i−1 := x i ; f i−1 := f i ;
x i := a + h ∗ i; f i := f (x i );
1 Ïåðâàÿ òåîðåìà Áîëüöàíî-Êîøè
1
If f i < f min Then
begin {min} f
min := f i ; x min := x i ;
end; {min}
If f i−1 ∗ f i ≤ 0 Then
Output x i−1 , f i−1 , x i , f i ;
end; {i}
Output f min , x min ;
Input YesDo;
end; {W hile}
1.2 Ìåòîä áèñåêöèé
Ìåòîä áèñåêöèé(ìåòîä äåëåíèÿ ïîïîëàì) îñíîâàí íà ñëåäóþùåì èòåðà-
öèîííîì ïðîöåññå: èíòåðâàë a, b, íà êîòîðîì (f a = f (a)) · (f b = f (b)) < 0 ,
äåëèòñÿ ïîïîëàì - x s = (a+b)/2 è âû÷èñëÿåòñÿ f s = f (x s ) . Åñëè f s ·f (a) ≥
0 , òî a := x s , f a := f s , èíà÷å b := x s , f b := f s ; Äàëåå âûïîëíÿåòñÿ ñëåäó-
þùèé øàã, è ò.ä.
Íà i-ì øàãå ïðèáëèæåííûì çíà÷åíèåì êîðíÿ ñëóæèò ïîëóñóììà (a+b)/2,
îöåíêîé ïîãðåøíîñòè - ïîëóðàçíîñòü (b − a)/2.
Ìåòîä áèñåêöèé ìîæíî îïèñàòü ñëåäóþùèì àëãîðèòìîì 2
1: Input a, b, δ, N ;
2: i := 0;
3: f a := f (a); f b := f (b);
4: Repeat
5: xs := (a + b)/2; f s := f (xs); ;
6: If fs ∗ fa ≥ 0
7: Then begin fa := fs; a := xs end;
8: Else begin fb := fs; b := xs end;
9: i := i + 1;
10: x i := (a + b)/2;
11: dx := (b − a)/2;
12: Until ((|dx| ≤ δ|x i |) OR (i ≥ N));
13: Output i, x i , dx;
2 Â ïðèâîäèìûõ íèæå àëãîðèòìàõ èñïîëüçóåòñÿ òîëüêî îäíà ñåðèÿ èòåðàöèé. Íóæ-
íî èõ ìîäèôèöèðîâàòü, èñïîëüçóÿ ñòðóêòóðû èç ôàéëà it_gen.pdf
2
1.3 Ìåòîä õîðä
 ìåòîäå õîðä âìåñòî äåëåíèÿ îòðåçêà (a, b) ïîïîëàì èñïîëüçóåòñÿ ëè-
íåéíàÿ èíòåðïîëÿöèÿ ãðàíè÷íûõ çíà÷åíèé ôóíêöèè f(x)
f (t) = f (a)(1 − t) + f (b)t, ˆ 0 ≤ t = (x − a)/(b − a) ≤ 1.
Ñëåäóþùàÿ êîíòðîëüíàÿ òî÷êà íàõîäèòñÿ èç óðàâíåíèÿ ˆ f (t) = 0 :
t ∗ = f (a)/(f (a) − f (b)), x s = a + t ∗ (b − a);
Äàëåå ïðîèñõîäèò ñäâèã ãðàíèö èíòåðâàëà òàê æå, êàê â ìåòîäå áèñåêöèé.
Ìåòîä õîðä ìîæíî îïèñàòü ñëåäóþùèì àëãîðèòìîì
1: Input a, b, δ, N ;
2: f a := f (a); f b := f (b);
3: i := 0;
4: f a := f (a); f b := f (b);
5: Repeat
6: y := x2 − x1;
7: t := f a/(f a − f b); xs := a + y ∗ t
8: f s := f (xs); ;
9: If fs ∗ fa ≥ 0
10: Then begin fa := fs; a := xs end;
11: Else begin fb := fs; b := xs end;
12: i := i + 1;
13: x i := (a + b)/2;
14: dx := (b − a)/2;
15: Until ((|dx| ≤ δ|x i |) OR (i ≥ N));
16: Output i, x i , dx;
Ìåòîä áèñåêöèé è ìåòîä õîðä íåëüçÿ èñïîëüçîâàòü â ìíîãîìåðíîì ñëó÷àå!
1.4 Ìåòîä óñòàíîâëåíèÿ
Èäåÿ ýòîãî ìåòîäà ñîñòîèò â ïåðåõîäå îò íåëèíåéíîãî óðàâíåíèÿ (1) ê
îáûêíîâåííîìó äèôôåðåíöèàëüíîìó óðàâíåíèþ
dx/dt = f (x), x(0) = x 0 . (2)
3
ñîñòîÿíèåì, ÷òîáû ïðè t → ∞ x(t) → x . Òîãäà ïðèáëèæåííîå ðåøåíèå
∗
óðàâíåíèèÿ (2) ñ ïîìîùüþ óñòîé÷èâîãî ÷èñëåííîãî ìåòîäà äàåò (äëÿ äî-
ñòàòî÷íî áîëüøèõ t) õîðîøåå ïðèáëèæåíèå ê ðåøåíèþ (1).
Ïðîñòåéøèì àëãîðèòìîì áóäåò ìåòîä Ýéëåðà, ÿâëÿþùèéñÿ âàðèàíòîì
ìåòîäà ïðîñòîé èòåðàöèè
x i+1 = x i + τ f (x i ). (3)
Ìåòîä óñòàíîâëåíèÿ ìîæíî îïèñàòü ñëåäóþùèì àëãîðèòìîì
1: Input x 0 , τ , δ, N;
2: i := 0;
3: Repeat
4: dx = τ ∗ f (x i ) ;
5: i := i + 1;
6: x i := x i + dx;
7: Until ((|dx| ≤ δ|x i |) OR (i ≥ N));
8: Output i, x i , dx;
Äëÿ ïîãðåøíîñòè k = x k − x ∗ èç (3) ïîëó÷àåòñÿ ñëåäóþùåå óðàâíåíèå
k+1 = k + τ (f (x k ) − f (x ∗ )).
Ïðåäñòàâèâ f(x k ) − f (x ∗ ) = f (˜ x) k , ïîëó÷èì ñîîòíîøåíèå
k+1 = (1 + τ f (˜ x)) k ,
èç êîòîðîãî ñëåäóåò, ÷òî äëÿ ñõîäèìîñòè ìåòîäà óñòàíîâëåíèÿ äîëæíû
âûïîëíÿòüñÿ ñëåäóþùèå óñëîâèÿ: ïîñëåäîâàòåëüíîñòü {x k , k = 0, 1, . . .} äîëæíà
íàõîäèòüñÿ â îáëàñòè |x k −x ∗ | < R , â êîòîðîé ïåðâàÿ ïðîèçâîäíàÿ îãðàíè-
÷åíà è ñîõðàíÿåò ñâîé çíàê. Òîãäà âûáîð ïàðàìåòðà τ, óäîâëåòâîðÿþùåãî
óñëîâèÿì,
sign(τ ) = −sign(f ), |τ | < 2/ max |f |,
îáåñïå÷èâàåò ñõîäèìîñòü ìåòîäà óñòàíîâëåíèÿ.
4
1.5 Ìåòîä Íüþòîíà
Ìåòîä Íüþòîíà äëÿ óðàâíåíèÿ (1) çàïèñûâàåòñÿ â âèäå
x i+1 = x i − [df/dx] −1 f (x i ). (4)
Îïðåäåëåíèå:
ãîâîðÿò, ÷òî ôóíêöèÿ g(x) ∈ Lip c (X) , åñëè |g(x) − g(y)| ≤ c|x − y| äëÿ
âñåõ (x, y) ∈ X.
Òåîðåìà(î ñõîäèìîñòè ìåòîäà Íüþòîíà).
Ïóñòü f : D → R ãäå D - îòêðûòûé èíòåðâàë , à R - âåùåñòâåííàÿ îñü,
è ïóñòü f ∈ Lip c (D) . Ïðåäïîëîæèì, ÷òî äëÿ íåêîòîðîãî ρ > 0 |f | ≥ ρ
ïðè âñåõ x ∈ D. Åñëè óðàâíåíèå f(x) = 0 èìååò ðåøåíèå, òî ñóùåñòâóåò
íåêîòîðîå η > 0, òàêîå, ÷òî åñëè |x 0 − x ∗ | < η , òî ïîñëåäîâàòåëüíîñòü,
çàäàâàåìàÿ ôîðìóëîé
x k+1 = x k − f (x k )/f (x k ), k = 0, 1, 2, . . . ,
ñóùåñòâóåò è ñõîäèòñÿ ê x . Áîëåå òîãî, äëÿ k = 0, 1, 2, . . .
∗
c
|x k+1 − x ∗ | ≤ 2ρ |x k − x ∗ | 2 .
Çàìå÷àíèå 1. Êàê ñëåäóåò èç òåîðåìû, ïðè f (x ∗ ) = 0 ñõîäèìîñòü êâàä-
ðàòè÷íàÿ. Åñëè æå f (x ∗ ) = 0 , òî òîëüêî ëèíåéíàÿ.
Çàìå÷àíèå 2. Äëÿ ñõîäèìîñòè ìåòîäà Íüþòîíà íà÷àëüíîå ïðèáëèæåíèå x
0 äîëæíî áûòü äîñòàòî÷íî áëèçêî ê êîðíþ. Åñëè æå ðàññòîÿíèå |x 0 −x ∗ |
âåëèêî, òî ìåòîä Íüþòîíà ìîæåò âîîáùå íå ñõîäèòüñÿ.
Ìåòîä Íüþòîíà ìîæíî ðåàëèçîâàòü ñëåäóþùèì àëãîðèòìîì
1: Input x 0 , δ, N;
2: i := 0;
3: Repeat
4: df := [df /dx](x i ) ;
5: dx = f (x i )/df ;
6: i := i + 1;
7: x i := x i − dx;
8: Until ((|dx| ≤ δ|x i |) OR (i ≥ N));
9: Output i, x i , −dx;
5
3
m=2
2
m=2
m=4
b 1
m=0
m=2
0
m=1
−1
−1 0 1 2 3
a
Ðèñ. 1: Ðàçáèåíèå ïëîñêîñòè ïàðàìåòðîâ óðàâíåíèÿ e x − a − bx 3 = 0
1.6 Òåñòîâîå óðàâíåíèå
1.  êà÷åñòâå 1-ãî òåñòîâîãî èñïîëüçóåòñÿ óðàâíåíèå
f (x) = exp(x) − a − bx 3 = 0. (5)
 çàâèñèìîñòè îò çíà÷åíèé ïàðàìåòðîâ a, b ýòî óðàâíåíèå ìîæåò èìåòü m = 0, 1, 2, 4
êîðíÿ. Äëÿ èññëåäîâàíèÿ çíàêà 1-é ïðîèçâîäíîé ôóíêöèè
f (x) ïîëåçíî íàõîäèòü êîðíè óðàâíåíèÿ
g(x) = f (x) = exp(x) − 3bx 2 = 0. (6)
Íà ðèñóíêå 1 ïîêàçàíî ðàçáèåíèå ïëîñêîñòè ïàðàìåòðîâ a, b íà ïîäîáëà-
ñòè ñ ðàçëè÷íûì ÷èñëîì êîðíåé óðàâíåíèÿ (5).
2.  êà÷åñòâå 2-ãî òåñòîâîãî èñïîëüçóåòñÿ óðàâíåíèå
f (x) = exp(−1/(x − 1) 2 ) = 0. (7)
6
ñòè( f (k) (1) = 0, k = 0, 1, . . . ). Ïåðâàÿ ïðîèçâîäíàÿ f (x) < 0 äëÿ x < 1
è f (x) > 0 äëÿ x > 1 .
1.7 Êîìïüþòåðíûå ýêñïåðèìåíòû
1. Äëÿ ôóíêöèè óðàâíåíèÿ(5) ñ ïàðàìåòðàìè a = 1.15, b = 1.25 íàéòè
ãðàíèöû êîðíåé. Äëÿ ôóíêöèè óðàâíåíèÿ (6) ñ ïàðàìåòðîì b = 1.25 íàé-
òè ãðàíèöû êîðíåé è åå çíàêè íà âñåé âåùåñòâåííîé îñè.
Êîíòðîëüíàÿ èíôîðìàöèÿ:
Ôóíêöèÿ f(x): êîðíè(ïðèáëèæåííî) x
1 = −0.83, x 2 = 0.14, x 3 = 1.20, x 4 = 5.14
Ôóíêöèÿ g(x) = f (x): çíàêè è êîðíè (− . . . −) − 0.41 (+ . . . +) 0.75 (− . . . −) 4.18 (+ . . . +)
2. Îïèñàííûìè âûøå ìåòîäàìè(áèñåêöèé, õîðä, óñòàíîâëåíèÿ, Íüþ-
òîíà) äëÿ çíà÷åíèé δ = 1.0e − 2, 1.0e − 3, 1.0e − 4, 1.0e − 5 íàéòè êîðíè
ôóíêöèè (5)ñî çíà÷åíèÿìè a = 1.15, b = 1.25. Äëÿ ýòèõ êîðíåé ñîñòàâèòü
òàáëèöû çàâèñèìîñòè ÷èñëà èòåðàöèé îò δ.
3. Ìåòîäîì óñòàíîâëåíèÿ ïîïûòàòüñÿ íàéòè êîðåíü ôóíêöèè (5), áåðÿ
çíà÷åíèÿ ïàðàìåòðà τ, äëÿ êîòîðûõ íåò ñõîäèìîñòè. Êàêèì îáðàçîì ïðî-
ÿâëÿåòñÿ ðàñõîäèìîñòü èòåðàöèîííîãî ïðîöåññà ?
4. Ìåòîä Íüþòîíà:
â ñëó÷àå êîðíÿ êðàòíîñòè 2 ìåòîä Íüþòîíà ñõîäèòñÿ ëèíåéíî,ò.å.ñóùåñòâåííî
ìåäëåííåå, ÷åì â ñëó÷àå ïðîñòîãî êîðíÿ. Ïðîâåðèòü, áóäåò ëè ìîäèôè-
öèðîâàííûé ìåòîä Íüþòîíà
x i+1 = x i − 2[df /dx] −1 f (x i )
èìåòü äëÿ êîðíÿ êðàòíîñòè 2 òó æå ñêîðîñòü ñõîäèìîñòè, ÷òî è ñòàíäàðò-
íûé ìåòîä äëÿ ïðîñòîãî êîðíÿ. Äëÿ ïðîâåðêè èñïîëüçîâàòü óðàâíåíèå
h(x) = sin((x − 1) 2 ) = 0.
Äëÿ çíà÷åíèÿ δ = 1.0e − 7 íàéòè êîðåíü ýòîãî óðàâíåíèÿ ïðîñòûì è
ìîäèôèöèðîâàííûì ìåòîäîì Íüþòîíà. Ñðàâíèòü ÷èñëî èòåðàöèé.
7