Newton-Raphsons metoden. Opgaver

1) Start med et gæt x_i for nulpunktet.

2) Bestem så ligningen for tangenten til grafen for funktionen f(x) i punktet (x_i , f(x_i)) .

3) Bestem så x-koordinaten x_i+1 for skæringspunktet mellem tangenten og x-aksen.

4) Benyt x_i+1 som en forbedret værdi for nulpunktet.

5) Fortsæt denne fremgangsmåde fra 2) - 4) indtil konvergens.

er x_i et tilfældigt tal?

#2

I princippet, ja. Afhængigt af hvor man starter, vil man iterere sig frem til de forskellige reelle rødder i f(x) .

Hvis man laver en passende tabel over funktionsværdierne, vil man se, at der er en rod i hvert af intervallerne

]-0,1 ; 0[   ,   ]1,2 ; 1,3[    ,    ]1,7 ; 1,8[   ,   ]3,1 ; 3,2[   ,   ]3,9 ; 4,0[ .

Polynomiet har altså 5 forskellige reelle rødder, der er indklamret med de angivne intervaller. For hver rod kan man som startværdi benytte et tal i intervallet, der indklamrer roden.

I princippet?

#4

Ja. man bør starte så tæt som muligt på den rod man vil finde. Starter man meget langt væk fra roden, kan der være numeriske instabiliteter, der bevirker, at metoden ikke vil konvergere med den startværdi.

Den iterative proces kan beskrives ved formlem:

x_n+1 = x_n  - f(x_n)/f'(x_n)

Gætter man på roden x₀ = 0, så bliver første step i iterationen

x₁ = 0 - 1/24 = 1/24

og

x₂ = 1/24 -f(1/24)/f'(1/24) osv.

Et helvedes regnearbejde som lettest udføres med et computerprogram af følgende form (tolerance er den fejl man vil tolerere):

x := x0; n := 0; tilvækst := 0;

for n := n+1 while abs(tilvækst) > tolerance do

begin

   tilvækst := f(x)/fdash(x);

   x := x - tilvækst

end;

return (x, tolerance,n);

#6

Undskyld, der er programmeringsfejl i algoritmen (det er der altid! Det er derfor det er så svært at være datalog).

Her er en bedre version:

x := x0;

repeat

   tilvækst := f(x)/fdash(x);

   x := x - tilvækst

until abs(tilvækst) <= tolerance; 

return (x, tolerance);

 

Det kan laves ganske simpelt i Excel, hvor man i benytter tre søjler til at iterere fra række til række. I tre celler kan man skrive indholdet:

K9: =K8-L8/M8
L9: =K9^5-10*(K9^4)+35*(K9^3)-50*(K9^2)+24*K9+1
M9: =5*(K9^4)-10*4*(K9^3)+35*3*(K9^2)-50*2*K9+24

Man starter med et gæt i K8 og kopierer formlerne i L9 og M9 til L8 og M8. Dernæst kopierer man blot formlerne fra række til række, indtil der er konvergens.

Således finder man de fem rødder:

 

          x           f(x)           f '(x) 0.2 4.0643 7.8880 -0.315253550 -12.7338 67.2634 -0.125940915 -2.8881 38.3407 -0.050613596 -0.3474 29.3356 -0.038770730 -0.0077 28.0372 -0.038495438 -4.104E-06 28.0074 -0.038495291 -1.162E-12 28.0074 -0.038495291 0 28.0074       1.1 0.4545 -4.8695 1.193338125 0.0563 -3.6435 1.208787079 0.0016 -3.4308 1.209265235 1.581E-06 -3.4242 1.209265696 1.471E-12 -3.4242 1.209265696 -7.105E-15 -3.4242 1.209265696 3.553E-15 -3.4242 1.209265696 0 -3.4242       1.5 -0.4063 0.5625 2.222222222 1.8346 3.2715 1.661443451 -0.1646 2.3464 1.731613820 0.0217 2.9455 1.724238584 0.0002 2.8882 1.724165814 2.080E-08 2.8877 1.724165807 -4.974E-14 2.8877 1.724165807 1.421E-14 2.8877 1.724165807 -7.105E-15 2.8877 1.724165807 -7.105E-15 2.8877       2.8 1.96768 -3.5520 3.353963964 -1.4444 -6.6948 3.138207891 0.0903 -7.0409 3.151035754 -0.0004 -7.0967 3.150984174 -5.364E-09 -7.0965 3.150984173 -1.137E-13 -7.0965 3.150984173 1.421E-14 -7.0965 3.150984173 1.421E-14 -7.0965       3.5 -2.2813 -4.4375 2.985915493 1.0835 -5.8562 3.170932214 -0.1423 -7.1669 3.151077506 -0.0007 -7.0968 3.150984176 -1.755E-08 -7.0965 3.150984173 2.842E-13 -7.0965 3.150984173 -2.274E-13 -7.0965 3.150984173 1.421E-13 -7.0965 3.150984173 -2.274E-13 -7.0965 3.150984173 -2.842E-14 -7.0965 3.150984173 9.948E-14 -7.0965 3.150984173 9.948E-14 -7.0965

 

Den sidste iteration i #8 gav samme rod som den foregående iteration. man skal starte med en lidt større x-værdi for at finde den sidste rod:

 

                x           f(x)           f '(x) 3.8 -2.0643 7.8880 4.0617038540 2.6796 30.5796 3.9740759367 0.4108 21.4775 3.9549479785 0.0171 19.7043 3.9540813505 3.407E-05 19.6257 3.9540796146 1.370E-10 19.6255 3.9540796146 2.842E-14 19.6255 3.9540796146 -4.547E-13 19.6255

hvordan er du kommet frem til disse x'er som står i #8? Har spurgt min vejleder, som har fået mig til at forstå det lidt nærmere omkring #6. Undskyld jeg spørger så dumt, men vil gerne have skæret det ud i pap

#7 så langt er jeg slet ikke nået i programmeringssprog, men kan sende dig en skabelon. Den pågældende filtype kan jeg åbenbart ikke smide op her i indlægget

Hvis du ser på #3, så vil du få en fornemmelse af hvordan Andersen har valgt startværdierne. Jeg er glad for at du ser lyset ud fra #6, men brug hellere algoritmen i #7, hvis du vil programmere det. Denne algoritme er også baggrunden for fremgangsmåden i #8, som er mere manuel.

kunne jeg sende dig en skabelon @hbhans?

Jeg har mailadresse [email protected], men jeg ved ikke hvad en "skabelon" er.

#10

Det bliver måske mere klart, når jeg medtager søjlebogstaver og rækkenumre i tabellen

 

 

  K L M   x f(x) f '(x) 8 0.2 4.0643 7.8880 9 -0.315253550 -12.7338 67.2634 10 -0.125940915 -2.8881 38.3407 11 -0.050613596 -0.3474 29.3356 12 -0.038770730 -0.0077 28.0372 13 -0.038495438 -4.104E-06 28.0074 14 -0.038495291 -1.162E-12 28.0074 15 -0.038495291 0 28.0074

I cellerne indtaster man præcis som beskrevet i #8.

her kommer lige en til: f(x)=x^2+x+1. Ved godt at metodens svaghed ligger i denne opgave, men hvorfor?

D<0 så der er ingen løsning

#5 hvilke numeriske instabiliteter?

Tegn grafen for en funktion, der starter under x aksen, bevæger sig opad mod højre, skærer x-aksen i et 0 punkt når et maksimum hvorefter funktionen er monoton aftagende og går mod 0 for x =>∞.

Algoritmen svarer til at du erstatter funktionen med tangentfunktionen i et punkt og finder skæringspunktet mellem x aksen og tangenten.

Hvis du starter i maksimum er tangenten vandret og den vil aldrig skære x aksen. Du kommer til at dividere med 0.

Hvis du starter i et punkt til højre for maksimum vil tangenten skære x aksen til højre for maksimum. Derfor vil algoritmen give x værdier der er større og større og altså flytte sig fra det korrekte 0 punkt. På et eller andet tidspunkt vil tallene blive så store at PC'en stopper med en fejlmeddelelse

er det de numeriske instabiliteter?