Using Newtons method

471 Views Asked by At

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?

3

There are 3 best solutions below

3
On BEST ANSWER

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

0
On

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$.
0
On

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.