0

Consider the non-linear equation $x^3 = 3375$. The real solution is given by $x^* = 15$. The iteration sequence $\{x^{(k)}\}$ has the convergence order $p$, if

$$\lim_{k \rightarrow \infty} {||x^{(k+1)} - x^*||_2 \over ||x^{(k)} - x^*||_2^p} = C$$

for $C \ge 0$. Determine the parameters $p$ and $C$ numerical by using $x^{(0)} = 1$ and $k_{max} = 16$. To do so, assume that

$$\log||x^{(k+1)} - x^*||_2 \approx \log(C||x^{(k)} - x^*||_2^p)$$

and solve the problem of least squares.

The only thing I know about the problem / method of least squares is that it has something to do with minimizing $1/2||Ax - b||_2^2$, and that is done by finding an $x \in \Bbb R^n$ such that $A^*Ax = A^*b$.

But I don't see how to apply this here. Could anybody explain to me what I have to do actually?

Thanks in advance!

Community
  • 1
Julian
  • 1,401

2 Answers2

1

Despite being a bit confused myself by the problem description, I'll take a stab at it:

The only way I see a least-squares problem arising out of this is if you construct the functional:

$$ f(p,C)=\sum_{k=k_{min}}^{k_{max}} \Big[\frac{|x^{(k+1)}-x_*|^p}{|x^{(k)}-x_*|}-C\Big]^2 $$

which you can minimise by requiring $f$ to be stationary with respect to $p$ and $C$, i.e.,

$$\frac{\partial f}{\partial p}=0$$

and

$$\frac{\partial f}{\partial C}=0$$

and solve the system of non-linear equations with a 2-D analogue of Newton's Method.

What confuses me however, is the iteration sequence for $x^{(k+1)}$

$$\log||x^{(k+1)} - x^*||_2 \approx ||x^{(k)} - x^*||_2^p$$

because I don't see how that converges to $x_*$ for any value of $p$.

Sharat V Chandrasekhar
  • 1,168
1

Your last equation should read $$ \log\|x^{(k+1)}-x^*\| \approx p·\log\|x^{(k)}-x^*\|+c $$ or $$ \log e_{k+1}=p·\log e_k+c $$ where $c=\log C$ and $e_k=\|x^{(k)}-x^*\|$. This can be treated by standard linear regression for the pairs $(x_k,y_k)=(\log e_k,\log e_{k+1})$.

Graphically you would have to determine the slope in a log-log-plot of the points $(e_k,e_{k+1})$

Lutz Lehmann
  • 126,666