Matematik

Opskriv rekursiv formel

08. november 2015 af Lubas (Slettet) - Niveau: Universitet/Videregående

Sidder og leger lidt med en rekursiv formel for approximering af kvadratroden af tallet N ud fra et 'start-gæt' x. Mit endelige mål er at finde en sammenhæng mellem modellens usikkerhed efter n gentagelser afhængig af hvor meget x afviger fra sqrt(N).

Nogen der har et bud på, hvordan følgende kan skrives på rekursiv form?

Brugbart svar (0)

Svar #1
08. november 2015 af SådanDa

Hvis du kalder dit gæt x₀, så vil du have at:

$x_n=\frac{\frac{N}{x_{n-1}}+x_{n-1}}{2}, \ n\geq1$

Er det sådan du mener? :)

Svar #2
08. november 2015 af Lubas (Slettet)

Hov, fik vidst ikke formuleret mig ordentligt. Jeg søger det eksplicitte udtryk for den rekursive formel :)

Brugbart svar (0)

Svar #3
08. november 2015 af peter lind

Det har du misforstået. Hvis der var en resulterende formel er det ikke en rekursiv formel. En rekursiv formel er af formen x_n = f(x_n-1, x_n-2, ...)

Brugbart svar (0)

Svar #4
08. november 2015 af Therk

Er du sikker på du ikke leder efter det nævnt i #1? Du kan lave en procedure, der kan gøre det for dig i Maple:

minkvrod := proc(N,x0,n)
# N = Value to take sqrt of
# x0 = initial guess
# n = number of recursions

local i, # Loop variable
x; # Recursion element

x := x0; # Initial guess

for i to n do
x := (N/x + x)/2; # Formula
end do;

# Return vector
return Vector(<'abs(sqrt("N")-x)','sqrt("N")','x'>) = evalf(Vector(<evalf(abs(sqrt(N)-x)),sqrt(N),x>));

end proc:
minkvrod(10,1,4);

Svar #5
08. november 2015 af Lubas (Slettet)

Ja det er jeg med på peter lind. Jeg søger et eksplicit udtryk for den rekursive funktion jeg har listet.

Brugbart svar (0)

Svar #6
08. november 2015 af peter lind

Den kan du se i #1

Brugbart svar (0)

Svar #7
08. november 2015 af SådanDa

For at finde noget der opfylder de første tre iterationer får jeg noget der ligner:

$x_n=\frac{1}{2^n}\frac{\sum_{i=0}^{2^{(n-1)}}N^i x^{2(2^{n-1}-i)}\binom{2^n}{2i}}{x\prod_{j=1}^{n-1}\sum_{k=0}^{2^{j-1}}N^k x^{2(2^{j-1}-k)}\binom{2^j}{2k}}$ , det er ret grimt, og jeg ved ikke om det holder ud over de første 3... så ja, det er ikke sikkert at du kan bruge det til noget som helst :)

Svar #8
08. november 2015 af Lubas (Slettet)

Hmm ja, den er ikke særlig køn - men i det mindste har du forstået, hvad jeg leder efter. *Jeg har vidst ikke fået formuleret mig så godt.

Brugbart svar (1)

Svar #9
08. november 2015 af Therk

Så forstår jeg også. Well, jeg fandt algoritmen i min numerisk analysebog og den algoritme du bruger kaldes den Babylonske algoritme og har et fejlled, der er kvadratisk konvergent, dvs. vi får omkring to cifres nøjagtighed per iteration. Den har ikke noget eksplicit udtryk, fordi selve pointen er at finde roden iterativt - selv hvis ovenstående var et udtryk, så ville den nødvendige regnekraft også være væsentligt større for udtrykket i #7 end i #1 - se nemt dette ved at sætte n = 20. Læs evt. Wikipedia-artiklen for at finde et udtryk for fejlstørrelsen.

Svar #10
09. november 2015 af Lubas (Slettet)

Spændende artikel, Therk. Mange tak for linket.

Skriv et svar til: Opskriv rekursiv formel

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.