Subsections

• 2.6.1 Introduction
• 2.6.2 Basic Newton Method
• 2.6.3 Simplified Newton Method
• 2.6.4 Damping

2.6 Newton Methods

2.6.1 Introduction

The discretization of the non-linear PDE systems leads to a large system of nonlinear algebraic equations. There are various methods which solve such systems. Among them the most popular is a Newton method with it's variations.

2.6.2 Basic Newton Method

Generally we have a system of N non-linear algebraic equations

$$g_i(x_1, x_2,\dots,x_N) = 0,\quad i=1,\dots,N,\quad (\mathbf{g}(\mathbf{x})=0),$$ (2.32)

assuming that the functions $g_i$ have continues first order derivations with respect to $x_j$. If the values $x_j^{k}$ $(j=1,\dots,N)$ of the $k$-th approximate solution are known, we write Taylor series expansion of the functions $g_i$ in the vicinity of $x_{j}^k$,

$$g_i(x_1, x_2,\dots,x_N)=g_i(x_1^{k}, x_2^{k},\dots,x_N^{k})+\sum_... ...2^{k},\dots,x_{N}^{k})}{\partial x_j}\delta_j^{k}+O(\delta_p^{k},\delta_q^{k}),$$ (2.33)

for $i=1,\dots,N$, where $\delta_j^{k}=x_j-x_j^{k}$. By choosing for $x_j$ the exact value $x_j^{*}$ and neglecting the terms of order $\delta_p^{k},\delta_q^{k}$ we have from (2.33)

$$\sum_{j=1}^{N}\frac{\partial g_i(x_1^{k}, x_2^{k},...,x_{N}^{k})}... ...tial x_j}\delta_j^{k}+g_i(x_1^{k}, x_2^{k},\dots,x_{N}^{k})=0,\quad i=1,\dots,N$$ (2.34)

The matrix

$$[\mathbf{J}]_{N\times N},\quad J_{ij}=\frac{\partial f_i(x_1^{k}, x_2^{k},\dots,x_{N}^{k})}{\partial x_j},$$ (2.35)

is called Jacobi matrix. In the case when this matrix is non-singular the linear equation system (2.34) can be solved. Depending on the problem itself different types of linear solvers should be applied [11].
The solutions of the linear system (2.34) are the increments $\delta_j^{k}$ $(j=1\dots N)$ and with these increments we can calculate new approximation,

$$x_j^{k+1}=x_j^{k}+t_k\delta_j^{k},\quad j=1,\dots,N.$$ (2.36)

The determination of damping value $t_k$ is the question of trial and error. The sequences often used for subsequent trials are,

$$t_k=\frac{1}{2^l} \quad t_k = \frac{1}{2^{\frac{l(l+1)}{2}}},\quad l=0,1,2,\dots$$ (2.37)

$t_k$ is accepted if the following criterion is fulfilled,

$$\Vert\mathbf{g}(\mathbf{x}^k+t_k\mathbf{\delta}^k)\Vert<\Vert\mathbf{g}(\mathbf{x}^k)\Vert,$$ (2.38)

where we use Euclidian norm.

2.6.3 Simplified Newton Method

Since the calculation of the Jacobi matrix is a very computer resources-consuming procedure, one can for a number of subsequent Newton iterations also use the same Jacobi matrix (2.35). In that case on obtains,

$$\sum_{j=1}^{N}\frac{\partial g_i(x_1^{0}, x_2^{0},...,x_{N}^{0})}{\partial x_j}\delta_j^{k}+g_i(x_1^{k}, x_1^{k},...,x_{N}^{k})=0,\quad i=0\dots N.$$ (2.39)

The simplified Newton method obviously has a worse convergence behavior.

2.6.4 Damping

In the cases where the convergence of the Newton scheme is attainable only for a very small time steps, methods for the enforcing of the convergence must be applied. The method which has also successfully been applied in semiconductor device modelling [4], is the so-called Bank-Rose algorithm [12].

Figure 2.3: Bank-Rose algorithm.

The algorithm is represented in Figure 2.3. It controls the behavior of Newton scheme through a damping factor $t_k$. The parameter of crucial importance for the algorithm is $K$. In Figure 2.3 we take $K_k/10$ as initial estimate for $K_{k+1}$. Alternatively, we have used $K_{k+1}=K_k 4^{j-k-1}$, where $j$ is the counter of failed tests ${t_k}^{-1}(1-\Vert\mathbf{g}(\mathbf{x}_{k+1})\Vert/\Vert\mathbf{g}(\mathbf{x}_{k})\Vert)<\omega$.
The algorithm searchs through the vincinity of the initial solution $\mathbf{x}_k$ for the shortest path through the attraction region of the Newton scheme to reach the next approximation $\mathbf{x}_{k+1}$. In the cases when the Bank-Rose algorithm fails the parameter $K$ grows infinitely and an improved approximation $\mathbf{x}_{k+1}$ is never found.