Newtons metode - nøyaktighet

[krje1980]

Hei.

Er litt usikker på en del av en utredning i boken jeg har begynt på i faget "Regnealgoritmer". Kapitlet tar for seg Newtons metode, og vi har gitt følgende oppgave:

Let Newton's method be used on [tex]f(x) = x^2 - q[/tex] (where [tex]q > 0[/tex]). Show that if [tex]x_{n}[/tex] has [tex]k[/tex] correct digits after the decimal point, then [tex]x_{n+1}[/tex] will have at least [tex]2k -1[/tex] correct digits after the decimal point, provided that [tex]q > 0.006[/tex] and [tex]k \geq 1[/tex].

Løsningsforslaget til oppgaven følger herved, frem til punktet jeg er usikker på:

We have [tex]f(x) = x^2 - q[/tex], [tex]f^{\prime}(x) = 2x[/tex], [tex]f^{\prime \prime}(x) = 2[/tex]. So [tex]x_{n+1} = x_{n} - \frac{(x_{n}^2 - q)}{2x_{n}} = \frac{x_{n}^2 + q}{2x_{n}}[/tex], and [tex]e_{n+1} = \frac{e_{n}^2 f^{\prime \prime}(\xi_{n})}{2f^{\prime}(x_{n})} = \frac{e_{n}^2}{2x_{n}}[/tex]. If [tex]x_{n}[/tex] has [tex]k[/tex] correct digits then: [tex]|e_n| \leq \frac{1}{2} \cdot 10^{-k}[/tex].

Mitt spørsmål er: Hvor kommer faktoren [tex]\frac{1}{2}[/tex] fra i det aller siste uttrykket her? Dersom noen kan forklare dette for meg, vil jeg være svært takknemlig!

[espen180]

Anta at [tex]x[/tex] er bestemt til [tex]k[/tex] korrekte siffer. Hvis [tex]|e|> \frac12 10^{-k}[/tex], vil [tex]|(x+e)-(x-e)|=2|e|> 10^{-k}[/tex], slik at vi får usikkerhet i det [tex]k[/tex]-te sifferet. Dette strider mot antagelsen, altså må vi ha [tex]|e|\leq\frac12 10^{-k}[/tex].

[krje1980]

Takk skal du ha! Jeg ser at dette er korrekt for denne oppgaven nå. Men jeg må innrømme at jeg generelt er litt usikker på hvordan jeg skal gå frem i denne typen oppgaver hvor vi skal bestemme akseptable grenser for feilberegning. Boken forklarer egentlig ikke dette særlig bra. Et annet eksempel - i seksjonen om halveringsmetoden, bes vi bl.a. om å finne "a root to two significant figures." Det skrives da:

So the error must be [tex]\frac{(b_n - a_n)}{2} < 0.05[/tex], or [tex](b_n - a_n) < 0.1[/tex]

Igjen ser jeg ikke helt hvor man bare "tar" [tex]0.05[/tex] fra her. Dette er sikkert veldig elementært, men i og med at dette er mitt første kurs i numerisk analyse er jeg litt på gyngende grunn. Dersom du kan forklare resonneringen her, og gi noen tips til hvordan man generalt bør tenke i slike problemstilliner, så ville det vært veldig fint!