Bahay Paggamot ng ngipin Paraan ng kalahating dibisyon ng circuit. Dichotomy method o bisection method

Paggamot ng ngipin

Paraan ng kalahating dibisyon ng circuit. Dichotomy method o bisection method

Paraan ng kalahating paghahati(ibang pangalan: paraan ng paghahati-hati, pamamaraan ng dichotomy) upang malutas ang equation f(x) = 0 ay ang mga sumusunod. Ipaalam ito na ang function ay tuloy-tuloy at tumatagal sa mga dulo ng segment
[a, b] mga halaga ng iba't ibang mga palatandaan, kung gayon ang ugat ay nakapaloob sa pagitan ( a, b). Hatiin natin ang pagitan sa dalawang halves at pagkatapos ay isasaalang-alang natin ang kalahati sa mga dulo kung saan ang function ay tumatagal ng mga halaga ng iba't ibang mga palatandaan. Muli naming hinati ang bagong segment na ito sa dalawang pantay na bahagi at piliin ang isa na naglalaman ng ugat. Magpapatuloy ang prosesong ito hanggang sa ang haba ng susunod na segment ay maging mas mababa sa kinakailangang halaga ng error. Isang mas mahigpit na presentasyon ng algorithm para sa paraan ng paghahati-hati:

1) Magkalkula tayo x = (a+ b)/2; kalkulahin natin f(x);

2) Kung f(x) = 0, pagkatapos ay pumunta sa hakbang 5;

3) Kung f(x)∙f(a) < 0, то b = x, kung hindi a = x;

4) Kung | b – a| > ε, pumunta sa punto 1;

5) I-output ang halaga x;

Halimbawa 2.4. Gamit ang paraan ng paghahati-hati, pinuhin ang ugat ng equation ( x– 1) 3 = 0, kabilang sa segment .

Solusyon sa programa Excel:

1) Sa mga cell A 1:F 4 ipinakilala namin ang notasyon, mga paunang halaga at mga formula, tulad ng ipinapakita sa Talahanayan 2.3.

2) Kopyahin ang bawat formula sa mas mababang mga cell na may fill marker hanggang sa ikasampung linya, i.e. B 4 - hanggang sa B 10, C 4 - hanggang sa C 10, D 3 - hanggang sa D 10, E 4 - hanggang sa E 10, F 3 - hanggang sa F 10.

Talahanayan 2.3

A	B	C	D	E	F
	f(a)=	=(1-B3)^3
k	a	x	f(x)	b	b-a
	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)

Ang mga resulta ng pagkalkula ay ibinibigay sa talahanayan. 2.4. Sa column F pagsuri sa mga halaga ng haba ng pagitan b – a. Kung ang halaga ay mas mababa sa 0.01, ang tinatayang halaga ng ugat na may tinukoy na error ay makikita sa linyang ito. Kinailangan ng 5 pag-ulit upang makamit ang kinakailangang katumpakan. Ang tinatayang halaga ng ugat na may katumpakan na 0.01 pagkatapos i-round sa tatlong decimal na lugar ay 1.0015625 ≈ 1.00.

Talahanayan 2.4

A	B	C	D	E	F
	f(a)=	0,000125
k	a	x	f(x)	b	b-a
	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

Ang ibinigay na algorithm ay isinasaalang-alang posibleng kaso"pagtama sa ugat", i.e. pagkakapantay-pantay f(x) zero sa susunod na yugto. Kung sa halimbawa 2.3 kinukuha namin ang segment , pagkatapos ay sa pinakaunang hakbang makarating kami sa ugat x= 1. Sa katunayan, sumulat tayo sa cell B 3 halaga 0.9. Pagkatapos ang talahanayan ng mga resulta ay kukuha ng form 2.5 (2 iterations lang ang ibinibigay).

Talahanayan 2.5

A	B	C	D	E	F
	f(a)=	0,001
k	a	x	f(x)	b	b-a
	0,9			1,1	0,2

Gawin natin ito sa programa Excel mga custom na function f(x) at bisect(a, b, eps) para sa paglutas ng mga equation gamit ang bisect method gamit ang built-in na wika Visual Basic. Ang kanilang mga paglalarawan ay ibinigay sa ibaba:

Function f(Byval x)

Function bisect(a, b, eps)

1 x = (a + b) / 2

Kung f(x) = 0 Pagkatapos GoTo 5

Kung f(x) * f(a)< 0 Then

Kung Abs(a - b) > eps Pagkatapos GoTo 1

Tinutukoy ng function na f(x). kaliwang bahagi equation, at ang function
kinakalkula ng bisect(a, b, eps) ang ugat ng equation gamit ang bisect method f(x) = 0. Tandaan na ang function bisect(a, b, eps) ay gumagamit ng access sa function na f(x). Narito ang algorithm para sa paglikha ng isang pasadyang function:

1) Ipatupad ang menu command na “Tools - Macro - Editor Visual Basic" Ang bintana " Microsoft Visual Basic" Kung nasa ang file na ito mga programa Excel macros o user function o procedures ay hindi pa nagagawa, ang window na ito ay magiging katulad ng ipinapakita sa Fig. 2.4.

2) Ipatupad ang menu command na "Insert - Module" at ipasok ang mga teksto ng mga function ng programa, tulad ng ipinapakita sa Fig. 2.5.

Ngayon sa mga cell ng sheet ng programa Excel Maaari mong gamitin ang mga nilikhang function sa mga formula. Halimbawa, pumasok tayo sa isang cell D 18 pormula

Bisect(0.95;1;0.00001),

pagkatapos makuha namin ang halaga 0.999993896.

Upang malutas ang isa pang equation (na may ibang kaliwang bahagi) kailangan mong pumunta sa window ng editor gamit ang command na "Tools - Macro - Editor Visual Basic” at muling isulat ang paglalarawan ng function na f(x). Halimbawa, hanapin natin, na may katumpakan na 0.001, ang ugat ng equation na sin5 x + x 2 – 1 = 0, kabilang sa pagitan (0.4; 0.5). Upang gawin ito, baguhin natin ang paglalarawan ng function

para sa bagong paglalarawan

f = Kasalanan(5 * x) + x^2 - 1

Tapos sa selda D 18 makuha natin ang halaga na 0.441009521 (ihambing ang resultang ito sa halaga ng ugat ng pagitan (0.4; 0.5) na makikita sa halimbawa 2.3!).

Upang malutas ang isang equation gamit ang half division method sa programa Mathcad gumawa tayo ng subroutine function bisec(f, a, b, ε), kung saan:

f- pangalan ng function na naaayon sa kaliwang bahagi ng equation f(x) = 0;

a, b- kaliwa at kanang dulo ng segment [ a, b];

ε - katumpakan ng tinatayang halaga ng ugat.

Solusyon ng halimbawa sa programa Mathcad:

1) Ilunsad ang programa Mathcad. Ipakilala natin ang kahulugan ng function bisec(f, a, b, ε). Upang gawin ito, gamit ang keyboard at ang toolbar na "Mga Simbolo ng Griyego", i-type bisec(f, a, b, ε):=. Pagkatapos ng tanda ng pagtatalaga na ":=" sa toolbar ng "Programming", gamitin ang pointer ng mouse upang i-left-click ang "Magdagdag ng linya". Lilitaw ang isang patayong linya pagkatapos ng tanda ng pagtatalaga. Susunod, ipasok ang teksto ng programa na ipinapakita sa ibaba, gamit ang "Programming" toolbar upang ipasok ang "←" sign, ang loop operator habang, operator pahinga at conditional operator kung hindi man.

2) Ipakilala natin ang kahulugan ng function f(x):=sin(5*x)+x^2–1, at pagkatapos ay kalkulahin ang halaga ng ugat gamit ang function bisec sa ibinigay na mga halaga:
bisec(f, –0.8,–0.7,0.0001)=. Pagkatapos ng “=” sign, awtomatikong lalabas ang root value na kinakalkula ng program –0.7266601563. Kalkulahin natin ang natitirang mga ugat sa parehong paraan.

Nasa ibaba ang sheet Mathcad na may kahulugan ng function bisec(f, a, b, ε) at mga kalkulasyon:

Magbigay tayo ng programa sa wika C++ upang malutas ang equation f(x) = 0 sa pamamagitan ng paraan ng paghahati:

#isama

dobleng f(dobleng x);

typedef double (*PF)(doble);

double bisec(PF f,double a,double b,double eps);

dobleng 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;

dobleng f(doble x)(

r = sin(5*x)+x*x-1;

double bisec(PF f, double a, double b,double eps)(

gawin( x = (a + b)/2;

kung (f(x) == 0) break;

kung (f(x)*f(a)<0) b = x;

)samantalang (fabs(b-a) > eps);

Ang programa ay may isang function f(x) ay tinukoy upang malutas ang equation

kasalanan5 x + x 2 – 1 = 0

mula sa halimbawa 2.3. Ang resulta ng programa para sa pagtukoy ng ugat ng pagitan (0.4; 0.5) na may katumpakan na 0.00001 ay ipinakita sa ibaba (screen ng computer):

Pindutin ang anumang key at Enter

Ang huling linya ay kailangan upang ayusin ang isang pause upang tingnan ang resulta.

Ang mga nonlinear na equation ay maaaring hatiin sa 2 klase - algebraic at transendental. Algebraic equation ay tinatawag na mga equation na naglalaman lamang ng mga algebraic function (integer, rational, irrational). Sa partikular, ang polynomial ay isang buong algebraic function. Ang mga equation na naglalaman ng iba pang mga function (trigonometric, exponential, logarithmic, atbp.) ay tinatawag na transendental.

Ang mga pamamaraan para sa paglutas ng mga nonlinear na equation ay nahahati sa dalawang grupo:

tumpak na pamamaraan

umuulit na pamamaraan

Ginagawang posible ng mga eksaktong pamamaraan na isulat ang mga ugat sa anyo ng ilang may hangganang kaugnayan (pormula). Mula sa kursong algebra ng paaralan, ang mga ganitong pamamaraan ay kilala para sa paglutas ng trigonometric, logarithmic, exponential, pati na rin ang mga simpleng algebraic equation.

Tulad ng nalalaman, maraming mga equation at sistema ng mga equation ay walang mga analytical na solusyon. Pangunahing naaangkop ito sa karamihan ng mga transendental na equation. Napatunayan din na imposibleng makabuo ng isang pormula na maaaring magamit upang malutas ang isang di-makatwirang algebraic equation na mas mataas sa apat. Bilang karagdagan, sa ilang mga kaso ang equation ay naglalaman ng mga coefficient na kilala lamang ng humigit-kumulang, at, samakatuwid, ang mismong gawain ng tumpak na pagtukoy sa mga ugat ng equation ay nawawala ang kahulugan nito. Upang malutas ang mga ito ginagamit namin umuulit na pamamaraan na may ibinigay na antas ng katumpakan.

Hayaang ibigay ang equation

Function f(x) ay tuloy-tuloy sa pagitan [ a, b] kasama ang 1st at 2nd order derivatives nito.
Mga halaga f(x) sa mga dulo ng segment ay may iba't ibang mga palatandaan ( f(a) * f(b) < 0).
Una at pangalawang derivatives f"(x) At f""(x) panatilihin ang isang tiyak na tanda sa buong segment.

Ang mga kundisyon 1) at 2) ay ginagarantiyahan na sa pagitan [ a, b] mayroong kahit isang ugat, at mula sa 3) sinusundan nito iyon f(x) ay monotoniko sa pagitan na ito at samakatuwid ang ugat ay magiging kakaiba.

Lutasin ang equation (1) umuulit na pamamaraan nangangahulugang upang maitaguyod kung mayroon itong mga ugat, gaano karaming mga ugat, at hanapin ang mga halaga ng mga ugat na may kinakailangang katumpakan.

Anumang halaga na nagbabalik sa isang function f(x) sa zero, i.e. tulad na:

tinawag ugat mga equation(1) o sero mga function f(x).

Ang problema sa paghahanap ng ugat ng isang equation f(x) = 0 sa pamamagitan ng umuulit na pamamaraan ay binubuo ng dalawang yugto:

paghihiwalay ng ugat

pagpipino ng tinatayang mga ugat

Ang proseso ng paghihiwalay ng ugat ay nagsisimula sa pagtatatag ng mga palatandaan ng pag-andar f(x) sa hangganan x=a At x=b mga punto sa rehiyon ng pagkakaroon nito.

Halimbawa 1 . Paghiwalayin ang mga ugat ng equation:

f( x) є x 3 - 6x + 2 = 0.

Gumawa tayo ng tinatayang diagram:

Dahil dito, ang equation (2) ay may tatlong tunay na ugat na nasa pagitan ng [-3, -1], at .

Tinatayang halaga ng mga ugat ( paunang pagtatantya) ay maaari ding malaman mula sa pisikal na kahulugan ng problema, mula sa paglutas ng katulad na problema na may iba't ibang paunang data, o maaaring matagpuan sa grapiko.

Karaniwan sa pagsasanay sa engineering graphic na pamamaraan pagpapasiya ng tinatayang mga ugat.

Isinasaalang-alang na ang mga tunay na ugat ng equation (1) ay ang mga intersection point ng graph ng function. f(x) gamit ang x-axis, sapat na upang i-plot ang function f(x) at markahan ang mga intersection point f(x) may ehe oh o markahan sa axis Oh mga segment na naglalaman ng isang ugat. Ang pagbuo ng mga graph ay kadalasang maaaring lubos na pinasimple sa pamamagitan ng pagpapalit ng equation (1) katumbas sa kanya gamit ang equation:

Ang equation (4) ay maaaring maginhawang muling isulat bilang isang pagkakapantay-pantay:

Malinaw mula rito na ang mga ugat ng equation (4) ay matatagpuan bilang abscissas ng mga intersection point ng logarithmic curve y= log x at hyperboles y = . Matapos mabuo ang mga kurba na ito, tinatayang mahahanap natin ang tanging ugat ng equation (4) o matukoy ang segment na naglalaman nito.

Ang umuulit na proseso ay binubuo ng sequential refinement ng paunang approximation X 0 . Ang bawat hakbang na ito ay tinatawag pag-ulit. Bilang resulta ng mga pag-ulit, natagpuan ang isang pagkakasunud-sunod ng tinatayang mga halaga ng ugat X 1 , X 2 , ..., xn. Kung ang mga halagang ito ay may pagtaas ng bilang ng mga pag-ulit n lapitan ang tunay na halaga ng ugat, pagkatapos ay sinasabi namin na ang umuulit na proseso nagtatagpo.

Upang mahanap ang ugat ng equation (1) na kabilang sa segment [ a, b], hatiin ang segment na ito sa kalahati. Kung f= 0, pagkatapos x = ay ang ugat ng equation. Kung f ay hindi katumbas ng 0 (na, sa pagsasagawa, ay malamang), pagkatapos ay pipiliin namin ang isa sa mga halves o sa mga dulo kung saan ang function f(x) may kabaligtaran na mga palatandaan. Bagong narrowed segment [ A 1 , b 1] muling hatiin sa kalahati at gawin ang parehong mga aksyon.

Ang pamamaraan ng mga halves ay praktikal na maginhawang gamitin para sa halos paghahanap ng ugat ng isang ibinigay na equation ang pamamaraan ay simple at maaasahan, at palaging nagtatagpo.

Halimbawa 3. Gamitin ang paraan ng paghahati upang linawin ang ugat ng equation

f( x) = x 4 + 2 x 3 - x - 1 = 0

nakahiga sa segment [0, 1] .

Patuloy na mayroon kaming:

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, atbp.

Maaaring tanggapin

x = (0.859 + 0.875) = 0.867

Sa pamamaraang ito, ang proseso ng pag-ulit ay binubuo sa mga sumusunod na halaga na kinukuha bilang mga pagtatantya sa ugat ng equation (1): X 1 , X 2 , ..., x n chord intersection point AB gamit ang x-axis (Larawan 3). Una naming isulat ang equation ng chord AB:

Para sa chord intersection point AB may x-axis ( x = x 1 ,y = 0) nakuha namin ang equation:

Hayaan para sa katiyakan f""(x) > 0 sa a x b(nangyayari f""(x) < Ang 0 ay bumababa sa atin kung isusulat natin ang equation sa anyo - f(x) = 0). Tapos yung curve sa = f(x) ay matambok pababa at, samakatuwid, matatagpuan sa ibaba ng chord nito AB. Mayroong dalawang posibleng kaso: 1) f(A) > 0 (Larawan 3, A) at 2) f(b) < 0 (Рисунок 3, b).

Larawan 3, a, b.

Sa unang kaso ang katapusan A hindi gumagalaw at sunud-sunod na pagtatantya: x 0 = b;x , kung saan ang function f (X) ay may tandang kabaligtaran ng tanda ng pangalawang derivative nito f""(X).

Nagpapatuloy ang umuulit na proseso hanggang sa matagpuan iyon

| x i - x i - 1 |< e ,

kung saan ang e ay ang tinukoy na maximum absolute error.

Halimbawa 4. Hanapin ang positibong ugat ng equation

f( x) = x 3 - 0,2 x 2 - 0,2 X - 1,2 = 0

na may katumpakan ng e = 0.01.

Una sa lahat, pinaghihiwalay namin ang ugat. kasi

f(1) = -0.6< 0 и f (2) = 5,6 > 0,

pagkatapos ang kinakailangang ugat x ay nasa pagitan. Ang resultang pagitan ay malaki, kaya hinahati namin ito sa kalahati. kasi

f (1.5) = 1.425 > 0, pagkatapos ay 1< x < 1,5.

kasi f""(x) = 6 x- 0.4 > 0 sa 1< X < 1,5 и f(1.5) > 0, pagkatapos ay ginagamit namin ang formula (5) upang malutas ang problema:

= 1,15;

| x 1-x 0 | = 0.15 > e,

samakatuwid, ipinagpatuloy namin ang mga kalkulasyon;

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 .

Kaya, maaari nating kunin ang x = 1.198 na may katumpakan ng e = 0.01.

Tandaan na ang eksaktong ugat ng equation ay x = 1.2.

Hayaan f(x) – patuloy na paggana sa [ a; b], .

Paraan ni Newton (paraan ng tangent)

Hayaan f(x) ay isang dalawang beses na patuloy na naiba-iba na function sa pagitan [ a; b],
,
At
huwag baguhin ang sign sa [ a; b].

Ipahiwatig natin sa pamamagitan ng na dulo ng segment kung saan ang mga palatandaan
At
magkatugma. Mga sunud-sunod na pagtatantya sa eksaktong ugat c hanapin sa pamamagitan ng formula

Para sa
.

Pagkatapos
ay ang eksaktong ugat ng equation (1).

Ang proseso ng pag-compute ay karaniwang hihinto kapag
lumalabas na mas mababa kaysa sa tinukoy na katumpakan ε . Gayunpaman, ang kundisyong ito ay hindi mahigpit na magagarantiya na ang tinukoy na katumpakan ay nakakamit. Para sa kumpletong katiyakan, maaari kang magsagawa ng pagsusuri sa katumpakan gaya ng nakasaad sa simula ng seksyong ito. Kung ang katumpakan ay hindi nakamit, pagkatapos ay kailangan mong ulitin ang mga pag-ulit nang maraming beses.

Secant na pamamaraan

Hayaang magkaroon ng ilang paunang pagtatantya . Makakakuha kami ng isa pang punto gamit ang formula
, Saan h- isang maliit na bilang. Ipagpalagay namin na nakumpleto namin ang ilang mga hakbang ng pamamaraan, at sa puntong ito mayroon kaming dalawang sunud-sunod na pagtatantya At
sa eksaktong ugat (sa paunang yugto ito ay At ). Pagkatapos ay makikita natin ang susunod na pagtatantya gamit ang formula

Ang proseso ay humihinto ayon sa parehong pamantayan tulad ng sa pamamaraan ni Newton.

Paraan ng pag-ulit

Sa pamamaraan ng pag-ulit, ang orihinal na equation (1) ay binago sa katumbas na equation
. Ang paunang pagtatantya ay pinili . Ang bawat kasunod na approximation ay nakuha ng formula
,
Ang proseso ay humihinto ayon sa parehong pamantayan tulad ng sa pamamaraan ni Newton. Magtatagpo ang pamamaraan, i.e. limitasyon katumbas ng eksaktong halaga ng ugat kung ang hindi pagkakapantay-pantay ay nananatili sa kapitbahayan ng ugat
at ang paunang approximation ay medyo malapit sa ugat.

Mga kalamangan at kahinaan ng mga pamamaraan

Ang paraan ng bisection ay nangangailangan ng ugat na paghiwalayin, at ang function ay dapat na masuri ng maraming beses upang makamit ang mataas na katumpakan. Ang pagkamit ng tinukoy na katumpakan sa paraang ito ay ginagarantiyahan.

Ang pamamaraan ni Newton ay may napakabilis na convergence (quadratic convergence), i.e.

saan c– eksaktong halaga ng ugat; M– ilang pare-pareho depende sa function. Sa halos pagsasalita, simula sa isang tiyak na pag-ulit, ang bilang ng mga tamang decimal na lugar ay magdodoble sa bawat pag-ulit.

Upang matiyak ang convergence ng pamamaraan ni Newton, medyo ilang mga kondisyon ang dapat matugunan. Sa pangkalahatan, maaari kang magsimula ng mga kalkulasyon gamit ang pamamaraan ni Newton nang hindi sinusuri ang mga kundisyong ito, ngunit pagkatapos ay maaaring hindi maobserbahan ang convergence.

Ang secant method ay nagbibigay para sa makinis na mga function ng convergence rate na malapit sa convergence rate ng Newton's method. Hindi ito nangangailangan ng pagkalkula ng derivative ng isang function. Kung ang panimulang punto ay kinuha malayo mula sa ugat, pagkatapos ay maaaring walang convergence.

Ang pamamaraan ng pag-ulit ay nagbibigay ng isang rate ng convergence na makabuluhang mas mababa kaysa sa pamamaraan ni Newton. Kung mayroong convergence, nalalapat ang pagtatantya
, Saan
- numero,
,
;c– eksaktong halaga ng ugat. Dami M, q depende sa function at hindi nakadepende sa iteration number. Kung
ay malapit sa 1, kung gayon q ay malapit din sa 1 at magiging mabagal ang convergence ng method. Ang pagkalkula gamit ang paraan ng pag-ulit ay maaaring simulan nang hindi sinusuri ang mga kondisyon
At . Sa kasong ito, ang proseso ay maaaring maging divergent, at pagkatapos ay hindi matatanggap ang sagot.

Mayroong maraming mga pamamaraan para sa paghahanap ng mga ugat ng isang nonlinear equation maliban sa mga nakalista. Sa MATHCAD, ang root function ay nasa format
gumagamit ng secant method, at kung hindi ito humahantong sa ninanais na resulta, pagkatapos ay ang Muller method. Sa huli, sa kaibahan sa paraan ng secant, sa bawat hakbang ay kukuha ng dalawang karagdagang puntos, ang graph ng function ay pinapalitan ng isang parabola na dumadaan sa tatlong puntos, at ang punto ng intersection ng parabola na may axis ay kinuha bilang ang susunod na pagtatantya baka. Sa root function sa format na root( f(x), x, a, b) Ginagamit ang mga pamamaraan ng Ridder at Brent. Upang mahanap ang mga ugat ng isang polynomial sa MATHCAD, ginagamit ang pamamaraang Laguerre.

Paraan ng dichotomy ay may pangalan nito mula sa sinaunang salitang Griyego, na isinalin ay nangangahulugang paghahati sa dalawa. Iyon ang dahilan kung bakit ang pamamaraang ito ay mayroon ding pangalawang pangalan: ang paraan ng halves. Madalas namin itong ginagamit. Sabihin nating naglalaro ng larong "Hulaan ang Numero", kung saan hinuhulaan ng isang manlalaro ang isang numero mula 1 hanggang 100, at sinusubukan ng isa pang hulaan ito, na ginagabayan ng mga pahiwatig na "higit pa sa" o "mas mababa sa". Ito ay lohikal na ipagpalagay na ang unang numero ay tatawagin na 50, at ang pangalawa kung ito ay mas mababa - 25, kung ito ay higit pa - 75. Kaya, sa bawat yugto (pag-ulit) ang kawalan ng katiyakan ng hindi alam ay nabawasan ng 2 beses. Yung. kahit na ang pinakamalas na tao sa mundo ay huhulaan ang nakatagong numero sa hanay na ito sa 7 hula sa halip na 100 random na mga pahayag.

Ang paraan ng kalahating paghahati sa paglutas ng equation

Ang tamang solusyon ng isang equation gamit ang paraan ng halves ay posible lamang kung alam na mayroong ugat sa isang naibigay na pagitan at ito ay natatangi. Hindi ito nangangahulugan na ang pamamaraan ng dichotomy ay magagamit lamang upang malutas ang mga linear na equation. Upang mahanap ang mga ugat ng mas mataas na pagkakasunud-sunod na mga equation gamit ang paraan ng paghahati-hati, kailangan mo munang paghiwalayin ang mga ugat sa mga segment. Ang proseso ng paghihiwalay ng mga ugat ay isinasagawa sa pamamagitan ng paghahanap ng una at pangalawang derivatives ng function at equating ang mga ito sa zero f"(x)=0 at f""(x)=0. Susunod, ang mga palatandaan ng f(x) sa kritikal at hangganan na mga punto ay tinutukoy Ang pagitan kung saan ang function ay nagbabago sign |a,b|, kung saan f(a)*f(b)< 0.

Algorithm ng pamamaraan ng dichotomy

Ang algorithm ng pamamaraan ng dichotomy ay napaka-simple. Isaalang-alang ang segment |a,b| kung saan mayroong isang ugat x 1

Sa unang yugto, kinakalkula ang x 0 =(a+b)/2

Susunod, ang halaga ng function sa puntong ito ay tinutukoy: kung f(x 0)< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.

Hihinto ang mga pagkalkula kapag ang pagkakaiba b-a ay mas mababa sa kinakailangang error.

Bilang halimbawa ng paggamit ng half division method, makikita natin ang ugat sa pagitan ng equation x 3 -3*x+1=0 na may katumpakan na 10 -3

Tulad ng makikita mula sa talahanayan, ang ugat ay 0.347. Ang bilang ng mga pag-ulit ay 10. Kondisyon ng pagkumpleto: a-b=0.0009< 10 -3

Paraan ng halves o dichotomy method ay ang pinakasimpleng para sa paglutas ng equation gamit ang mga numerical na pamamaraan.

I-download:

Paglutas ng equation gamit ang dichotomy method - Paglutas ng equation gamit ang bisection method sa Pascal.

Tinatawag din itong dichotomy method. Ang pamamaraang ito ng paglutas ng mga equation ay naiiba sa mga pamamaraan na tinalakay sa itaas dahil hindi ito nangangailangan ng katuparan ng kondisyon na ang una at pangalawang derivative ay nagpapanatili ng kanilang tanda sa pagitan. Ang paraan ng paghahati-hati ay nagtatagpo para sa anumang tuluy-tuloy na function f(x), kabilang ang mga hindi nakikilala.

Hatiin ang segment sa kalahati na may isang punto. Kung (na kung saan ay halos ang pinaka-malamang), kung gayon ang dalawang kaso ay posible: alinman sa f(x) ay nagbabago ng sign sa segment (Fig. 3.8), o sa segment (Fig. 3.9)

Sa pamamagitan ng pagpili sa bawat kaso ng segment kung saan nagbabago ang pag-sign ng function, at pagpapatuloy sa proseso ng paghahati pa, maaaring maabot ng isa ang isang maliit na segment na naglalaman ng ugat ng equation.

Halimbawa 4. Ang equation na 5x - 6x -3 = 0 ay may iisang ugat sa pagitan. Lutasin ang equation na ito gamit ang half division method.

Solusyon: Maaaring ganito ang hitsura ng isang Pascal program:

function f(x: real): tunay;

f:=exp(x*ln(5))-6*x-3;

a, b, e, c, x: tunay;

habang ginagawa ng abs(b-a)>e

kung f(a)*f(c)<0 then

writeln("x=",x:3:3," f(x)=",f(x):4:4);

Resulta ng pagpapatupad ng programa:

e=0.001 x=1.562 f(x)=-0.0047

20.Algorithm ng paraan ng paghahati ng halves.

1.Tumuko ng bagong pagtatantya ng ugat X sa gitna ng segment [a,b]: x=(a+b)/2.

2. Hanapin ang mga halaga ng function sa mga punto A At X: F(a) At F(x).

3. Suriin ang kondisyon F(a)*F(x)< 0 . Kung ang kondisyon ay natutugunan, kung gayon ang ugat ay matatagpuan sa segment [Oh] b lumipat sa punto x (b=x). Kung ang kondisyon ay hindi natutugunan, kung gayon ang ugat ay matatagpuan sa segment [x,b]. Sa kasong ito, kailangan mo ng isang punto A lumipat sa punto x (a=x).

4. Pumunta sa hakbang 1 at muling hatiin ang segment sa kalahati. Nagpapatuloy ang algorithm hanggang sa matugunan ang kundisyon /F(x)/< e (tinukoy na katumpakan).

21. Simpleng paraan ng pag-ulit para sa paghahanap ng mga ugat. Geometric na interpretasyon.

Ang orihinal na equation na f(x)=0 ay nababawasan ng mga katumbas na pagbabago sa anyo na may hindi alam sa kaliwang bahagi na napili, iyon ay, x=φ(x), kung saan ang φ(x) ay ilang function na nauugnay sa orihinal na function na f (x). Ang paraan ng pagsulat ng equation na ito ay nagbibigay-daan, dahil sa paunang pagtataya x 0, na makuha ang susunod, unang pagtataya x 1 =φ(x 0), pagkatapos ay makuha ang pangalawang pagtatantya x 2 =φ(x 1) at iba pa x n +1 =φ(x n)… . Ang sequence (x n )= x 0, x 1, x 2, …, x n,… ay tinatawag na sequence of iterations o approximations na may initial value x 0. Kung ang function na φ(x) ay hindi tuloy-tuloy at may limitasyon ξ = lim x n bilang n→∞, pagkatapos, na pumasa sa limitasyon sa pagkakapantay-pantay x n +1 =φ(x n), makikita natin na bilang n→ ∞: lim x n +1 =lim φ(x n)=φ(lim x n ), iyon ay, ξ=φ(ξ Dahil dito, kung ang pagkakasunod-sunod ng mga pagtatantya ay nagtatagpo, pagkatapos ito ay nagtatagpo sa ugat ng equation (2), at samakatuwid ay equation (1). Dahil sa convergence ng umuulit na proseso, ang ugat na ito ay maaaring kalkulahin para sa isang sapat na malaki n sa anumang naibigay na katumpakan. Gayunpaman, ito ay kinakailangan upang matukoy sa ilalim ng kung anong mga kondisyon ang sequence (x n) ay magiging convergent. Kumuha tayo ng koneksyon sa pagitan ng mga error ng dalawang magkalapit na pagtatantya - ε n at ε n +1: x n =ξ+ε n, x n +1 =ξ+ε n +1. Palitan natin ang mga representasyong ito sa x n +1 =φ(x n) at palawakin ang function sa isang serye ng Taylor sa paligid ng ugat:ξ+ε n +1 =φ(ξ+ε n)=φ(ξ)+ε n φ'(ξ)+ (ε n 2 /2!)φ''(η), kung saan η О [ξ; ξ+ε n ] М Dahil ang ξ ay isang ugat, kung gayon ξ=φ(ξ) , nakukuha natin ang: ε n +1 =ε n φ'(ξ)+(φ''(η)/2)ε n 2 Mula noong ε<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n|ε n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.

Theorem sa convergence ng simpleng paraan ng pag-ulit. Hayaang ξ ang ugat ng equation na x=φ(x), ang function na φ(x) ay tinukoy at naiba sa pagitan, at para sa x О lahat ng value ng function na φ (x) О . Pagkatapos, kung mayroong ganoong positibong numero 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, pagkatapos ay ang mga kalapit na approximation ay namamalagi sa magkabilang panig ng ugat - ang naturang convergence ay tinatawag na two-way (o spiral) - Fig. 2. Dahil sa kasong ito ang ugat ay nakapaloob sa pagitan, ang mga dulo nito ay mga kalapit na pagtatantya – ξÎ(x n ,x n +1), pagkatapos ay ang katuparan ng kondisyon |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.

Upang maihambing ang mga umuulit na pamamaraan sa mga tuntunin ng bilis ng convergence, ang mga sumusunod na konsepto ay ipinakilala:

Kahulugan 1: Ang convergence ng isang sequence (x n) sa ξ ay tinatawag linear(ayon dito, ang umuulit na proseso ay linearly convergent), kung mayroong pare-parehong CО(0,1) at isang numero n 0 na ang mga hindi pagkakapantay-pantay |ξ-x n +1 |≤C|ξ-x n | para sa n≥n 0.

Para sa mga error na ipinakilala mas maaga ito ay nangangahulugan na |ε n+1 |≤C|ε n |. Sa simpleng paraan ng pag-ulit, ang pare-parehong C ay ang halaga q, iyon ay, ang pamamaraan ay nagtatagpo ng linearly.

Kahulugan 2: Ang pagkakasunod-sunod ng mga pagtatantya (x n ) ay nagtatagpo sa ξ na may hindi bababa sa R-th order (ayon dito, ang umuulit na proseso ay may hindi bababa sa p-ika-order), kung mayroong ganitong mga pare-pareho C>0, p≥1 at n 0 , na para sa lahat ng n≥n 0 ang mga kondisyon |ξ-x n +1 |≤C|ξ-x n | p (o sa ibang mga notasyon |ε n+1 |≤C|ε n | p).