2
$\begingroup$

Use Newtons method with initial guess $x^{(0)} = (0,0)$ to find the second iteration $x^{(2)}$ of $$\left(1-2x_1\right)^2+x_1x_2 = 1$$ $$\left( x_1-1 \right)^2+\left( x_2+2 \right)^2 = -2$$

I know that Newton Method states:

If $x_n$ is an approximation a solution of $f(x) = 0 $ and if $f'(x_n) \ne 0 $ then the next approximation is given by, $$x_{n+1} = x_n -\frac{f(x_n)}{f'(x_n)}$$

But how can I use this to solve my problem? Is my question a system of equations?

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ How can a sum of two suares be negative? $\endgroup$ – Dr. Sonnhard Graubner Oct 31 '18 at 16:55
  • $\begingroup$ @Moo could you show the workings? $\endgroup$ – fr14 Oct 31 '18 at 17:00
  • $\begingroup$ @Moo that would be great, and yeah it is written correctly $\endgroup$ – fr14 Oct 31 '18 at 17:05
  • $\begingroup$ Then there are no real solutions that could be found by numerical methods. If you are looking for complex solutions, you should say so. But they can not be found by starting from a real point. $\endgroup$ – Lutz Lehmann Oct 31 '18 at 17:08
3
$\begingroup$

$\color{red}{Note!}$ There is something wrong with this problem as you have the sum of two squares equal to a negative result! I suspect they meant to have a negative in that second expression somewhere and there is a typo. Another possibility is that they are looking for imaginary roots, but then the initial condition would have been given as an imaginary vector. Regardless, we can still find the first two iterations by going through the steps, but this will never converge based on this.

The regular Newton-Raphson method is initialized with a starting point $x_0$ and then you iterate $\tag 1x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$

In higher dimensions, there is an exact analog. We define:

$$F\left(\begin{bmatrix}x_1\\x_2\end{bmatrix}\right) = \begin{bmatrix}f_1(x_1,x_2) \\ f_2(x_1,x_2) \end{bmatrix} = \begin{bmatrix}(1-2x_1)^2+x_1x_2 -1 \\ (x_1-1)^2+( x_2+2 )^2 +2\end{bmatrix} = \begin{bmatrix}0\\0\end{bmatrix}$$

The derivative of this system is the $2x2$ Jacobian given by:

$$J(x_1,x_2) = \begin{bmatrix} \dfrac{\partial f_1}{\partial x_1} & \dfrac{\partial f_1}{\partial x_2} \\ \dfrac{\partial f_2}{\partial x_1} & \dfrac{\partial f_2}{\partial x_2} \end{bmatrix} = \begin{bmatrix} x_2-4 (1-2 x_1)&x_1\\ 2(x_1-1)& 2 (x_2+2) \end{bmatrix}$$

The function $G$ is defined as:

$$G(x) = x - J(x)^{-1}F(x)$$

and the functional Newton-Raphson method for nonlinear systems is given by the iteration procedure that evolves from selecting an initial $x^{(0)}$ and generating for $k \ge 1$ (compare this to $(1)$),

$$x^{(k)} = G(x^{(k-1)}) = x^{(k-1)} - J(x^{(k-1)})^{-1}F(x^{(k-1)}).$$

We can write this as:

$$\begin{bmatrix}x_1^{(k)}\\x_2^{(k)}\end{bmatrix} = \begin{bmatrix}x_1^{(k-1)}\\x_2^{(k-1)}\end{bmatrix} + \begin{bmatrix}y_1^{(k-1)}\\y_2^{(k-1)}\end{bmatrix}$$

where

$$\begin{bmatrix}y_1^{(k-1)}\\y_2^{(k-1)}\end{bmatrix}= -\left(J\left(x_1^{(k-1)},x_2^{(k-1)}\right)\right)^{-1}F\left(x_1^{(k-1)},x_2^{(k-1)}\right)$$

Using the given starting vector

$$x^{(0)} = \begin{bmatrix}x_1^{(0)}\\x_2^{(0)}\end{bmatrix} = \begin{bmatrix}0\\0\end{bmatrix}$$

The first two iterations are

$$x^{(1)} =\begin{bmatrix}x_1^{(1)}\\x_2^{(1)}\end{bmatrix} = \begin{bmatrix} 0\\-1.75 \end{bmatrix}, x^{(2)} =\begin{bmatrix}x_1^{(2)}\\x_2^{(2)}\end{bmatrix} = \begin{bmatrix} 0\\-7.875 \end{bmatrix}$$

Of course, for a different starting vector you are going to get a different solution and perhaps no solution at all.

Note: There are also other approaches that do not require Newton's Method to solve this, for example, we have a $2x2$ matrix and can use many approaches to solve that.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ That is what I mean, there is some typo, but it could be there is a negative in any of the three expressions in the second equation. $\endgroup$ – Moo Oct 31 '18 at 17:23
  • $\begingroup$ Note, it can be $-a^2 + b^2 = -2$ or $a^2 - b^2 = -2$ or $a^2 + b^2 = 2$, you have to check the original problem statement or ask whomever wrote the problem. Please be sure to understand that the iterates shown are wrong for the corrected problem and we are sure these will never converge because the problem is errant. $\endgroup$ – Moo Oct 31 '18 at 17:47
  • 1
    $\begingroup$ Yes, the shown iterations are correct for the stated "wrong" problem. :-) $\endgroup$ – Moo Oct 31 '18 at 17:58
1
$\begingroup$

Yes, your question is system of equations. Defining
$$f_1 = (1-2x_1)^2 + x_1x_2 -1$$ $$f_2 = (x_1-1)^2 + (x_2+2)^2 +2$$ and $$ f=\left[f_1,f_2\right]$$ you in fact are searching for $x=[x_1,x_2]$ such that $f(x)=0$. Note that the above problem is equivalent to yours, but it was reformulated so it has the zero right-hand side. That is a useful convention for all nonlinear algebraic equations in general.

Also, note that the formula for Newton's method you wrote above is to be used only for the scalar equations, but your example is equation in 2 variables. Therefore, the derivative (by which you divide in your formula above) is in this case a 2-by-2 matrix and hence you will have to substitute the division by inversion or ideally by process of solving a 2-by-2 system of linear algebraic equations.

| cite | improve this answer | | | | |
$\endgroup$
1
$\begingroup$

You need to solve this for a vector-valued system of equations $F(x)=y$ with the Jacobian matrix $F'(x)$ as derivative. Then the Newton step is $$ x_{n+1}=x_n-F'(x_n)^{-1}(F(x_n)-y) $$ or in steps:

  • compute $A_n=F'(x_n)$, $b_n=y-F(x_n)$, then
  • solve the linear system $A_ns_n=b_n$ for $s_n$, and finally
  • set $x_{n+1}=x_n+s_n$.
| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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