Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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)$. –  Christian Blatter Jul 3 '12 at 10:00
add comment

2 Answers

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.

share|improve this answer
1  
I don't see how this answers the question. It does not seem to address the given lemma. –  Daryl May 12 '13 at 12:56
add comment

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]$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.