View source for Linearization methods

<!--
l0595401.png
$#A+1 = 32 n = 0
$#C+1 = 32 : ~/encyclopedia/old_files/data/L059/L.0509540 Linearization methods
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

Methods that make it possible to reduce the solution of non-linear problems to a successive solution of related linear problems.

Consider a non-linear operator equation

$$ \tag{1 }
L ( u)  =  f ,
$$

where the operator  $  L $
maps a Banach space  $  H $
into itself,  $  L ( 0) = 0 $, 
and is Fréchet differentiable. One of the classical methods for solving (1), based on linearizing (1), is the Newton–Kantorovich iterative method (cf. also [[Newton method|Newton method]]; [[Kantorovich process|Kantorovich process]]), in which from a known approximation  $  u  ^ {n} $
a new one  $  u  ^ {n+} 1 $
is determined as the solution of the linear equation

$$ \tag{2 }
L _ {u  ^ {n}  }  ^  \prime 
( u  ^ {n+} 1 - u  ^ {n} ) + L ( u  ^ {n} )  =  f .
$$

The basis of the method is the approximation of  $  L ( u  ^ {n} + z ) $(
for small  $  \| z \| $) 
by the expression  $  L _ {u  ^ {n}  }  ^  \prime  ( z) $, 
where  $  L _ {u  ^ {n}  }  ^  \prime  $
is the [[Fréchet derivative|Fréchet derivative]] of  $  L $
at the point  $  u  ^ {n} $. 
Various modifications of this method and corresponding estimates of the rate of convergence can be found in [[#References|[1]]]–[[#References|[4]]]. The operator equation (1) itself may correspond, for example, to a non-linear boundary value problem for a partial differential equation (see [[#References|[2]]], [[#References|[4]]], [[#References|[5]]]), and then at each stage in (2) one must solve a linear boundary value problem, which makes it necessary to use numerical methods and some discretization of the original problem and the linear problems related to it. From the computational point of view it is more natural to consider linearization methods after a suitable discretization of the original problem, taking (1) as an operator equation in a finite-dimensional space.

Another example of a linearization method for the approximate solution of (1) is the iterative method of sections (of false position) (see [[#References|[2]]], [[#References|[3]]]). In many cases, for problems (1) that arise in mathematical physics it is preferable to carry out the linearization of  $  L ( u  ^ {n} + z ) $
on the basis of physical arguments, replacing  $  L ( u  ^ {n} + z ) $
by  $  M _ {u  ^ {n}  } ( z) $
for some a linear operator  $  M _ {u  ^ {n}  } $(
see [[#References|[5]]]–[[#References|[10]]]). Then the resulting iterative methods can be written in the form

$$ \tag{3 }
M _ {u  ^ {n}  } ( u  ^ {n+} 1 )  = \ 
f - ( L ( u  ^ {n} ) - M _ {u  ^ {n}  } ( u  ^ {n} ) ) .
$$

Examples of methods of this kind are methods of elastic solutions and variable parameters for the solution of non-linear problems in elasticity theory (see [[#References|[5]]]–[[#References|[8]]]); for the method of elastic solutions the linear operator  $  M _ {u  ^ {n}  } = M $
corresponds to the operator of linear elasticity theory. Closely related to it are the iterative methods of Kachanov (see [[#References|[9]]], [[#References|[10]]]) and the method of sequential loading (see [[#References|[6]]]–[[#References|[8]]]), which combines the idea of linearization and extension with respect to the parameter. Sometimes, instead of methods such as (3) one uses more general iterative methods of the type

$$ \tag{4 }
M _ {u  ^ {n}  } ( u  ^ {n+} 1 - u  ^ {n} )  = \ 
- \gamma _ {n} ( L ( u  ^ {n} ) - f  )
$$

with an iteration parameter  $  \gamma _ {n} $
subject to choice.

In the realization of these methods one should take into account the approximate nature of a solution of the systems (for example, as a consequence of the application of auxiliary iterative methods) (see [[#References|[1]]], [[#References|[11]]], [[#References|[12]]], for example). In considering non-linear eigen value problems (problems of finding bifurcation points), for example of the form

$$ \tag{5 }
L ( u)  =  \lambda M ( u) ,\ \ 
L ( 0)  =  0 ,\ \ 
M ( 0)  =  0 ,
$$

the idea of linearizing (5) by reducing the investigation of the problem (5) to an investigation of the linear eigen value problem

$$ 
L _ {0}  ^  \prime  ( z)  =  \lambda M _ {0}  ^  \prime  ( z) ,
$$

has turned out to be very fruitful (see [[#References|[13]]], [[#References|[14]]]). One frequently uses linearization of one kind or other in grid methods for solving non-stationary non-linear problems (see [[#References|[15]]]–[[#References|[18]]], for example), which proceeds from known solutions at instants of time up to  $  t _ {n} $
and gives linear equations for the solution at the next discrete instant  $  t _ {n+} 1 = t _ {n} + \tau $(
$  \tau $
is the time step).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M.A. Krasnosel'skii,   G.M. Vainikko,   P.P. Zabreiko,   et al.,   "Approximate solution of operator equations" , Wolters-Noordhoff  (1972)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L. Collatz,   "Funktionalanalysis und numerische Mathematik" , Springer  (1964)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  J.M. Ortega,   W.C. Rheinboldt,   "Iterative solution of non-linear equations in several variables" , Acad. Press  (1970)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  R.E. Bellman,   R.E. Kalaba,   "Quasilinearization and nonlinear boundary-value problems" , Amer. Elsevier  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  B.E. Pobedrya,   "Numerical methods for visco-elastic problems" , ''Elasticity and inelasticity'' , '''3''' , Moscow  (1973)  pp. 95–173  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  J.T. Oden,   "Finite elements of nonlinear continua" , McGraw-Hill  (1972)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  O. Zenkevich,   "The method of finite elements in engineering" , McGraw-Hill  (1977)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  I.V. Svirskii,   "Methods of Bubnov–Galerkin type and succesive approximations" , Moscow  (1968)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  S.G. Mikhlin,   "Numerical realization of variational methods" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  S. Fučik,   A. Kratochvil,   J. Nečas,   "Kačanov–Galerkin method and its applications"  ''Acta Univ. Carolinae Math. Phys.'' , '''15''' :  1–2  (1974)  pp. 31–33</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  S.C. Eisenstat,   M.H. Schultz,   A.H. Sherman,   "The application of sparse matrix methods to the numerical solution of nonlinear elliptic partial differential equations"  D.L. Colton (ed.)  R.P. Gilbert (ed.) , ''Constructive and computational methods for differential and integral equations'' , ''Lect. notes in math.'' , '''430''' , Springer  (1974)  pp. 131–153</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  E.G. D'yakonov,   "Minimization of computational work. Asymptotically optimal algorithms for elliptic problems" , Moscow  (1969)  (In Russian)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  J.B. Keller (ed.)  S. Antman (ed.) , ''Bifurcation theory and nonlinear eigenvalue problems'' , Benjamin  (1969)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  I.V. Skrypnik,   "Non-linear elliptic equations of higher order" , Kiev  (1973)  (In Russian)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  O.A. Ladyzhenskaya,   "The mathematical theory of viscous incompressible flows" , Gordon &amp; Breach  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  E.G. D'yakonov,   "Difference methods for solving boundary value problems" , '''2. Non-stationary problems''' , Moscow  (1972)  (In Russian)</TD></TR><TR><TD valign="top">[17]</TD> <TD valign="top">  G. Fairweather,   "Finite element Galerkin methods for differential equations" , M. Dekker  (1978)</TD></TR><TR><TD valign="top">[18]</TD> <TD valign="top">  M. Luskin,   "A Galerkin method for nonlinear parabolic equations with nonlinear boundary conditions"  ''SIAM J. Num. Anal.'' , '''16''' :  2  (1979)  pp. 284–299</TD></TR></table>

====Comments====
The above article concerns linearization methods in numerical analysis. Such methods also appear in other areas. For example, the study of the operator polynomial  $  L ( \lambda ) = A _ {0} + \lambda A _ {1} + {} \dots + \lambda  ^ {k} A _ {k} $, 
where  $  A _ {0} , \dots , A _ {k} $
are operators acting on a Banach space  $  X $, 
may be reduced to the study of the linear pencil

$$ 
\lambda
\left [

\begin{array}{cccc}
 I  &\dots  & 0  & 0  \\
 0  &\dots  & .  & .  \\
 .  &\dots  & .  & .  \\
 .  &\dots  & I  & 0  \\
 0  &\dots  & 0  &A _ {k}  \\
\end{array}
 \right ]  - \ 
\left [

\begin{array}{cccc}
 0  & I  &\dots  & 0  \\
 .  & 0  &\dots  & .  \\
 .  & .  &\dots  & .  \\
 0  & 0  &\dots  & I  \\
- A _ {0}  &- A _ {1}  &\dots  &- A _ {k-} 1  \\
\end{array}
 \right ] ,
$$

where  $  I $
stands for the identity operator on  $  X $. 
For other examples in this direction see [[#References|[a1]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  I.C. Gohberg,   M.A. Kaashoek,   D.C. Lay,   "Equivalence, linearization, and decomposition of holomorphic operator functions"  ''J. Funct. Anal.'' , '''28'''  (1978)  pp. 102–144</TD></TR></table>