3
$\begingroup$

In a non-english textbook of Numerical Analysis there is a method for solving systems of non-linear equations. But not only I can't understand how this method is used but I can't even found the name of it in english so to be able to search for it. The direct translation of its name is "Perturbation of Parameters" but I don't think that this is the name used in english. I have searched in various textbooks in the chapters concerning systems of equations in case I find it with no luck.

I will describe the method as it is presented in the textbook and I hope that someone will recognize it and tell me its name in english. If he can also describe it as to how it is used that would be great.

Method:

We have the system of non-linear equations:

\begin{align*} &f_{1}(x_{1},...,x_{n})=0\\ &\quad \vdots\\ &f_{n}(x_{1},...,x_{n})=0 \end{align*}

Instead of using these equations we use the following ones:

\begin{align*} &\sigma_{1}^{(0)}(x_{1},...,x_{n})=0\\ &\quad \vdots \\ &\sigma_{n}^{(0)}(x_{1},...,x_{n})=0 \end{align*}

We must already know one solution of the second system which we must now transform slightly, having as a goal to match the first one.

The transformation of the second set of equations is done in $N$ steps by using:

\begin{equation*} \sigma_{i}^{(K)}(x_{1},...,x_{n})+\frac{K}{N}\left[f_{1}(x_{1},...,x_{n})-\sigma_{i}^{(K-1)}(x_{1},...,x_{n})\right] \end{equation*}

Where $i=1,2,...,n, \quad K=1,2,...,N$

The known solution of the second set of equations is:

\begin{equation*} x_{1}^{(0)},...,x_{n}^{(0)} \end{equation*}

and is used as the first approach in the first step.

In the last step $K=N$ and at that point the second set of equations matches the first one.

It seems hard to believe that there won't be someone able to identify it.

$\endgroup$
  • $\begingroup$ Slightly reminds me the numerical continuation method. Take a look at en.wikipedia.org/wiki/… . The pararmeter $\lambda = \frac{K}{N}$ for your case $\endgroup$ – uranix Jun 25 '15 at 21:53
  • $\begingroup$ @uranix thank you I will check it. $\endgroup$ – Adam Jun 25 '15 at 21:58
0
$\begingroup$

Let $\mathbf{F}(\mathbf{x}) = 0$ be the original set of equations. Assume that we could solve $\mathbf{S}(\mathbf{x}) = 0$ easily. Let's constuct a parametrical system of equations $$ \mathbf{F}(\lambda, \mathbf{x}) = \lambda \mathbf F(\mathbf x) + (1 - \lambda) \mathbf S(\mathbf x) = \mathbf S(\mathbf x) + \lambda (\mathbf F(\mathbf x) - \mathbf S(\mathbf x))= 0. $$ Solving it with $\lambda = 0$ is the same as solve $\mathbf S(\mathbf x) = 0$, which is simple. Solving it with $\lambda = 1$ is hard, since it is the original problem $\mathbf F(\mathbf x) = 0$.

Let's move from $\lambda = 0$ to $\lambda = 1$ in $N$ steps, with $\lambda_k = \frac{k}{N}, k = 0,1,2, \dots, N$.

The solution for $\mathbf{F}(\lambda_0, \mathbf{x}) = 0$ is already known, it is the solution $\mathbf x^{(0)}$ to $\mathbf S(\mathbf x)= 0$. The solution for $\mathbf{F}(\lambda_1, \mathbf{x}) = 0$ should not be far away from that. Using Newton's method we could find the $\mathbf x^{(1)}$ using $\mathbf{x}^{(0)}$ as the initial guess.

Repeat the same but for $\mathbf{F}(\lambda_2, \mathbf{x}) = 0$ using the solution $\mathbf x^{(1)}$ as the initial guess. Doing this procedure $N$ times brings us to $\lambda_N = 1$ and we finally solve the initial problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.