Algorithms for Best L1 and L_infinity Linear Approximations on a...
需积分: 9 111 浏览量
2011-09-26
01:28:53
上传
评论
收藏 642KB PDF 举报
Numerische Mathematik 8, 295--306 (t966)
Algorithms for Best L x and Loo
Linear Approximations on a Discrete Set
IAN BARRODALE and ANDREW YOUNG
Received December 7, t965
Abstract.
This paper supplies algorithms for the best approximation to a real-
valued function, defined as a table of values, by a linear approximating function
in both the L I and Loo norms. The algorithms are modified simplex algorithms which
due to the particular structures of the tableaux have been condensed and require
minimal storage space. Both algorithms are given as ALGOL procedures and sample
times are noted for several examples.
I. Statement of the Problems
Let ](x)
be a given real-vaiued function defined on a finite subset X-----
{xl, x2 ..... xN}
of an interval I on the real line. Given a set of n real-valued
continuous functions ~v/(x) defined on I we form a linear approximating function
F(A, x) = ~ aicp/(x )
for any real set a = {a 1, a, ..... a.}.
i=x
The L 1 approximation problem is to determine A* such that
,,Xxl F(A*, x)- [(x) I
~ZxlF(A, x)-
I( )1
for all A E E..
The Loo (or Chebyshev) approximation problem is to determine A* such that
maxX IFCA *, x) -- I(~)1
-- < max,,~x
l~(a, x) -1(~)1
for all A ~ E~.
We now restate each problem as a linear programming problem of a type
that can be solved by methods that appear to be more efficient than any published
to date. GOLDSTEIN and CHENEY [1, Th. Q., p. 425] and STIEFEL [3, p. 10]
have reduced the Loo approximation problem, while RICE
[2,
p. 182] has converted
the L x approximation problem, each into linear programming problems. How-
ever STIEFEL'S formulation doubles the number of constraints and he remarks
on the
"'tedious trans/ormations"
necessary to reduce the constraints to the
original number; the number of constraints introduced by RICE is 2 t¢ and, as
he says,
"'this approach does not appear to lead to a practical solution o[ the L 1
approximation problem".
We proceed as follows. To ensure the non-negativity of the unknown vari-
ables we put
~+l=max(0,--nfi'naj) and then
og=ai+o~+ x
for
t~j~_n.
1
剩余11页未读，继续阅读
资源评论
