Pusdalīšanas metode(citi vārdi: bisekcijas metode, dihotomijas metode), lai atrisinātu vienādojumu f(x) = 0 ir šāds. Dariet zināmu, ka funkcija ir nepārtraukta un aizņem segmenta galus
[a, b] dažādu zīmju vērtības, tad sakne ir ietverta intervālā ( a, b). Sadalīsim intervālu divās daļās un tad apskatīsim pusi, kuras galos funkcija ņem dažādu zīmju vērtības. Mēs atkal sadalām šo jauno segmentu divās vienādās daļās un atlasām to, kurā ir sakne. Šis process turpinās, līdz nākamā segmenta garums kļūst mazāks par nepieciešamo kļūdas vērtību. Stingrāks bisekcijas metodes algoritma izklāsts:
1) Parēķināsim x = (a+ b)/2; aprēķināsim f(x);
2) Ja f(x) = 0, pēc tam pārejiet uz 5. darbību;
3) Ja f(x)∙f(a) < 0, то b = x, citādi a = x;
4) Ja | b – a| > ε, pārejiet uz 1. punktu;
5) Izvadiet vērtību x;
Piemērs 2.4. Izmantojot bisekcijas metodi, precizējiet vienādojuma sakni ( x– 1) 3 = 0, kas pieder segmentam .
Risinājums programmā Excel:
1) Šūnās A 1:F 4 mēs iepazīstinām ar apzīmējumiem, sākotnējām vērtībām un formulām, kā parādīts 2.3. tabulā.
2) Kopējiet katru formulu apakšējās šūnās ar aizpildījuma marķieri līdz desmitajai rindai, t.i. B 4 - līdz B 10, C 4 - līdz C 10, D 3 - līdz D 10, E 4 - līdz E 10, F 3 - līdz F 10.
2.3. tabula
| A | B | C | D | E | F | |
| f(a)= | =(1-B3)^3 | |||||
| k | a | x | f(x) | b | ba | |
| 0,95 | =(B3+E3)/2 | =(1-C3)^3 | 1,1 | =E3-B3 | ||
| =IF(D3=0,C3; IF(C$1*D3<0;B3;C3)) | =IF(C$1*D3>0; E3;C3) |
Aprēķinu rezultāti ir norādīti tabulā. 2.4. Kolonnā F pārbaudot intervāla garuma vērtības b – a. Ja vērtība ir mazāka par 0,01, tad šajā rindā tiek atrasta aptuvenā saknes vērtība ar norādītu kļūdu. Lai sasniegtu nepieciešamo precizitāti, bija nepieciešamas 5 iterācijas. Aptuvenā saknes vērtība ar precizitāti 0,01 pēc noapaļošanas līdz trim zīmēm aiz komata ir 1,0015625 ≈ 1,00.
2.4. tabula
| A | B | C | D | E | F | |
| f(a)= | 0,000125 | |||||
| k | a | x | f(x) | b | ba | |
| 0,95 | 1,025 | -2E-05 | 1,1 | 0,15 | ||
| 0,95 | 0,9875 | 2E-06 | 1,025 | 0,075 | ||
| 0,9875 | 1,00625 | -2E-07 | 1,025 | 0,0375 | ||
| 0,9875 | 0,996875 | 3.1E-08 | 1,00625 | 0,0187 | ||
| 0,996875 | 1,0015625 | -4E-09 | 1,00625 | 0,0094 | ||
| 0,996875 | 0,9992188 | 4.8E-10 | 1,0015625 | 0,0047 | ||
| 0,99921875 | 1,0003906 | -6E-11 | 1,0015625 | 0,0023 | ||
| 0,99921875 | 0,9998047 | 7.5E-12 | 1,000390625 | 0,0012 |
Dotais algoritms ņem vērā iespējamais gadījums“trāpīt saknē”, t.i. vienlīdzība f(x) nulle nākamajā posmā. Ja 2.3 piemērā mēs ņemam segmentu , tad pašā pirmajā solī mēs nonākam pie saknes x= 1. Patiešām, ierakstīsim šūnā B 3 vērtība 0,9. Tad rezultātu tabula būs 2.5 formā (tiek dotas tikai 2 iterācijas).
2.5. tabula
| A | B | C | D | E | F | |
| f(a)= | 0,001 | |||||
| k | a | x | f(x) | b | ba | |
| 0,9 | 1,1 | 0,2 | ||||
Izveidosim to programmā Excel pielāgotas funkcijas f(x) un bisect(a, b, eps) vienādojumu risināšanai, izmantojot bisect metodi, izmantojot iebūvēto valodu Visual Basic. To apraksti ir sniegti zemāk:
Funkcija f (Byval x)
Funkciju dalīšana uz pusēm (a, b, eps)
1 x = (a + b) / 2
Ja f(x) = 0, tad GoTo 5
Ja f(x) * f(a)< 0 Then
Ja Abs(a - b) > eps, tad GoTo 1
Funkcija f(x) nosaka kreisā puse vienādojumi un funkcija
bisect(a, b, eps) aprēķina vienādojuma sakni, izmantojot bisect metodi f(x) = 0. Ņemiet vērā, ka funkcija bisect(a, b, eps) izmanto piekļuvi funkcijai f(x). Šis ir pielāgotas funkcijas izveides algoritms:
1) Izpildiet izvēlnes komandu "Rīki - Makro - redaktors Visual Basic" Logs " Microsoft Visual Basic" Ja iekšā šo failu programmas Excel makro vai lietotāja funkcijas vai procedūras vēl nav izveidotas, šis logs izskatīsies tā, kā parādīts 2.4.
2) Izpildiet izvēlnes komandu “Ievietot - Modulis” un ievadiet programmas funkciju tekstus, kā parādīts 2.5. attēlā.
Tagad programmas lapas šūnās Excel Izveidotās funkcijas varat izmantot formulās. Piemēram, ieejam šūnā D 18 formula
Bisect(0,95;1;0,00001),
tad mēs iegūstam vērtību 0,999993896.
Lai atrisinātu citu vienādojumu (ar citu kreiso pusi), jums jāiet uz redaktora logu, izmantojot komandu “Rīki - Makro - redaktors Visual Basic” un vienkārši pārrakstiet funkcijas f(x) aprakstu. Piemēram, ar precizitāti 0,001 atradīsim vienādojuma sin5 sakni x + x 2 – 1 = 0, kas pieder pie intervāla (0,4; 0,5). Lai to izdarītu, mainīsim funkcijas aprakstu
jaunam aprakstam
f = grēks(5 * x) + x^2 - 1
Pēc tam kamerā D 18 iegūstam vērtību 0.441009521 (salīdziniet šo rezultātu ar 2.3. piemērā atrasto intervāla saknes vērtību (0.4; 0.5!).).
Atrisināt vienādojumu, izmantojot programmā dalīšanas uz pusi metodi Mathcad izveidosim apakšprogrammas funkciju bisec(f, a, b, ε), kur:
f- funkcijas nosaukums, kas atbilst vienādojuma kreisajai pusei f(x) = 0;
a, b- segmenta kreisais un labais gals [ a, b];
ε - saknes aptuvenās vērtības precizitāte.
Piemēra risinājums programmā Mathcad:
1) Palaidiet programmu Mathcad. Iepazīstinām ar funkcijas definīciju bisec(f, a, b, ε). Lai to izdarītu, ierakstiet tastatūru un rīkjoslu “Grieķu simboli”. bisec(f, a, b, ε):=. Pēc piešķiršanas zīmes “:=” rīkjoslā “Programmēšana” izmantojiet peles rādītāju, lai ar peles kreiso taustiņu noklikšķiniet uz “Pievienot rindu”. Pēc uzdevuma zīmes parādīsies vertikāla līnija. Pēc tam ievadiet tālāk redzamo programmas tekstu, izmantojot rīkjoslu “Programmēšana”, lai ievadītu zīmi “←”, cilpas operatoru kamēr, operators pārtraukums un nosacījuma operators ja citādi.
2) Ieviesīsim funkcijas definīciju f(x):=sin(5*x)+x^2–1 un pēc tam aprēķiniet saknes vērtību, izmantojot funkciju bisec pie dotajām vērtībām:
bisec(f, –0,8,–0,7,0,0001)=. Pēc “=” zīmes automātiski parādīsies programmas aprēķinātā saknes vērtība –0.7266601563. Tādā pašā veidā aprēķināsim atlikušās saknes.
Zemāk ir lapa Mathcad ar funkcijas definīciju bisec(f, a, b, ε) un aprēķini:
Dosim programmu valodā C++, lai atrisinātu vienādojumu f(x) = 0 ar pusi sadalīšanas metodi:
#iekļauts
#iekļauts
dubultā f(dubultā x);
typedef double (*PF)(double);
double bisec(PF f,double a, double b,double eps);
dubultā a, b, x, eps;PF pf;
cout<< "\n a = "; cin >>a;
cout<< "\n b = "; cin >>b;
cout<< "\n eps = "; cin >> eps;
x = bisec(pf,a,b,eps); cout<< "\n x = " << x;
cout<< "\n Press any key & Enter "; cin >>a;
dubultā f(dubultā x)(
r = sin(5*x)+x*x-1;
dubultā bisek (PF f, dubultā a, dubultā b, dubultā eps) (
do(x = (a + b)/2;
ja (f(x) == 0) pārtraukums;
ja (f(x)*f(a)<0) b = x;
)while (fabs(b-a) > eps);
Funkcija programmā f(x) ir definēts, lai atrisinātu vienādojumu
grēks5 x + x 2 – 1 = 0
no piemēra 2.3. Programmas rezultāts intervāla saknes (0,4; 0,5) noteikšanai ar precizitāti 0,00001 ir parādīts zemāk (datora ekrāns):
Nospiediet jebkuru taustiņu un ievadiet
Pēdējā rindiņa ir nepieciešama, lai organizētu pauzi, lai skatītu rezultātu.
Nelineāros vienādojumus var iedalīt 2 klasēs – algebriskajā un transcendentālajā. Algebriskie vienādojumi sauc par vienādojumiem, kas satur tikai algebriskas funkcijas (vesels skaitlis, racionāls, iracionāls). Jo īpaši polinoms ir visa algebriskā funkcija. Tiek izsaukti vienādojumi, kas satur citas funkcijas (trigonometriskās, eksponenciālās, logaritmiskās utt.). pārpasaulīgs.
Nelineāro vienādojumu risināšanas metodes ir sadalītas divās grupās:
- precīzas metodes ;
- iteratīvas metodes .
Precīzas metodes dod iespēju uzrakstīt saknes kādas galīgas attiecības (formulas) formā. No skolas algebras kursa šādas metodes ir zināmas trigonometrisko, logaritmisko, eksponenciālo, kā arī vienkāršu algebrisko vienādojumu risināšanai.
Kā zināms, daudziem vienādojumiem un vienādojumu sistēmām nav analītisko risinājumu. Tas galvenokārt attiecas uz lielāko daļu transcendentālo vienādojumu. Ir arī pierādīts, ka nav iespējams izveidot formulu, ko varētu izmantot, lai atrisinātu patvaļīgu algebrisko vienādojumu, kura pakāpe ir augstāka par četrām. Turklāt dažos gadījumos vienādojumā ir koeficienti, kas ir zināmi tikai aptuveni, un tāpēc pats uzdevums precīzi noteikt vienādojuma saknes zaudē nozīmi. Lai tos atrisinātu, mēs izmantojam iteratīvas metodes ar noteiktu precizitātes pakāpi.
Ļaujiet iegūt vienādojumu
- Funkcija f(x) ir nepārtraukts intervālā [ a, b] kopā ar tā 1. un 2. kārtas atvasinājumiem.
- Vērtības f(x) segmenta galos ir dažādas zīmes ( f(a) * f(b) < 0).
- Pirmais un otrais atvasinājums f"(x) Un f""(x) saglabā noteiktu zīmi visā segmentā.
Nosacījumi 1) un 2) garantē, ka intervālā [ a, b] ir vismaz viena sakne, un no 3) izriet, ka f(x) šajā intervālā ir monotons, tāpēc sakne būs unikāla.
Atrisiniet (1) vienādojumu iteratīvā metode nozīmē noteikt, vai tai ir saknes, cik sakņu, un atrast sakņu vērtības ar nepieciešamo precizitāti.
Jebkura vērtība, kas apvērš funkciju f(x) uz nulli, t.i. tāds, ka:
sauca sakne vienādojumi(1) vai nulle funkcijas f(x).
Problēma par vienādojuma saknes atrašanu f(x) = 0 pēc iteratīvās metodes sastāv no diviem posmiem:
- sakņu atdalīšana - saknes vai to saturoša segmenta aptuvenas vērtības atrašana;
- aptuveno sakņu precizēšana - panākt tos līdz noteiktai precizitātes pakāpei.
Sakņu atdalīšanas process sākas ar funkcijas pazīmju noteikšanu f(x) robežās x=a Un x=b punktus tās pastāvēšanas reģionā.
1. piemērs . Atdaliet vienādojuma saknes:
|
f( x) є x 3 - 6x + 2 = 0. |
Izveidosim aptuvenu diagrammu:
Līdz ar to vienādojumam (2) ir trīs reālas saknes, kas atrodas intervālos [-3, -1] un .
Aptuvenās sakņu vērtības ( sākotnējie tuvinājumi) var uzzināt arī no problēmas fiziskās nozīmes, no līdzīgas problēmas risināšanas ar dažādiem sākotnējiem datiem vai atrodams grafiski.
Izplatīts inženiertehniskajā praksē grafiskā metode aptuveno sakņu noteikšana.
Ņemot vērā, ka (1) vienādojuma reālās saknes ir funkcijas grafika krustošanās punkti f(x) ar x asi, pietiek ar funkcijas attēlojumu f(x) un atzīmējiet krustojuma punktus f(x) ar asi Ak, vai atzīmējiet uz ass Ak segmenti, kas satur vienu sakni. Grafiku konstruēšanu bieži var ievērojami vienkāršot, aizstājot vienādojumu (1) ekvivalents viņam ar vienādojumu:
Vienādojumu (4) var ērti pārrakstīt kā vienādojumu:
No tā ir skaidrs, ka (4) vienādojuma saknes var atrast kā logaritmiskās līknes krustošanās punktu abscises y= baļķis x un hiperbolas y = . Konstruējot šīs līknes, mēs aptuveni atradīsim vienīgo (4) vienādojuma sakni vai noteiksim segmentu, kas to satur.
Iteratīvais process sastāv no sākotnējās aproksimācijas secīgas precizēšanas X 0 . Katrs šāds solis tiek saukts iterācija. Iterāciju rezultātā tiek atrasta aptuveno sakņu vērtību secība X 1 , X 2 , ..., xn. Ja šīs vērtības ar pieaugošu iterāciju skaitu n pieeja patiesajai saknes vērtībai, tad mēs sakām, ka iteratīvais process saplūst.
Lai atrastu vienādojuma (1) sakni, kas pieder segmentam [ a, b], sadaliet šo segmentu uz pusēm. Ja f= 0, tad x = ir vienādojuma sakne. Ja f nav vienāds ar 0 (kas praksē ir visdrīzāk), tad izvēlamies vienu no pusēm vai kuras galos funkcija f(x) ir pretējas pazīmes. Jauns sašaurināts segments [ A 1 , b 1] atkal sadaliet uz pusēm un veiciet tās pašas darbības.
Puses metodi ir praktiski ērti izmantot, lai aptuveni atrastu dotā vienādojuma sakni, metode ir vienkārša un uzticama, un vienmēr konverģē.
3. piemērs. Lai noskaidrotu vienādojuma sakni, izmantojiet sadalīšanas metodi
f( x) = x 4 + 2 x 3 - x - 1 = 0
guļus uz segmenta [0, 1] .
Pastāvīgi mums ir:
f(0) = -1; f(1) = 1; f(0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;
f(0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;
f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;
f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;
f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;
f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043 utt.
Var pieņemt
x = (0,859 + 0,875) = 0,867
Šajā metodē iterācijas process sastāv no šādām vērtībām, kas tiek pieņemtas kā vienādojuma (1) saknes tuvinājums: X 1 , X 2 , ..., x n akordu krustošanās punkti AB ar x asi (3. attēls). Vispirms mēs uzrakstām akorda vienādojumu AB:
.
Akordu krustpunktam AB ar x asi ( x = x 1 ,y = 0) mēs iegūstam vienādojumu:
Ļaujiet skaidrībai f""(x) > 0 plkst a x b(notiek f""(x) < 0 tiek samazināts līdz mūsējam, ja mēs rakstām vienādojumu formā - f(x) = 0). Tad līkne plkst = f(x) būs izliekta uz leju un tāpēc atrodas zem tā horda AB. Ir divi iespējamie gadījumi: 1) f(A) > 0 (3. attēls, A) un 2) f(b) < 0 (Рисунок 3, b).
3. attēls, a, b.
Pirmajā gadījumā beigas A nekustīgi un secīgi tuvinājumi: x 0 = b;x , kur funkcija f (X) ir zīme, kas ir pretēja tā otrā atvasinājuma zīmei f""(X).
Iteratīvais process turpinās, līdz tas tiek konstatēts
| x i - x i - 1 |< e ,
kur e ir norādītā maksimālā absolūtā kļūda.
4. piemērs. Atrodiet vienādojuma pozitīvo sakni
f( x) = x 3 - 0,2 x 2 - 0,2 X - 1,2 = 0
ar precizitāti e = 0,01.
Pirmkārt, mēs atdalām sakni. Jo
f(1) = -0,6< 0 и f (2) = 5,6 > 0,
tad vajadzīgā sakne x atrodas intervālā . Iegūtais intervāls ir liels, tāpēc mēs to sadalām uz pusēm. Jo
f (1,5) = 1,425 > 0, tad 1< x < 1,5.
Jo f""(x) = 6 x- 0,4 > 0 pie 1< X < 1,5 и f(1.5) > 0, tad mēs izmantojam formulu (5), lai atrisinātu problēmu:
= 1,15;
| x 1-x 0 | = 0,15 > e,
tāpēc turpinām aprēķinus;
f ( X 1) = -0,173;
= 1,190;
|x 2-x 1 | = 0,04 > e,
f (X 2) = -0,036;
= 1,198;
| x 3-x 2 | = 0,008 < e .
Tādējādi mēs varam ņemt x = 1,198 ar precizitāti e = 0,01.
Ņemiet vērā, ka precīza vienādojuma sakne ir x = 1,2.
Ļaujiet f(x) – nepārtraukta funkcija ieslēgta [ a; b], .
Ņūtona metode (tangences metode)
Ļaujiet f(x)
ir divreiz nepārtraukti diferencējama funkcija intervālā [ a;
b],
,
Un 
nemainiet zīmi uz [ a;
b].
Apzīmēsim ar 
segmenta beigas, kur atrodas zīmes 
Un 
sakrīt. Secīgi tuvinājumi precīzai saknei c atrast pēc formulas
Priekš 
.
Tad 
ir precīza (1) vienādojuma sakne.
Skaitļošanas process parasti tiek apturēts, kad 
izrādās mazāka par norādīto precizitāti ε
. Tomēr šis nosacījums nevar stingri garantēt noteiktās precizitātes sasniegšanu. Lai iegūtu pilnīgu pārliecību, varat veikt precizitātes pārbaudi, kā norādīts šīs sadaļas sākumā. Ja precizitāte netiek sasniegta, atkārtojumi ir jāatkārto vēl vairākas reizes.
Sekanta metode
Lai ir kāds sākotnējais tuvinājums 
. Mēs iegūstam vēl vienu punktu, izmantojot formulu 
, Kur h- neliels skaits. Mēs pieņemsim, ka esam pabeiguši vairākas metodes darbības, un šajā brīdī mums ir divi secīgi tuvinājumi 
Un 
līdz precīzai saknei (sākotnējā posmā tas ir 
Un 
). Tad mēs atrodam nākamo tuvinājumu, izmantojot formulu
,
Process apstājas pēc tā paša kritērija kā Ņūtona metodē.
Iterācijas metode
Iterācijas metodē sākotnējais vienādojums (1) tiek pārveidots par līdzvērtīgu vienādojumu 
. Tiek izvēlēta sākotnējā tuvināšana 
. Katru nākamo tuvinājumu iegūst pēc formulas 
,
Process apstājas pēc tā paša kritērija kā Ņūtona metodē. Metode konverģēs, t.i. ierobežojums 
vienāds ar precīzu saknes vērtību, ja nevienlīdzība ir saknes tuvumā 
un sākotnējā tuvināšana ir diezgan tuvu saknei.
Metožu priekšrocības un trūkumi
Bisekcijas metode prasa atdalīt sakni, un funkcija ir jānovērtē daudzas reizes, lai sasniegtu augstu precizitāti. Šajā metodē norādītās precizitātes sasniegšana tiek garantēta.
Ņūtona metodei ir ļoti ātra konverģence (kvadrātiskā konverģence), t.i.
,
Kur c– precīza saknes vērtība; M– dažas nemainīgas atkarībā no funkcijas. Aptuveni runājot, sākot no noteiktas iterācijas, pareizo decimāldaļu skaits katrā iterācijā dubultosies.
Lai garantētu Ņūtona metodes konverģenci, ir jāizpilda diezgan daži nosacījumi. Vispārīgi runājot, jūs varat sākt aprēķinus, izmantojot Ņūtona metodi, nepārbaudot šos nosacījumus, bet tad konverģence var netikt novērota.
Sekanta metode nodrošina gludām funkcijām konverģences ātrumu, kas ir tuvu Ņūtona metodes konverģences ātrumam. Tam nav jāaprēķina funkcijas atvasinājums. Ja sākumpunkts tiek ņemts tālu no saknes, tad konverģences var nebūt.
Iterācijas metode nodrošina konverģences ātrumu, kas ir ievērojami zemāks nekā Ņūtona metode. Ja ir konverģence, piemēro aplēsi 
, Kur 
- skaitļi, 
,
;c– precīza saknes vērtība. Daudzumi M,
q ir atkarīgi no funkcijas un nav atkarīgi no iterācijas numura. Ja 
ir tuvu 1, tad q arī ir tuvu 1, un metodes konverģence būs lēna. Aprēķinu, izmantojot iterācijas metodi, var sākt, nepārbaudot nosacījumus 
Un 
. Šajā gadījumā process var kļūt atšķirīgs, un tad atbilde netiks saņemta.
Ir daudzas metodes, lai atrastu nelineāra vienādojuma saknes, izņemot uzskaitītās. Programmā MATHCAD saknes funkcija ir formātā 
izmanto sekanta metodi, un, ja tā nedod vēlamos rezultātus, tad Mullera metodi. Pēdējā, atšķirībā no secant metodes, katrā solī tiek ņemti divi papildu punkti, funkcijas grafiks tiek aizstāts ar parabolu, kas iet cauri trim punktiem, un parabolas krustošanās punkts ar asi tiek uzskatīts par nākamais tuvinājums Vērsis. Saknes funkcijā formātā root( f(x),
x,
a,
b) Tiek izmantotas Ridera un Brenta metodes. Lai atrastu polinoma saknes programmā MATHCAD, tiek izmantota Lagera metode.
Dihotomijas metode nosaukums ir no sengrieķu vārda, kas tulkojumā nozīmē sadalīšana divās daļās. Tāpēc šai metodei ir arī otrs nosaukums: sadalīšanas uz pusēm metode. Mēs to lietojam diezgan bieži. Pieņemsim, spēlējot spēli "Uzmini skaitli", kur viens spēlētājs uzmin skaitli no 1 līdz 100, bet otrs mēģina to uzminēt, vadoties pēc norādēm "vairāk nekā" vai "mazāk nekā". Ir loģiski pieņemt, ka pirmais skaitlis tiks saukts par 50, bet otrs, ja tas ir mazāks, - 25, ja tas ir vairāk - 75. Tādējādi katrā posmā (iterācijā) nezināmā nenoteiktība tiek samazināta 2 reizes. Tie. pat visneveiksmīgākais cilvēks pasaulē uzminēs slēpto skaitli šajā diapazonā ar 7 minējumiem, nevis 100 nejaušiem apgalvojumiem.
Pusdalīšanas metode vienādojuma risināšanā
Pareizs vienādojuma atrisinājums, izmantojot pusīšu metodi, ir iespējams tikai tad, ja ir zināms, ka noteiktā intervālā ir sakne un tā ir unikāla. Tas nebūt nenozīmē, ka dihotomijas metodi var izmantot tikai lineāru vienādojumu risināšanai. Lai atrastu augstākas kārtas vienādojumu saknes, izmantojot sadalīšanas metodi, vispirms saknes ir jāsadala segmentos. Sakņu atdalīšanas process tiek veikts, atrodot funkcijas pirmo un otro atvasinājumu un pielīdzinot tos nullei f"(x)=0 un f""(x)=0. Tālāk f(x) zīmes kritiskajos un robežpunktos nosaka Intervāls, kurā funkcija maina zīmi |a,b|, kur f(a)*f(b)< 0.
Dihotomijas metodes algoritms
Dihotomijas metodes algoritms ir ļoti vienkāršs. Apsveriet segmentu |a,b| kurā ir viena sakne x 1
Pirmajā posmā aprēķina x 0 =(a+b)/2
Tālāk tiek noteikta funkcijas vērtība šajā punktā: ja f(x 0)< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.
Aprēķini tiek pārtraukti, kad starpība b-a ir mazāka par nepieciešamo kļūdu.
Kā piemēru dalīšanas uz pusi metodes izmantošanai mēs atradīsim sakni vienādojuma intervālā x 3 -3*x+1=0 ar precizitāti 10 -3
Kā redzams no tabulas, sakne ir 0,347. Iterāciju skaits ir 10. Pabeigšanas nosacījums: a-b=0,0009< 10 -3
Puses metode vai dihotomijas metode ir vienkāršākais vienādojuma atrisināšanai, izmantojot skaitliskās metodes.
Lejupielādēt:
Vienādojuma atrisināšana, izmantojot dihotomijas metodi - Vienādojuma atrisināšana, izmantojot sadalīšanas metodi Paskālā.
To sauc arī par dihotomijas metodi. Šī vienādojumu risināšanas metode atšķiras no iepriekš apskatītajām metodēm ar to, ka tai nav jāizpilda nosacījums, ka pirmais un otrais atvasinājums saglabā savu zīmi intervālā. Bisekcijas metode konverģē jebkurām nepārtrauktām funkcijām f(x), tostarp nediferencējamām.
Sadaliet segmentu uz pusēm ar punktu. Ja (kas ir praktiski visticamākais), tad iespējami divi gadījumi: vai nu f(x) maina zīmi uz nogriežņa (3.8. att.), vai uz segmenta (3.9. att.)
Katrā gadījumā izvēloties segmentu, uz kura funkcija maina zīmi, un turpinot vēl vairāk samazināt uz pusi, var sasniegt patvaļīgi mazu segmentu, kurā ir vienādojuma sakne.
4. piemērs. Vienādojumam 5x - 6x -3 = 0 intervālā ir viena sakne. Atrisiniet šo vienādojumu, izmantojot pusi dalīšanas metodi.
Risinājums: Pascal programma varētu izskatīties šādi:
funkcija f(x: reāls): reāls;
f:=exp(x*ln(5))-6*x-3;
a, b, e, c, x: reāls;
kamēr abs(b-a)>e darīt
ja f(a)*f(c)<0 then
writeln("x=",x:3:3," f(x)=",f(x):4:4);
Programmas izpildes rezultāts:
e=0,001 x=1,562 f(x)=-0,0047
20. Uz pusēm dalīšanas metodes algoritms.
1.Nosakiet jaunu saknes tuvinājumu X segmenta vidū [a,b]: x=(a+b)/2.
2. Atrodiet funkcijas vērtības punktos A Un X: F(a) Un F(x).
3.Pārbaudiet stāvokli F(a)*F(x)< 0 . Ja nosacījums ir izpildīts, tad sakne atrodas segmentā [Ak] b pāriet uz punktu x (b=x). Ja nosacījums nav izpildīts, tad sakne atrodas segmentā [x,b]. Šajā gadījumā jums ir nepieciešams punkts A pāriet uz punktu x (a=x).
4. Pārejiet uz 1. darbību un vēlreiz sadaliet segmentu uz pusēm. Algoritms turpinās, līdz tiek izpildīts nosacījums /F(x)/< e (norādīta precizitāte).
21. Vienkārša iterācijas metode sakņu atrašanai. Ģeometriskā interpretācija.
Sākotnējais vienādojums f(x)=0 tiek reducēts ar līdzvērtīgām transformācijām formā, kuras kreisajā pusē ir atlasīts nezināmais, tas ir, x=φ(x), kur φ(x) ir kāda funkcija, kas saistīta ar sākotnējo funkciju f (x). Šī vienādojuma rakstīšanas forma ļauj, ņemot vērā sākotnējo tuvinājumu x 0, iegūt nākamo, pirmo tuvinājumu x 1 =φ(x 0), pēc tam iegūt otro tuvinājumu x 2 =φ(x 1) un tā tālāk x n +1 =φ(x n)… . Secību (x n )= x 0, x 1, x 2, …, x n,… sauc par iterāciju vai aproksimāciju secību ar sākotnējo vērtību x 0. Ja funkcija φ(x) nav nepārtraukta un tai ir robeža. ξ = lim x n kā n→∞, tad, pārejot uz robežu vienādībā x n +1 =φ(x n), mēs secinām, ka kā n→ ∞: lim x n +1 =lim φ(x n)=φ(lim x n ), tas ir, ξ=φ(ξ) Līdz ar to, ja tuvinājumu secība saplūst, tad tā saplūst vienādojuma (2) saknei un līdz ar to (1) vienādojumam. Iteratīvā procesa konverģences dēļ šo sakni var aprēķināt pietiekami lielai n ar jebkuru norādīto precizitāti. Tomēr ir jānosaka, kādos apstākļos secība (x n) būs konverģenta. Iegūsim saikni starp divu blakus esošo tuvinājumu kļūdām - ε n un ε n +1: x n =ξ+ε n, x n +1 =ξ+ε n +1. Aizstāsim šos attēlojumus ar x n +1 =φ(x n) un paplašināsim funkciju Teilora sērijā saknes tuvumā:ξ+ε n +1 =φ(ξ+ε n)=φ(ξ)+ε n φ'(ξ)+ (ε n 2 /2!)φ''(η), kur η О [ξ; ξ+ε n ] М Tā kā ξ ir sakne, tad ξ=φ(ξ) , iegūstam: ε n +1 =ε n φ'(ξ)+(φ''(η)/2)ε n 2 Kopš ε<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n|ε n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.
Teorēma par vienkāršās iterācijas metodes konverģenci. Pieņemsim, ka ξ ir vienādojuma x=φ(x) sakne, funkcija φ(x) ir definēta un diferencējama uz intervālu, un x О visas funkcijas φ (x) О vērtības. Tad, ja ir tik pozitīvs skaitlis q<1, что при x Î выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x n +1 =φ(x n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x 0 Î .Таким образом, последовательность {x n },начинающаяся с любого x 0 Î , сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ'(x)>-1, tad blakus tuvinājumi atrodas saknes pretējās pusēs - šādu konverģenci sauc par divvirzienu (vai spirāli) - 2. att. Tā kā šajā gadījumā sakne ir ietverta intervālā, kura galos ir blakus esošie tuvinājumi – ξÎ(x n ,x n +1), tad nosacījuma |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.
Lai varētu salīdzināt iteratīvās metodes konverģences ātruma ziņā, tiek ieviesti šādi jēdzieni:
1. definīcija: Tiek izsaukta secības (x n) konverģence uz ξ lineārs(attiecīgi iteratīvais process ir lineāri konverģenta), ja ir tāda konstante CО(0,1) un skaitlis n 0, ka nevienādības |ξ-x n +1 |≤C|ξ-x n | ja n≥n 0.
Iepriekš ieviestajām kļūdām tas nozīmē |ε n+1 |≤C|ε n |. Vienkāršajā iterācijas metodē konstante C ir vērtība q, tas ir, metode konverģē lineāri.
2. definīcija: Tuvinājumu secība (x n ) tuvojas ξ ar vismaz R secībā (attiecīgi iteratīvajam procesam ir vismaz lpp-th order), ja ir šādas konstantes C>0, lpp≥1 un n 0 , ka visiem n≥n 0 nosacījumi |ξ-x n +1 |≤C|ξ-x n | p (vai citos apzīmējumos |ε n+1 |≤C|ε n | p).
