2
$\begingroup$

I'd like to prove that the following non-linear system

$ F(x) = \begin{pmatrix} x_1^3 + x_2^3 - 4 \\ x_1^3 - x_2^3 \\ \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \end{pmatrix} $ will converge when using the Newton's Method for the start vectors $x^{(0)} = (x_1^{(0)}, x_2^{(0)})^T \in [1,2] \times [1, 2] \subset \mathbb R^2$.

I'm trying to use this lemma I learned on class

Let $f: D \subset \mathbb R^n \rightarrow \mathbb R^n$ be continuously differentiable and let $D$ be convex as well open, $f'$ is the jacobian matrix. If $q = \sup_{x\in D}||f'(x)|| < 1$ then $f$ is a contraction mapping using the Norm $|| \cdot ||$ with a contraction rate $q$.

I have calculated the Jacobian matrix, and it is as follows $ \begin{pmatrix} 3x_1^2 & 3x_2^2 \\ 3x_1^2 & - 3x_2^2 \\ \end{pmatrix} $ Using the maximum norm (sum of lines) for matrixes, I get: $||F' (x_1, x_2)||_\infty = \max \{3x_1^2 + 3x_2^2, 3x_1^2 - 3x_2^2\} = 3x_1^2 + 3x_2^2$ which is for sure not $< 1$ in the desired interval. Where have I gone wrong? Thanks a lot guys!

  • 1
    You would have to apply this lemma not to $F$ but to the "Newton map" $N(x):=x-F'^{-1}\bigl(F(x)\bigr)$.2012-07-03

2 Answers 2

0

Suppose that $x$ is one vector root of $F(x)=0$, then $F(x_k)-F(x)=F'(x)(x_k-x)+(O(x_k-x)^2)$, here $F'(x)$ is a Jocobian matrix. $x_{k+1}=x_k-F(x_k)/F'(x_k)$

as for this problem $F'(x)$ is $ \begin{pmatrix} 3x_1^2 & 3x_2^2 \\ 3x_1^2 & - 3x_2^2 \\ \end{pmatrix} $

Using Newton's method: $x_{k+1}=x_k-F(x_k)/F'(x_k)$, then $x_{k+1}-x=x_k-x-(F(x_k)-F(x))/F'(x_k)=F^{-1}(x_k)(O(x_k-x)^2)$. If $|F^{-1}(x_k)|\le M$, then newton's method will converge.

where you also need to think which root the formula will converge to, because sometime you can find several roots, at different initial condition will have different root's convergence.

  • 1
    I don't see how this answers the question. It does not seem to address the given lemma.2013-05-12
0

For a more general approach on the convergence of Newton method ( and different from his attempt ) see the this article here. In Theorem 1.1 make $E = F = \mathbb{R}^2$ both with norm $ \| (x_1,x_2)\|= |x_1|+|x_2|. $ and make your initial point in $B(x_0,r)$ whit $x_0=(\frac{3}{2},\frac{3}{2})$ and $r=\frac{1}{2}$, i.e. \begin{align} B(x_0,r)= & \left\{ (x_1,x_2)\in \mathbb{R}^2 : \bigg\| (x_1,x_2)-\left(\frac{3}{2},\frac{3}{2}\right)\bigg\|= |x_1-\frac{3}{2}|+|x_2-\frac{3}{2}| < \frac{1}{2} \right\} \\ = & (1,2)\times(1,2) \end{align} Nothe that $\overline{B(x_0,r)}=[1,2]\times[1,2]$.