Atgal Pirmyn
Dėmesio! Skaidrių peržiūros yra skirtos tik informaciniams tikslams ir gali neatspindėti visų pristatymo funkcijų. Jei jus domina šis darbas, atsisiųskite pilną versiją.
Pamokos tipas: Pirminių žinių įsisavinimo ir įtvirtinimo pamoka.
Pamokos tikslas:
- Supažindinkite mokinius su daugianario šaknų samprata ir išmokykite juos rasti.
- Tobulinkite įgūdžius naudojant Hornerio schemą, skirtą daugianario išplėtimo laipsniais ir daugianario padalijimui iš dvejetainio.
- Išmokite rasti lygties šaknis naudodami Hornerio schemą.
- Ugdykite abstraktų mąstymą.
- Puoselėti kompiuterių kultūrą.
Tarpdisciplininių ryšių plėtra.
Pamokos eiga
1. Organizacinis momentas.
Informuokite pamokos temą, suformuluokite tikslus.
2. Namų darbų tikrinimas.
3. Naujos medžiagos studijavimas. = Tegul Fn(x) - a n x n +a n-1 x n-1 +...+ a 1 x +a 0 n laipsnio daugianario x, kur a 0, a 1,...,a n yra pateikti skaičiai, o a 0 nėra lygus 0. Jei daugianarį F n (x) padaliname su likučiu iš dvinario x-a , tada dalinys (neužbaigtas koeficientas) yra n-1 laipsnio daugianomas Q n-1 (x), likusioji dalis R yra skaičius, o lygybė yra teisinga F n (x)=(x-a) Q n-1 (x) +R.
Dauginamas F n (x) dalijasi iš dvinaro (x-a) tik tuo atveju, kai R=0. Bezout teorema: Likutis R dalijant daugianarį F n (x) iš dvejetainio (x-a) lygi vertei
daugianario F n (x), kai x=a, t.y. R = Pn(a).
Šiek tiek istorijos. Bezouto teorema, nepaisant akivaizdaus paprastumo ir akivaizdumo, yra viena iš pagrindinių daugianario teorijos teoremų. Ši teorema sieja daugianario algebrines savybes (kurios leidžia daugianarius traktuoti kaip sveikuosius skaičius) su jų funkcinėmis savybėmis (kurios leidžia daugianario traktuoti kaip funkcijas). Vienas iš būdų išspręsti aukštesnio laipsnio lygtis yra kairėje lygties pusėje esantį polinomą. Dauginamo ir liekanos koeficientų apskaičiavimas parašytas lentelės forma, vadinama Hornerio schema. Hornerio schema yra daugianarių dalijimo algoritmas, parašytas ypatingam atvejui, kai koeficientas yra lygus dvinariui.
Horneris Viljamas Džordžas (1786–1837), anglų matematikas. Pagrindiniai tyrimai yra susiję su teorija algebrines lygtis. Sukūrė bet kokio laipsnio lygčių apytikslio sprendimo metodą. 1819 m. jis pristatė svarbų algebros metodą, dalijantį daugianarį iš dvejetainio x - a (Hornerio schema).
Išvada bendroji formulė Hornerio schemai.
Padalijus polinomą f(x) su liekana iš dvejetainio (x-c) reiškia, kad reikia rasti daugianarį q(x) ir skaičių r, kad f(x)=(x-c)q(x)+r
Parašykime šią lygybę išsamiai:
f 0 x n + f 1 x n-1 + f 2 x n-2 + ...+f n-1 x + f n = (x-c) (q 0 x n-1 + q 1 x n-2 + q 2 x n-3 +...+ q n-2 x + q n-1)+r
Sulyginkime koeficientus tais pačiais laipsniais:
xn: f 0 = q 0 => q 0 = f 0 xn-1: f 1 = q 1 – c q 0 => q 1 = f 1 + c q 0 xn-2: f 2 = q 2 – c q 1 => q 2 = f 2 + c q 1 ... ... x0: f n = q n - c q n-1 => q n = f n + c q n-1.
Hornerio grandinės demonstravimas naudojant pavyzdį.
1 užduotis. Naudodami Hornerio schemą, daugianarį f(x) = x 3 - 5x 2 + 8 su likusia dalijame iš dvejetainio x-2.
| 1 | -5 | 0 | 8 | |
| 2 | 1 | 2*1+(-5)=-3 | 2*(-3)+0=-6 | 2*(-6)+8=-4 |
f(x) = x 3 - 5x 2 + 8 =(x-2)(x 2 -3x-6) -4, kur g(x) = (x 2 -3x-6), r = -4 liekana.
Daugiakalnio plėtimas dvinario laipsniais.
Naudodami Hornerio schemą, daugianario f(x)=x 3 +3x 2 -2x+4 išplečiame dvinario (x+2) laipsniais.
Dėl to turėtume gauti išplėtimą f(x) = x 3 +3x 2 -2x+4 = (x+2)(x 2 +x-4)+12 = (x+2) ((x-1) )(x+ 2)-2)+12 = (((1*(x+2)-3)(x+2)-2)(x+2))+12 = (x+2) 3 -3( x+2) 2 -2(x+2)+12
Hornerio schema dažnai naudojama sprendžiant trečiojo, ketvirto ir aukštesnio laipsnio lygtis, kai patogu daugianarį išplėsti į dvinarį x-a. Skaičius a paskambino daugianario šaknis F n (x) = f 0 x n + f 1 x n-1 + f 2 x n-2 + ...+f n-1 x + f n, jei x=a daugianario F n (x) reikšmė lygi nuliui: F n (a)=0, t.y. jei daugianaris dalijasi iš binomo x-a.
Pavyzdžiui, skaičius 2 yra daugianario F 3 (x)=3x 3 -2x-20 šaknis, nes F 3 (2)=0. tai reiškia. Kad šio daugianario faktorizacija turi koeficientą x-2.
F 3 (x) = 3x 3 -2x-20 = (x-2) (3x 2 +6x+10).
Bet koks F n(x) laipsnio daugianomas n 1 negali turėti daugiau n tikrosios šaknys.
Bet koks visa šaknis lygtis su sveikaisiais koeficientais yra jos daliklis laisvas narys.
Jei pirminis lygties koeficientas yra 1, tada visi racionalios šaknys lygtys, jei jos egzistuoja, yra sveikieji skaičiai.
Studijuotos medžiagos konsolidavimas.
Naujai medžiagai įtvirtinti mokiniai kviečiami pildyti skaičius iš vadovėlio 2.41 ir 2.42 (p. 65).
(2 mokiniai sprendžia prie lentos, o likusieji, apsisprendę, pasitikrina užduotis sąsiuvinyje su atsakymais lentoje).
Apibendrinant.
Suvokus Hornerio schemos sandarą ir veikimo principą, ji gali būti naudojama ir informatikos pamokose, kai svarstomas sveikųjų skaičių konvertavimas iš dešimtainės skaičių sistemos į dvejetainę sistemą ir atvirkščiai. Perėjimo iš vienos skaičių sistemos į kitą pagrindas yra tokia bendroji teorema
Teorema. Norėdami konvertuoti sveiką skaičių Ap iš p-arinė skaičių sistema į bazinę skaičių sistemą d būtina Ap nuosekliai padalykite su likusia dalimi iš skaičiaus d, parašyta tame pačiame p-arinė sistema, kol gautas koeficientas tampa lygus nuliui. Likusios dalybos bus d- skaitiniai skaitmenys Skelbimas, pradedant nuo jauniausios kategorijos iki vyriausios. Visi veiksmai turi būti atlikti p-arinė skaičių sistema. Žmogui šią taisyklę patogu tik tada, kai p= 10, t.y. verčiant iš dešimtainė sistema. Kalbant apie kompiuterį, priešingai, jam „patogiau“ atlikti skaičiavimus dvejetainėje sistemoje. Todėl norint konvertuoti „2“ į 10, dvejetainėje sistemoje naudojamas nuoseklus padalijimas iš dešimties, o „10 į 2“ yra dešimties laipsnių pridėjimas. Norint optimizuoti „10 in 2“ procedūros skaičiavimus, kompiuteris naudoja Hornerio ekonomiško skaičiavimo schemą.
Namų darbai. Siūloma atlikti dvi užduotis.
1-oji Naudodami Hornerio schemą, padalykite daugianarį f(x)=2x 5 -x 4 -3x 3 +x-3 iš dvejetainio (x-3).
2-oji. Raskite daugianario f(x)=x 4 -2x 3 +2x 2 -x-6 sveikąsias šaknis (atsižvelgiant į tai, kad bet kuri sveikoji lygties su sveikųjų skaičių šaknis yra jos laisvojo nario daliklis).
Literatūra.
- Kurosh A.G. „Aukštosios algebros kursas“.
- Nikolskis S.M., Potapovas M.K. ir kiti 10 klasė „Algebra ir matematinės analizės pradžia“.
- http://inf.1september.ru/article.php?ID=200600907.
Hornerio schema – daugianario dalybos metodas
$$P_n(x)=\sum\limits_(i=0)^(n)a_(i)x^(n-i)=a_(0)x^(n)+a_(1)x^(n-1) )+a_(2)x^(n-2)+\ltaškai+a_(n-1)x+a_n$$
ant dvejetainio $x-a$. Turėsite dirbti su lentele, kurios pirmoje eilutėje yra nurodyto daugianario koeficientai. Pirmasis antrosios eilutės elementas bus skaičius $a$, paimtas iš dvejetainio $x-a$:
N-ojo laipsnio daugianarį padalijus iš dvinario $x-a$, gauname daugianarį, kurio laipsnis vienu mažesnis už pradinį, t.y. lygus $n-1$. Tiesioginį Hornerio schemos taikymą lengviausia parodyti pavyzdžiais.
1 pavyzdys
Padalinkite $5x^4+5x^3+x^2-11$ iš $x-1$ naudodami Hornerio schemą.
Padarykime dviejų eilučių lentelę: pirmoje eilutėje užrašome daugianario $5x^4+5x^3+x^2-11$ koeficientus, išdėstytus kintamojo $x$ laipsnių mažėjimo tvarka. Atkreipkite dėmesį, kad šiame daugianario nėra $x$ iki pirmojo laipsnio, t.y. $x$ koeficientas iki pirmosios laipsnio yra 0. Kadangi dalijame iš $x-1$, antroje eilutėje rašome vieną:
Pradėkime užpildyti tuščius langelius antroje eilutėje. Antroje antrosios eilutės langelyje įrašome skaičių $5$, tiesiog perkeldami jį iš atitinkamo pirmosios eilutės langelio:
Kitą langelį užpildykime tokiu principu: $1\cdot 5+5=10$:
Taip pat užpildykime ketvirtą antros eilutės langelį: $1\cdot 10+1=11$:
Už penktą langelį gauname: $1\cdot 11+0=11$:
Ir galiausiai, paskutiniame, šeštajame langelyje, turime: $1\cdot 11+(-11)=0$:
Problema išspręsta, belieka užsirašyti atsakymą:
Kaip matote, antroje eilutėje esantys skaičiai (tarp vieno ir nulio) yra daugianario koeficientai, gauti padalijus $5x^4+5x^3+x^2-11$ iš $x-1$. Natūralu, kad pradinio daugianario $5x^4+5x^3+x^2-11$ laipsnis buvo lygus keturiems, tai gauto daugianario $5x^3+10x^2+11x+11$ laipsnis yra vienu mažiau, t.y. lygus trims. Paskutinis skaičius antroje eilutėje (nulis) reiškia likutį dalijant daugianarį $5x^4+5x^3+x^2-11$ iš $x-1$. Mūsų atveju likusi dalis lygus nuliui, t.y. daugianariai dalijasi tolygiai. Šį rezultatą taip pat galima apibūdinti taip: daugianario $5x^4+5x^3+x^2-11$ reikšmė $x=1$ yra lygi nuliui.
Išvadą galima suformuluoti ir tokia forma: kadangi daugianario $5x^4+5x^3+x^2-11$ reikšmė ties $x=1$ yra lygi nuliui, tai vienybė yra daugianario šaknis. 5x^4+5x^3+ x^2-11$.
2 pavyzdys
Padalinkite daugianarį $x^4+3x^3+4x^2-5x-47$ iš $x+3$, naudodami Hornerio schemą.
Iš karto nustatykime, kad išraiška $x+3$ turi būti pavaizduota forma $x-(-3)$. Hornerio schema apims lygiai -3 USD. Kadangi pradinio daugianario $x^4+3x^3+4x^2-5x-47$ laipsnis yra lygus keturiems, tai dalybos rezultate gauname trečiojo laipsnio daugianarį:
Rezultatas reiškia
$x^4+3x^3+4x^2-5x-47=(x+3)(x^3+0\cdot x^2 +4x-17)+4=(x+3)(x^ 3+4x-17)+4$
Esant tokiai situacijai, likusi dalis padalijus $x^4+3x^3+4x^2-5x-47$ iš $x+3$ yra $4$. Arba, kas yra tas pats, daugianario $x^4+3x^3+4x^2-5x-47$ vertė $x=-3$ yra lygi $4$. Beje, tai nesunku dar kartą patikrinti, tiesiogiai pakeičiant $x=-3$ į nurodytą daugianarį:
$$x^4+3x^3+4x^2-5x-47=(-3)^4+3 \ctaškas (-3)^3-5 \ctaškas (-3)-47=4.$$
Tie. Hornerio schema gali būti naudojama, jei reikia rasti daugianario reikšmę ties nustatyta vertė kintamasis. Jei mūsų tikslas yra rasti visas daugianario šaknis, tai Hornerio schemą galima taikyti kelis kartus iš eilės, kol išnaudosime visas šaknis, kaip aptarta 3 pavyzdyje.
3 pavyzdys
Raskite visas daugianario $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ sveikąsias šaknis naudodami Hornerio schemą.
Aptariamo daugianario koeficientai yra sveikieji skaičiai, o koeficientas yra prieš didžiausią kintamojo laipsnį (ty prieš $x^6$) lygus vienam. Šiuo atveju tarp laisvojo nario daliklių reikia ieškoti sveikųjų daugianario šaknų, t.y. tarp skaičiaus 45 daliklių. Tam tikro daugianario tokios šaknys gali būti skaičiai $45; \; 15; \; 9; \; 5; \; 3; \; 1 USD ir -45 USD; \; -15; \; -9; \; -5; \; -3; \; -1 $. Patikrinkime, pavyzdžiui, skaičių $1$:
Kaip matote, daugianario $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ vertė su $x=1$ yra lygi $192$ ( paskutinis numeris antroje eilutėje), o ne $0$, todėl vienybė nėra šio daugianario šaknis. Kadangi vieno patikrinimas nepavyko, patikrinkime reikšmę $x=-1$. Naujas stalasŠiuo tikslu mes nekompiliuosime, bet ir toliau naudosime lentelę. Nr. 1, pridedant prie jo naują (trečią) eilutę. Antroji eilutė, kurioje buvo pažymėta 1 USD vertė, bus paryškinta raudonai ir nebus naudojama tolesnėse diskusijose.
Žinoma, lentelę galite tiesiog perrašyti dar kartą, tačiau jos pildymas rankiniu būdu užtruks daug laiko. Be to, gali būti keli skaičiai, kurių patikrinimas nepavyks, ir kiekvieną kartą sunku parašyti naują lentelę. Skaičiuojant „ant popieriaus“, raudonas linijas galima tiesiog perbraukti.
Taigi, daugianario $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ reikšmė ties $x=-1$ lygi nuliui, t.y. skaičius $-1$ yra šio daugianario šaknis. Padalijus daugianarį $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ iš dvinario $x-(-1)=x+1$, gauname daugianarį $x ^5+x ^4-22x^3+2x^2+69x+45$, kurių koeficientai paimti iš trečios lentelės eilės. Nr. 2 (žr. pavyzdį Nr. 1). Skaičiavimų rezultatas taip pat gali būti pateiktas tokia forma:
\begin(lygtis)x^6+2x^5-21x^4-20x^3+71x^2+114x+45=(x+1)(x^5+x^4-22x^3+2x^2 +69x+45)\pabaiga (lygtis)
Tęskime sveikųjų skaičių šaknų paiešką. Dabar reikia ieškoti daugianario $x^5+x^4-22x^3+2x^2+69x+45$ šaknų. Vėlgi, sveikųjų šio daugianario šaknų ieškoma tarp jo laisvojo termino daliklių, skaičių $45$. Pabandykime dar kartą patikrinti skaičių $-1$. Mes nekursime naujos lentelės, bet toliau naudosime ankstesnę lentelę. Nr.2, t.y. Pridėkime prie jo dar vieną eilutę:
Taigi skaičius $-1$ yra daugianario $x^5+x^4-22x^3+2x^2+69x+45$ šaknis. Rezultatą galima parašyti taip:
\begin(lygtis)x^5+x^4-22x^3+2x^2+69x+45=(x+1)(x^4-22x^2+24x+45) \end(lygtis)
Atsižvelgiant į lygybę (2), lygybė (1) gali būti perrašyta tokia forma:
\begin (lygtis)\begin (lygiuotas) & x^6+2x^5-21x^4-20x^3+71x^2+114x+45=(x+1)(x^5+x^4-22x ^2+2x^2+69x+45)=\\ & =(x+1)(x+1)(x^4-22x^2+24x+45)=(x+1)^2(x^ 4–22x^2+24x+45)\pabaiga (sulygiuota)\pabaiga (lygtis)
Dabar reikia ieškoti daugianario $x^4-22x^2+24x+45$ šaknų, žinoma, tarp jo laisvojo nario daliklių (skaičiai $45$). Dar kartą patikrinkime skaičių $-1$:
Skaičius $-1$ yra daugianario $x^4-22x^2+24x+45$ šaknis. Rezultatą galima parašyti taip:
\begin(lygtis)x^4-22x^2+24x+45=(x+1)(x^3-x^2-21x+45) \end(lygtis)
Atsižvelgdami į lygybę (4), lygybę (3) perrašome tokia forma:
\begin (lygtis)\begin (lygiuotas) & x^6+2x^5-21x^4-20x^3+71x^2+114x+45=(x+1)^2(x^4-22x^3 +24x+45)= \\ & =(x+1)^2(x+1)(x^3-x^2-21x+45)=(x+1)^3(x^3-x^ 2–21x+45)\pabaiga (sulygiuota)\pabaiga (lygtis)
Dabar ieškome daugianario $x^3-x^2-21x+45$ šaknų. Dar kartą patikrinkime skaičių $-1$:
Patikrinimas baigėsi nesėkmingai. Pažymėkime šeštąją eilutę raudonai ir pabandykime patikrinti kitą skaičių, pavyzdžiui, skaičių $3$:
Likutis lygi nuliui, todėl skaičius $3$ yra aptariamo daugianario šaknis. Taigi $x^3-x^2-21x+45=(x-3)(x^2+2x-15)$. Dabar lygybę (5) galima perrašyti taip.
1.1 Bendras algoritmo aprašymas
1.1.1 Spręstina problema
Pirmasis įvertinimas pagrįstas daps charakteristika, kuri įvertina per sekundę atliekamų atminties prieigos (skaitymo ir rašymo) skaičių. Ši savybė yra šnipščių įvertinimo analogas, susijęs su darbu su atmintimi ir yra didesniu mastu atminties sąveikos našumo vertinimas, o ne vietos įvertinimas. Tačiau tarnauja geras šaltinis informacija, įskaitant palyginimą su rezultatais iš tokia charakteristika cvg.
4 paveiksle parodytos įprastų algoritmų diegimo daps reikšmės, surūšiuotos didėjančia tvarka (kuo daugiau daps, tuo daugiau bendras atvejis didesnis našumas). Pagal šį paveikslą Hornerio grandinės įgyvendinimas rodo mažą atminties našumą. Gali pasirodyti keista, kad daps reikšmė šiuo atveju yra žymiai mažesnė nei STREAM testų, nepaisant to, kad skambučių profilis visais atvejais yra labai panašus – vienu metu atliekamos kelios nuoseklios masyvų paieškos.
Tokio elgesio priežastis yra susijusi su atminties posistemio struktūrinėmis savybėmis. Įgyvendinant Hornerio schemą, kaip minėta aukščiau, vieno iš masyvų elementai pasiekiami du kartus iš eilės. Tačiau, jei pažvelgsite į diegimo šaltinio kodą, pamatysite, kad iš tikrųjų antrasis skambutis atliekamas kitoje iteracijoje - tai yra ankstesnio elemento iškvietimas:
už (int i = 1 ; i< size ; i ++ ) { c [ i ] = a [ i ] + c [ i - 1 ] * x ; }
Dėl to dėl iteracijų priklausomybės aparatūros prefetcher daug prasčiau susidoroja su reikiamų talpyklos eilučių ištraukimu, todėl programos vykdymas pastebimai sulėtėja, palyginti su kitais diegimais, pagrįstais nuoseklia paieška (pavyzdžiui, STREAM testai).
Šis pavyzdys dar kartą parodo, koks sudėtingas yra atminties posistemis – visiškai mažas pokytis kilpos korpuso struktūra lemia gana netikėtą rimtą programos sulėtėjimą.
4 pav. Daps balų reikšmių palyginimas
Antroji charakteristika, cvg, skirta pateikti labiau nuo mašinos nepriklausomą vietovės įvertinimą. Jis nustato, kaip dažnai programai reikia perkelti duomenis į talpyklos atmintį. Atitinkamai, nei mažesnė vertė cvg, kuo rečiau tai reikia daryti, tuo geresnė vietovė.
5 paveiksle parodytos to paties diegimo rinkinio cvg reikšmės, surūšiuotos mažėjančia tvarka (kuo mažesnis cvg, tuo didesnė vietovė apskritai). Matyti, kad pagal cvg sąmatą Hornerio schemos įgyvendinimas yra labai lokalus.
5 pav. Cvg balų reikšmių palyginimas
Kaip matėme anksčiau, tai nėra gerai koreliuojama su tikruoju atminties našumu dėl atminties dizaino pobūdžio. Tačiau čia reikia pabrėžti du dalykus. Pirma, panašių atvejų, kai darbo su atmintimi našumas taip stipriai priklauso nuo specifinių atminties posistemio struktūros aparatinės įrangos ypatybių, praktikoje nėra taip įprasta. Antra, cvg sukurtas siekiant pateikti nuo mašinos nepriklausomą vietovės įvertinimą; įjungta šis lygis Vargu ar įmanoma atsižvelgti į tokias techninės įrangos savybes, bent jau neprarandant dalies nuo mašinos nepriklausomų savybių.
2.3 Galimi algoritmo lygiagretaus įgyvendinimo būdai ir ypatumai
Aprašytas algoritmas nereiškia lygiagrečio įgyvendinimo.
2.4. Algoritmo mastelio keitimas ir jo įgyvendinimas
Mastelio keitimo sąvoka netaikoma, nes aprašytas algoritmas nereiškia lygiagretaus įgyvendinimo. Atlikime algoritmo įgyvendinimo mastelio tyrimą pagal metodiką. Tyrimas buvo atliktas Maskvos universiteto Superkompiuterių komplekso Lomonosovo superkompiuteryje. Keičiamų parametrų verčių rinkinys ir ribos, kad būtų galima pradėti įgyvendinti algoritmą:
- procesorių skaičius 1;
- ploto dydis 10240 žingsniais.
Eksperimentų metu buvo gautas toks algoritmo įgyvendinimo efektyvumo diapazonas:
- minimalus įgyvendinimo efektyvumas 0,0324 %;
- maksimalus įgyvendinimo efektyvumas 0,0331%.
Tolesniuose paveikslėliuose pateikiami pasirinkto algoritmo įgyvendinimo našumo ir efektyvumo grafikai, atsižvelgiant į kintamus paleidimo parametrus.
6 pav. Algoritmo įgyvendinimas. Veikimas keičiasi priklausomai nuo vektoriaus dydžio.
7 pav. Algoritmo įgyvendinimas. Efektyvumas keičiasi priklausomai nuo vektoriaus dydžio.
Atrodo, kad menką efektyvumą lėmė pernelyg didelė vietovė, aprašyta skyriuje apie .
2.5 Dinaminės charakteristikos ir algoritmo įgyvendinimo efektyvumas
Dėl algoritmo nuoseklumo ir per didelio lokalumo jo dinaminių charakteristikų tyrimas yra mažai vertingas.
Eksperimentams atlikti buvo naudojamas Hornerio schemos algoritmo įgyvendinimas turimoje realizacijoje. Visi rezultatai buvo gauti naudojant „GraphIT“ superkompiuterį. Buvo naudojami „Intel Xeon X5570“ procesoriai, kurių didžiausias našumas – 94 Gflops, taip pat „Gnu 4.4.7“ kompiliatorius. Paveikslėliai parodo priešpriešinio šlavimo algoritmo įgyvendinimo efektyvumą.
3 skaidrė
Horner Williams George (1786-1837 9 22) – anglų matematikas. Gimė Bristolyje. Ten jis mokėsi ir dirbo, vėliau – Bato mokyklose. Pagrindiniai algebros darbai. 1819 metais paskelbė apytikslį daugianario realių šaknų apskaičiavimo metodą, kuris dabar vadinamas Ruffini-Horner metodu (šis metodas buvo žinomas kinams dar XIII a. Dauginamo dalijimosi iš binomo x-a schema). po Hornerio.
4 skaidrė
HORNER SCHEMA
Padalijimo metodas n-asis daugianario tiesinio dvinario laipsnis - a, remiantis tuo, kad nepilnojo dalinio ir liekanos koeficientai yra susieti su dalijamojo daugianario koeficientais ir su formulėmis:
5 skaidrė
Skaičiavimai pagal Hornerio schemą pateikiami lentelėje:
Pavyzdys 1. Padalinimas Dalinis koeficientas yra x3-x2+3x - 13, o likusioji dalis yra 42=f(-3).
6 skaidrė
Pagrindinis šio metodo privalumas yra įrašymo kompaktiškumas ir galimybė greitas padalijimas daugianario į dvinarį. Tiesą sakant, Hornerio schema yra dar viena grupavimo metodo įrašymo forma, nors, skirtingai nei pastarasis, ji yra visiškai nevaizdi. Atsakymas (faktorizavimas) čia gaunamas savaime, o jo gavimo proceso nematome. Mes nesiimsime į griežtą Hornerio schemos pagrindimą, o tik parodysime, kaip ji veikia.
7 skaidrė
2 pavyzdys.
Įrodykime, kad daugianomas P(x)=x4-6x3+7x-392 dalijasi iš x-7, ir raskime dalybos koeficientą. Sprendimas. Naudodami Hornerio schemą randame P(7): Iš čia gauname P(7)=0, t.y. dalijant polinomą iš x-7, likusi dalis yra lygi nuliui, todėl polinomas P(x) yra (x-7) kartotinis. Be to, antroje lentelės eilutėje esantys skaičiai yra koeficientai P(x) dalinys, padalytas iš (x-7), todėl P(x)=(x-7)(x3+x2+7x+56).
8 skaidrė
Padalinkite daugianario koeficientą x3 – 5x2 – 2x + 16.
Šis daugianomas turi sveikųjų skaičių koeficientus. Jei sveikasis skaičius yra šio daugianario šaknis, tai jis yra skaičiaus 16 daliklis. Taigi, jei duotasis daugianomas turi sveikųjų skaičių šaknis, tai gali būti tik skaičiai ±1; ±2; ±4; ±8; ±16. Tiesioginiu patikrinimu įsitikiname, kad skaičius 2 yra šio daugianario šaknis, tai yra x3 – 5x2 – 2x + 16 = (x – 2)Q(x), kur Q(x) yra antrojo laipsnio daugianario
9 skaidrė
Gauti skaičiai 1, −3, −8 yra daugianario koeficientai, gaunami pradinį daugianarį padalijus iš x – 2. Tai reiškia, kad padalijimo rezultatas yra: 1 x2 + (–3)x + ( –8) = x2 – 3x – 8. Dauginamo laipsnis, gautas dėl padalijimo, visada yra 1 mažesnis už pradinio laipsnį. Taigi: x3 – 5x2 – 2x + 16 = (x – 2) (x2 – 3x – 8).
Horneris Williamas George'as () anglų matematikas. Pagrindinis tyrimas yra susijęs su algebrinių lygčių teorija. Sukūrė bet kokio laipsnio lygčių apytikslio sprendimo metodą. 1819 m. jis pristatė svarbų algebrai skirtą daugianario padalijimo į dvinarį metodą (x – a) (Hornerio schema).
Hornerio schemos formulių išvedimas Polinomo f(x) dalijimas su likusia dalimi iš dvinario (x-c) reiškia, kad reikia rasti daugianarį q(x) ir skaičių r, kad f(x)=(x-c)q(x)+ r Išsamiai parašykite šią lygybę: f 0 x n + f 1 x n-1 + f 2 x n-2 + …+f n-1 x + f n = =(x-c) (q 0 x n-1 + q 1 x n-2 + q 2 x n-3 +…+ q n-2 x + q n-1)+r Sulyginkime koeficientus lygiais laipsniais: x n: f 0 = q 0 => q 0 = f 0 x n-1: f 1 = q 1 - c q 0 => q 1 = f 1 + c q 0 x n-2: f 2 = q 2 - c q 1 => q 2 = f 2 + c q 1 … X 0: f n = q n - c q n-1 => q n = f n + c q n-1 q 0 = f 0 x n-1: f 1 = q 1 - c q 0 => q 1 = f 1 + c q 0 x n-2: f 2 = q 2 - c q 1 => q 2 = f 2 + c q 1 … X 0: f n = q n - c q n-1 => q n = f n + c q n-1"> 
Hornerio schemos veikimo demonstravimas Hornerio schemoje daugianarį f(x) = x 3 - 5x su likusia dalijame iš dvinario x-2 Užrašome pradinio daugianario koeficientus f 0, f 1, f 2, f 3. f0f0 f1f1 f2f2 f3f c 2 Jei dalijame ant (x-c), tai antroje eilutėje iš kairės rašome c Likusiai r ir nepilno dalinio q 0, q 1 koeficientams paruošti tuščius langelius ,q 2 q0q0 q1q1 q2q2 r g 0:=f 0 =1 1 g 1:= c *g 0 + f 1 * + =2 * 1 + (-5)=-3 g 2:= s *g 1 + f 2 =2 * (-3) + 0=-6 * + r:= s *g 2 + f 3 =2 * (-6) + 8= * + -4 Atsakymas: g(x)=x 2 -3x -6; r = -4. f(x)= (x-2)(x 2 -3x-6)-4
Polinomo išplėtimas dvinalio laipsniais Naudodami Hornerio schemą, išplečiame daugianario f(x)=x 3 +3x 2 -2x+4 dvinalio laipsniais (x+2) f(x)=x 3 +3x 2-2x+4 =(x +2)(x 2 +x-4) f(x)=x 3 +3x 2 -2x+4= (x+2)((x-1)(x+2) -2) f(x)= x3 +3x2 -2x+4= (((1*(x+2)-3)(x+2)-2)(x+2)) f(x) = x 3 +3x 2 -2x+ 4 = (x+2)(x 2 +x-4)+12 = (x+2)((x-1)(x+2)-2)+12 = = (( (1*(x+2)-3)(x+2)-2)(x+2))+12 = (x+2)3-3(x+2)2-2(x+2)+ 12
Namų darbai a 1. Padalinkite f(x)=2x 5 -x 4 -3x 3 +x-3 iš x-3; 2. Naudodami Hornerio schemą raskite daugianario f(x)=x 4 -2x 3 +2x 2 -x-6 sveikąsias šaknis (*Pastaba: tarp daliklių reikia ieškoti sveikųjų daugianario šaknų su sveikaisiais skaičiais laisvojo termino ±1;±2;± 3;±6)
