Suppose you have an equation of the form $Ax=f(x)$, where $A$ is a $n \times n$ matrix, $x$ is a vector of length $n$ and $f(\cdot)$ is some function. Is there a name for this sort of problem?
$\begingroup$
$\endgroup$
6
asked Sep 7, 2012 at 1:14
-
4$\begingroup$ In other words, you have an equation of the form $g(x) = 0$ where $g$ is some function. $\endgroup$– Qiaochu YuanSep 7, 2012 at 2:27
-
$\begingroup$ You can reduce almost all of mathematics to your equation. Hardly a helpful concept, I'm afraid. $\endgroup$– Felix GoldbergSep 7, 2012 at 10:09
-
$\begingroup$ @Felix: I don't understand. Your equation and my equation are equivalent. Take $g(x) = f(x) - Ax$. $\endgroup$– Qiaochu YuanSep 8, 2012 at 20:16
-
$\begingroup$ @Qiaochu: Well, yes. But I thought you were over-generalizing the question to a point of absurdity. Perhaps I over-reacted, so I offer my apologies. I wrote below that my actual interest is in $Mx=\frac{1}{x}$ where I wish to bound the solution from below componentwise - perhaps you'll have some pointers for that. Thanks! $\endgroup$– Felix GoldbergSep 8, 2012 at 22:55
-
$\begingroup$ @Felix: no, I was pointing out that the question itself was already overgeneralized to the point of absurdity (if you place no conditions on $f$). Your actual interest seems much more tractable. $\endgroup$– Qiaochu YuanSep 9, 2012 at 1:06
|
Show 1 more comment
4 Answers
$\begingroup$
$\endgroup$
0
If $f$ is assumed to be small in some sense, a common choice is semilinear equation.
answered Sep 7, 2012 at 7:44
$\begingroup$
$\endgroup$
1
and to be sure: the notion of "nonlinear eigenvalue problem" is usually used for equations of the form $A(u)=\lambda u$, where $A$ is a nonlinear operator (or a nonlinear mapping from $R^n$ to $R^n$, if you wish).
-
$\begingroup$ I know, that's why I added sorta to the title. :) $\endgroup$ Sep 7, 2012 at 10:10
$\begingroup$
$\endgroup$
4
Do you have any examples in mind? As it stands it is essentially a system of $n$ simultaneous equations in $n$ variables. That term would (as commented above) usually suggest a system $$g_i(x)=0 \text{ for } 1 \le i \le n.$$ But that is easily obtained by setting $A$ to be the zero matrix.
If that is too degenerate then we can use your formulation with $A$ your favorite matrix and $f(x)$ returning the vector whose $i$th component is $g_i(x)+(Ax)_i.$
So some restriction is needed to get an interesting question.
answered Sep 8, 2012 at 6:10
-
$\begingroup$ I was thinking about $f(x)=\frac{1}{x}$ and am interested in bounding the minimum component of a solution. $\endgroup$ Sep 8, 2012 at 10:35
-
1
-
$\begingroup$ If $1/x$ is pointwise inverse then the $n=2$ case with diagonal entries $0$ would give $bx_2=1/x_1,\ cx_1=1/x_2$ with either no solutions (if $bc\ne 1$ ) or else $x_1=1/x_2$ $\endgroup$ Sep 9, 2012 at 8:58
-
1$\begingroup$ @Aaron: In the case that $M$ is, say, symmetric positive definite, there is a unique positive solution. (A result of Marshall & Olkin). $\endgroup$ Sep 9, 2012 at 13:00
$\begingroup$
$\endgroup$
This does not answer the question as stated, but your specific question (assuming the inverse is coordinate-wise) can be stated as
$\min_i \min x_i,$ subject to the system of constraints
$x_i <A_i, x> = 1.$
If you remove one level of $\min,$ you are trying to minimize the function (wlog) $x_1$ over the set defined by the constraints, which reduces to a lagrange multiplier problem:
$1 = \lambda_1 \langle A_1, x\rangle + \sum_{j=2}^n \lambda_j A_{j1} x_j.$
and for $k=2, \dotsc, n$
$0 = \lambda_1 x_1 A_{1k} + \lambda_k \langle A_k, x\rangle + \sum_{j=2, j \neq k}^n A_{jk} x_1.$
Unless there is some trick to reduce this system (quite possible, I don't really want to think too hard about it), this is a general system of quadratic equations, which is ETR hard (that is, about as hard as any computational problem), so in that sense, @Quiochu's comment is very a propos.
answered Sep 9, 2012 at 0:52