Jökull - 01.12.1973, Page 41

Fig. 3. Solution of the linear program in two
dimensions where m = 1.
Obviously, the vector x0 has the smallest I2-
norm of all vectors satisfying (1). It is unique
and it determines the position of the solution
space uniquely. The components of x0 there-
fore respresent the least h-norm solution to the
present undertermined problem and x0 can be
defined as the generalized solution to the pro-
blem.
The square-sum or 12-norm applied above
bas in some cases the disadvantage of being of
bttle direct practical importance. Frequently
°ne is more interested in minimizing a linear-
sum or li-norm of the form (|xi| + |x2|) and solv-
lng equation (1) (m = 1) with the constraints
xi >0, x2 S 0
xi -f x2 = min.
I his problem setting is equivalent to a pro-
blem in linear programming which is very
easily solved in the present case. We find that
b an > a12, we can solve equation (1) for xi
and insert into (4). This leads to
x2 [1 — (ai2/an)] + (bi/an) = min. x2 & 0 (5)
'vhich has the solution
x2 = 0, and hence xi = bi/an (6)
TWs solution is illustrated graphically by the
vector OS in Fig. 3.
The overdetermined case m > 2 is character-
ized by the presence of more than two lines in
the plane. The case of m = 3 is illustrated in
Fig. 4. In the general case there will be no
unique common point of intersection of the
lines and hence no solution to the equations.
Nevertheless, a generalized solution can be de-
fined in the following way. The point of inter-
section between two lines in the plane is the
point of least distance from the two lines. This
distance is zero because the lines intersect. This
concept can be generalized and carried over
to the overdetermined case where m > 2. We
select the point of least distance square sum
from the m lines and define our generalized
solution as being represented by this point. This
solution will generally be unique. In the case
m = 3 illustrated in Fig. 4, the solution point
S is characterized by
di2 + d22 + d32 = min. (7)
where di, d2, and d3 are the lengths of the
perpendiculars from S to the lines 1 to 3.
Cases with more than two unknowns
These considerations are easily extended to
higher dimensions. Let
i aíkxk = bi, i = 1, 2,..., m (8)
k = t
Fig. 4. Overdetermined problem in two dim-
ensions where m = 3.
JÖKULL 23. ÁR 39