Minden ember természetesen keresi a tudást. (Arisztotelész. Metafizika)

Numerikus módszerek: Nemlineáris egyenletek megoldása

A gyakorlatban folyamatosan felmerülnek egyenletmegoldási problémák, például a közgazdaságtanban, egy vállalkozás fejlesztésekor tudni akarjuk, hogy mikor ér el a nyereség egy bizonyos értéket, az orvostudományban a gyógyszerek hatásának vizsgálatakor fontos tudni, hogy mikor ér el a koncentráció egy anyag elér egy adott szintet stb.

Az optimalizálási feladatok során gyakran meg kell határozni azokat a pontokat, ahol egy függvény deriváltja 0 lesz, ami szükséges feltétel helyi extrémum.

A statisztikában a legkisebb négyzetek módszerével vagy a maximum likelihood módszerrel történő becslések megalkotásakor nemlineáris egyenleteket és egyenletrendszereket is meg kell oldani.

Tehát a megoldások keresésével kapcsolatos problémák egész osztálya van nem lineáris egyenletek, pl. egyenletek vagy egyenletek stb.

A legegyszerűbb esetben van egy függvényünk a ( a, b ) és bizonyos értékek felvétele.

Mindegyik érték x ebből a szegmensből párosíthatjuk a számot, ez az funkcionális függőség, a matematika kulcsfogalma.

Meg kell találnunk egy olyan értéket, amelynél az ilyeneket a függvény gyökereinek nevezzük

Vizuálisan meg kell határoznunk a függvény grafikonjának metszéspontjátaz abszcissza tengellyel.

Felezési módszer

Az egyenlet gyökereinek megtalálásának legegyszerűbb módszere a felezési módszer, ill kettősség.

Ez a módszer intuitív, és mindenki hasonlóan jár el a probléma megoldása során.

Az algoritmus a következő.

Tegyük fel, hogy találtunk két pontot és olyat, hogy és van különféle jelek, akkor ezek között a pontok között van legalább egy gyöke a függvénynek.

Oszd ketté a szakaszt és írd be középső pont .

Akkor akár , vagy .

Hagyjuk meg a szegmensnek azt a felét, amelynél a végén lévő értékek eltérő előjelűek. Most ismét kettéosztjuk ezt a szegmenst, és meghagyjuk azt a részt, amelynek határán a függvény különböző előjelekkel rendelkezik, és így tovább, hogy elérjük a kívánt pontosságot.

Nyilvánvalóan fokozatosan leszűkítjük azt a területet, ahol a függvény gyökere található, és ezért bizonyos fokú pontossággal határozzuk meg.

Vegye figyelembe, hogy a leírt algoritmus bármely folytonos függvényre alkalmazható.

A felezési módszer előnyei közé tartozik a nagy megbízhatóság és az egyszerűség.

A módszer hátránya, hogy az alkalmazás megkezdése előtt két pontot kell találni, amelyekben a függvény értékei eltérő előjelűek. Nyilvánvaló, hogy a módszer nem alkalmazható páros többszörös gyökök esetén, és nem is általánosítható összetett gyökökre és egyenletrendszerekre.

A módszer konvergencia sorrendje lineáris, minden lépésnél megduplázódik a pontosság, minél több iteráció történik, annál pontosabban határozható meg a gyök.

Newton módszere: elméleti alapok

Newton klasszikus módszere vagy érintők abban rejlik, hogy ha valamilyen közelítés az egyenlet gyökeréhez , akkor a következő közelítést a pontban megrajzolt függvény érintőjének gyökeként definiáljuk.

A függvény érintőjének egyenlete egy pontban a következőképpen alakul:

Az érintőegyenletben tegyük fel és .

Ekkor a szekvenciális számítások algoritmusa Newton módszerében a következő:

A tangens módszer konvergenciája másodfokú, a konvergencia sorrendje 2.

Így a Newton-tangens módszer konvergenciája nagyon gyors.

Emlékezz erre a csodálatos tényre!

Változás nélkül a módszert általánosítjuk az összetett esetre.

Ha a gyök a második multiplicitás gyöke vagy annál nagyobb, akkor a konvergencia sorrendje leesik és lineárissá válik.

1. Feladat. Az érintők módszerével keressük meg az egyenlet megoldását a (0, 2) szakaszon.

2. gyakorlat. Az érintők módszerével keressük meg az (1, 3) szakaszon az egyenlet megoldását!

A Newton-módszer hátrányai közé tartozik a lokalitása, mivel csak akkor garantáltan konvergál egy tetszőleges kiindulási közelítésre, ha a feltétel , egyébként csak a gyökér valamely szomszédságában van konvergencia.

A Newton-módszer hátránya, hogy minden lépésben derivatívákat kell kiszámítani.

Newton-módszer vizualizálása

Newton módszerét (tangens módszer) alkalmazzuk, ha az egyenlet f(x) = 0 gyökérrel rendelkezik, és a következő feltételek teljesülnek:

1) funkció y= f(x) definiált és folyamatos a ;

2) f(a)· f(b) < 0 (a függvény különböző előjelű értékeket vesz fel a szegmens végén [ a; b]);

3) származékok f"(x) és f""(x) tartsa a jelet a szegmensen [ a; b] (azaz függvény f(x) vagy nő, vagy csökken a szegmensen [ a; b], miközben megtartja a konvexitás irányát);

A módszer fő gondolata a következő: az intervallumon [ a; b] ilyen számot választanak x 0 , amely alatt f(x 0 ) ugyanaz a jele, mint f"" (x 0 ), azaz a feltétel f(x 0 )· f"" (x) > 0 . Így egy abszcissza pontot választunk x 0 , ahol a görbe érintője y= f(x) a szegmensen [ a; b] keresztezi a tengelyt Ökör. Egy pontért x 0 Először is célszerű kiválasztani a szegmens egyik végét.

Tekintsük Newton módszerét egy konkrét példán.

Adjunk egy növekvő függvényt y \u003d f (x) \u003d x 2 -2, folytonos a (0;2) intervallumon, és amelynek f"(x) = 2 x > 0 és f "" (x) = 2 > 0 .

Kép1 . f(x)=x2-2

Az érintőegyenlet általános formában a következőképpen ábrázolható:

y-y 0 = f" (x 0) (x-x 0).

A mi esetünkben: y-y 0 \u003d 2x 0 (x-x 0). Pontként x 0 válassz egy pontot B1(b; f(b)) = (2,2). Rajzoljuk a függvény érintőjét y = f(x) a B 1 pontban, és jelölje az érintő és a tengely metszéspontját Ökör pont x 1. Megkapjuk az első érintő egyenletét: y-2=22(x-2), y=4x-6.

Ökör: x 1 =

Kép2. Az első iteráció eredménye

y=f(x) Ökör ponton keresztül x 1, pontot kapunk B 2 =(1,5; 0,25). Rajzoljon ismét egy érintőt a függvényhez y = f(x) a B 2 pontban, és jelölje az érintő és a tengely metszéspontját Ökör pont x2.

A második érintő egyenlete: y-0.25=2*1.5(x-1.5), y = 3 x - 4.25.

Az érintő és a tengely metszéspontja Ökör: x 2 =.

Kép3. Newton-módszer második iterációja

Ezután megtaláljuk a függvény metszéspontját y=f(x)és a tengelyre merőleges Ökör az x 2 ponton keresztül megkapjuk a B 3 pontot és így tovább.

Kép4. A tangens módszer harmadik lépése

A gyökér első közelítését a következő képlet határozza meg:

= 1.5.

A gyökér második közelítését a következő képlet határozza meg:

=

A gyökér harmadik közelítését a következő képlet határozza meg:

Ily módon , én-a gyökér közelítését a következő képlet határozza meg:

A számításokat a válaszadáshoz szükséges tizedesjegyekig, vagy a megadott e pontosság eléréséig végzik - az egyenlőtlenség teljesüléséig | xi- xi-1 | < e.

Esetünkben vessük össze a harmadik lépésben kapott közelítést a számológépen számított valós válasszal:

5. ábra: Számológépen számított 2 gyöke

Mint látható, már a harmadik lépésnél 0,000002-nél kisebb hibát kaptunk.

Így a "2 négyzetgyöke" érték bármilyen pontossággal kiszámítható. Ezt a csodálatos módszert Newton találta ki, és lehetővé teszi, hogy megtalálja a nagyon összetett egyenletek gyökereit.

Newton-módszer: C++ alkalmazás

Ebben a cikkben automatizáljuk az egyenletek gyökereinek kiszámításának folyamatát egy konzolalkalmazás C++ nyelven írásával. Visual C++ 2010 Expressben fejlesztjük, ami egy ingyenes és nagyon kényelmes C++ fejlesztői környezet.

Kezdjük a Visual C++ 2010 Expresszel. Megjelenik a program indító ablaka. A bal sarokban kattintson a "Projekt létrehozása" gombra.

Rizs. 1. Visual C++ 2010 Express kezdőlap

A megjelenő menüben válassza a "Win32 Console Application" lehetőséget, írja be az alkalmazás nevét "Newton_Method".

Rizs. 2. Hozzon létre egy projektet

// Newton_method.cpp: a konzolalkalmazás belépési pontját határozza meg #include "stdafx.h" #beleértve névtér használata std; float f(double x) //visszaadja az f(x) = x^2-2 függvény értékét float df(float x) //visszaadja a derivált értékét float d2f(float x) // második derivált érték int _tmain(int argc, _TCHAR* argv) int exit = 0, i=0;//exit és ciklusváltozók dupla x0,xn;// számított közelítések a gyökér számára dupla a, b, eps;// szegmenshatárok és a szükséges pontosság cout<<"Please input \n=>"; cin>>a>>b; // adja meg annak a szegmensnek a határait, amelyen a gyökeret keresni fogjuk cout<<"\nPlease input epsilon\n=>"; cin>>eps; // adja meg a kívánt számítási pontosságot if (a > b) // ha a felhasználó összekeverte a szegmens határait, cserélje fel őket if (f(a)*f(b)>0) // ha a függvény előjelei a szegmens élein megegyeznek, akkor nincs gyök cout<<"\nError! No roots in this interval\n"; ha (f(a)*d2f(a)>0) x0 = a; // a kezdőpont kiválasztásához jelölje be az f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // megszámoljuk az első közelítést cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // amíg el nem érjük a szükséges pontosságot, folytatja a számítást xn = x0-f(x0)/df(x0); // közvetlenül a Newton-képlet cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; ) while (kilépés!=1); // amíg a felhasználó belép az exit = 1-be

Lássuk, hogyan működik. Kattintson a zöld háromszögre a képernyő bal felső sarkában, vagy nyomja meg az F5 billentyűt.

Ha fordítási hiba történik "LNK1123 hiba: a COFF-ba konvertálás sikertelensége: a fájl érvénytelen vagy sérült", akkor ezt az első Service Pack 1 telepítésével kezeli, vagy a projektbeállítások Tulajdonságok -> Linker menüpontban tiltsa le a növekményes hivatkozást.

Rizs. 4. A projekt összeállítási hibájának megoldása

Megkeressük a függvény gyökereit f(x) =x2-2.

Először teszteljük az alkalmazást a "rossz" bemeneti adatokon. A szegmensen nincsenek gyökerek, programunknak hibaüzenetet kell adnia.

Van egy alkalmazás ablakunk:

Rizs. 5. Bemeneti adatok bevitele

Bevezetjük a 3. és 5. szakasz határait, a pontosság 0,05. A program, ahogy kell, hibaüzenetet adott, hogy ezen a szegmensen nincsenek gyökerek.

Rizs. 6. Hiba "Nincs gyökér ezen a szegmensen!"

Még nem indulunk el, így a „Kilépés?” üzenet jelenik meg. írja be a „0”-t.

Most teszteljük az alkalmazást a megfelelő bemeneti adatokon. Vezessünk be egy szegmenst és egy 0,0001 pontosságot.

Rizs. 7. A gyökér kiszámítása a szükséges pontossággal

Amint látjuk, a szükséges pontosságot már a 4. iterációnál elértük.

Az alkalmazásból való kilépéshez írja be a "Kilépés?" => 1.

A szekáns módszer

A derivált kiszámításának elkerülése érdekében a Newton-módszer egyszerűsíthető, ha a deriváltot az előző két pontból számított közelítő értékkel helyettesítjük:

Az iteratív folyamat így néz ki:

Ez egy kétlépéses iteratív folyamat, mivel az előző kettőt használja a következő közelítés megtalálásához.

A szekáns módszer konvergenciája alacsonyabb, mint a tangens módszeré, és egyetlen gyökér esetén egyenlő.

Ezt a csodálatos értéket aranymetszésnek nevezik:

Ezt úgy ellenőrizzük, hogy az egyszerűség kedvéért feltételezzük, hogy .

Így a magasabb rendű infinitezimálisokig

A maradék tagot elvetve ismétlődési relációt kapunk, melynek megoldását természetesen a formában keressük.

Csere után van: és

A konvergenciához szükséges, hogy pozitív legyen, ezért .

Mivel a derivált ismerete nem szükséges, így a szekant módszerben ugyanannyi számítással (az alacsonyabb konvergenciarend ellenére) nagyobb pontosság érhető el, mint a tangens módszerrel.

Megjegyzendő, hogy a gyökér közelében kis számmal kell osztani, és ez a pontosság elvesztéséhez vezet (főleg több gyökér esetén), ezért egy viszonylag kis értéket választva a számításokat a végrehajtásig végezzük. és addig folytassuk, amíg a szomszédos közelítések közötti különbség modulusa le nem csökken.

Amint a növekedés megkezdődik, a számítások leállnak, és az utolsó iterációt nem használják fel.

Ezt az eljárást az iterációk végének meghatározására technikának nevezzük Harvick.

Parabola módszer

Tekintsünk egy háromlépéses módszert, amelyben a közelítést az előző három pont határozza meg , és .

Ehhez a szekant módszerhez hasonlóan a függvényt a pontokon áthaladó interpolációs parabolára cseréljük, és.

Newton alakjában így néz ki:

A pont úgy definiálható, mint a polinom gyökeinek pontja, amely modulusában közelebb van a ponthoz.

A parabola módszer konvergencia sorrendje magasabb, mint a szekantáló módszeré, de alacsonyabb, mint a Newton-módszeré.

Lényeges különbség a korábban vizsgált módszerekhez képest, hogy még ha valós is valós, és a kiindulási közelítéseket valósnak választjuk, a parabola módszer az eredeti probléma összetett gyökeréhez vezethet.

Ez a módszer nagyon hasznos nagyfokú polinomok gyökeinek megtalálásához.

Egyszerű iterációs módszer

Az egyenletek megoldásának problémája megfogalmazható gyökkeresési problémaként: , vagy fixpont megtalálásának problémájaként.

Hadd és - tömörítés: (különösen az a tény, hogy - a tömörítés, amint az könnyen belátható, azt jelenti).

Banach tétele szerint van egy egyedi fix pont

Megtalálható egy egyszerű iteratív eljárás határaként

ahol a kezdeti közelítés egy tetszőleges pont az intervallumban.

Ha a függvény differenciálható, akkor kényelmes tömörítési kritérium a szám. Valóban, a Lagrange-tétel szerint

Így, ha a derivált kisebb, mint egy, akkor az összehúzódás.

Állapot lényeges, mert ha például on , akkor nincs fix pont, pedig a derivált nullával egyenlő. A konvergencia mértéke az értékétől függ. Minél kisebb, annál gyorsabb a konvergencia.

Legyen az f(x)=0 egyenlet gyöke elválasztva a szakaszon, és f’(x) első és második deriváltja, ill. f""(x) folyamatosak és állandó előjelűek хн esetén.

Legyen az x n gyökér következő közelítése a gyökérfinomítás valamelyik lépésében . Ekkor tegyük fel, hogy a h n korrekció segítségével kapott következő közelítés , a gyökér pontos értékét eredményezi

x \u003d x n + h n. (1.2.3-6)

Számolás h n kis érték, az f(x n + h n)-t Taylor sorozatként ábrázoljuk, lineáris kifejezésekre korlátozva magunkat

f(x n + h n) "f(x n) + h n f'(x n). (1.2.3-7)

Ha figyelembe vesszük, hogy f(x) = f(х n + h n) = 0, akkor f(х n) + h n f ’(х n) » 0-t kapunk.

Ezért h n "- f (x n) / f' (x n). Cserélje ki az értéket h n(1.2.3-6)-ban és a gyökér pontos értéke helyett xújabb közelítést kapunk

Az (1.2.3-8) képlet lehetővé teszi az x 1, x 2, x 3 ... közelítések sorozatát, amely bizonyos feltételek mellett a gyök pontos értékéhez konvergál. x, vagyis

A Newton-módszer geometriai értelmezése az alábbiak
(1.2.3-6. ábra). A b szakasz jobb végét vesszük x 0 kezdeti közelítésnek, és az y \u003d f (x) függvény grafikonjának megfelelő B 0 pontjában megszerkesztünk egy érintőt. Az érintőnek az x tengellyel való metszéspontját új, pontosabb x 1 közelítésnek vesszük. Ha ezt az eljárást többször megismételjük, akkor x 0, x 1, x 2 közelítési sorozatot kaphatunk , . . ., amely a gyökér pontos értékére irányul x.

A Newton-módszer számítási képlete (1.2.3-8) geometriai konstrukcióból nyerhető. Tehát derékszögű háromszögben x 0 B 0 x 1 láb
x 0 x 1 = x 0 V 0 / tga. Tekintettel arra, hogy a B 0 pont a függvény grafikonján van f(x),és a hipotenuszt az f (x) gráf B 0 pontjában lévő érintője alkotja, azt kapjuk

(1.2.3-9)

(1.2.3-10)

Ez a képlet egybeesik az (1.2.3-8) n-edik közelítéssel.

Az 1.2.3-6. ábrából látható, hogy az a pont kezdeti közelítésként való megválasztása oda vezethet, hogy a következő x 1 közelítés azon a szakaszon kívül lesz, amelyen a gyök el van választva. x. Ebben az esetben a folyamat konvergenciája nem garantált. Általános esetben a kezdeti közelítés kiválasztása a következő szabály szerint történik: a kezdeti közelítéshez olyan x 0 н pontot kell venni, ahol f (x 0) × f '' (x 0) > 0, vagyis a függvény és második deriváltjának előjelei egyeznek.

A Newton-módszer konvergenciafeltételeit a következő tétel fogalmazza meg.

Ha az egyenlet gyökét a szakaszon elválasztjuk, és f'(x 0) és f''(x) eltérnek a nullától, és megtartják előjeleiket xo, akkor ha egy ilyen pontot választunk kezdeti közelítésnek x 0 О , mit f(x 0).f¢¢(x 0)>0 , akkor az egyenlet gyöke f(x)=0 bármilyen pontossággal kiszámítható.

A Newton-módszer hibabecslését a következő kifejezés határozza meg:

(1.2.3-11)

hol a legkisebb érték nál nél

Legmagasabb érték nál nél

A számítási folyamat leáll, ha ,

hol van a megadott pontosság.

Ezenkívül a gyökér Newton-módszerrel történő finomítása során a következő kifejezések feltételül szolgálhatnak egy adott pontosság eléréséhez:

A Newton-módszer algoritmusának sémája az ábrán látható. 1.2.3-7.

Az eredeti f(x) egyenlet bal oldala és származéka f'(x) az algoritmusban külön szoftvermodulként van kialakítva.

Rizs. 1.2.3-7. Newton-módszer algoritmus diagramja

1.2.3-3. példa Finomítsa az x-ln(x+2) = 0 egyenlet gyökét a Newton-módszerrel, feltéve, hogy ennek az egyenletnek a gyökerei el vannak választva az x 1 н[-1.9;-1.1] szakaszokon. és x 2 н [-0,9;2].

Az f'(x) = 1 - 1 / (x + 2) első deriváltja minden szegmensen megtartja előjelét:

f'(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 xО-nél [-0,9; 2].

A második derivált f "(x) \u003d 1 / (x + 2) 2\u003e 0 bármely x esetén.

Így a konvergencia feltételei teljesülnek. Mivel f "" (x)> 0 a megengedett értékek teljes tartományában, akkor a gyökér finomítása a kezdeti közelítéshez x 1 válassza az x 0 \u003d -1,9 értéket (mivel f (-1,9) × f ”(-1,9)> 0). A közelítések sorozatát kapjuk:

A számításokat folytatva az első négy közelítésből a következő sorrendet kapjuk: -1,9; –1,8552, -1,8421; -1,8414 . Az f(x) függvény értéke az x=-1,8414 pontban egyenlő: f(-1,8414)=-0,00003 .

Az x 2 н[-0.9;2] gyök finomításához a 0 =2 (f(2)×f”(2)>0 kezdeti közelítést választjuk. Az x 0 = 2 alapján egy közelítési sorozatot kapunk: 2,0; 1,1817; 1,1462; 1.1461. Az f(x) függvény értéke az x=1,1461 pontban egyenlő: f(1,1461)= -0,00006.

Newton módszerének nagy a konvergencia rátája, de minden lépésben nem csak a függvény értékét, hanem deriváltját is ki kell számítani.

akkordmódszer

Az akkordmódszer geometriai értelmezése az alábbiak
(1.2.3-8. ábra).

Rajzoljunk egy egyenes szakaszt az A és B pontokon keresztül. A következő x 1 közelítés a húr 0x tengellyel való metszéspontjának abszcissza. Szerkesszük meg az egyenes szakasz egyenletét:

Tegyük fel y=0-t, és keressük meg az x=x 1 értéket (egy másik közelítés):

Megismételjük a számítási folyamatot, hogy megkapjuk a következő közelítést a gyökérhez - x 2 :

Esetünkben (1.2.11. ábra) és az akkordmódszer számítási képlete így fog kinézni

Ez a képlet akkor érvényes, ha a b pontot fix pontnak vesszük, és az a pont kezdeti közelítésként működik.

Tekintsünk egy másik esetet (1.2.3-9. ábra), amikor .

Az egyenes egyenletnek ebben az esetben a formája van

A következő közelítés x 1 y = 0-nál

Ekkor az akkordmódszer rekurzív képlete ebben az esetben a következővel rendelkezik

Megjegyzendő, hogy az akkordok módszerében a fix ponthoz válassza ki a szakasz végét, amelyre az f (x)∙f¢¢ (x)>0 feltétel teljesül.

Így ha az a pontot fix pontnak vesszük , akkor x 0 = b kezdeti közelítésként működik, és fordítva.

Az f(x)=0 egyenlet gyökének akkordok képletével történő kiszámítását biztosító elegendő feltétel ugyanaz lesz, mint a tangens módszernél (Newton-módszer), de a kezdeti közelítés helyett egy fix pontot választunk. Az akkordmódszer a Newton-módszer egy módosítása. A különbség az, hogy a következő közelítés a Newton-módszerben az érintő metszéspontja a 0X tengellyel, a húrok módszerében pedig - az akkord metszéspontja a 0X tengellyel - a közelítések a gyökérhez konvergálnak. különböző oldalak.

Az akkordmódszer hibájának becslését a kifejezés határozza meg

(1.2.3-15)

Az iterációs folyamat befejezési feltétele akkordok módszerével

(1.2.3-16)

Ha M 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Példa 1.2.3-4. Adja meg az e x - 3x = 0 egyenlet gyökerét, 10 -4 pontosságú szakaszon elválasztva.

Tekintsük a konvergencia feltételét:

Ezért a=0-t kell fix pontnak választani, és x 0 \u003d 1-et kell venni kezdeti közelítésnek, mivel f (0) \u003d 1> 0 és f (0) * f "(0)> 0 .

Newton (tangens) módszere a gyökerek megtalálására

Ez egy iteratív módszer Isaac Newton(Isaak Newton) 1664 körül. Ezt a módszert azonban néha Newton-Raphson módszernek (Raphson) is nevezik, mivel Raphson néhány évvel később találta fel ugyanazt az algoritmust, mint Newton, de dolgozata jóval korábban jelent meg.

A feladat a következő. Adott az egyenlet:

Ezt az egyenletet meg kell oldani, pontosabban meg kell találni az egyik gyökerét (feltételezzük, hogy a gyök létezik). Feltételezzük, hogy folytonos és differenciálható a szegmensen.

Algoritmus

Az algoritmus bemeneti paramétere a függvényen kívül még az kezdeti közelítés- néhány , ahonnan elindul az algoritmus.

Legyen már kiszámítva, számoljon a következőképpen. Rajzoljunk egy érintőt a függvény grafikonjára a pontban, és keressük meg ennek az érintőnek az x tengellyel való metszéspontját. állítsa egyenlőnek a talált ponttal, és ismételje meg az egész folyamatot az elejétől.

Könnyen beszerezhető a következő képlet:

Intuitív módon egyértelmű, hogy ha a függvény elég "jó" (sima), és elég közel van a gyökérhez, akkor még közelebb lesz a kívánt gyökérhez.

A konvergencia mértéke az négyzetes, ami relatíve azt jelenti, hogy a közelítő értékben lévő pontos bitek száma minden iterációval megduplázódik.

Alkalmazás a négyzetgyök kiszámításához

Tekintsük Newton módszerét a négyzetgyök kiszámításának példájával.

Ha behelyettesítjük, akkor a kifejezés egyszerűsítése után a következőt kapjuk:

A probléma első tipikus változata az, amikor egy törtszámot adunk meg, és bizonyos pontossággal kell kiszámítani a gyökerét:

kettős n; cin >> n; const dupla EPS = 1E-15 ; dupla x = 1 ; for (;; ) ( double nx = (x + n / x) / 2 ; if (abs (x - nx)< EPS) break ; x = nx; } printf ("%.15lf" , x) ;

A probléma másik gyakori változata az, amikor az egész szám gyökjét akarjuk kiszámítani (adott gyökérnél keressük meg a legnagyobbat, amely ). Itt kicsit módosítanunk kell az algoritmus leállási feltételét, mert előfordulhat, hogy a válasz közelében "ugrálni" kezd. Ezért adunk hozzá egy feltételt, hogy ha az előző lépésnél az érték csökkent, az aktuális lépésnél pedig próbál növekedni, akkor az algoritmust le kell állítani.

intn; cin >> n; int x = 1; bool csökkent = false ; for (;; ) ( int nx = (x + n / x) >> 1 ; if (x == nx || nx > x && csökkentve) törés ; csökkentett = nx< x; x = nx; } cout << x;

Végül adunk egy harmadik lehetőséget - hosszú aritmetika esetén. Mivel a szám meglehetősen nagy lehet, érdemes odafigyelni a kezdeti közelítésre. Nyilvánvaló, hogy minél közelebb van a gyökérhez, annál gyorsabban érhető el az eredmény. Meglehetősen egyszerű és hatékony lesz kezdeti közelítésként a számot venni, ahol a szám bitjeinek száma. Itt van a Java kód, amely bemutatja ezt a lehetőséget:

BigIntegern; // beviteli adat BigInteger a = BigInteger.ONE .shiftLeft (n.bitLength () / 2 ) ; logikai érték p_dec = false ; for (;; ) ( BigInteger b = n.oszt (a) .add (a) .shiftRight (1 ) ; if (a.comareTo (b) == 0 || a.compareTo (b)< 0 && p_dec) break ; p_dec = a.compareTo (b) >0; a = b; )

Például a kódnak ez a változata egy számon fut ezredmásodpercben, és ha eltávolítja a kezdeti közelítés továbbfejlesztett beállítását (csak kezdje a -val), akkor körülbelül ezredmásodperc alatt fut le.

Az iskolában a matematikaórákon egyenletek megoldásán kínlódva sok diák gyakran biztos abban, hogy pazarolja az idejét, de egy ilyen készség nem csak azoknak válik jól az életben, akik úgy döntenek, hogy Descartes, Euler vagy Lobacsevszkij nyomdokaiba lépnek. .

A gyakorlatban például az orvostudományban vagy a közgazdaságtanban gyakran előfordulnak olyan helyzetek, amikor a szakembernek azt kell kiderítenie, hogy egy adott gyógyszer hatóanyagának koncentrációja mikor éri el a kívánt szintet a beteg vérében, vagy szükséges az idő kiszámítása. szükséges ahhoz, hogy egy adott vállalkozás nyereséges legyen.

Leggyakrabban különféle típusú nemlineáris egyenletek megoldásáról beszélünk. Ezt a lehető leggyorsabban megtenni, különösen számítógépek használatával, a numerikus módszerek lehetővé teszik. Jól tanulmányozták, és régóta bizonyítják hatékonyságukat. Ezek közé tartozik a Newton-tangens módszer, amely a cikk tárgya.

A probléma megfogalmazása

Ebben az esetben van egy g függvény, amely az (a, b) szakaszon van megadva, és bizonyos értékeket vesz fel rajta, azaz minden egyes x-hez, amelyhez tartozik egy adott g (x) szám társítható. a, b).

Az a és b pontok közötti intervallumból (beleértve a végeket is) meg kell határozni az egyenlet összes gyökerét, amelyre a függvény nullára van állítva. Nyilvánvalóan ezek lesznek az y = g(x) és az OX metszéspontjai.

Bizonyos esetekben célszerűbb a g(x)=0 helyett egy hasonlót, g 1 (x) = g 2 (x). Ebben az esetben a g 1 (x) és g 2 (x) gráfok metszéspontjainak abszcisszái (x érték) gyökként működnek.

A nemlineáris egyenlet megoldása optimalizálási feladatoknál is fontos, amelyeknél a lokális szélsőség feltétele egy függvény deriváltjának 0-ra való átalakítása. Más szavakkal, egy ilyen probléma levezethető a p(x) = 0 egyenlet gyökeinek megtalálására, ahol p(x) azonos g"(x)-vel.

Megoldási módszerek

Bizonyos típusú nemlineáris egyenleteknél, például négyzetes vagy egyszerű trigonometrikus egyenleteknél, a gyökök meglehetősen egyszerű módon kereshetők. Különösen minden diák ismeri a képleteket, amelyek segítségével könnyen megtalálhatja azon pontok argumentumának értékét, ahol a négyzetes trinomit nullázzák.

A nemlineáris egyenletek gyökereinek kinyerésére szolgáló módszereket általában analitikus (direkt) és iteratív módszerekre osztják. Az első esetben a kívánt megoldás egy képlet formájú, amelynek segítségével bizonyos számú aritmetikai műveletben megtalálhatja a kívánt gyök értékét. Hasonló módszereket fejlesztettek ki exponenciális, trigonometrikus, logaritmikus és elemi algebrai egyenletekre is. A többihez speciális numerikus módszereket kell alkalmazni. Könnyen megvalósíthatók számítógépek segítségével, amelyek lehetővé teszik a gyökerek megtalálását a szükséges pontossággal.

Ezek közé tartozik az úgynevezett numerikus érintőmódszer, amelyet a nagy tudós, Isaac Newton javasolta a 17. század végén. A következő évszázadokban a módszert többször is tökéletesítették.

Lokalizálás

Az analitikai megoldást nem tartalmazó összetett egyenletek megoldásának numerikus módszereit általában 2 lépésben hajtják végre. Először lokalizálnia kell őket. Ez a művelet abból áll, hogy az OX-en olyan szegmenseket keresünk, amelyeken a megoldandó egyenlet egyik gyöke van.

Tekintsünk egy szegmenst. Ha a rajta lévő g(x)-nek nincsenek megszakadásai, és különböző előjelű értékeket vesz fel a végpontokban, akkor a és b között vagy önmagukban legalább 1 gyöke van a g(x) = 0 egyenletnek. legyen egyedi, akkor g(x) monotonnak kell lennie. Mint ismeretes, akkor lesz ilyen tulajdonsága, ha g’(x) állandó előjelű.

Más szóval, ha g(x)-nek nincsenek megszakadásai, és monoton nő vagy csökken, és a végponti értékei nem azonos előjelűek, akkor 1 és csak 1 gyök van g(x).

Ebben az esetben tudnia kell, hogy ez a feltétel nem működik a többszörös egyenletek gyökére.

Az egyenlet megoldása felezéssel

Mielőtt megvizsgálnánk a bonyolultabb numerikus érintőket és fajtáit), érdemes megismerkedni a gyökerek azonosításának legegyszerűbb módjával. Ezt dichotómiának nevezik, és a gyökök intuitív megtalálására utal azon a tételen alapuló, hogy ha g (x) esetén folytonos be, különböző előjelek feltétele teljesül, akkor a vizsgált szakaszon legalább 1 gyökér g ( x) = 0.

Ennek megtalálásához fel kell osztani a szakaszt, és a felezőpontot x 2-vel kell kijelölni. Ekkor két lehetőség lehetséges: g (x 0) * g (x 2) vagy g (x 2) * g (x 1) egyenlő vagy kisebb, mint 0. Azt választjuk, amelyikre igaz az egyenlőtlenségek közül. A fent leírt eljárást addig ismételjük, amíg a hossz kisebb lesz egy bizonyos, előre kiválasztott értéknél, amely meghatározza az egyenlet gyökének meghatározásának pontosságát a -n.

A módszer előnyei között szerepel a megbízhatóság és az egyszerűség, hátránya pedig az, hogy kezdetben azonosítani kell azokat a pontokat, ahol g (x) különböző előjeleket vesz fel, így nem használható akár többszörös gyökökhöz. Ezenkívül nem általánosít egyenletrendszerre vagy összetett gyökökre.

1. példa

Meg akarjuk oldani a g(x) = 2x 5 + x - 1 = 0 egyenletet. Hogy ne keressünk sokáig megfelelő szegmenst, készítünk egy gráfot például a jól ismert Excel programmal. . Azt látjuk, hogy jobb az intervallum értékeit szegmensként venni a gyökér lokalizálásához. Biztosak lehetünk benne, hogy a kívánt egyenletnek legalább egy gyöke létezik rajta.

g "(x) \u003d 10x 4 + 1, azaz ez egy monoton növekvő függvény, ezért csak 1 gyökér van a kiválasztott szegmensen.

Helyettesítsd be a végpontokat az egyenletbe. Nálunk 0 és 1 van. Első lépésben a 0,5 pontot vesszük megoldásnak. Ekkor g(0,5) = -0,4375. Tehát a következő szegmens a felére osztva lesz. Felezőpontja 0,75. Ebben a függvény értéke 0,226. Figyelembe vesszük a szakaszt és felezőpontját, amely a 0,625 pontban található. Számítsa ki g(x) értékét 0,625-re! Ez egyenlő -0,11, azaz negatív. Ezen eredmény alapján választjuk ki a szegmenst. Azt kapjuk, hogy x = 0,6875. Ekkor g(x) = -0,00532. Ha a megoldás pontossága 0,01, akkor feltételezhetjük, hogy a kívánt eredmény 0,6875.

Elméleti alap

Ez a Newton-tangens módszerrel végzett gyökérkeresési módszer nagyon gyors konvergenciája miatt népszerű.

Ez azon a bizonyított tényen alapszik, hogy ha x n egy f(x)=0 gyök közelítése úgy, hogy f" C 1 , akkor a következő közelítés azon a ponton lesz, ahol az f(x) érintőjének egyenlete eltűnik. , azaz

Helyettesítse x = x n+1 értékét, és állítsa y-t nullára.

Ekkor az érintő így néz ki:

2. példa

Próbáljuk meg a klasszikus Newton-tangens módszert használni, és találjunk megoldást néhány nemlineáris egyenletre, amelyet analitikusan nehéz vagy lehetetlen megtalálni.

Legyen megkövetelve az x 3 + 4x - 3 = 0 gyökeinek bizonyos pontosságú feltárása, például 0,001. Mint ismeretes, bármely függvény grafikonjának páratlan fokú polinom formájában legalább egyszer kereszteznie kell az OX tengelyt, azaz nincs okunk kételkedni a gyökök létezésében.

Mielőtt a példánkat az érintő módszerrel megoldanánk, pontról pontra ábrázoljuk f (x) \u003d x 3 + 4x - 3. Ez nagyon könnyen megtehető például egy Excel-táblázat használatával. A kapott grafikonból látható, hogy metszi az OX tengellyel, és az y \u003d x 3 + 4x - 3 függvény monoton növekszik. Biztosak lehetünk abban, hogy az x 3 + 4x - 3 = 0 egyenletnek van megoldása, és az egyedi.

Algoritmus

Az egyenletek érintőmódszeres megoldása f "(x) kiszámításával kezdődik.

Ekkor a második derivált így fog kinézni: x * 6.

Ezekkel a kifejezésekkel írhatunk egy képletet az egyenlet gyökereinek azonosítására a tangens módszerrel a következő formában:

Ezután ki kell választani egy kezdeti közelítést, azaz meg kell határozni, hogy melyik pontot tekintsük az iteratív folyamat kiindulópontjának (rev. x 0). Figyelembe vesszük a szegmens végeit. Számunkra az alkalmas, amelyre igaz a függvény feltétele és 2. deriváltja x 0-nál. Amint láthatja, az x 0 = 0 helyettesítésekor ez megsérül, de az x 0 = 1 teljesen megfelelő.

akkor ha az e pontosságú érintők módszerével történő megoldás érdekel bennünket, akkor x n értéke a feladat követelményeit kielégítőnek tekinthető, feltéve, hogy az |f(x n) / f’(x n)|< e.

Az érintők első lépésében a következőket kapjuk:

• x 1 \u003d x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) \u003d 1 - 0,2857 \u003d 0,71429;
• mivel a feltétel nem teljesül, tovább megyünk;
• új értéket kapunk x 2-re, ami 0,674;
• észrevesszük, hogy a függvény értékének és deriváltjának aránya x 2-ben kisebb, mint 0,0063, leállítjuk a folyamatot.

Tangens módszer Excelben

Az előző példát sokkal könnyebben és gyorsabban tudod megoldani, ha nem manuálisan (számológépen) végezsz számításokat, hanem a Microsofttól származó táblázatkezelő processzor lehetőségeit használod.

Ehhez az Excelben új oldalt kell létrehoznia, és a celláit a következő képletekkel kell kitöltenie:

• a C7-ben ezt írjuk: "= POWER (B7; 3) + 4 * B7 - 3";
• a D7-be írjuk be: "= 4 + 3 * DEGREE (B7; 2)";
• az E7-ben a következőt írjuk: "= (POWER (B7; 3) - 3 + 4 * B7) / (3 * POWER (B7; 2) + 4)";
• a D7-ben beírjuk a "= B7 - E7" kifejezést;
• a B8-ban beírjuk a „= HA” képlet-feltételt (E7< 0,001;"Завершение итераций"; D7)».

Egy adott feladatban, már a B10-es cellában, megjelenik az „Iterációk befejezése” felirat, és a probléma megoldásához fel kell vennie az egy sorral feljebb lévő cellába írt számot. Ehhez egy külön „nyújtható” oszlopot is kiválaszthatunk egy feltételes képlet beírásával, amely szerint oda írjuk az eredményt, ha a B oszlop egyik vagy másik cellájában a tartalom „Iterációk befejezése” formát ölt.

Megvalósítás Pascalban

Próbáljuk meg az y = x 4 - 4 - 2 * x nemlineáris egyenlet megoldását Pascal tangens módszerével.

Segédfüggvényt használunk, amely segít az f "(x) \u003d (f (x + delta) - f (x)) / delta közelítő számítás elvégzésében. Az iteratív folyamat befejezésének feltételeként a következőt választjuk: az egyenlőtlenség teljesítése |x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

A program figyelemre méltó, hogy nem igényli a derivált manuális kiszámítását.

akkordmódszer

Vegyünk egy másik módszert a nemlineáris egyenletek gyökereinek azonosítására. Az iterációs folyamat abból áll, hogy az f(x)=0 kívánt gyökének egymás utáni közelítéseként a húr metszéspontjainak értékeit az a és b végpontok abszcisszáival OX-al veszik. , jelölése x 1 , ..., x n . Nekünk van:

Abban a pontban, ahol az akkord metszi az OX tengellyel, a kifejezés a következőképpen lesz írva:

Legyen a második derivált pozitív x £-ra (az ellenkező esetet a vizsgált esetre redukáljuk, ha f(x) = 0-t írunk le). Ebben az esetben az y \u003d f (x) gráf egy alul konvex görbe, amely az akkord alatt helyezkedik el. AB. 2 eset lehet: amikor a függvény pozitív az a pontban vagy negatív a b pontban.

Az első esetben az a végét választjuk fixnek, és a b pontot vesszük x 0-ra. Ekkor az egymást követő közelítések a fent bemutatott képlet szerint monoton csökkenő sorozatot alkotnak.

A második esetben a b vége x 0 = a helyen van rögzítve. Az egyes iterációs lépésekben kapott x értékek monoton növekvő sorozatot alkotnak.

Így kijelenthetjük, hogy:

• az akkordok módszerében a szakasznak az a vége fix, ahol a függvény és második deriváltjának előjele nem esik egybe;
• az x - x m - gyök közelítései azon az oldalon fekszenek, ahol f (x) előjele nem esik egybe f "" (x) előjelével.

Az iterációkat addig lehet folytatni, amíg a gyökök közelségének feltételei nem teljesülnek ennél és az előző iterációs lépésnél modulo abs(x m - x m - 1)< e.

Módosított módszer

Az akkordok és érintők kombinált módszere lehetővé teszi az egyenlet gyökereinek megállapítását, különböző oldalakról megközelítve őket. Egy ilyen érték, amelynél az f(x) gráf metszi az OX-et, sokkal gyorsabban teszi lehetővé a megoldás finomítását, mintha az egyes módszereket külön-külön használnánk.

Tegyük fel, hogy meg kell találnunk az f(x)=0 gyököket, ha léteznek a -n. A fent leírt módszerek bármelyikét használhatja. Azonban jobb, ha kipróbáljuk ezek kombinációját, ami jelentősen növeli a gyökér pontosságát.

Az esetet egy kezdeti közelítéssel vizsgáljuk, amely megfelel annak a feltételnek, hogy az első és a második derivált eltérő előjelű egy adott x pontban.

Ilyen körülmények között a nemlineáris egyenletek tangens módszerrel történő megoldása lehetővé teszi, hogy találjunk egy gyököt többlettel, ha x 0 =b, és a b fix végén lévő akkordokat használó módszer hátrányos közelítő gyökér megtalálásához vezet.

Felhasznált képletek:

Most a kívánt x gyökért kell keresni az intervallumban. A következő lépésben már erre a szegmensre kell alkalmazni a kombinált módszert. Így eljárva a következő képleteket kapjuk:

Ha az első és a második származék között előjelkülönbség van, akkor hasonló módon érvelve a gyök finomításához a következő rekurzív képleteket kapjuk:

Feltételként a becsült egyenlőtlenség | b n +1 - a n +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

Ha a fenti egyenlőtlenség igaz, akkor a nemlineáris egyenlet gyökének egy pontot veszünk egy adott intervallumon, amely pontosan középen van az adott iterációs lépésben talált megoldások között.

A kombinált módszer könnyen megvalósítható a TURBO PASCAL környezetben. Erős vágy esetén megpróbálhatja az összes számítást táblázatos módszerrel elvégezni az Excel programban.

Ez utóbbi esetben több oszlopot választanak ki a probléma akkordokkal történő megoldására és külön az Isaac Newton által javasolt módszerre.

Ebben az esetben az egyes sorokat a számítások rögzítésére használják egy adott iteratív lépésben két módszer esetében. Ezután a megoldási terület bal oldalán, az aktív munkalapon egy oszlop van kiemelve, amelyben az egyes módszerekre beírják a következő iterációs lépés értékei közötti különbség moduljának kiszámításának eredményét. Egy másikkal a számítási eredményeket lehet megadni az „IF” logikai konstrukció számítási képlete szerint, amellyel megállapítható, hogy a feltétel teljesül-e vagy sem.

Most már tudja, hogyan kell összetett egyenleteket megoldani. A tangens módszer, amint azt már láthatta, meglehetősen egyszerűen implementálható, mind Pascalban, mind Excelben. Ezért mindig meg lehet határozni egy nehezen vagy egyáltalán nem megoldható egyenlet gyökerét képletekkel.

Ugyanaz, mint a közelítés. A P. kifejezést néha közelítő objektum értelmében használják (például a kezdeti P.) ... Matematikai Enciklopédia

Newton módszere- A Newton-módszer, a Newton-algoritmus (más néven tangens módszer) egy iteratív numerikus módszer egy adott függvény gyökének (nulla) meghatározására. A módszert először Isaac Newton angol fizikus, matematikus és csillagász javasolta ... ... Wikipédia

Egy érintő módszer

Gauss-Newton módszer- A Newton-módszer (más néven tangens módszer) egy iteratív numerikus módszer egy adott függvény gyökének (nulla) meghatározására. A módszert először Isaac Newton angol fizikus, matematikus és csillagász (1643, 1727) javasolta ... ... Wikipédia néven.

Newton-Raphson módszer- A Newton-módszer (más néven tangens módszer) egy iteratív numerikus módszer egy adott függvény gyökének (nulla) meghatározására. A módszert először Isaac Newton angol fizikus, matematikus és csillagász (1643, 1727) javasolta ... ... Wikipédia néven.

Newton - Raphson módszer- A Newton-módszer (más néven tangens módszer) egy iteratív numerikus módszer egy adott függvény gyökének (nulla) meghatározására. A módszert először Isaac Newton angol fizikus, matematikus és csillagász (1643, 1727) javasolta ... ... Wikipédia néven.

Érintő módszer- A Newton-módszer (más néven tangens módszer) egy iteratív numerikus módszer egy adott függvény gyökének (nulla) meghatározására. A módszert először Isaac Newton angol fizikus, matematikus és csillagász (1643, 1727) javasolta ... ... Wikipédia néven.

Tangens módszer (Newton-módszer)- A Newton-módszer (más néven tangens módszer) egy iteratív numerikus módszer egy adott függvény gyökének (nulla) meghatározására. A módszert először Isaac Newton angol fizikus, matematikus és csillagász (1643, 1727) javasolta ... ... Wikipédia néven.

Érintő módszer- A Newton-módszer (más néven tangens módszer) egy iteratív numerikus módszer egy adott függvény gyökének (nulla) meghatározására. A módszert először Isaac Newton angol fizikus, matematikus és csillagász (1643, 1727) javasolta ... ... Wikipédia néven.

Egyenletek numerikus megoldása- és rendszereik egy egyenlet vagy egyenletrendszer gyökének vagy gyökereinek közelítő meghatározásából állnak, és olyan esetekben használatosak, amikor lehetetlen vagy nagyon időigényes a pontos érték kiszámítása. Tartalom 1 Feladatfelvetés 2 Numerikus módszerek ... Wikipédia

Szekvenciális közelítési módszer- egy módszer matematikai problémák megoldására olyan közelítési sorozat felhasználásával, amely egy megoldáshoz konvergál és ismétlődően épül fel (azaz minden új közelítést az előző alapján számítanak ki; a kezdeti közelítést a ... ... Nagy szovjet enciklopédia