home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / math / smooth11 / smooth.doc < prev    next >
Encoding:
Text File  |  1991-06-09  |  7.9 KB  |  209 lines
  1. NAME
  2.     smooth - split linear smoothing
  3.  
  4. SYNOPSIS
  5.     smooth [file] [options]
  6.  
  7. USAGE
  8.     By default, SMOOTH reads pairs of numbers (x- and y-values)
  9.     from the standard input (or the given file), fits a smooth
  10.     curve to the points, and writes to the standard output points
  11.     from the smooth curve.
  12.  
  13.     Two smoothing algorithms are available.  By default, the curve
  14.     is calculated using the "lowness" procedure developed by W.  S. 
  15.     Cleveland (see below).  This technique achieves robustness by
  16.     decreasing weights on data points which are far from the fitted
  17.     line.  An alternate procedure due to Art Owen is also provided
  18.     (with the -s switch).  This technique smooths the data while
  19.     preserving sharp discontinuities in slope or value.
  20.     
  21.     As with GRAPH, each pair of points may optionally be followed
  22.     by a comment.  If the comment is surrounded by quotes "...",
  23.     the comment may contain spaces.  The given points, and their
  24.     comments if any, will be included in the output.  The
  25.     interpolation may optionally be restarted after each label, so
  26.     that a family of curves may be processed together (see the -b
  27.     switch).
  28.  
  29.     Input lines starting with ";" are copied to the beginning of
  30.     the output file but are otherwise ignored.  Blank lines are
  31.     ignored.
  32.  
  33. OPTIONS
  34.     Options can appear anywhere on the command line.
  35.  
  36.       -a  [step [start]] automatic abscissas 
  37.       -b     break smooth after each label 
  38.       -c     general curve
  39.       -f  <num>  for "lowness", the fraction of points to use for 
  40.            each fitted value (default .5)
  41.       -n  <num>  for "lowness", the number of points to use for 
  42.            each fitted value (default 50%)
  43.       -r     print residuals rather than smoothed values
  44.       -s     split linear fit rather than "lowness"
  45.       -xl    take logs of x values before smoothing 
  46.       -yl    take logs of y values before smoothing 
  47.       -zl    take logs of z values before interpolating 
  48.              (implies -3)
  49.       -3     3D case: x, y, and z given for each point
  50.  
  51.     If the -c switch is not used, the input points must be from a
  52.     function - that is, the x values must be strictly increasing. 
  53.     The output points will also be from a function.  (If the -b
  54.     switch is used, this restriction applies only within each
  55.     segment.)
  56.  
  57.     If the -c switch is used (indicating a general curve), the
  58.     input points need not be from a function, but each pair of
  59.     points must be separated from the previous pair by a finite
  60.     distance.  (If the -b switch is used, this restriction applies
  61.     only within each segment.) 
  62.  
  63.     The -f or -n switch designate the number of data points used to
  64.     calculate a given smoothed value.  The larger the number, the
  65.     smoother the resulting curve.  It is not possible to specify
  66.     the number in terms of a range of the independent variable
  67.     (e.g.  a "time constant").  Therefore, these methods are
  68.     appropriate when the density of data points is approximately
  69.     constant, or else the density is higher in the "interesting"
  70.     (i.e.  rapidly changing) part of the curve.
  71.  
  72.     The distinction between the -f and -n switch becomes useful
  73.     only when there are several data sets.  Suppose one had two
  74.     data sets for the same range of independent variables, and that
  75.     one set had twice the number of data points as the other.  For
  76.     equivalent treatment, one could smooth the two sets with the
  77.     same value for the -f switch.
  78.  
  79.     On the other hand, suppose two sets of data have data points at
  80.     the same density, but that one set covered twice the range of
  81.     independent variable (and therefore had twice as many data
  82.     points).  For equivalent smoothing, one could use the -n switch
  83.     with the same value in each case.
  84.  
  85.     For general curves, the given x- and y- (and z-, if present) points
  86.     are regarded as functions of the distance along a smoothed path.  This
  87.     doesn't work very well for split linear smoothing, since it tends to
  88.     conceal abrupt changes in position.  However, the split linear smooth
  89.     is still able to preserve abrupt changes in the first derivative.
  90.  
  91. METHODS
  92.     Lowness by W. S. Cleveland, and split linear fit by A. Owen
  93.  
  94.     Lowness
  95.  
  96.         Robust locally weighted regression is a method for
  97.         smoothing a scatterplot, (x[i], y[i]), i=1,...,n, in
  98.         which the fitted value at x[k] is the value of a
  99.         polynomial fit to the data using weighted least
  100.         squares, where the weight for (x[i], y[i]) is large if
  101.         x[i] is close to x[k].  Robustness is added by
  102.         calculating residuals and repeating the procedure with
  103.         reduced weights on points with large residuals.
  104.  
  105.     Reference: 
  106.         W.  S.  Cleveland, "Robust Locally Weighted Regression
  107.         and Smoothing Scatterplots", Journal of the American
  108.         Statistical Association, v74, n368, p829 (Dec 79)
  109.  
  110.  
  111.     Split Linear Smoothing Algorithm
  112.  
  113.         Given:
  114.             A list of window sizes, SizeList, and n pairs (x[i],y[i]) sorted on x,
  115.  
  116.         Returns:
  117.             the split linear smooth of y on x.
  118.  
  119.  
  120.         The general technique is due to Art Owen, who offers this
  121.         discussion:
  122.  
  123.             "You should feel free to experiment with the
  124.             algorithm, since it has some ad hoc parts.  The
  125.             essentials are: to use uncentered windows of
  126.             varying sizes along with the central ones, to
  127.             get zero weight on the worst fitting lines, and
  128.             to make the weight attached to a particular
  129.             line size and orientation vary smoothly as one
  130.             traverses the data.  We tried to find a simple
  131.             way to meet all of these goals; the algorithm
  132.             we settled on was the simplest that worked for
  133.             us.  ...
  134.  
  135.             "West and Chan et.  al.  are useful for getting
  136.             numerically stable updating formulae for the
  137.             regressions."
  138.  
  139.         references...
  140.  
  141.             John Alan McDonald and Art B.  Owen, "Smoothing with
  142.             Split Linear Fits", LCS Technical Report No. 
  143.             7, SLAC-PUB 3423, AD-A149032, Laboratory for
  144.             Computational Statistics, Dept.  of Statistics,
  145.             Stanford University, July 1984.
  146.  
  147.  
  148.             West, D.H.D., 1979, Updating Mean and Variance
  149.             Estimates: An Improved Method, Communications
  150.             of the ACM, v 22, no.  9 p 532-535 (1979).
  151.  
  152.             Chan, T.F., Golub, G.H., and Leveque, R.J., 1983,
  153.             Algorithms for Computing the Sample Variance:
  154.             Analysis and Recommendations, The American
  155.             Statistician v 37, p 242-247 (1983).
  156.  
  157. IMPLEMENTATION
  158.  
  159.     The implementation of the split linear smoothing is based on
  160.     pseudocode by Art Owen.
  161.  
  162.     The arrays take a lot of space.  For n points, the number of
  163.     doubles is approximately 38*n, plus 2*n for general curve, plus
  164.     2*n for 3D case.  For 100 points and 8 byte doubles, this means
  165.     at least 8*38*100=30400 bytes.
  166.  
  167.     Execution time...  The program will employ a numeric
  168.     coprocessor if it is available, but will run correctly without
  169.     it.  Time for "lowness" is proportional to the square of the
  170.     number of data points.  101 points took 151 seconds on a 7.5
  171.     MHz V-20, with no 8087, but only 0.98 seconds on a 20 MHz 80386
  172.     with an 80387.  Time for split linear smoothing increases
  173.     slightly faster than linearly in the number of data points.
  174.  
  175.     The updating formulas mentioned by Art Owen are not used in
  176.     this program.  The selection of window sizes (a geometric
  177.     sequence) is my own.  -JVZ
  178.  
  179. EXAMPLES
  180.     The file ROUGH contains data points from sin(x) with one abrupt
  181.     phase reversal (creating a discontinuity) and some added noise. 
  182.     To see the effect of the two algorithms, try
  183.  
  184.         C>smooth rough -f .2 >rlow
  185.         C>smooth rough -s >rsl
  186.  
  187.     Then display all three files with GRAPH...
  188.  
  189.         C>graph rough rlow rsl -m -32 10 20
  190.  
  191.     Note how the split linear smooth preserved the discontinuity
  192.     whereas "lowness" smoothed it out somewhat.
  193.  
  194.     The file SP contains points from a general curve...
  195.  
  196.         C>smooth sp -f .2 -c >splow
  197.         C>smooth sp -s -c >spsl
  198.         C>graph sp splow spsl -m 1 10 20
  199.  
  200.     This input file has a discontinuity in the first derivative
  201.     which the split linear smooth was able to preserve.
  202.         
  203. AUTHOR
  204.     Copyright (c) 1987, 1991 by James R.  Van Zandt
  205.     (jrv@mbunix.mitre.org) 27 Spencer Dr., Nashua NH 03062,
  206.     603-888-2272.  Resale forbidden, copying for personal use
  207.     encouraged.  Constructive comments welcome.
  208.  
  209.