Peržiūrėti šaltinį Apytikslis šaknų skaičiavimas (stygų ir liestinių metodai)



==Apytikslis šaknų skaičiavimas==

:Yra metodai leidžiantys ''atskirti'' realiąsias šaknis polinomo <math>f(x)</math> su realiaisiais koeficientais, t. y. kiekvienai šakniai nurodyti ribas, tarp kurių yra tik ''viena'' šita šaknis. Jeigu šitos ribos (intervalas) pakankamai siauros, tai bet kokį skaičių, esantį tarp jų, galima laikyti apytikslia reikšme ieškomos šaknies. Tokiu budu, po to, kai Šturmo metodu (arba kokiu nors kitu, ekonomiškesniu budu) bus nustatyta, kad tarp '''racionaliųjų''' skaičių <math>a</math> ir <math>b</math> yra tik viena šaknis polinomo <math>f(x),</math> lieka užduotis tiek susiaurinti šitas ribas (intervalo kraštus), kad naujos ribos (kraštai) <math>a'</math> ir <math>b'</math> turėtų į priekį nustatytą skaičių sutampančių pirmų dešimtainių skaitmenų; šituom ieškoma šaknis bus apskaičiuota su užduotu tikslumu.
:Egzistuoja daug metodų, leidžiančių pakankamai greitai rasti apytikslią šaknies reikšmę su reikalaujamu tikslumu. Mes nurodysime du iš jų, teoriškai paprastesnius ir bendresnius, ir kuriuos naudojant kartu pakankamai greitai prieinama prie tikslo. Reikia pastebėti, kad metodai, kurie bus dabar išdėstyti, pritaikomi ne tik polinomams, bet ir platesnėms klasėms tolydžių funkcijų. Toliau laikysime, kad <math>\alpha</math> yra '''paprasta''' (nekartotinė) šaknis polinomo <math>f(x),</math> kadangi nuo kartotinių šaknų mes visada galim išsilaisvint (jeigu šaknies <math>\alpha</math> kartotinumas yra ''k'', tai polinomas <math>f^{(k-1)}(x)</math> turės tik ''paprastą'' šaknį <math>\alpha</math>), ir kad šaknis <math>\alpha</math> jau atskirta ribom ''a'' ir ''b'', <math>a<\alpha<b;</math> iš čia seka, kad <math>f(a)</math> ir <math>f(b)</math> turi skirtingus ženklus.

===Tiesinės interpoliacijos metodas (stygų metodas)===

:Apytikslia reikšme šaknies <math>\alpha</math> būtų galima laikyti, pavyzdžiui, pusė sumos kraštų ''a'' ir ''b'', <math>\frac{a+b}{2},</math> t. y. atkarpos vidurį, kurio galai ''a'' ir ''b''. Natūraliau manyti, kad šaknis guli arčiau prie tos iš ribų (kraštų) ''a'', ''b'', kuriai atitinka mažesnė absoliučiu dydžiu polinomo reikšmė. Tiesinės (linijinės) interpoliacijos metodo esmė yra tokia, kad skaičius ''c'' laikomas apytikslia reikšme šaknies <math>\alpha</math> ir dalinantis atkarpą (''a'', ''b'') į dalis, proporcingas absoliučioms reikšmėms skaičių <math>f(a)</math> ir <math>f(b),</math> t. y.
:<math>\frac{c-a}{b-c}=-\frac{f(a)}{f(b)} ;</math>
:minuso ženklas dešinėje dalyje pastatytas dėl to, kad <math>f(a)</math> ir <math>f(b)</math> turi skirtingus ženklus. Iš čia
:<math>(c-a)f(b)=-(b-c)f(a),</math>
:<math>cf(b) -af(b)=cf(a) -bf(a),</math>
:<math>cf(b) -cf(a)=af(b) -bf(a),</math>
:<math>c=\frac{af(b) -bf(a)}{f(b) -f(a)},</math>
:<math>c=\frac{bf(a) -af(b)}{f(a) -f(b)}. \quad (1)</math>
[[File:Stygumetodas10brez.png|thumb|10 brėž.]]
:Geometriškai, kaip parodyta 10 brėž., linijinės interpoliacijos metodo esmė tame, kad ant atkarpos (''a'', ''b'') kreivė <math>y=f(x)</math> pakeičiama jos styga, jungiančia taškus A(a, f(a)) ir B(b, f(b)), ir apytikslia reikšme šaknies <math>\alpha</math> laikoma abscisė taško susikirtimo šitos stygos su ašimi ''x''.

===Niutono metodas (liestinių metodas)===

:Kadangi <math>\alpha</math> — paprasta šaknis polinomo f(x), tai <math>f'(\alpha)\neq 0.</math> Priimsime, kad taip pat ir <math>f''(\alpha)\neq 0,</math> kadangi kitaip klausimas suvedamas į skaičiavimą šaknies polinomo <math>f''(x),</math> turinčio mažesnį laipsnį, negu <math>f(x).</math> Toliau priimsime, kad atkarpa (''a'', ''b'') ne tik neturi <math>f(x)</math> šaknų, skirtingų nuo <math>\alpha,</math> bet ir neturi nei vienos šaknies polinomo <math>f'(x),</math> o taipogi ir polinomo <math>f''(x)</math>*. Tokiu budu, kaip seka iš matematinės analizės kurso, kreivė <math>y=f(x)</math> ant atkarpos (''a'', ''b'') yra arba monotoniškai didėjanti, arba monotoniškai mažėjanti, o taip pat arba visuose taškuose šitos atkarpos yra išgaubta į viršų, arba visuose taškuose šitos atkarpos įgaubta žemyn. Kreivės išsidėstymas ant atkarpos (''a'', ''b'') gali priklausyti vienam iš keturių atvejų, parodytų brėžiniuose 11—14.
[[File:Breziniai11-14-6.png|thumb|Brėžiniai 11-14.]]
[[File:15brezinys-2.png|thumb|15 brėž.]]
:Pažymėsime per <math>a_0</math> tą iš ribų ''a'' ir ''b'', pas kurią '''ženklas''' f(x) '''sutampa su ženklu''' <math>f''(x).</math> Kadangi f(a) ir f(b) turi skirtingus ženklus, o <math>f''(x)</math> išsaugo ženklą visoje atkarpoje (''a, b''), tai toks <math>a_0</math> gali būti nurodytas (jeigu kreivė išgaubta į viršų, tai jos antra išvestinė visada neigiama toje atkarpoje (<math>f''(x)<0</math>), o jeigu kreivė įgaubta į apačią, tai jos antra išvestinė visada teigiama (<math>f''(x)>0</math>) toje atkarpoje). Atvejais, parodytais brėžinuose 11 ir 14, bus <math>a_0=a,</math> kitais dviais atvejais <math>a_0=b.</math> Kreivės taške <math>y=f(x)</math> su abscise <math>a_0,</math> t. y. taške su koordinatėmis <math>(a_0, \; f(a_0)),</math> pravesime liestinę šitos kreivės ir pažymėsime per ''d'' abscisę taško susikirtimo šitos liestinės su ašimi ''x''. Brėžiniai 11-14 rodo, kad skaičių ''d'' galima laikyti apytikslia reikšme šaknies <math>\alpha.</math> Niutono metodas susideda iš pakeitimo kreivės <math>y=f(x)</math> ant atkarpos (''a'', ''b'') jos liestine vienoje iš ribų šitos atkarpos. Skaičiaus <math>a_0</math> pasirinkimo sąlyga yra svarbi: brėž. 15 parodo, kad be šitos sąlygos paisymo, liestinės susikirtimo taškas su ašimi ''x'' gali visai neduoti priartėjimo prie ieškomos šaknies.

_________________________
:''*'' Ribų (kraštų) siaurinimas, privedantis prie to, kad šita sąlyga bus tenkinama, pasiekiamas įprastai be didesniu sunkumu, kadangi metodai, aptarti anksčiau, leidžia nustatyti šaknų skaičių polinomo <math>f'(x)</math> ir <math>f''(x)</math> bet kokioje atkarpoje.

[[File:16brezinys-4.png|thumb|16 brėžinys.]]
:Išvesime formulę, pagal kurią ieškomas skaičius ''d''. Kaip žinoma, liestinės lygtis kreivės <math>y=f(x)</math> taške <math>(a_0, \; f(a_0))</math> gali būti užrašyta pavidale
:<math>y-f(a_0)=f'(a_0)(x-a_0).</math>
:Įstatydami čia koordinates (''d'', 0) susikirtimo taško liestinės su ašimi ''x'', gausime:
:<math>-f(a_0)=f'(a_0)(d-a_0),</math>
:iš kur
:<math>d=a_0-\frac{f(a_0)}{f'(a_0)}. \quad (2)</math>
:Jeigu skaitytojas sujungs ant brėž. 11-14 taškus ''A'' ir ''B'' stygom, tai pastebės, kad ''metodu linijinės interpoliacijos ir Niutono visais atvejais duoda priartėjimą prie tikros reikšmės šaknies <math>\alpha</math> iš skirtingų pusių''. Tikslinga todėl, jeigu atkarpa (a, b) jau tokia, kaip to reikalaujama Niutono metode, kombinuoti šituos du metodus. Mes gausime šituo budu daug labiau siauras ribas ''c'' ir ''d'' šakniai <math>\alpha.</math> Jeigu jie dar neduoda reikalaujamo tikslumo, tai šitoms riboms reikia dar kartą pritaikyti nurodytus abu metodus (žr. 16 brėž.) ir t. t., be to galima įrodyti, kad šitas procesas tikrai leidžia apskaičiuoti šaknį <math>\alpha</math> su bet kokiu tikslumu.

==Niutono metodo įrodymas==

:Mes iki šiol neparodėme, kad išdėstyti aukščiau metodai iš tikro leidžia apskaičiuoti šaknį su bet kokiu tikslumu, t. y. neįrodėme konvergavmo šitų metodų. Įrodysime tai Niutono metodui.
:Tegu, kaip ir aukščiau, paprasta šaknis <math>\alpha</math> polinomo f(x) yra atkarpoje (''a'', ''b''), išrinktoje taip, kaip tai būtina Niutono metodo naudojime. Iš čia seka egzistavimas tokių teigiamų skaičių ''A'' ir ''B'', kad visur ant atkarpos (''a'', ''b'')
:<math>|f'(x)| >A, \quad |f''(x)|<B. \quad (3)</math>
:Įvesime žymėjimą
:<math>C=\frac{B}{2A}</math>
:ir laikysime, kad 
:<math>C(b-a)<1. \quad(4)</math>
:Šios nelygybės išpildymui galimai prireiks pakeisti ribas (''a'', ''b'') šaknies <math>\alpha</math> siauresnėm ribom; tai nepakeis nelygybių (3) teisingumo. Tegu <math>a_0</math> bus ta iš ribų ''a'', ''b'', kuriai taikomas Niutono metodas. Pagal formulę (2) mes nuosekliai gausime apytikslias šaknies <math>\alpha</math> reikšmes <math>a_1, \; a_2, \; ..., \; a_k, \; ...,</math> gulinčias atkarpoje (''a'', ''b'') ir surištas tarpusavyje lygybėmis
:<math>a_k=a_{k-1}-\frac{f(a_{k-1})}{f'(a_{k-1})}, \quad k=1, \; 2, \; ... \quad (5)</math>
:Tegu
:<math>\alpha=a_k+h_k, \quad k=0, \; 1, \; 2, \; ... \quad (6)</math>
:Tada (pagal Teiloro formulę)
:<math>0=f(\alpha)=f(a_k)+h_k f'(a_k)+\frac{h^2_k}{2} f''(a_k+\theta h_k), \quad (6.5)</math>
:kur <math>0<\theta<1.</math> Kadangi <math>f'(a_k)\neq 0</math> dėl sąlygos atkarpai (''a'', ''b''), tai, atsižvelgdami į (5) ir (6), gausime:
:<math>-\frac{h^2_k}{2} f''(a_k+\theta h_k)=f(a_k)+h_k f'(a_k),</math>
:<math>-\frac{h^2_k}{2} \frac{f''(a_k+\theta h_k)}{f'(a_k)}=h_k +\frac{f(a_k)}{f'(a_k)}=\alpha-a_k +\frac{f(a_k)}{f'(a_k)}= \alpha-\left(a_k -\frac{f(a_k)}{f'(a_k)}\right)=\alpha-a_{k+1} =h_{k+1}.</math>
:Iš čia
:<math>|h_{k+1}|=h^2_k \left| \frac{f''(a_k+\theta h_k)}{2 f'(a_k)}\right| <h^2_k \frac{B}{2A}=Ch^2_k, \quad k=0, \; 1, \; 2, \; ...</math>
:Tokiu budu,
:<math>|h_{k+1}| <Ch^2_k < C^3 h^4_{k-1} < C^7 h^8_{k-2} < ...< C^{2^{k+1}-1} h^{2^{k+1}}_{0}</math>
:[ <math>|h_{k+1}|=Ch^2_k; \;\;\; Ch^2_k=C\cdot [Ch^2_{k-1}]^2=C^3 h^4_{k-1}, \;\;\; C^3 h^4_{k-1}=C^3 [C h^2_{k-2}]^4=C^7 h^8_{k-2}, \;\; ...</math> ]
:arba, kadangi <math>|h_0|=|\alpha-a_0| <b-a,</math>
:<math>|h_{k+1}| <C^{-1} [C(b-a)]^{2^{k+1}}, \quad k=0, \; 1, \; 2, \; ... \quad (7)</math>


:Jeigu Teiloro formulėje
:<math>f(x)=f(a)+\frac{f'(a)}{1!}(x-a)+\frac{f''(a)}{2!}(x-a)^2+\frac{f'''(a)}{3!}(x-a)^3+...+\frac{f^{(n)}(a)}{n!}(x-a)^n+\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-a)^{n+1}=</math>
:<math>=f(a)+\frac{f'(a)}{1!}(x-a)+\frac{f''(a)}{2!}(x-a)^2+\frac{f'''(a)}{3!}(x-a)^3+...+\frac{f^{(n)}(a)}{n!}(x-a)^n+\frac{f^{(n+1)}[a+\theta(x-a)]}{(n+1)!}(x-a)^{n+1},</math>
:paimsime, kad n=1, tai gausime tokią Teiloro formulę:
:<math>f(x)=f(a)+\frac{f'(a)}{1!}(x-a)+\frac{f^{(n+1)}[a+\theta(x-a)]}{(n+1)!}(x-a)^{n+1}=</math>
:<math>=f(a)+\frac{f'(a)}{1!}(x-a)+\frac{f^{(1+1)}[a+\theta(x-a)]}{(1+1)!}(x-a)^{1+1}=</math>
:<math>=f(a)+f'(a)(x-a)+\frac{f^{(2)}[a+\theta(x-a)]}{2}(x-a)^{2}. \quad (8)</math>
:Toliau pažymėkime
:<math>x=\alpha=a_k+h_k,</math>
:<math>a=a_k,</math>
:<math>x-a=[a_k+h_k]-a_k=h_k,</math>
:<math>a<\xi <x,</math>
:<math>\xi=a+\theta(x-a)=a_k+\theta h_k.</math>
:Įstatykime šiuos pakeitimus į (8) formulę:
:<math>f(x)=f(a)+f'(a)(x-a)+\frac{f^{(2)}[a+\theta(x-a)]}{2}(x-a)^{2}, \quad (8)</math>
:<math>0=f(\alpha)=f(a_k)+f'(a_k) h_k+\frac{f^{(2)}[a_k+\theta h_k]}{2} h_k^{2}.</math>
:Taigi, gavome formulę (6.5),
:<math>0=f(\alpha)=f(a_k)+h_k f'(a_k)+\frac{h^2_k}{2} f''(a_k+\theta h_k). \quad (6.5)</math>


:Iš (7) formulės, pagal (4) sąlygą, seka, kad ''skirtumas <math>h_k</math> tarp šaknies <math>\alpha</math> ir jos apytikslės reikšmės <math>a_k,</math> gautos nuosekliai taikant Niutono metodą, artėja prie nulio, kai k didėja, ką ir reikėjo įrodyti''.
:Pastebėsime, kad (7) formulė duoda ''paklaidos įvetinimą'' <math>(k+1)</math>-am žingsniui, kas reikšminga, jeigu Niutono metodas taikomas vienas, o ne kombinacijoje su metodu linijinės interpoliacijos.
:Kursuose teorijos apytikslių skaičiavimų galima rasti išdėstymą daugelį kitų metodų apytikslio šaknų skaičiavimo. Tarp jų labiausiai tobulu yra ''Lobačevskovo metodas'' (''метод Лобачевского'') (kai kada klaidingai vadinamas metodu Grefe (Греффе)). Šitas metodas leidžia rasti apytikslias reikšmes visų šaknų iš karto, tame tarpe ir kampleksinių, be to nereikalauja išankstinio šaknų atskyrimo; jis surištas, visgi, su pakankamai griozdiškais skaičiavimais. Šio metodo pagrindą sudaro teorija simetrinių polinomų.

==Pavyzdžiai==

*Pritaikysime šituos metodus polinomui
:<math>h(x)=x^5+2x^4-5x^3+8x^2-7x-3.</math>
:Mes žinome, kad šitas polinomas turi paprastą šaknį <math>\alpha_1,</math> esančią ribose <math>1< \alpha_1< 2.</math> Iš anksto galima pasakyti, kad šitos ribos per plačios tam, kad metodai linijinės interpoliacijos ir Niutono, pritaikyti tik po vieną kartą, galėtų duoti gerą rezultatą. Visgi pritaikysime juos, kad turėti vieną pavyzdį, nereikalaujantį sudetingų skaičiavimų.
:Su <math>x=1</math> išvestinės <math>h'(x), \; h''(x), \; ..., \; h^V(x) \;</math> yra teigiamos. Iš čia seka (pagal tam tikrą teoriją), kad šaknis <math>x=1</math> tarnauja <math>h'(x),</math> o taip pat <math>h''(x)</math> viršutine riba teigiamų šaknų. Atkarpa (1, 2) to pasekoje neturi šaknų šitų išvestinių, todėl jai galima pritaikyti Niutono metodą. Be to, <math>h''(x)</math> visur šitoje atkarpoje teigiama, o kadangi
:<math>h(1)=-4, </math>
:h(2) = 2^5 + 2*2^4 - 5*2^3 + 8*2^2 - 7*2 - 3 = 32 + 2*16 -5*8 +8*4 - 7*2 - 3 = 32+32-40+32-14-3 = 39,
:tai reikia priimti <math>a_0=2</math> (12 brėž.). Atsižvelgdami, kad <math>h'(2)=109,</math> mes pagal (2) formulę gauname:
:[ <math>h'(x)=5x^4+8x^3-15x^2+16x-7,</math>
:h'(2) = 5*2^4+8*2^3-15*2^2+16*2-7 = 5*16 + 8*8 -15*4 +16*2 -7 = 80 + 64 - 60 + 32 - 7 = 109. ]
:<math>d=a_0-\frac{f(a_0)}{f'(a_0)} = 2-\frac{39}{109} =\frac{218-39}{109}=\frac{179}{109} = 1.64 \; ... </math>
:Iš kitos pusės, formulė (1) duoda:
:<math>c=\frac{bf(a) -af(b)}{f(a) -f(b)} =\frac{2\cdot (-4) -1\cdot 39}{-4 -39} = \frac{-8 - 39}{-43} = \frac{47}{43} =1.09 \; ...</math>
:ir, to pasekoje, šaknis <math>\alpha_1</math> yra ribose
:<math>1.09<\alpha_1<1.65.</math>
:Mes gavome nereikšmingą ribų susiaurėjimą tam, kad pripažinti šitą rezultatą tenkinančiu. Žinoma, gautoms riboms būtų galima dar kartą pritaikyti mūsų metodus. Tikslinga, visgi, iš pat pradžių rasti šakniai <math>\alpha_1</math> pakankamai ankštas ribas, pavyzdžiui su tikslumu iki 0.1 arba net 0.01, ir tik po to panaudoti šituos metodus. Tai, suprantama,  iškart padarys visus skaičiavimus gana griozdiškais, bet sprendžiant konkrečius uždavinius, reikalaujančius pakankamai tikslaus polinomo šaknų žinojimo, tenka tai daryti.
:Grįškime prie mūsų polinomo <math>h(x)</math> ir jo šaknies <math>\alpha_1,</math> be kita ko pastebėsime, kad visos reikšmės polinomų, pateiktos žemiau, apskaičiuojamos Hornerio metodu. Kadangi
:<math>h(1.3)=-0.13987, \quad h(1.31)=0.0662923851,</math>
:[h(1.3) = 1.3^5 +2*1.3^4 -5*1.3^3 +8*1.3^2 -7*1.3 -3 = -0.13987, 
:h(1.31) = 1.31^5 +2*1.31^4 -5*1.31^3 +8*1.31^2 -7*1.31 -3 = 0.0662923851.]
:tai
:<math>1.3<\alpha_1<1.31,</math>
:t. y. mes radome reikšmes šaknies <math>\alpha_1</math> tikslumu iki 0.01. Pritaikysime dabar šitoms naujoms riboms linijinės interpoliacijos metodą:
:<math>c=\frac{bf(a) -af(b)}{f(a) -f(b)} =\frac{1.31\cdot (-0.13987) -1.3\cdot 0.0662923851}{-0.13987 -0.0662923851} = </math>
:= (1.31*(-0.13987) - 1.3*0.0662923851)/(-0.13987 -0.0662923851) = 1.3067844577919563465508238340613 = 1.30678 ...
:Pritaikysime šitoms riboms Niutono metodą, priedo reikia paimti <math>a_0=1.31.</math> Kadangi
:<math>h'(1.31)=20.92822405,</math>
:[h'(x) = 5*1.31^4 +8*1.31^3 -15*1.31^2 +16*1.31 -7 = 20.92822405.]
:tai
:<math>d=a_0-\frac{f(a_0)}{f'(a_0)} = 1.31-\frac{0.0662923851}{20.92822405} =\frac{1.31\cdot 20.92822405-0.0662923851}{20.92822405}=\frac{27.4159735055 -0.0662923851 }{20.92822405} =\frac{27.3496811204}{20.92822405}=  </math>
:= 1.306832393186272296239106824738 = 1.30683 ...
:Tokiu budu,
:<math>1.30678<\alpha_1 <1.30684,</math>
:ir todėl, paėmę <math>\alpha_1=1.30681,</math> mes padarysime klaidą, mažesnę nei 0.00003.
:Pastebėsime, kad 0.01^2 = 0.0001 > 0.00003. Be to,
:h(1.30681) = 1.30681^5 +2*1.30681^4 -5*1.30681^3 +8*1.30681^2 -7*1.30681 -3 = -0.0001496088153666072602599.

==Nuorodos==

* https://talpykla.elaba.lt/elaba-fedora/objects/elaba:1862841/datastreams/MAIN/content