6 svar
82 visningar
Urboholic 150
Postad: 27 okt 17:04

Fixed point iteration

Säg jag har denna iterationen för att hitta en rot xi+1=cos(xi), jag behöver lösa hur många iterationer jag behöver göra för att error termen ska vara ε  10-12

jag tänker att jag behöver använda mig av denna xi - x* =ε på något sätt. x* är roten. x0 =1 men jag vet inte hur jag ska beräkna detta då x kommer ha ett nytt värde efter varje iteration?

Laguna 30210
Postad: 27 okt 18:50

Det beror på var man börjar. Vet man x0?

Urboholic 150
Postad: 27 okt 18:55

kan börja på x0=1

Laguna 30210
Postad: 27 okt 21:07

Ja, det skrev du ju.

På den här sidan finns en bra bild, fast de börjar på -1: https://en.m.wikipedia.org/wiki/Fixed-point_iteration

Man kan approximera kurvan med dess tangent nära fixpunkten, och då känns det lätt att räkna ut hur mycket närmare man kommer för varje iteration med en smula geometri.

LuMa07 Online 28
Postad: 28 okt 09:15 Redigerad: 28 okt 09:22

Man kan utnyttja medelvärdessatsen för att hitta en lämplig lipschitzkonstant för cosinusfunktionens iterationer. Den sökta lösningen uppfyller x*=cos(x*)x^* = \cos(x^*), så

|x*-xi+1|=|cos(x*)-cos(xi)||sin(ξi)|·|x*-xi||x^* - x_{i+1}| = |\cos(x^*) - \cos(x_i)| \le |\sin(\xi_i)| \cdot |x^*-x_i|,

där ξi\xi_i ligger någonstans mellan x*x^* och xix_i. Man kan därmed göra en uppskattning

|x*-xi+1||x*-x0|·k=0i|sin(ξk)||x^* - x_{i+1}| \le |x^*-x_0| \cdot \prod_{k=0}^i |\sin(\xi_k)| .

Det återstår att uppskatta sinusvärdena. En väldigt grov uppskattning skulle vara att |sin(ξk)|<|sin(1)|0.842|\sin(\xi_k)| < |\sin(1)| \le 0.842, så |x*-xi+1|0.842i+1/3|x^* - x_{i+1}| \le 0.842^{i+1} /3. Sedan är det bara att hitta ett ii-värde, så att felet blir mindre än 10^(-12).

Man kan få en betydligt bättre uppskattning om man inser att x4<0.8x_4 < 0.8, så |sin(ξk)|<0.718|\sin(\xi_k)|<0.718 för alla k4k \ge 4.

Urboholic 150
Postad: 28 okt 11:39 Redigerad: 28 okt 11:43

okej jag tror jag förstår, så man vet liksom inte sin(ξk) så man får uppskatta den då och eftersom att vi har x0 = 1 så kan vi använda detta i sin funktionen som ett uppskattat värde?
jag skulle inte kunna använda x* i uppskattningen för sin funktionen? eller måste jag använda x0 då det är där jag startar? för jag kommer väl ändå behöva använda x* i formeln för att kunna beräkna detta?

SaintVenant 3912
Postad: 28 okt 12:19 Redigerad: 28 okt 12:19

Jag vet inte vad ramarna för uppgiften kräver men en uppskattning ges av:

|xn-x*|f'(ξi)n|x0-x*||x_n-x*|\approx f'(\xi_i)^n |x_0-x*|

Där vi alltså vill ha |xn-x*|<ϵ|x_n-x*|<\epsilon. Sedan kan du gissa värdet på |x0-x*||x_0 - x*| utifrån basala kunskaper om fixpunktsekvationen. Du vet i detta fall definitivt att 0|x0-x*|20\leq |x_0 -x*|\leq 2. Men detta kan du smalna av för mer korrekta uppskattningar. Likaså gäller för Lipschitzkonstanten. 

Svara
Close