Numerical Analysis - Richardson Extrapolation Question: Suppose that N(h) is an approximation to $M$ for every $h > 0$ and that
$M = N(h) + K_1 h + K_2 h^2 + K_3 h^3 +\cdots$, for some constants $K_1, K_2, K_3,\cdots$. Use the values $N(h), N( h/3),$ and $N (h/9)$ to produce an $O(h^3)$
approximation to $M$.
My work:
$$M=N(h)+K_1 h+K_2 h^2 + K_3 h^3+\cdots$$
$$M=N(\frac{h}{3})+\frac{K_1}{3} h+\frac{K_2}{9}h^2 + \frac{K_3}{27}h^3+\cdots$$
$$M=N(\frac{h}{9})+\frac{K_1}{9}h+\frac{K_2}{81}h^2 + \frac{K_3}{729}h^3+\cdots$$
I'm not sure what to do next.
I was told that $N_1(h)$ gives $O(h^2)$, $N_2(h)$ gives $O(h^4)$, $N_3(h)$ gives $O(h^6)$, $N_4(h)$ gives $O(h^8)$, so I'm not sure how to get $O(h^3)$.
 A: It is not true that $N_1(h)=O(h^2), N_2(h)=O(h^4), \cdots$ for the formula
$$
M=N(h)+K_1 h+K_2 h^2+K_3 h^3+\cdots
$$
but it is true for
$$
M=N(h)+K_1 h^2+K_2 h^4+K_3 h^6+\cdots
$$
It's easy to get an $O(h^3)$ formula. Subtracting the first formula from $3$ times the second formula eliminates the $h$ term
$$
2M=3N(\frac{h}{3})-N(h)+(\frac{K_2}{3}h^2-K_2 h^2)+(\frac{K_3}{9}h^3-K_3 h^3)+\cdots\\
$$
Dividing this equation by $2$ produces an $O(h^2)$ formula
$$
M=\frac{3}{2}N(\frac{h}{3})-\frac{1}{2}N(h)-\frac{K_2}{3}h^2-\frac{4K_3}{9}h^3+\cdots\\
$$
Subtracting the second formula from $3$ times the third formula eliminates the $h$ term
$$
2M=3N(\frac{h}{9})-N(\frac{h}{3})+(\frac{K_2}{27}h^2-\frac{K_2}{9}h^2)+(\frac{K_3}{243}h^3-\frac{K_3}{27}h^3)+\cdots
$$
Dividing this equation by $2$ produces an $O(h^2)$ formula
$$
M=\frac{3}{2}N(\frac{h}{9})-\frac{3}{2}N(\frac{h}{3})-\frac{2K_2}{27}h^2-\frac{8K_3}{243}h^3+\cdots
$$
Multiplying this by $9/2$ gives
$$
\frac{9}{2}M=\frac{27}{4}N(\frac{h}{9})-\frac{27}{4}N(\frac{h}{3})-\frac{K_2}{3}h^2+\frac{4K_3}{27}h^3+\cdots
$$
Subtracting the first $O(h^2)$ formula from this $O(h^2)$ formula eliminates the $h^2$ term
$$
\frac{7}{2}M=\frac{27}{4}N(\frac{h}{9})-\frac{3}{2}N(\frac{h}{3})-\frac{27}{4}N(\frac{h}{3})+\frac{1}{2}N(h)+(\frac{4K_3}{27}h^3+\frac{4K_3}{9}h^3)+\cdots
$$
Multiplying this equation by $2/7$ produces an $O(h^3)$ formula
$$
M=\frac{27}{14}N(\frac{h}{9})-\frac{201}{28}N(\frac{h}{3})+\frac{1}{7}N(h)+\frac{32 K_3}{189}h^3+\cdots
$$
then $N_3(h)=\frac{27}{14}N(\frac{h}{9})-\frac{201}{28}N(\frac{h}{3})+\frac{1}{7}N(h)$ with the truncation error $O(h^3)$.
