Linearization of Single Variable Non-Linear function

Linearization is a way to approximate a non-linear function around a point. In the blog post, I’ll show an implementation of best linearization of an equation around a point using Newton-raphson method. Before proceeding further, please note the following.

  1. Newton raphson is better suited for monotonic functions or in the regions where monotonic behaviour is seen. Hence, my implementation is not ideal condition.
  2. Newton Raphson may not converge if the equation may achieve a horizontal or vertical slope before the required point.

Now, with that out of the way, let me show you cool function which I tried to linearize.

Problem Statement

Consider the following non-linear equation. u(x)=xβˆ’x2+Ξ³(14Ο€sin⁑(2Ο€xΞ³)βˆ’x2Ο€sin⁑(2Ο€xΞ³)βˆ’Ξ³4Ο€2cos⁑(2Ο€xΞ³)+Ξ³4Ο€2) \displaystyle{u\left( x \right) = x - x^2 + \sqrt\gamma\left( \frac{1}{4\pi}\sin\left( \frac{2\pi x}{\gamma} \right)- \frac{x}{2\pi}\sin\left( \frac{2\pi x}{\gamma} \right) -\frac{\gamma}{4\pi^2}\cos\left( \frac{2\pi x}{\gamma} \right) + \frac{\gamma}{4\pi^2} \right) } where x∈[0,1]x \in [0,1] and Ξ³\gamma is a parameter that ranges from 10βˆ’110^{-1} to 10βˆ’210^{-2}. The resulting plots for this equation for various set of Ξ³\gamma values are as follows:

plot-gamma01plot-gamma005plot-gamma001

Derivation of linear equation

The linearized equation is of the form, uL(x)=c1+c2x \displaystyle{u_L(x) = c_1 + c_2 x} Applying the boundary conditions at index i=0i=0,

u(x0)=c1+c2x0uβ€²(x0)=c2 \begin{aligned} u(x_0) &= c_1 + c_2 x_0 \\ u'(x_0) &= c_2 \end{aligned}

we get,

uL(x)=u(x0)+u’(x0)(xβˆ’x0) \displaystyle{u_L(x) = u(x_0) + u’(x_0)(x-x_0)}

where,

u’(x)=(1βˆ’2x)(1+12Ξ³cos⁑(2Ο€xΞ³)) \displaystyle{u’(x) = (1-2x) \left( 1+ \frac{1}{2\sqrt{\gamma}}\cos\left(\frac{2\pi x}{\gamma} \right) \right) } linearplot

Algorithm

Rearranging uL(x)u_L(x) in terms of xx and substituting uL(x)=u(xβˆ—)u_L(x) = u(x^*), we get xi+1=xi+u(xβˆ—)βˆ’u(xi)u’(xi) x_{i+1} = x_i + \frac{u(x^*) - u(x_i)}{u’(x_i)} Then, the code is generated as per following pseudocode.

1
2
3
4
5
6
7
8
Ɛ = 1e-11
x_i = 0
x* = 0.5

repeat
	x_i+1 = x_i + (u(x*) - u(x_i))/u'(x_i)
	residue = |u(x*) - u_l(x*)|
while residue > Ɛ

Convergence

Solution 1

Here’s the Convergence of solution with x0=0.0,Ξ³=0.1x_0=0.0, \gamma=0.1

anim_fps1

This was done in 17 iterations.

convergence-residue

Solution 2

Here is another solution which took quite a detour before convergence. This is the convergence of solution with x0=0.0,Ξ³=0.031x_0=0.0, \gamma=0.031 which took 87 iterations.

convergence-uxplot2

convergence-residue2

There is no exact way to predict the iterations or whether it will converge because the equation doesn’t satisfy the conditions meant for the newton raphson.

Convergence for various parameter values

To get the general idea of convergence, I generated a surface plot of 1No of iterations\frac 1 {\text{No of iterations}} for various initial conditions and parameter values - x0∈[0,1],γ∈[0.01,0.1]x_0\in[0,1], \gamma\in[0.01, 0.1].

Here, I had to truncate the height to 0.15 since, for the exact condition x0=xβˆ—x_0 = x^*, the equation was linearized in one iteration. The peaks represent lesser iterations than the trough.

I also generated a contour plot of the number of iterations ranging upto 10,000 iterations which I had set as the maximum limit.

convergence-contour-1

I had generated the above code as a python notebook which can be found here or it can be run directly online using binder if you follow this link.

Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Load Comments?