Laboratorijas darbs #1

( Jevgenijs Rogovs, 2 Dz ₃ )

Uzdevums.

Atrast visas reālas saknes vienādojumiem x⁴-5x³-12x²+76x-79=0 un x⁶=x⁴+ x³+1 ar precizitāti e=0.00001, pie tam jāizmanto vismaz divas dažādas skaitļiskās risināšanas metodes.

Teorija.

Bija izmantoti sekojošas teorijas daļas: dažas polinomu īpašības, Šturma metode, dihotomijas metode, hordu metode, pieskaru metode.

·         Polinomu īpašības.
                                            n
a) Ja ir dots polinoms f(x)=S a_ix_i , tad to reālo sakņu skaits nepārsniedz n.  
                                                ^{i=1
b)  Katrs polinoms ir nepārtrauktā funkcija intervālā (-¥; +¥).}

·         Šturma metode.
Šī metode ļauj polinomam f(x) noteikt reālo sakņu skaitu dotajā intervālā [a; b].
Vispirms konstruē galīgu funkciju virkni
w(x)={R_-1(x), R₀(x), R1(x), R₂(x), … ,R_N(x)},

kur R_i-2(x)=R_i-1(x)×Q(x)+(-R_i(x)), jeb citiem vārdiem sakot, katrs virknes loceklis ir atlikums (kas ņemts ar pretējo zīmi), ko iegūst dalot  divus iepriekšējus polinomus. Šeit Q(x) ir kautkāds polinoms un pie tam R_-1(x)=f(x) – sākotnējais polinoms,
R₀(x)=f ¢ (x) – tā atvasinājums un deg (R_N(x))=0 (t.i. R_N(x)=const).

Tālāk šinī virknē izrēķina katra polinoma vērtību punktā a (kreisā intervāla robeža) un noskaidro zimju maiņu skaitu rindā
{R_-1(a), R₀(a), R1(a), R₂(a), … ,R_N(a)} un apzīmē to ar N(a).

Analoģiski rīkojoties iegūst N(b).

Visbeidzot aprēķina reālo sakņu skaitu polinomam f(x) intervālā [a; b]: Y=N(a)-N(b).

·         Dihotomijas metode.
Metode atrod nepārtrauktas funkcijas sakni dotajā intervālā, ja ir iepriekš zināms, ka tajā intervālā ir tieši viena sakne. Ja ir dots intervāls [a; b] un funkcija f(x), tad n-tais tuvinājums ir

x⁽ⁿ⁾=0.5(a^(n-1)+b^(n-1)  ) un a⁽⁰⁾=a, b⁽⁰⁾=b un pie tam
a) a⁽ⁿ⁾=x^(n-1) , ja f(a^(n-1)) × f(x⁽ⁿ⁾) ³ 0 un a⁽ⁿ⁾= a^(n-1) pretējā gadījumā;
b) b⁽ⁿ⁾= x^(n-1) , ja f(b^(n-1)) × f(x⁽ⁿ⁾) ³ 0 un b⁽ⁿ⁾= b^(n-1) pretējā gadījumā.

T.i. kā nākošo tuvinājumu ņem tekošā intervāla viduspunktu un gadījumā ja tas neder kā atrisinājums (t.n.  ½f(x⁽ⁿ⁾)½³ e), tad par nākamā tuvinājuma intervālu pasniedz intervālu, kurā viens no galapunktiem ir tekošais tuvinājums x⁽ⁿ⁾ , bet par otro galapunktu izvēlas vienu no iepriekšējā intervāla galapunktiem tā, lai jauns (divreiz mazāks) intervāls saturētu funkcijas sakni. Ir zināms, ka ja nepārtrauktajai funkcijai vērtības kautkāda intervāla galapunktos ir ar dažādām zīmēm, tad tajā intervālā šai funkcijai ir 2k+1 (kÎ{0,1,2,…}) saknes. Un pēc tam visu atkārto un rīkojas tā līdz atrod piemērotu tuvinājumu.

·         Hordu metode.
Metode atrod nepārtrauktas funkcijas sakni dotajā intervālā, ja ir iepriekš zināms, ka tajā intervālā ir tieši viena sakne. Ja ir dots intervāls [a; b] un funkcija f(x), tad n-tā iterācija ir
            
                 f(a) × (x^(n-1) - a)
x⁽ⁿ⁾ = a - ¾¾¾¾¾¾¾  un x⁽⁰⁾=b.
                  f(x^(n-1)) – f(a)

T.i. par nākamo tuvinājumu x⁽ⁿ⁾ ņem punktu, kas veidojas krustoties Ox un hordai, kas savieno punktu (a, f(a)) ar punktu
(x^(n-1), f(x^(n-1))). Tātad sakotnēja intervāla kreisais galapunkts a it kā “stāv uz vietas”, bet labais galapunkts b (kas ir reizē arī tuvinājums) “kustās” pa kreisi kamēr nonāks pietiekoši tuvu funkcijas nulles punktam (t.i. kamēr ½f(x⁽ⁿ⁾)½< e).

·         Pieskaru metode.
Metode atrod nepārtrauktas funkcijas sakni dotajā intervālā, ja ir iepriekš zināms, ka tajā intervālā ir tieši viena sakne. Ja ir dots intervāls [a; b] un funkcija f(x), tad n-tā iterācija ir
            
                        f(x^(n-1))
 x⁽ⁿ⁾  = x^(n-1) - ¾¾¾¾  un x⁽⁰⁾=a.
                      f ¢ (x^(n-1))
 
T.i. par nākamo tuvinājumu x⁽ⁿ⁾ ņem punktu, kas veidojas krustoties Ox un pieskarei, kas vilkta no punkta (a, f(a)). Tātad sakotnēja intervāla labais galapunkts b it kā “stāv uz vietas”, bet kresais galapunkts a (kas ir reizē arī tuvinājums) “kustās” pa labii kamēr nonāks pietiekoši tuvu funkcijas nulles punktam (t.i. kamēr ½f(x⁽ⁿ⁾)½< e).

Izpildīšanas kārta.

Uzdevums tika risināts trijos posmos: sakņu skaita noskaidrošana, sakņu atdalīšana, sakņu precizēšana.

·         Pirmais posms: sakņu skaita noteikšana ar grafiskām metodēm.

Abām dotājām funkcijām tika uzzīmēti grafiki, lietojot paketu Mathematica v2.20.
Funkcijai f₁(x)=x⁴-5x³-12x²+76x-79 :

a) intervālā [-5; 6]

b) intervālā [0; 3] – lai precizētu, cik sakņu ir punkta x=2 apkārtnē.

Tātad, no grafikiem ir redzams, ka funkcijaj y=x⁴-5x³-12x²+76x-79 ir 4 saknes, kuras ir izvietotas starp punktiem x=-5 un x=6 un vairāk sakņu nevar būt, jo polinomam sakņu skaits nevar pārsniegt šī polinoma pakāpi.

Vienādojums x⁶=x⁴+x³+1 vispirms tika pārveidots par vienādojumu x⁶- x⁴- x³-1=0 un tad funkcijai f₂(x)= x⁶- x⁴- x³-1 tika uzzīmēts grafiks intervālā [-2; 2]:

Kā redzams, vienādojumam f₂(x)=0 ir tikai divas reālās saknes un tās atrodas intervālā [-2; 2].

·         Otrais posms: sakņu atdalīšana ar Šturma metodi.

Kad jau ir noskaidrots sakņu skaits, jāatrod intervāli, kuros dotām funkcijām būtu precīzi viena sakne, lai pēc tam varētu pielietot tuvinātas metodes sakņu precizēšanai. Šīm nolukam tika izmantota programma, kas bija uzrakstīta Borland Turbo Pascal v7.0 vidē. Šī programma izmanto Šturma metodi, ko pilieto pēc kārtas visiem intervāliem ar garumu 0.1 starp –5 un 6 (vai –2 un 2  - funkcijai f₂), t.i. intervāliem [-5; -4.9], [-4.9; -4.8], … , [5.9; 6]. Tiklīdz ir konstatēts, ka kāds no intervāliem satur tieši vienu sakni, tad šī intervāla galapunktu koordinātes tiek paziņoti. Rīkojoties šādi tika atrasti četri intarvāli priekš pirmās funkcijas ([-4; -3.9], [1.7; 1.8], [2.2; 2.3], [4.9; 5]) un divi priekš otrās ([-1.1; -1], [1.4; 1.5]). Tātad uz šī posma visas reālas saknes tika izolētas. Tālāk seko izmantotās pilns programmas teksts:

{=======================================================================================}

Const MaxPak=6;

Type polinoms=array[0..MaxPak] of real;

Var f: polinoms;

    a,b: real;

Function Saknes(poli: polinoms; a_,b_: real): byte;

{---------------------------------------------------------------------------}

Procedure Atvasin(var f: polinoms);

Var tmp: polinoms;

    j: integer;

Begin

     For j:=1 to MaxPak do tmp[j]:=0;

     For j:=MaxPak downto 1 do

         if f[j]<>0 then tmp[j-1]:=f[j]*j;

     f:=tmp

End;

{---------------------------------------------------------------------------}

Procedure Reiz(var f: polinoms; k: real; pak: byte);

Var tmp: polinoms;

    j: integer;

Begin

     For j:=0 to MaxPak do tmp[j]:=0;

     For j:=0 to MaxPak do

         if pak+j<=MaxPak then tmp[pak+j]:=f[j]*k;

     f:=tmp

End;

{---------------------------------------------------------------------------}

Function PolPak(f: polinoms): byte;

Var j: integer;

Begin

     PolPak:=0;

     For j:=0 to MaxPak do

         if f[j]<>0 then PolPak:=j

End;

{---------------------------------------------------------------------------}

Procedure Atn(var f: polinoms; g: polinoms);

Var tmp: polinoms;

    j: integer;

Begin

     For j:=0 to MaxPak do tmp[j]:=f[j]-g[j];

     f:=tmp

End;

{---------------------------------------------------------------------------}

Procedure Atlikums(f,g: polinoms; var atl: polinoms);

Var a,b: polinoms;

    k: real;

    pak: byte;

Begin

     a:=f;

     While PolPak(a)>=PolPak(g) do begin

                                   k:=a[PolPak(a)]/g[PolPak(g)];

                                   pak:=PolPak(a)-PolPak(g);

                                   b:=g;

                                   Reiz(b,k,pak);

                                   Atn(a,b)

                                   end;

     atl:=a

End;

{---------------------------------------------------------------------------}

Function Pakape(x: real; p: integer): real;

Var j: integer;

    r: real;

Begin

     r:=1;

     For j:=1 to p do r:=r*x;

     Pakape:=r

End;

{---------------------------------------------------------------------------}

Function Vertiba(f: polinoms; x: real): real;

Var v: real;

    j: integer;

Begin

     v:=0;

     For j:=0 to MaxPak do

         if f[j]<>0 then v:=v+f[j]*Pakape(x,j);

     Vertiba:=v

End;

{---------------------------------------------------------------------------}

Function Mainas(f: polinoms; x: real): integer;

Var Virkne: array[1..MaxPak*2] of polinoms;

    s,i,m: integer;

Begin

     Virkne[1]:=f;

     Virkne[2]:=f;

     Atvasin(Virkne[2]);

     s:=2;

     Repeat

          inc(s);

          Atlikums(Virkne[s-2],Virkne[s-1],Virkne[s]);

          Reiz(Virkne[s], -1,0)

     Until PolPak(Virkne[s])=0;

     m:=0;

     For i:=2 to s do

         if Vertiba(Virkne[i-1],x)*Vertiba(Virkne[i],x)<0 then inc(m);

     Mainas:=m

End;

Begin

     Saknes:=Mainas(poli,a_)-Mainas(poli,b_)

End;

BEGIN

     f[6]:=1;

     f[5]:=0;

     f[4]:=-1;

     f[3]:=-1;

     f[2]:=0;

     f[1]:=0;

     f[0]:=-1;

     a:=-2;

     b:=-2;

     Repeat

     if Saknes(f,a,b)=1 then Writeln('[',a:2:1,';',b:2:1,']');

     a:=a+0.1;

     b:=b+0.1

     Until abs(b-10.0)<0.1

END.

{=======================================================================================}

Šīs programmas teksts atbilst funkcijai f₂(x)=x⁶- x⁴- x³-1 un lai pārveidotu to priekš pirmās funkcijas, tekstu, kas izdālīts ar palielinātajiem burtiem būtu jāaizvieto ar šādu:

f[6]:=0;

f[5]:=0;

f[4]:=1;

f[3]:=-5;

f[2]:=-12;

f[1]:=76;

f[0]:=-79;

a:=-5;

b:=6;

Šinī programmā polinomi tika aprakstīti kā masīvi un masīva elementā ar kārtas numuru j glabājas polinomiāls koeficients pie j-tās x pakāpes.

·         Trešais posms: sakņu precizēšana ar iterāciju metodēm.

Tika izmantotas trīs iterāciju metodes: dihotomijas metodi, pieskaru metodi un hordu metodi. Visas trīs metodes tika uzprogrammētas kā atsevišķās procedūras, lietojot to pašu Borland Turbo Pascal v7.0 vidi. Šīs trīs procedūras izmanto kā globālus objektus intervāla galapunktus (tos interaktīvi uzdod lietotājs – šinī gadījumā tika izmantoti intervāli, kurus atlasīja iepriekšējā programma) un apakšprogrammas, kas izrēķina dotā polinoma un tā atvasinājuma vērtību dotajā punktā (F(x) un F_(x) atbilstoši; šīs procedūras te ir tikai priekš f₂(x)=x⁶- x⁴- x³-1, jo priekš f₁(x)=x⁴-5x³-12x²+76x-79 tās ir absolūti analoģiskās).

{=============================================================================================}

Const Eps=1e-5;

Var a_,b_: real;

{-------------------------------------------------------------------------}

Function F(x: real): real;

Begin

     F:=x*x*x*x*x*x-x*x*x*x-x*x*x-1

End;

{-------------------------------------------------------------------------}

Function F_(x: real): real;

Begin

     F_:=6*x*x*x*x*x-4*x*x*x-3*x*x

End;

{-------------------------------------------------------------------------}

Function Dihotom(a,b: real): real;

Var x,y: real;

Begin

     Repeat

     x:=(a+b)/2;

     y:=F(x);

     if F(a)*y<0 then b:=x

                 else a:=x

     Until abs(y)

     Dihotom:=x

End;

{-------------------------------------------------------------------------}

Function HorduMet(a,b: real): real;

Begin

     Repeat

     b:=a-(F(a)*(b-a))/(F(b)-F(a))

     Until abs(F(b))

     HorduMet:=b

End;

{-------------------------------------------------------------------------}

Function PieskaruMet(a,b: real): real;

Begin

     Repeat

     a:=a-(F(a)/F_(a))

     Until abs(F(a))

     PieskaruMet:=a

End;

BEGIN

     Write('A='); Readln(a_);

     Write('B='); Readln(b_);

     Writeln('Dihotomijas metode: ',Dihotom(a_,b_));

     Writeln('Hordu metode:       ',HorduMet(a_,b_));

     Writeln('Pieskaru metode:    ',PieskaruMet(a_,b_))

END.

{=============================================================================================}

Ievadot pēc kārtas visus iepriekš atrastus intervālus tika izrēķinātas atbilstošas saknes;

Vienādojumam f₁(x)=x⁴-5x³-12x²+76x-79=0 :

	Dihotomijas metode	Hordu metode	Pieskaru metode
X1	-3.99691	-3.99691	-3.99691
X2	1.76839	1.76839	1.76839
X3	2.24099	2.24099	2.24099
X4	4.98753	4.98753	4.98753

Vienādojumam f₂(x)=x⁶- x⁴- x³-1=0 :

	Dihotomijas metode	Hordu metode	Pieskaru metode
X1	-1.00000	-1.00000	-1.00000
X2	1.40360	1.40360	1.40360

Redzams, ka abiem vienādojumiem ar trīm metodēm atrastās saknes pilnīgi sakrīt precizitātes robezos (pieci cipari aiz komata, jo pieņemts ka e=0.00001).  Šīs fakts ļauj apgalvot, ka tuvinājums ir bijsi pietiekoši labs un saknes sekmīgi atrastas ar doto precizitāti.

Rezultāti.

Visas saknes, kas bija atrastas ar aprakstītājām metodēm ir saliktas sekojošā tabulā:

	x4-5x3-12x2+76x-79=0	x6=x4+ x3+1
X1	-3.99691	-1.00000
X2	1.76839	1.40360
X3	2.24099	-
X4	4.98753	-