Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-24T10:25:31.280Z Has data issue: false hasContentIssue false
  • English
  • Français

The RANGE family of propagation operations for intervals on simultaneous linear equations

Published online by Cambridge University Press:  27 February 2009

R. Chen  and
A.C. Ward
R. Chen
Affiliation:
Department of Power Mechanical Engineering, National Tsing Hua University, Hsinchu, Taiwan 30043, Republic of China
A.C. Ward
Affiliation:
Department of Mechanical Engineering and Applied Mechanics, University of Michigan, Ann Arbor, MI 48109
Get access Rights & Permissions [Opens in a new window]

Abstract

Interval arithmetic has been extensively applied to systems of linear equations by the interval matrix arithmetic community. This paper demonstrates through simple examples that some of this work can be viewed as particular instantiations of an abstract “design operation,” the RANGE operation of the Labeled Interval Calculus formalism for inference about sets of possibilities in design. These particular operations promise to solve a variety of design problems that lay beyond the reach of the original Labeled Interval Calculus. However, the abstract view also leads to a new operation, apparently overlooked by the matrix mathematics community, that should also be useful in design; the paper provides an algorithm for computing it.

Keywords

Set-based DesignFinite ElementsInterval MatricesInterval VectorsDesign Compiler
Type
Articles
Information
AI EDAM , Volume 9 , Issue 3 , June 1995 , pp. 183 - 196
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Alefeld, G., & Herzberger, J. (1983). Introduction to Interval Computation. Academic Press, San Diego.Google Scholar
Bains, N., & Ward, A. Multiple-type interval propagations through non-monotonic equations. ASME Journal of Mechanical Design (in press).Google Scholar
Brett, C.S., Saldanha, C.M., & Lowther, D.A. (1990). Interval mathematics for knowledge-based computer aided design in magnetics. IEEE Transaction on Magnetics 26(2), 803–806.CrossRefGoogle Scholar
Chand, D.R., & Kapur, S.S. (1970). An algorithm for convex polytopes. J. ACM 17, 78–86.Google Scholar
Chang, T.-S., Ward, A., Lee, J., & Jacox, E. Conceptual robustness in simultaneous engineering: An extension of Taguchi’s parameter design. Research in Engineering Design (in press).Google Scholar
Chen, R. (1992). Generalizing Interval Matrix Operations for Design: Fusing the Labeled Interval Calculus and Interval Matrix Arithmetic. Ph.D. Thesis, University of Michigan.Google Scholar
Cope, J.E., & Rust, B.W. (1979). Bounds on solutions of linear systems with inaccurate data. SIAM J. Numer. Anal. 16, 951–963.CrossRefGoogle Scholar
Cvetkovic, L., & Herceg, D. (1989). The AOR method for solving linear interval equations. Computing 41, 359–364.CrossRefGoogle Scholar
Davis, E. (1987). Constraint propagation with interval labels. Artificial Intelligence 32, 281–331.CrossRefGoogle Scholar
Deif, A. (1986). Sensitivity Analysis in Linear System. Springer-Verlag, New York.CrossRefGoogle Scholar
Demmel, J.W. (1985). An interval algorithm for solving of linear equations to prespecified accuracy. Computing 34, 117–129.CrossRefGoogle Scholar
Finch, W., & Ward, A. Extending generalized interval propagation to monotonic relations among more than three variables (in preparation).Google Scholar
Gay, D. (1982). Solving interval linear equations. SIAM J. Numerical Analysis 19(4), 858–870.CrossRefGoogle Scholar
Garloff, J. (1990). Block methods for the solution of linear interval equations. SIAM J. Matrix Anal. Appl. 11(1), 89–106.Google Scholar
Habib, W., & Ward, A. (1991). In pursuit of a design mathematics: Generalizing the labeled interval calculus. ASME Design Theory and Methodology Conference, Miami Beach, pp. 279–284.Google Scholar
Hahn, W., & Mohr, K. (1985). Some techniques for solving linear equation systems with guarantee. Computing 34, 375–379.Google Scholar
Hansen, E. (1965). Interval arithmetic in matrix computations, Part I. SIAM J. Numerical Analysis 2(2), 308–320.Google Scholar
Hansen, E., & Smith, R. (1967). Interval arithmetic in matrix computations, Part II. SIAM J. Numerical Analysis 4, 1–8.CrossRefGoogle Scholar
Hansen, E. (1969). On the solution of linear algebraic equations with interval coefficients. Linear Algebra Appl. 2, 153–165.Google Scholar
Hartfiel, D.J. (1980). Concerning the solution set of Ax = b where P ≤ A ≤ Q and p ≤ b ≤ q. Numer. Math. 35, 355–359.Google Scholar
Herzberger, J. (1989). On the convergence of an interval method for bounding the inverses of an interval matrix. Computing 41, 153–162.Google Scholar
Herzberger, J. (1990). Efficient iterative algorithms for bounding the inverse of a matrix. Computing 44, 237–244.Google Scholar
Hudak, D. (1991). On the determination of the interval hull of linear interval equations. Computing 46, 253–263.Google Scholar
Ly, T.E.A., & Girczyc, E.F. (1988). Constraint propagation in the object-oriented IC design environment. 25th ACM/IEEE Design Automation Conference, pp. 628–633.Google Scholar
Matthews, J., Broadwater, R., & Long, L. (1990). The application of interval mathematics to utility economic analysis. IEEE Transactions on Power Systems 5(1), 177–181.Google Scholar
Moore, R.E. (1966). Interval Analysis. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Moore, R.E. (1979). Methods and applications of interval analysis. SIAM, Philadelphia.Google Scholar
Neumaier, A. (1984). New techniques for the analysis of linear interval equations. Linear Algebra Appl. 581, 273–325.CrossRefGoogle Scholar
Neumaier, A. (1985a). Linear interval equations. Interval Mathematics, Proceedings of the International Symposium, Freiburg I., Br., Germany, pp. 107–120.Google Scholar
Neumaier, A. (1985b). Further results on linear interval equations. Freiburger Intervall-Berichte 4, 37–xxx.Google Scholar
Neumaier, A. (1986). Tolerance analysis with interval arithmetic. Freiburger Intervall-Berichte 9, 5–19.Google Scholar
Neumaier, A. (1987). Further results on linear interval equations. Linear Algebra Appl. 87, 155–179.CrossRefGoogle Scholar
Neumaier, A. (1990). Interval Methods for Systems of Equations. Cambridge University Press, New York.Google Scholar
Oettli, W. (1965). On the solution set of linear systems with inaccurate coefficients. SIAM J. Numerical Analysis 2(1), 115–118.Google Scholar
Oettli, W., & Prager, W. (1964). Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numer. Math. 6, 405–409.CrossRefGoogle Scholar
Oppenheimer, E.P., & Michel, A.N. (1988). Application of interval analysis techniques to linear systems: Part I—Fundamental results. IEEE Trans, on Circuits and Systems 35(9), 1129–1138.Google Scholar
Oppenheimer, E.P., & Michel, A.N. (1988). Application of interval analysis techniques to linear systems: Part II —The interval matrix exponential function. IEEE Trans, on Circuits and Systems 35(10), 1230–1242.Google Scholar
Oppenheimer, E.P., & Michel, A.N. (1988). Application of interval analysis techniques to linear systems: Part III —Initial value problems. IEEE Trans, on Circuits and Systems 35(10), 1243–1256.CrossRefGoogle Scholar
Popplestone, R.J. (1987). The Edinburgh designer system as a framework for robotics: The design of behavior. AI EDAM 1(1).Google Scholar
Rinderle, J.R., & Krishnan, V. (1990). Constraint reasoning in concurrent design. Proceedings of the 1990 ASME Design Theory and Methodology Conference, pp. 53–62.CrossRefGoogle Scholar
Ratschek, H., & Sauer, W. (1982). Linear Interval Equations. Computing 28, 105–115.CrossRefGoogle Scholar
Ris, F.N. (1972). Interval Analysis and Applications to Linear Algebra. Ph.D. Thesis, Oxford.Google Scholar
Ris, F.N. (1975). Tools for the analysis of interval arithmetic. Interval Mathematics, Proceedings of the International Symposium, Karlsruhe, Germany, pp. 75–98.CrossRefGoogle Scholar
Rohn, J. (1981a). Interval linear systems with prescribed column sums. Linear Algebra Appl. 39, 143–148.CrossRefGoogle Scholar
Rohn, J. (1981b). Strong solvability of interval linear programming problems. Computing 26, 79–82.CrossRefGoogle Scholar
Rohn, J. (1982). An algorithm for solving interval linear systems and inverting interval matrices. Freiburger Intervall-Ber, 82/5, 23–36.Google Scholar
Rohn, J. (1985). Inner solutions of linear interval system. Interval Mathematics, Proceedings of the International Symposium, Freiburg I., Br., Germany, pp. 157–158.Google Scholar
Rohn, J. (1988). Solving systems of linear interval equations. In Reliability in Computing (Moore, R.E., Ed.), pp. 171–182.Google Scholar
Rohn, J. (1989a). Systems of linear interval equations. Linear Algebra Appl. 126, 39–78.CrossRefGoogle Scholar
Rohn, J. (1989b). A two-sequence method for linear interval equations. Computing 41, 137–140.CrossRefGoogle Scholar
Rohn, J. (1989c). A Farkas-type theorem for linear interval equations. Computing 43, 93–95.CrossRefGoogle Scholar
Rohn, J. (1989d). The asymptotic result for linear interval systems. BIT 29, 372–374.Google Scholar
Rohn, J. (1989e). On nonconvexity of the solution set of a system of linear interval equations. BIT 30, 161–165.CrossRefGoogle Scholar
Sarma, E.S., & Rinderle, J.R. (1991). Quiescence in internal propagation. Proceedings of the ASME Design Theory and Methodology Conference, pp. 257–263.Google Scholar
Varga, R.S. (1962). Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Ward, A., Liker, J., Sobek, D., & Cristiano, J. The second Toyota paradox: How delaying decisions can make better cars faster. Sloan Management Review (in press).Google Scholar
Ward, A., Lozano-Perez, T., & Seering, W. (1990). Extending the constraint propagation of intervals. AI EDAM 4(1), 47–54.Google Scholar
Ward, A., & Seering, W. (1993a). Quantitative inference in a mechanical design compiler. ASME Journal of Mechanical Design 115(1), 29–35.Google Scholar
Ward, A., & Seering, W. (1993b). The performance of a mechanical design compiler. ASME Journal of Mechanical Design 115(3), 341–345.CrossRefGoogle Scholar
Wood, K., Otto, K., & Antonsson, E. (1992). Engineering design calculations with fuzzy parameters. International Journal of Fuzzy Sets and Systems 52(1), 1–20.CrossRefGoogle Scholar