Newtonova metoda

Neka je #math2226##tex2html_wrap_inline36070# klase #tex2html_wrap_inline36072# na #tex2html_wrap_inline36074# Želimo riješiti jednadžbu #math2227#

#tex2html_wrap_indisplay36076#

Newtonova metoda, koja se često zove Newton-Raphsonova metoda ili metoda tangente, sastoji se u tome da se #tex2html_wrap_inline36078#-va aproksimacija #tex2html_wrap_inline36080# odredi kao sjecište tangente na graf funkcije #tex2html_wrap_inline36082# u točki s apscisom #tex2html_wrap_inline36084# s osi #tex2html_wrap_inline36086#
#math2228##tex2html_wrap24618#
Jednadžba tangente na graf funkcije #tex2html_wrap_inline36089# u točki #math2229##tex2html_wrap_inline36091# je #math2230#

#tex2html_wrap_indisplay36093#

Kad stavimo #tex2html_wrap_inline36095# dobijemo njezino sjecište s osi #math2231#

#tex2html_wrap_indisplay36097#

Dakle #tex2html_wrap_inline36099#-va aproksimacija se računa po formuli #math2232#

#tex2html_wrap_indisplay36101#

Time smo dobili sljedeći algoritam.

Algoritam 3   <#11949#>(Newtonova metoda)<#11949#> Izaberemo #math2233##tex2html_wrap_inline36104# i računamo niz #tex2html_wrap_inline36106# za #math2234##tex2html_wrap_inline36108# po formuli

#math2235#
#tex2html_wrap_indisplay36110# (3.8)

Ako je #math2236##tex2html_wrap_inline36112# za neki #tex2html_wrap_inline36114# onda je #tex2html_wrap_inline36116# U protivnom nastavljamo računanje daljnih članova niza.

Mathematica program 3   (Newtonova metoda)
verbatim171#

Primjer 3.5   Newtonovom metodom riješiti jednadžbu iz primjera #pr:kubna#8004>. Rješenje. Pomoću programa #prg:newtmet#8005> s početnom aproksimacijom #tex2html_wrap_inline36120# dobivamo #math2237#

#tex2html_wrap_indisplay36122#

#math2238#

#tex2html_wrap_indisplay36124#

i to je sve, jer se nakon 10 iteracija postiže strojna točnost. To pokazuje da Newtonova metoda iteracije u ovom slučaju vrlo brzo konvergira.

Primjer 3.6   Riješiti problem iz primjera #pr:transc#8010> Newtonovom metodom. Rješenje. Pomoću programa #prg:newtmet#8011> s početnom aproksimacijom #tex2html_wrap_inline36127# dobivamo #math2239#

#tex2html_wrap_indisplay36129#

Program je napravljen tako da ponavlja iteracije 100 puta ili završava postupak kad postigne strojnu točnost. Ovo pokazuje da je u ovom primjeru strojna točnost postignuta već u četvrtoj aproksimaciji.

S druge strane ako s istim programom (Newtonovom metodom) pokušamo riješiti jednadžbu #math2240#

#tex2html_wrap_indisplay36131#

počevši s #tex2html_wrap_inline36133# dobivamo #math2241##tex2html_wrap_inline36135# To pokazuje da konvergencija nije uvijek tako brza kao u prethodnim primjerima. Dapače, ako pokušamo na isti način riješiti jednadžbu #math2242#

#tex2html_wrap_indisplay36137#

počevši s #tex2html_wrap_inline36139# dobivamo redom #math2243##tex2html_wrap_inline36141# #math2244##tex2html_wrap_inline36143# #math2245##tex2html_wrap_inline36145# #math2246##tex2html_wrap_inline36147# #math2247##tex2html_wrap_inline36149# itd. Aproksimacije se sve više udaljavaju od rješenja koje je očito #tex2html_wrap_inline36151# Sljedeći teorem je jedan od mnogih koji daju dovoljne uvjete da Newtonova metoda konvergira. Uvjerite se da su uvjeti teorema ispunjeni za primjer #pr:kubnanewt#8016> na segmentu #tex2html_wrap_inline36153#

Teorem 24   Neka je #math2248##tex2html_wrap_inline36156# klase #tex2html_wrap_inline36158# i neka vrijedi
<#36179#>1.<#36179#>
#math2249##tex2html_wrap_inline36160#
<#36180#>2.<#36180#>
#math2250##tex2html_wrap_inline36162# za svaki #math2251##tex2html_wrap_inline36164#
<#36181#>3.<#36181#>
#math2252##tex2html_wrap_inline36166# ili #math2253##tex2html_wrap_inline36168# za svaki #math2254##tex2html_wrap_inline36170#
<#36182#>4.<#36182#>
ako je #tex2html_wrap_inline36172# ona rubna točka segmenta #tex2html_wrap_inline36174# u kojoj je #tex2html_wrap_inline36176# manji, onda je #math2255#

#tex2html_wrap_indisplay36178#

Tada Newtonova metoda konvergira k rješenju jednadžbe #tex2html_wrap_inline36184# za bilo koju početnu aproksimaciju #math2256##tex2html_wrap_inline36186#
<#12360#>Dokaz. Kombinirajući uvjete iz teorema, mogli bismo promatrati razne slučajeve, no može se pokazati da se svaki od njih, uzimajući #tex2html_wrap_inline36188# umjesto #tex2html_wrap_inline36190# i/ili #tex2html_wrap_inline36192# umjesto #tex2html_wrap_inline36194# može svesti na slučaj #math2257#

#tex2html_wrap_indisplay36196#

Iz 2. uvjeta i neprekidnosti funkcije #tex2html_wrap_inline36198# slijedi #tex2html_wrap_inline36200# ili #tex2html_wrap_inline36202# za svaki #math2258##tex2html_wrap_inline36204# Prema tome funkcija #tex2html_wrap_inline36206# na segmentu #tex2html_wrap_inline36208# raste ili pada. Kako je #math2259##tex2html_wrap_inline36210# funkcija #tex2html_wrap_inline36212# raste. Osim toga iz #math2260##tex2html_wrap_inline36214# slijedi da je #tex2html_wrap_inline36216# konkavna. Dakle graf funkcije #tex2html_wrap_inline36218# izgleda kao na slici
#math2261##tex2html_wrap24626#
Osim toga za proizvoljan #math2262##tex2html_wrap_inline36221# vrijedi
#math2263#

#tex2html_wrap_indisplay36223#

pa je

#math2264#
#tex2html_wrap_indisplay36225# (3.9)

tj. tangenta u bilo kojoj točki se nalazi iznad grafa funkcije #tex2html_wrap_inline36227#
Razmotrimo najprije slučaj #math2265##tex2html_wrap_inline36229# gdje je #tex2html_wrap_inline36231# jedinstveno rješenje jednadžbe #tex2html_wrap_inline36233# Za takav #tex2html_wrap_inline36235# je #math2266##tex2html_wrap_inline36237# i #math2267##tex2html_wrap_inline36239# Prema tome je
#math2268#

#tex2html_wrap_indisplay36241#

#math2269##tex2html_wrap24628#
Iz (#eq:tang#8057>) slijedi da je #math2270#

#tex2html_wrap_indisplay36244#

pa je #math2271##tex2html_wrap_inline36246# Polazeći od #tex2html_wrap_inline36248# na isti način možemo zaključiti da je #math2272##tex2html_wrap_inline36250# odnosno #math2273##tex2html_wrap_inline36252# Nastavljajući tako vidimo da je #math2274##tex2html_wrap_inline36254# Tako smo dobili rastući niz aproksimacija odozgo ograničen. Takav niz ima limes #math2275#

#tex2html_wrap_indisplay36256#

Zbog neprekidnosti funkcije #tex2html_wrap_inline36258# i njezine derivacije #tex2html_wrap_inline36260# imamo #math2276#

#tex2html_wrap_indisplay36262#

Odatle slijedi #math2277##tex2html_wrap_inline36264# pa je tako #math2278##tex2html_wrap_inline36266#
Neka je sada #tex2html_wrap_inline36268# Za #tex2html_wrap_inline36270# imamo
#math2279#

#tex2html_wrap_indisplay36272#

Ako je #math2280##tex2html_wrap_inline36274# onda iz #math2281#

#tex2html_wrap_indisplay36276#

i (#eq:tang#8102>) slijedi #math2282#

#tex2html_wrap_indisplay36278#

#math2283#

#tex2html_wrap_indisplay36280#

Prema tome tangenta u točki #tex2html_wrap_inline36282# prolazi iznad točke #tex2html_wrap_inline36284# pa se njezino sjecište #tex2html_wrap_inline36286# s osi #tex2html_wrap_inline36288# nalazi lijevo od #tex2html_wrap_inline36290# Tako je #math2284#

#tex2html_wrap_indisplay36292#

#math2285##tex2html_wrap24630#
Sada smo u situaciji iz prvog dijela dokaza, pa dalje dokaz ide kao tamo. #math2286##tex2html_wrap_inline36295#<#12360#>

Primjer 3.7   Neka je #tex2html_wrap_inline36298# prirodan broj, i neka je #tex2html_wrap_inline36300# Nađimo, pomoću Newtonove metode, približnu vrijednost pozitivnog #tex2html_wrap_inline36302#-tog korijena iz #tex2html_wrap_inline36304# Rješenje. Izračunati #tex2html_wrap_inline36306#-ti korijen iz broja #tex2html_wrap_inline36308# znači riješiti po #tex2html_wrap_inline36310# jednadžbu #math2287#

#tex2html_wrap_indisplay36312#

Ovdje je #math2288##tex2html_wrap_inline36314# pa Newtonova metoda daje #math2289#

#tex2html_wrap_indisplay36316#

odnosno #math2290#

#tex2html_wrap_indisplay36318#

Što se tiče izbora početne aproksimacije #tex2html_wrap_inline36320# i konvergencije, primijetimo sljedeće. Za #math2291##tex2html_wrap_inline36322# imamo #math2292##tex2html_wrap_inline36324# Zatim, zbog #math2293##tex2html_wrap_inline36326# #math2294##tex2html_wrap_inline36328# za svaki #math2295##tex2html_wrap_inline36330# je #tex2html_wrap_inline36332# i #tex2html_wrap_inline36334# Na kraju, iz pozitivnosti funkcije #tex2html_wrap_inline36336# slijedi rast funkcije #tex2html_wrap_inline36338# pa je #tex2html_wrap_inline36340# onaj rub segmenta u kojem #tex2html_wrap_inline36342# ima manju vrijednost. Da bi vrijedilo #math2296#

#tex2html_wrap_indisplay36344#

mora biti #math2297#

#tex2html_wrap_indisplay36346#

Dakle za tako veliki #tex2html_wrap_inline36348# ispunjeni su svi uvjeti teorema #tm:newtmet#8136>. Kako #tex2html_wrap_inline36350# smijemo uzeti još veći, i kako #tex2html_wrap_inline36352# može biti bilo koji broj veći od #tex2html_wrap_inline36354# i manji od #math2298##tex2html_wrap_inline36356# slijedi da postupak konvergira za svaki #tex2html_wrap_inline36358# Specijalno kad je #tex2html_wrap_inline36360# imamo formulu za približno računanje drugog korijena

#math2299#
#tex2html_wrap_indisplay36362# (3.10)

U programskom paketu Mathematica se ovaj postupak programira vrlo jednostavno

Mathematica program 4   (#tex2html_wrap_inline36365#-ti korijen)
verbatim172#

gdje je 8 broj aproksimacija koje želimo, a broj 9 je početna aproksimacija. Naravno 10 je broj korijena koji se vadi. Uvjerite se na primjerima kako je formula za računanje drugog korijena efikasna.

Primjer 3.8   Za dani pozitivan broj #tex2html_wrap_inline36368# naći približnu vrijednost njemu recipročnog broja bez dijeljenja. Rješenje. To je isto kao približno riješiti jednadžbu #math2300#

#tex2html_wrap_indisplay36370#

Newtonova metoda daje #math2301#

#tex2html_wrap_indisplay36372#

U ovoj formuli nema dijeljenja, i mi smo riješili zadatak, ako postoji interval u kojem možemo birati početnu aproksimaciju tako da ovaj postupak konvergira. Ispitajmo uvjete teorema #tm:newtmet#8160> u ovom slučaju. #math2302#

#tex2html_wrap_indisplay36374#

Neka su sada #tex2html_wrap_inline36376# takvi da je #math2303##tex2html_wrap_inline36378# Time je uvjet #math2304##tex2html_wrap_inline36380# ispunjen. Iz pozitivnosti #tex2html_wrap_inline36382# slijedi da #tex2html_wrap_inline36384# raste. No #tex2html_wrap_inline36386# ima negativne vrijednosti, pa iz rasta #tex2html_wrap_inline36388# slijedi da #tex2html_wrap_inline36390# pada. Tako #tex2html_wrap_inline36392# prima manju vrijednost u rubnoj točki #tex2html_wrap_inline36394# #math2305#

#tex2html_wrap_indisplay36396#

pa #tex2html_wrap_inline36398# određujemo iz kvadratne nejednadžbe #math2306#

#tex2html_wrap_indisplay36400#

Izlazi da se #tex2html_wrap_inline36402# mora nalaziti između #math2307#

#tex2html_wrap_indisplay36404#;SPMnbsp; ;SPMnbsp;<#1#>i<#1#>#tex2html_wrap_indisplay36405#

Budući da #tex2html_wrap_inline36407# možemo uzeti po volji malen, slijedi da se za #tex2html_wrap_inline36409# može uzeti bilo koji broj manji od #tex2html_wrap_inline36411# Tako se za početnu aproksimaciju može uzeti bilo koji #tex2html_wrap_inline36413# takav da je #math2308#

#tex2html_wrap_indisplay36415#

Ako želimo ocijeniti grešku, primijetimo da je Newtonova metoda zapravo metoda iteracije, ako stavimo #math2309#

#tex2html_wrap_indisplay36417#

Tada je #math2310#

#tex2html_wrap_indisplay36419#

Neka je #math2311#

#tex2html_wrap_indisplay36421#

Tada je apriorna ocjena greške dana formulom (#eq:aprocj#8185>), a aposteriorna formulom (#eq:apoocj#8186>).

Primjer 3.9   Naći #tex2html_wrap_inline36424# u slučaju približnog računanja drugog korijena po formuli (#eq:pribsqrt#8188>). Rješenje. Treba naći približnu vrijednost od #tex2html_wrap_inline36426# Neka je #math2312#

#tex2html_wrap_indisplay36428#

Prirodno je početnu aproksimaciju uzeti u segmentu #tex2html_wrap_inline36430# Tada je #math2313#

#tex2html_wrap_indisplay36432#

U ovom slučaju je #math2314#

#tex2html_wrap_indisplay36434#

pa je #math2315#

#tex2html_wrap_indisplay36436#

Odavde se vidi da je uvijek #math2316##tex2html_wrap_inline36438#