Non-linear system in matrix form

Question

I have some problems by solving a non-linear system. The system may be written in the form:

$Ax=b$

The problem is that matrix $A$ and vector $b$ depend on $x$ so

$A=A(x) \quad b=b(x) \quad \Longrightarrow\quad Ax=b \equiv A(x)x=b(x)$

So there is no way to solve the system in the standard way $x=A^{-1}b$. Since a numerical solution would be enough for my problem, my idea was to proceed numerically: I guess a certain $x_0$ (supposed to be near the real solution of the system) and I evaluate $x_1 = A^{-1}(x_0)b(x_0)$. Thereafter, I proceed by iterating:

$x_{k+1} = A^{-1}(x_k)b(x_k)$

The problem is that this procedure never converges. Is there something wrong in your opinion? Do you think there are better way to solve this problem?

Thank you very much!

Answer 1

your numerical approach does not solve your problem. You just assume a random starting point and plug that into your equation giving basically a random output. Now you use this random output again as input. There is no reason why your algorithm should ever converge, as you do not compare your result with the expected result in any way. You should at least plug your solution in the original equation $A(x)\cdot x$ and see how much it differs from $b(x)$ to get at least any information about if your most recent iteration got better or not.

I suggest you start reading here: https://en.wikipedia.org/wiki/Newton%27s_method

Or here on stackexchange about the Newton-Raphson algorithm do get a better understanding of the way to solve such problems

Answer 2

You are looking for roots of $$ f(x) = A(x) x - b(x) $$ or in components $$ f_i(x) = \sum_j a_{ij}(x) x_j - b_i(x) $$ so you could try some procedure for root solving.

If you have partial derivatives $J(x)=(\partial f_i/\partial x_j|x)$, you can try Newton-Raphson:

Solving the linear system $$ J(x_n) \, \Delta x_n = -f(x_n) $$ for the unknown $\Delta x_n$ and then iterating to the next point via $$ x_{n+1} = x_n + \Delta x_n $$ In your case $$ \frac{\partial f_i}{\partial x_k} = \left( \sum_j \frac{\partial a_{ij}}{\partial x_k} x_j + a_{ij} \delta_{jk} \right)- \frac{\partial b_i}{\partial x_k} $$ Otherwise you might check for some bisection method.

Another road might be recasting the problem as a fixed-point iteration $$ F(x) = x $$ e.g. for $$ F(x) = (A(x) + 1) x - b(x) $$