Absztrakt módszer Newton
Összefoglaló a témáról:
-
bevezetés
- 1 A módszer leírása
- 1.1 Indoklás
- 1.2 Geometriai értelmezés
- 1.3 algoritmus
- 1.4 példa
- 2. Üzemi feltételek
- 2.1 ellenpéldák
- 2.2 Korlátozások
- 3. Háttér
- 4. bővítmények és módosítások
- 4.1 Eljárás egy érintő
- 4.2 A többdimenziós esetben
- 4.3 Ami a optimalizálási problémák
- 4.4 Newton-módszer - Raphson
- 4.5 Ami a problémák a legkisebb négyzetek
- 4.6 Gauss - Newton módszer
- 4.7 Általánosítás komplex síkban
jegyzetek
Newton-módszer. Newton algoritmus (más néven az érintőleges módszer) - iteratív numerikus módszert kell találni a gyökér (nulla) az adott funkciót. A módszert először javasolta az angol fizikus, matematikus és csillagász Sir Isaac Newton (1643-1727) néven, amelynek tett szert hírnévre. Keresés megoldások végzi az épület egy sorozatos közelítési és elvek alapján egyszerű iteráció. Az eljárás másodfokú konvergenciát. Egy jobb módszer az a módszer, az akkordokat, és érintők. Továbbá, Newton módszer használható megoldani optimalizálási problémákat, hogy meg kell határozni a nulla első deriváltja a gradiens esetén a többdimenziós térben.
1. A módszer leírása
1.1. logika
Ahhoz, hogy számszerűen egyenlet megoldásához egyszerű iteráció azt kell eredményeznie az alábbi formában: ahol - összehúzódás feltérképezése.
A legjobb módszer konvergenciáját a következő megközelítést kell eleget tenni. Az oldatot ez az egyenlet kérik formájában, majd a:
Feltételezve, hogy a menetnél „elég közel” a gyökér, és egy adott függvény folytonos, a végső képlet erre:
Tekintettel erre a funkció által adott kifejezést:
Ez a funkció a környéken a gyökér végez kompressziós térkép [1]. és egy algoritmust megtalálásához a numerikus egyenlet megoldása csökkenti, hogy iteratív számítási eljárás:
By Banach-tétel szekvenciájának közelítések elkötelezett a gyökere az egyenlet.
Illusztráció Newton-módszer (kék funkcióját mutatja, amely ahhoz szükséges, hogy megtalálják nulla, piros - az érintő a következő közelítés). Itt azt látjuk, hogy a közelítés jobb, mint az utolsó.
1.2. geometriai értelmezése
Az alapötlet az eljárás a következő: egy kezdeti közelítését közelében helyezkedik feltételezett gyökér, majd épített pontját érintő a függvény közelítés, amely a metszéspontig abszcisszán. Ez a pont veszik, mint a következő közelítés. És így tovább, amíg a kívánt pontosság érhető el.
Let - meghatározott intervallumon és differenciálható valós függvény rajta. Ezután a képlet az iteratív közelítéseket lehet levezetni a következőképpen:
ahol α - hajlásszöge az érintő egy ponton.
Ezért a kívánt expressziós a formában:
Az iteratív folyamat kezdődik, néhány kezdeti közelítés x0 (minél közelebb a nullához, annál jobb, de ha a feltételezés, hogy megoldást találjanak elérhető, próbálgatással, szűkítheti a lehetséges értéket, a tétel a köztes értékek).
1.3. algoritmus
- Beállítja a kezdeti közelítését x0.
- Amíg a stop feltétel teljesül, ahol lehet venni, vagy (azaz a hiba a kívánt tartományban), kiszámítja az új megközelítés :.
1.4. példa
Ábrák egy alkalmazása Newton módszerét az f (x) = cosx - x 3 kezdeti közelítését pont X0 = 0,5.
Az eljárás szerint a meghatározására gyakorlati konvergencia sebességét meg lehet becsülni, mint a lejtőn a grafikon a konvergencia, azaz ebben az esetben a két.
Tekintsük a probléma megtalálni a pozitív x. amelyre x = cosx 3. Ez is képviselteti magát a probléma megtalálni a nulla függvény f (x) = cosx - x 3 Van egy kifejezés a származékos f „(x) = - sinx - 3x 2. Mivel minden x és x 3> 1 x> 1. nyilvánvaló, hogy a megoldás abban rejlik 0 és 1 között Vegyük kezdeti közelítését értéket x0 = 0,5. akkor:
Az aláhúzás jelöli a helyes számjeggyel. Nyilvánvaló, hogy ezek száma növekszik lépésről-lépésre (hozzávetőleg kétszeres ahol mindegyik lépés): 1-2, 2-5, 5-10, amely szemlélteti a kvadratikus konvergencia sebességét.
2. A használat feltételei
Illusztráció divergencia Newton módszer alkalmazható egy kezdeti közelítését funkciót a ponton.
Tekintsük több példát a módszer jelzésére hibák.
2.1. ellenpéldák
- Ha a kezdeti közelítését elég közel az oldathoz, akkor a módszer nem konvergálnak.
Vegyünk nulla kezdeti közelítését. Az első iteráció ad közelítő egységet. Másfelől, a második ad újabb nulla. A módszer hurok és a megoldás nem található. Általában, az építési sorozata közelítések is nagyon zavaró.
A grafikon differenciálhányados nullát megközelítő a jobb oldalon.
- Ha a származékos termék nem folyamatos a gyökér, az eljárás széttarthatnak minden környéken a gyökér.
Majd mindenhol, kivéve 0.
A környéken a gyökér a származékos előjelet a megközelítés x nullára jobbra vagy balra. Abban az időben, mindkettő.
Így nem korlátozódik a közelében a gyökér, és a módszer eltérnek, bár a funkció mindenütt differenciálható, annak származéka nem nulla a gyökér, fokozatmentesen differenciálható mindenütt, kivéve a gyökér, és annak származéka korlátozott közelében a gyökér.
- Ha nincs második deriváltja a gyökér, akkor a konvergencia sebessége a módszer jelentősen meg lehet csökkenteni.
Aztán, kivéve, ha nincs definiálva.
A következő lépésben már:
A konvergencia sebessége a kapott szekvencia körülbelül 4/3. Ez lényegesen kevesebb, mint 2, a kívánt négyzetes konvergencia, így ebben az esetben beszélhetünk csak lineáris konvergencia, bár a funkció folyamatosan differenciálható mindenhol, a származékos termék nem nulla a gyökér és végtelenül differenciálható kivételével mindenhol a gyökér.
- Ha a származék a ponton a gyökér nullával egyenlő, a konvergencia sebessége lesz másodfokú, és az eljárás idő előtt felmondani a keresést, és így a rossz megközelítés egy adott pontossággal.
Akkor és így. Így a konvergencia az eljárás nem kvadratikus és lineáris, bár a funkció végtelenül differenciálható mindenhol.
2.2. korlátozások
Legyen adott az egyenletet, ahol meg kell találni a megoldást.
Az alábbiakban egy nyilatkozatot a fő tétel, mely lehetővé teszi, hogy törölje a feltételek alkalmazhatóságát. Ez nevezték szovjet matematikus és közgazdász, Nobel-díjas közgazdász, 1975-ben „az ő hozzájárulása az elméleti optimális forráselosztás” Kantorovich Kantorovich (1912-1986), és egyike a számos elmélet keletkezett az ő tudományos kutatás.
Ha vannak állandók, hogy:
- be, vagyis van nem nulla;
- on, hogy a korlátozott;
- tovább, és;
És a hossza a szegmens vizsgálják. Ekkor a következő állítások igazak:
- Van a gyökere az egyenlet;
- ha az iteratív szekvencia konvergál ez a gyökér :;
- hiba lehet becsülni a képlet.
Az utolsó tétel állítása különösen fontos, hogy legyen egy négyzetes módszer konvergenciáját:
Ezután az eredeti funkciót korlátozásokat fog kinézni:
- funkciót kell korlátozni;
- funkciót kell sima, kétszer differenciálható;
- az első származékok egyenletesen korlátos távol nulla;
- második deriváltja egyenletesen kell korlátozni.
3. Háttér
1879-ben Arthur Cayley tanulmányában: „A probléma komplex számok Newton - Fourier” (. Angol «A Newton-Fourier képzeletbeli probléma») volt az első, aki megjegyezte, hogy nehéz általánosítani Newton módszerét az esetben a képzeletbeli gyökerei polinomokként magasabb, mint a második és első átfogó közelítés. Ez a munka kövezte ki az utat a tanulmány az elmélet a fraktálok.
4. bővítmények és módosítások
Illusztráció a szukcesszív approximáció módszert egy tangens alkalmazott kezdeti közelítését funkciót a ponton.
4.1. Módszer audio tangens
Annak érdekében, hogy csökkentsék a számos hivatkozás értékek a függvény deriváltját használjuk módszerrel úgynevezett egy érintő.
Formula iterációk e módszer a következő:
A módszer lényege az, hogy kiszámítja egy származéka csak egyszer, egy kezdeti közelítését, majd ezt az értéket minden következő iterációban:
Egy ilyen választás a ponton az egyenlőség:
és ha a szegmens, amelyben azt feltételezzük, a jelenléte a gyökér és a kezdeti közelítését választjuk elég kicsi, és a származék folytonos, az értéke nem lesz sokban különbözik, és ezért, a grafikon kerül sor közel vízszintesen, átkelés az egyenes vonal, amely viszont biztosítja a gyors konvergenciát közelítő pontok a gyökér.
Ez a módszer is tekinthető korszerűsítési eljárás akkordok (keresztmetszetek), ahol a szám úgy kell megválasztani,
4.2. A többdimenziós esetben
Mi általánosítani ezt az eredményt a többdimenziós esetben.
Hagyja, hogy meg kell találni a megoldást, hogy a rendszer:
Kiválasztása kiindulási értéket, az egymást követő közelítések talált megoldása az egyenletrendszert:
4.3. Ami a optimalizálási problémák
Tegyük fel, hogy szeretné megtalálni a minimum egy sok változó függvénye. Ez a probléma egyenértékű a probléma megtalálni a gradiens nulla. Mi kell alkalmazni Newton-módszer fent vázolt:
ahol - a hesseni.
Egy még kényelmesebb formáját iteráció, ez a kifejezés így néz ki:
Meg kell jegyezni, hogy abban az esetben a másodfokú Newton módszer szélsőséges érték egyetlen iteráció.
Megtaláljuk a hesseni mátrix járó nagy számítási fölött, és gyakran nem lehetséges. Ilyen esetekben, az alternatív lehet kvázi-Newton módszerek, amelyekben a megközelítés a Hessian mátrixot kialakítani a folyamat felhalmozódása a görbület a funkció információt.
4.4. Newton-módszer - Raphson
Newton-módszer - Newton Raphson módszer javulást szélsőérték megállapítás a fent leírt. A fő különbség az, hogy a következő iterációs által bármely módszer egydimenziós optimalizálási kiválasztja az optimális lépés:
mellyel optimalizálja a számítás a következő javításokat: ahelyett, hogy minden egyes iteráció újra kiszámítja a hesseni a célfüggvény korlátozódik a kezdeti közelítését és frissíti azt csak egyszer a lépések vagy nem frissül egyáltalán.
4.5. Ami a problémát a legkisebb négyzetek
A gyakorlatban gyakran vannak problémák, amelyek megkövetelik a dallam nélküli objektum paramétereit, vagy illik egy matematikai modell valós adatokat. Ezekben az esetekben is vannak a probléma a legkisebb négyzetek:
E feladatok, különös tekintettel a gradiens és a hesseni:
ahol - Jacobi mátrix vektor függvények - Hesse mátrix komponensei számára is.
Ezután egy másik irányát a rendszer:
4.6. Gauss - Newton
Gauss - Newton módszer alapja az a feltételezés, hogy a tag dominál. Ez a követelmény nem teljesül, ha a minimális maradék magas, azaz, ha az arány hasonló a maximális sajátérték. Ellenkező esetben, akkor írj:
Így, amikor az arány közel nulla, és a mátrix teljes rangú stolbtsevoy irányban alig különbözik a newtoni (alany), és az eljárás eléri a kvadratikus konvergencia sebességét, bár a második származékok és nem készített. Egy jobb módszer algoritmusa Levenberg - Marquardt algoritmus alapján heurisztikus megfontolások.
4.7. Az általánosítás a komplex síkban
Newton Edények polinomja az ötödik fokozat. A különböző színek vannak árnyékolva régió vonzerejét a különböző gyökerek. Sötétebb területek megfelelnek az nagyobb számú iteráció.
Mostanáig a módszer leírását használt funkciók használt kijelző sokaságán belül a valós érték. Azonban a módszer alkalmazható találni egy nulla a komplex változó. Ebben az esetben az eljárás ugyanaz marad:
Különösen érdekes az a választás a kezdeti közelítés. Tekintettel arra, hogy a funkció több nullát, több esetben az eljárás különböző értékekhez konvergálnak, és ez teljesen természetes, hogy a vágy, hogy megtudja, melyik területeken nyújtanak konvergencia egy adott gyökér. Ez a kérdés érdekli Arthur Cayley vissza 1879-ben, de csak megoldani, hogy a 70 év a huszadik század, az Advent a számítástechnika. Kiderült, hogy a csomópontok e területek (nevezik őket doménjei vonzás) vannak kialakítva az úgynevezett fraktálok - végtelen önhasonló geometriai formák.
Mivel Newton alkalmazta a módszert csak a polinomok, fraktálok, eredményeként jött létre az ilyen használat, megszerezte a nevét Newton vagy Newton fraktálok medencék.
irodalom
jegyzetek
- Bizonyítás: Legyen a függvény egy valós változó kétszer folytonosan differenciálható, saját domain, a származék, amely sehol nulla És be is kell bizonyítani, hogy a függvény a kontrakció feltérképezése mellett a gyökere az egyenlet. Mivel egy folyamatosan differenciálható függvény és az egyenlőtlenség nullára az első deriváltját folyamatos. A származék: A vele szemben megszabott feltételek is folyamatos. Hagyja, - az előírt gyökere az egyenlet, ezért annak környékén: Akkor szerint a középérték-tétel: Tekintettel arra, hogy az egymás közelségében, a delta végezzük: így a függvény kapott a közelben a gyökér végez összehúzódás feltérképezése.