|
|
|
| 网 通 站 | ||
| 电 信 站 | ||
| 本站淘宝店 |
 |
 |
 |
 |
 |
 |
|
免费外文材料翻译—数值分析 numerical analysis
General introduction Some problems in continuous mathematics can be solved exactly by an algorithm. These algorithms are called direct methods. Examples are Gaussian elimination for solving systems of linear equations and the simplex method in linear programming. However, no direct methods exist for most problems. We might then try to replace the continuous problem by a discrete problem; this process is called discretization. Another possibility is to use an iterative method. Such a method starts from a guess and finds successive approximations that hopefully converge to the solution. Even when a direct method does exist, an iterative method may be preferable because it is more efficient. ? The generation and propagation of errors It follows that the study of errors forms an important part of numerical analysis. Errors arise in iterative methods because the approximate solutions differ from the exact solution. Similarly, discretization induces a discretization error because the solution of the discrete problem does not coincide with the solution of the continuous problem. Even when a direct method is employed, round-off errors arise because of the use of floating point numbers. Once an error is generated, it propagates through the calculation. This leads to the notion of numerical stability: an algorithm is numerically stable if an error, once it is generated, does not grow too much during the calculation. This is only possible if the problem is well-conditioned, meaning that the solution changes by only a small amount if the problem data are changed by a small amount. Indeed, if a problem is ill-conditioned, then any error in the data will grow a lot. However, an algorithm that solves a well-conditioned problem may or may not be numerically stable. An art of numerical analysis is to find a stable algorithm for solving a well-posed mathematical problem. Applications As a consequence, efficiency plays an important role and a heuristic method may be preferred above a method with a solid theoretic foundation because it is more efficient. Generally, numerical analysis uses empirical results of computation runs to probe new methods and analyze problems, though it of course also employs mathematical axioms, theorems and proofs.? Software There are a number of computer programs used for performing numerical calculations: ·??MATLAB is a widely-used program for performing numerical calculations. It comes with its own programming language, in which numerical algorithms can be implemented. ?Areas of study Computing values of functions Interpolation, extrapolation and regression Interpolation solves the following problem: given the value of some unknown function at a number of points, what value does that function have at some other point between the given points? A very simple method is to use linear interpolation, which assumes that the unknown function is linear between every pair of successive points. This can be generalized to polynomial interpolation, which is sometimes more accurate but suffers from Runge's phenomenon. Other interpolation methods use localized functions like splines or wavelets. Extrapolation is very similar to interpolation, except that now we want to find the value of the unknown function at a point which is outside the given points. Regression is also similar, but it takes into account that the data is imprecise. Given some points, and a measurement of the value of some function at these points (with an error), we want to determine the unknown function. The least squares-method is one popular way to achieve this.? Solving equations Much effort has been put in the development of methods for solving systems of linear equations. Standard methods are Gauss-Jordan elimination and LU-factorization. Iterative methods such as the conjugate gradient method are usually preferred for large systems. Root-finding algorithms are used to solve nonlinear equations (they are so named since a root of a function is an argument for which the function yields zero). If the function is differentiable and the derivative is known, then Newton's method is a popular choice. Linearization is another technique for solving nonlinear equations.? Optimization Optimization problems ask for the point at which a given function is maximized (or minimized). Often, the point also has to satisfy some constraints. The field of optimization is further split in several subfields, depending on the form of the objective function and the constraint. For instance, linear programming deals with the case that both the objective function and the constraints are linear. A famous method in linear programming is the simplex method. The method of Lagrange multipliers can be used to reduce optimization problems with constraints to an unconstrained optimization problems.? Evaluating integrals （http://www.answers.com/main/ntquery?method=4&dsid=2222&dekey=Numerical+integration&gwp=8&curtab=2222_） Numerical integration, also known as numerical quadrature, asks for the value of a definite integral. Popular methods use some Newton-Cotes formula, for instance the midpoint rule or the trapezoid rule, or Gaussian quadrature. However, if the dimension of the integration domain becomes large, these methods become prohibitively expensive. In this situation, one may use a Monte Carlo method or, in modestly large dimensions, the method of sparse grids. ?Differential equations Numerical analysis is also concerned with computing (in an approximate way) the solution of differential equations, both ordinary differential equations and partial differential equations. Partial differential equations are solved by first discretizing the equation, bringing it into a finite-dimensional subspace. This can be done by a finite element method, a finite difference method, or (particularly in engineering) a finite volume method. The theoretical justification of these methods often involves theorems from functional analysis. This reduces the problem to the solution of an algebraic equation.? ? History To facilitate computations by hand, large books were produced with formulas and tables of data such as interpolation points and function coefficients. Using these tables, often calculated out to 16 decimal places or more for some functions, one could look up values to plug into the formulas given and achieve very good numerical estimates of some functions. The canonical work in the field is the NIST publication edited by Abramowitz and Stegun, a 1000 plus page book of a very large number of commonly used formulas and functions and their values at many points. The function values are no longer very useful when a computer is available, but the large listing of formulas can still be very handy. The mechanical calculator was also developed as a tool for hand computation. These calculators evolved in electronic computers in the 1940s, and it was then found that these computers were also useful for administrative purposes. But the invention of the computer also influenced the field of numerical analysis, since now longer and more complicated calculations could be done. ? ? ? 译文 ?? 数值分析 数值分析是研究“连续数学”（区别于“离散数学”）问题的算法的学科。这说明了它主要处理实数与复数的问题，求实数与复数的领域的数值线性代数，解微分方程，以及处理其他与物理学和工程学有关的问题。? 简要介绍 一些连续数学中的问题可以通过一种算法而得到准确的结果。这些算法称为直接方法。比如解决线性方程系统的高斯消元法，和线性规划中的单纯形法。 尽管如此，并非所有的问题都存在直接方法。我们可能需要将连续问题转换为一个离散的问题。这个过程叫做离散化。另一个可行的方法是使用迭代。这种方法来自于猜测和寻找一个接近于要求解的近似值的方法。即使当直接方法不存在时，迭代法也可能是更可取的方法，因为它效率高。? 误差的产生与传播 由此得出结论，误差的研究是构成数值分析的重要的组成部分。误差产生于迭代方法，因为近似值不同于真实值。同样由于离散问题的解不能等同于连续问题的解，离散方法也存在着离散误差的问题。即使使用了直接方法，但由于使用了浮点数，误差也是不可避免的。 当一个误差产生时，它会通过计算过程传播。这就产生了数值稳定性的概念：当产生的误差，不会在计算过程中产生过大的增长，就称这个算法是数值稳定的。这种情况只有当问题具备很好的条件时才有可能。也就是说，当问题的已知条件改变微小的值，结果只产生微小的变化。的确，如果问题的条件不好，那么所有的误差都会剧烈增长。 应用 通常，数值分析的算法应用于计算一些科学和工程设计问题。比如:桥梁和飞机的结构设计（可以参考计算物理学和计算流体动力学），天气预报，气候模拟，分子分析与设计（计算化学），寻找石油储藏。事实上，所有的超级计算机都在连续不断地运用着数值分析算法。 总之，效率发挥着重要的作用，并且启发式的方法比一个具有坚实理论基础的方法更重要，因为它的更有效。一般来说，数值分析使用经验的估计值去寻找新的方法和分析问题的目的，即使它也使用数学公理，定理和证明。 ?软件 现在，所有的算法都已经在计算机中实现，运行。Netlib知识库中收藏着丰富的数值问题的程序，它们大多是用Fortran和C语言编写的。（http://www.answers.com/main/ntquery?method=4&dsid=2222&dekey=Netlib&gwp=8&curtab=2222_1）商用的产品实现了很多不同的数值算法包括IMSL和NAG方法库；还有另一个免费的选择是GNU的科学函数库。另一种有特别吸引力的获得途径是Numerical Ricipes库，它重点放在算法的详细的理解之上。 有许多执行了数值计算的计算机程序，它们有： ·??????MATLAB：（一种用于数学计算的程序，特别是线性代数的计算），它是一个被广泛使用的执行数值计算的程序。它与它特有的程序语言同时产生，这种语言可用于实现数值计算。 研究领域 根据解决的问题不同，数值分析领域可被分为不同的学科。? ★函数的值 其中一个最简单的问题是，给定一点的函数估计。但是，即使估计一个多项式也不是直接得到的：Homer计划经常比明显的方法更有效。一般而言，评估和控制浮点运算产生的舍入误差是很重要的。? ★内插，外插和回归 内插方法可解决下列问题：为一些点给出未知的函数值，或在所给的点之间的其它点的函数值。一个非常简单的方法是使用线性内插方法，它是假设未知函数在每两个点之间都是线性的。这可以一般化为多项式内插法，这种方法有时更加精确但是会有龙格现象（Runge phenomenon）。其他的插值方法使用定位函数，如：样条或微波。 除了我们先寻找已知点范围之外的函数值外，外插法与内插法很相似。 回归也很类似，但是它考虑到那些数据是不精确。我们想根据给出的一些点和这些点的一些函数值（有误差），决定未知的函数。实现它最流行的方法是最小方差（least squares）。? ★解方程组 另一个重要的问题是求给定方程组的解。有两个情况是非常重要的，那就是方程是线性的还是非线性的。 在解线性方程组的方法的改进上，我们已经做了很多的努力。标准的方法有“高斯－约旦消元法”和“LU－分解法”。迭代法比如“共轭梯度法”通常比较适合于大型系统。 根查找算法用于解决非线性方程组（如此命名的原因是有个函数的根是该函数为此输出零的一个条件）。如果该函数是可微的并且导数是可知的，那么牛顿（插值）法个合适的选择。线性化是解非线性问题的另一种技术。? ★最优化 主要文章：优选法（数学） 最优化问题需要寻找所给的函数的最大或最小值的点。经常，这个点必须满足一些约束调条件。 根据目标函数和约束限制的形式，最优化领域可进一步分为几个子域。举个例子，线性规划处理目标函数和约束条件都是线性的情况。在线性规划中的一个著名的方法就是“单纯形法”。 拉格朗日乘子可用于将约束的最优问题简化为无约束的最优问题。? ★积分评测 主要文章：数值积分 （http://www.answers.com/main/ntquery?method=4&dsid=2222&dekey=Numerical+integration&gwp=8&curtab=2222_） 数值积分，也叫数值积分法，用于求解定积分。流行的方法是使用“牛顿－科特”公式（比如中点法则或梯形法则），或者高斯求积法。尽管如此，当积分定义的维数很大时，这种方法会付出高昂的代价。在这种情况下，可能要使用“蒙特卡罗法”(统计试验法)，或者当定义域（维数）适当大时，使用稀疏栅格法。? ★微分方程 主要文章：数值常微分方程组，数值偏微分方程组 不管是解常微分方程还是解偏微分方程，数值分析都同样关心解计算的逼近方法。 偏微分方程是把问题离散化成有限维的子空间来求解。这种方法可以通过一个“有限元法”, 或者一个“有限差分法”，或者（特别是在工程技术中）一个“有限容积法”来完成。这些方法的理论依据经常牵涉到一些泛函分析的理论。这可把问题简化为代数方程的求解。? 历史 数值分析领域的研究比现代计算机的发明早了许多世纪。事实上，过去的许多数学家就投入数值分析的研究当中，很明显从现在的一些重要的算法的名称就可以看出，比如：“牛顿插值”，“拉格朗日插值多项式”，“高斯消元”，或着“欧拉方法”。 |
 |
 |
 |
 |
 |
 |
