Name and explanation of a Numerical Analysis method for solving systems of non-linear equations

195 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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.