next up previous contents
Next: 2.7 Assembling Up: 2. Finite Element Method Previous: 2.5 Finite Element Spaces


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

$\displaystyle 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$,

$\displaystyle 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)

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

$\displaystyle [\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,

$\displaystyle 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,

$\displaystyle t_k=\frac{1}{2^l}$   or$\displaystyle \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,

$\displaystyle \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,

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

Image grph1_snapshot_cut_small

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.

next up previous contents
Next: 2.7 Assembling Up: 2. Finite Element Method Previous: 2.5 Finite Element Spaces

H. Ceric: Numerical Techniques in Modern TCAD