I'm doing homework, and I am stumped on the first problem. I'm given this:
Apply the extrapolation process described in Example 1 to determine $N_3(h)$, an approximation to $f(x_0)$, for the following functions and stepsizes.
Where $f(x) = ln(x), x_0 = 1, h = 0.4$
So I go to build the table. In the reference example they use forward difference, so I will use that here.
$$ N_1(0.4) = \frac{f(1.4)-f(1)}{0.4}=0.841181 \\ N_1(0.2) = \frac{f(1.2)-f(1)}{0.2}=0.911608 \\ N_1(0.1) = \frac{f(1.1)-f(1)}{0.1}=0.953102 \\ N_2(0.4) = N_1(0.2)+(N_1(0.2) - N_1(0.4)) = .982035 \\ N_2(0.2) = N_1(0.1)+(N_1(0.1) - N_1(0.2)) = .994596 \\ N_3(0.4) = N_2(0.2) + (N_2(0.2) - N_2(0.4)) = 1.077584 $$
This is wrong, according to the book this approximation should be around 1.0000109. Can anyone give me a in-depth explanation of where I'm going wrong here? I'm trying to understand this, but it doesn't help when your professor just does book examples and doesn't explain much even when asked.
Thanks!
Richardson extrapolation for the forward difference approximation is:
$$N_2(h) = 2N_1(h/2) - N_1(h),\\N_2(h/2) = 2N_1(h/4) - N_1(h/2), \\N_3(h) = \frac{4N_2(h/2) - N_2(h)}{3}.$$
Consider a Taylor series expansion of $\ln(1+h):$
$$\ln(1+h) = \ln(1) + h -\frac1{2}h^2 + \frac1{3}h^3+O(h^4).$$
The forward difference approximation is
$$N_1(h) = \frac{\ln(1+h)-\ln(1)}{h}.$$
The difference between the forward difference approximation and the exact value of the first derivative ($f'(1) = 1$) is $O(h)$
$$N_1(h) -1= -\frac1{2}h+\frac1{3}h^2+O(h^3).$$
Also
$$N_1(h/2) -1= -\frac1{4}h+\frac1{12}h^2+O(h^3).$$
To reduce the order of the error, the first stage Richardson extrapolation is
$$N_2(h) = 2N_1(h/2)-N_1(h).$$
Hence, after the first stage Richardson extrapolation the error becomes $O(h^2)$
$$N_2(h) - 1= 2N_1(h/2)- N_1(h)-1= 2[N_1(h/2)-1]- [N_1(h)-1]\\= -\frac{1}{6}h^2+O(h^3),$$
and
$$N_2(h/2) - 1= -\frac{1}{24}h^2+O(h^3),$$
To reduce the order of the error further, the second stage Richardson extrapolation is
$$N_3(h) = \frac{4N_2(h/2)-N_2(h)}{3}.$$
Repeating the error analysis we find
$$N_3(h) - 1=\frac{4N_2(h/2)- N_2(h)}{3}-1=\frac{4}{3}[N_2(h/2)-1]- \frac{1}{3}[N_2(h)-1]\\= -\frac{4}{3}\frac{1}{24}h^2+\frac{1}{3}\frac{1}{6}h^2+O(h^3)=0 + O(h^3).$$
A second application of the first stage Richardson extrapolation will not achieve an $O(h^3)$ error.
$$2N_2(h/2)- N_2(h)-1= 2[N_2(h/2)-1]- [N_2(h)-1]\\= -2\frac{1}{24}h^2+\frac{1}{6}h^2+O(h^3)= \frac{1}{12}h^2+ O(h^3).$$