Matematik

Newton's metode

03. juni 2006 af Sabrina (Slettet)

Jeg er i gang med at forstå Newton's metode (også kaldet Newton-Raphsons metode). Der er dog nogle detajler, som volder lidt problemer.

Bogens måde at udlede den på gør brug af Taylorpolynomiet af 1. grad, dvs. vi har, at

f(x) cirka lig f(x0)+(x-x0)f'(x0)

Dernæst siger bogen, at hvis x0 ligger tæt på løsningen s, så kan vi forvente at opnå en bedre approksimation af løsningen ved at sætte højresiden lig 0, dvs:

f(x0)+(x-x0)f'(x0)=0

Hvorfor?

I må forresten have en god weekend :)

Brugbart svar (0)

Svar #1
04. juni 2006 af fixer (Slettet)

Tænk geometrisk. Ligningen

f(x0)+(x-x0)f'(x0) = y

er ligningen for tangenten til grafen for f gennem punktet (x0,f(x0)). Hele clout'et i NR-metoden er at lade tangentens skæring med abscissen være næste gæt på løsningen til ligningen f(x)=0. Prøv at lave en tegning og overbevis dig om, at for "skikkelige" funktioner, og for initialgæt x0 "tæt" på den virkelige løsning, da vil løsning af ligningen y=0 give en bedre approksimation til den eksakte løsning end gættet x0. Ved nu at fortsætte denne proces iterativt håber vi på at den approksimative løsning konvergerer mod den eksakte.

For værdier "langt" fra det søgte nulpunkt _er_ højere ordens led vigtige i Taylorapproksimationen og NR kan derfor give meningsløse resultater. Eksempelvis kan initialgættet være så langt fra den eksakte rod at søgeintervallet inkluderer lokale ekstrema for funktionen. Hvis startgættet ligger i nærheden af et ekstrema, hvor den første afledede næsten er nul, kollapser NR. Som med alle kraftige værktøjer skal man omgåes det med forsigtighed.

Svar #2
04. juni 2006 af Sabrina (Slettet)

Mange tak! :)
Jeg sidder oppe på universitetet og er ved at regne CSB. Men jeg prøver at lave tegningen, når jeg kommer hjem.

Jeg er imidlertid løbet ind i et problem i forbindelse med interpolerende kvadraturregler.

Det interpolerende polynomium har formen:

p(x)=a_N*x^N+a_{N-1}*x^{N-1}+ ... + a_1*x+a_0

Dette polynomium har de samme funktionsværdier som f i punkterne x_0, x_1, ... , x_N

For at bestemme a'erne skal jeg bruge basispolynomiumer:

l_k(x_j) = 1 for j=k
l_k(x_j) = 0 for j forskellig fra k

Men jeg forstår ikke idéen med basispolynomier. Heller ikke hvordan de kan bruges til at bestemme a'erne i p.

Men er det korrekt, at
l_0 (x_0) = 1, mens
l_1 (x_0) = 0
l_2 (x_0) = 0
osv. ?

På samme måde med l_1, hvor l_1(x_1) = 1 og for resten giver det 0.

Brugbart svar (0)

Svar #3
04. juni 2006 af fixer (Slettet)

Du roder med Lagrangeinterpolanter.

Givet et sæt af P+1 punkter x_q, 0

h_p(x_q) = delta_{pq} (*)

hvor delta_{pq} er Kroneckers delta. Lagrangepolynomiet kan også skrives på produktform som [smid det selv i LaTeX]:

h_{p}(x) = \\frac{\\prod^{P}_{q=0,q\
eq p}(x-x_{q})}{\\prod^{P}_{q=0,q\
eq p}(x_{p}-x_{q})} (**)

Egenskaben (*) ved Kroneckers delta gør Lagrangepolynomier særligt velegnede som interpolationsbasis. Lagrangeinterpolanten I gennem de P+1 punkter x_q til en funktion u(x) er givet ved

Iu(x) = \\sum_{p=0}^{P}\\hat{u}_{p}h_{p}(x) (***)

hvor \\hat{u}_{p} er ukendte koefficienter. Interpolationsapproksimationen kræver at interpolanten i de P+1 punkter x_q antager samme værdi sum u, og af (*) ses da umiddelbart at \\hat{u}_{p} = u(x_p). Fordelen ved at bruge Lagrangepolynomierne (**) som basis er defor at koefficienterne i (***) netop bliver lig funktionsværdierne u(x_q) i de P+1 punkter x_q.

Interpolationsapproksimationen til u(x) er derfor

Iu(x) = \\sum_{p=0}^{P}u(x_p)h_p(x)

Svar #4
04. juni 2006 af Sabrina (Slettet)

Endnu en gang mange tak for dit svar! Jeg læser det grundigt igennem, når jeg kommer hjem.

Jeg er imidlertid gået i stå i forbindelse med udledningen af Simpsons regel i intervallet [-h,h].

Jeg har, at

h
S f(x)dx cirka lig alpha*f(-h)+beta*f(0)+gamma*f(h)
-h

Vi skal således bestemme alpha, beta og gamma.

Dernæst står der i mine noter:

f(x) identisk lig med 1:
alpha+beta+gamma=

h
S 1 dx = 2h
-h

f(x) = x (og så indsættes på samme måde som før)

f(x) = x^2 (og igen indsættes)

Men hvorfor vælges netop, at f(x) identisk lig med 1, f(x)=x og f(x)=x^2 ?

Jeg er lidt i tvivl, om det kan have noget at gøre med, at det interpolerende polynomium højst behøver at have grad 2, hvis det skal gå igennem 3 punkter. Men jeg er i tvivl, om det har noget med dette at gøre, eller om løsningen er en helt anden?

Brugbart svar (0)

Svar #5
04. juni 2006 af fixer (Slettet)

Det er fordi man søger en formel der er eksakt for polynomier til og med anden grad. Faktisk er den på grund af symmetrien i formlen (som du vil se) eksakt for polynomier op til 3. grad da der giver anledning til en heldig cancellering af koefficienter. Vi kan sige at den er O(h^5f^(4)) jvf. vores tidligere snak om Landausymboler-

Brugbart svar (0)

Svar #6
04. juni 2006 af sigmund (Slettet)

Altså, i en bog jeg har, der vedrører emnet, står der bl.a. under udledningen af Simpsons regel (s. 168):

"In order to get a simple system of equations we use the polynomials p_k(x) = (x - x1)^k (...)".

Her er x1 = a + h.

Reference:

Lars Eldén et. al., Introduction to Numerical Computation -- analysis and Matlab illustrations, Studentlitteratur, Lund 2004.

Brugbart svar (0)

Svar #7
04. juni 2006 af fixer (Slettet)

Og det skal nævnes at der i #6 netop refereres til Langrangepolynomier. Simpson's regel fremkommer ved at intergrere en trediegrads Lagrangeinterpolant gennem tre ækvidistante punkter.

Svar #8
04. juni 2006 af Sabrina (Slettet)

Tak til jer begge! :)

Dagens sidste spørgsmål (håber jeg):

Jeg har udledt, at præcisionsgraden af Simpsons regel er 3.

Men kan man på en hurtig måde finde præcisionsgraden for midtpunktsmetoden og trapezreglen? Eller skal man igennem de mange udregninger igen?

Brugbart svar (0)

Svar #9
04. juni 2006 af sigmund (Slettet)

#8,

Se
http://www.math.aau.dk/~kim/Undervisning/06-csb/Lektion07/l07Rep.pdf

og

http://www.math.aau.dk/~lasse/05-csb/lektion07/repetition.pdf.

Det se ud til, at du må igennem de samme beregninger hver gang for at finde præcisionsgraden.

Svar #10
04. juni 2006 af Sabrina (Slettet)

Så fik jeg endelig tid til at læse jeres svar grundigt igennem. De er uddybet så meget, at I slipper for flere spørgsmål i denne omgang ;)

Jeg siger endnu en gang mange tak for jeres assistance!

Skriv et svar til: Newton's metode

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.