Skip to content

w03-g01-newton-raphson

Newton Raphson

The goal of this exercise is to find the value of x^{T}=(x, y) which minimizes the quadratic function S(\boldsymbol{x}) defined by the equation:

S(\boldsymbol{x}) = \boldsymbol{x}^{T} \left(\begin{array}{cc}8 & 2 \\ 2 & 6 \end{array}\right)\boldsymbol{x} - \boldsymbol{x}^{T} \left( \begin{array}{c}1 \\ 2\end{array}\right)

Minimization of S(x,y)

The Newton-Raphson (N-R) method is one of the most widely used methods for root finding. This is an iterative algorithm: given an initial guess x_0, successive iterates satisfy

x_i = x_{i−1} − \frac{f(x_{i−1})}{f'(x_{i−1})}

for i=1,2,3,…. It can be easily generalized to multi-dimensional root finding problems. To solve systems of k equations, the scalars x_n are replaced by vectors \boldsymbol{x_n} and instead of dividing the function f(x_n) by its derivative f'(x_n), one instead has to left multiply the k-dimentional function F(x_n) by the inverse of its k × k Jacobian matrix J_F(x_n). This results in the expression

\boldsymbol{x_i} = \boldsymbol{x_{i−1}} − J_F(\boldsymbol{x_{i−1}})^{-1}F(\boldsymbol{x_{i−1}})

Please refer to the following wikipedia links for a detailed explaination of N-R method and Jacobian matrix.
https://en.wikipedia.org/wiki/Newton%27s_method
https://en.wikipedia.org/wiki/Jacobian_matrix_and_determinant

For this exercise, since A is positive definite, the N-R method will allow us to find the minimum of the quadratic function

S(\boldsymbol{x}) = \dfrac{1}{2}\boldsymbol{x}^{T}\boldsymbol{A}~\boldsymbol{x}-\boldsymbol{x}^{T}\boldsymbol{b}

The minimizer of the above function is also the solution of the linear system of equation

\boldsymbol{A}~\boldsymbol{x} = \boldsymbol{b}

Implementation

Your code should have the following variables:

max_iter for the maximum number of iterations to reach the convergence

epsilon tolerance value acceptable for a converged solution

x_prev a 1D array that stores the values of (x, y) at i-1 step

x_next a 1D array that stores the values of (x, y) at i step

A a 2D array to store the second derivative of function S(x,y)

b a 1D array that stores the constant item of the first derivative of function S(x,y)

delta_x a 1D array that stores the values of x_next - x_prev

Your code should be named newton_raphson.cpp and be placed into the tehpc/basics/ directory. Follow these steps to write the code:

  1. Declare all variables described above.

  2. A for loop, that iterates for i = 1,2,3,...,max_iter where max_iter is the maximum number of iterations to reach the convergence.

  3. A if statement to terminate the iteration when |x_next - x_prev| < epsilon. Print a message, displaying the values of (x,y), when convergence is succesfully reached within the given number of iterations.

  4. Print an error message, displaying Convergence not reached when number of iterations exceed the maximum iterations max_iter

Hint

\boldsymbol{A}^{-1} = \frac{adj(\boldsymbol{A})}{det(\boldsymbol{A})}

Notes

Compile and run your code by:

  1. going into the tehpc/build/basics/ folder
  2. compile with the following command: g++ -Werror -Wpedantic -g -o newton_raphson ../../basics/newton_raphson.cpp
  3. run code with ./newton_raphson