<s>[INST] Solve $x_{n+1}=Ax_n+\frac{B}{x_n^5}+\frac{C}{x_n^9}$ 
For $$x_{n+1}=Ax_n+\frac{B}{x_n^5}+\frac{C}{x_n^9}$$
  a. Find $A,B,C$ that will give an optimal approximation (Highest order) for $\sqrt{2}$
b. Solve the system using LU decomposition, what is the given order? 

So we are looking to approximate the function $f(x)=x^2-2$
therefore we will demand that $x=\sqrt{2}$ is a fixed point of the iterative method $g(x)=Ax+\frac{B}{x^5}+\frac{C}{x^9}$ i.e:
$$\sqrt{2}=g(\sqrt{2})=\sqrt{2}A+\frac{B}{(\sqrt{2})^5}+\frac{C}{(\sqrt{2})^9}$$
$$\sqrt{2}=\sqrt{2}A+\frac{B}{4\sqrt{2}}+\frac{C}{16\sqrt{2}}$$
Therefore:
$$a)\sqrt{2}=\sqrt{2}(A+\frac{B}{4\cdot 2}+\frac{C}{16\cdot 2})\rightarrow 1=A+\frac{B}{8}+\frac{C}{32}$$
Now we will demand that $g'(\sqrt{2})=0$
$$0=g'(\sqrt{2})=A-\frac{5x^4B}{x^{10}}-\frac{9x^8C}{x^{18}}\Rightarrow b. 0=A-\frac{5B}{8}-\frac{9C}{32}$$
can we next demand that $g''(\sqrt{2})=0$? (the $x^2-2$ second derivative is non zero?)
If so we get:
$$0=g(\sqrt{2})=\frac{30B}{x^7}+\frac{90C}{x^11}\Rightarrow 0=\frac{30B}{8\sqrt{2}}+\frac{90C}{32\sqrt{2}}\Rightarrow c) 0=\frac{15B}{4\sqrt{2}}+\frac{45C}{16\sqrt{2}}$$
Now we have $3$ equations so we can find $A,B,C$:
a)-b):
$$1=\frac{6B}{8}+\frac{10C}{32}$$
From c) we get $$-B=\frac{3}{4}C$$
Plugin it back we get $C=-4, B=3, A=\frac{3}{4}$
Is this answer correct? How to use LU decomposition here if there is no matrices?
 [/INST] Your answer is just fine... Your linear system is
$$
\begin{cases}
g(\sqrt 2) = \sqrt 2\\
g'(\sqrt 2)=0\\
g''(\sqrt 2)=0
\end{cases}
$$ 
or, in terms of $A,B,C$:
$$
\begin{bmatrix}
\sqrt 2 & \frac{\sqrt 2}{8} & \frac{\sqrt 2}{32}\\
1 & -\frac 58 & -\frac{9}{32}\\
0 & \frac{15 \sqrt 2}{8} &\frac{45 \sqrt 2}{32}
\end{bmatrix}\begin{bmatrix}A \\ B \\ C\end{bmatrix}=\begin{bmatrix}\frac{\sqrt 2}{2} \\ 0 \\0\end{bmatrix}
$$
Now, you just need to solve this system using the LU decomposition. In the end you should obtain the values of $A, B, C$ you already have...
Edit:
The requirement for $g'(\sqrt 2) = g''(\sqrt 2)=0$ comes from the fact that a convergent fixed point iteration of the form $x_{n+1}=g(x_n)$ converges with at least order $p$ when $g'(z)=\cdots = g^{(p-1)}(z)=0$. This comes from Taylor's formula:
$$
g(x_n) = g(z) + g'(z)(x_n-z) + \cdots \frac{1}{(p-1)!}g^{(p-1)}(z)(x_n-z)^{p-1} + \frac{1}{p!} g^{(p)}(\xi)(x_n-z)^p 
$$
If you substitute  $g'(z)=\cdots = g^{(p-1)}(z)=0$ and note that $g(x_n)=x_{n+1}$, you have that
$$
x_{n+1} - z = \frac{1}{p!} g^{(p)}(\xi)(x_n-z)^p
$$ 
from where you can deduce that
$$
\lim \frac{|x_{n+1}-z|}{|x_n-z|^p} = \frac{g^{(p)}(z)}{p!}.
$$
</s>