③线性代数方程求解计算

在自然科学和工程技术的许多实际问题中，如结构分析、大地测量、网络分析、数据分析、最优化等问题中常常遇到线性代数方程组求解问题。数学中，例如求解非线性方程组或微分方程数值解问题也常转化为线性代数方程组求解问题。早在中国古代的《九章算术》中，就已经有了解线性方程组的消元法。到19世纪初，西方又有了高斯消元法。然而求解未知数很多的大型线性代数方程组，则是在20世纪中叶电子计算机问世以后才成为可能。如何利用计算机更精确、更有效地解大型线性代数方程组是计算数学研究中的基本性的重要课题之一。
线性代数方程组数值解法可分为二大类，即直接法和迭代法，现简介如下。

1.解线性方程组的直接法

解线性方程组 Ax=F的直接法是指经过有限步运算后能求得方程组精确解的方法。如果A的行列式detA≠0,按克拉默法则，线代数方程的解x_j=detA_j/detA，式中A_j是把A中的第j列元素用自由项？₁,？₂,…，？_n代替后所得的矩阵。克拉默法则之功效主要在于理论意义，若用于数值求解，则因n+1个n阶行列式求值的计算量很大而不实用。但由于实际计算中舍入误差是客观存在的，因而使用这类方法也只能得到近似解。目前较实用的直接法是古老的高斯消去法的变形，即主元素消去法及矩阵的三角分解法。引进选主元的技巧是为了控制计算过程中舍入误差的增长，减少舍入误差的影响。一般说来，列主元消去法及列主元三角分解法是数值稳定的算法，它具有精确度较高、计算量不大和算法组织容易等优点，是目前计算机上解中、小型稠密矩阵方程组可靠而有效的常用方法。

2.解线性方程组的迭代法

解线性方程组的迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法，即是从一个初始向量x⁽⁰⁾出发，按照一定的迭代格式产生一个向量序列{x^(k)}，构造一个向量的无穷序列，使其收敛到方程组 Ax=F的解。熟知的简单迭代法、高斯－赛德尔迭代法、松弛法等都属此类。迭代法的优点是所需计算机存储单元少，程序设计简单，原始系数矩阵在计算过程中始终不变等。迭代法是解大型稀疏矩阵方程组的重要方法，但存在收敛性及收敛速度等问题。
上述两种方法各有优缺点，直接法普遍适用，但要求计算机有较大的存储量，迭代法要求的存储量较小，但必须在收敛性得以保证的情况下才能使用。直接法可以求得精确解是指就计算公式而言保证得到精确解，但计算机计算过程中的舍入误差是不可避免的，要求这种误差对解的精度影响会不会太大，也就是计算的稳定性，是要考虑的问题。对于迭代法，其收敛性则是要考虑的问题。
所以，不论是直接法还是迭代法都要根据方程组的具体性质，例如系数矩阵的稀疏状态、正定性、对角优势等等，选择计算方法和采用诸如稀疏技术、加速收敛等相应措施，才能更为有效地利用计算机得出比较满意的结果。

④非线性代数方程求解计算

当f(x)中含有超越函数（如三角函数、指数和对数函数等不能用有限次加、减、乘、除、乘方、开方 运算表示的函数）或高次多项式时，f(x)=0称为非线性方程。此类方程除少数情形外，多数情况中只能求取近似解。在科学研究与工程技术中，经常会遇到求解这类非线性方程的问题。
非线性问题是现代数学中的一个非常活跃的领域，大量的非线性问题，如非线性有限元问题、经济与非线性规划问题以及物理、化学、流体力学中许多关键问题的解决，往往归结为求解某些特定的非线性方程；在非线性力学中，有多种类型的非线性，如材料非线性、几何非线性、接触非线性等；非线性方程的求解也是科学与工程计算中一个常见且重要的问题。然而除了一些非常的特殊情形外，直接法很难求解非线性方程。对于实际问题，很多情况下并不必求出方程的真实解，只需求得一个近似值，当然此近似值与真实解之间的误差应该控制在实际问题所能允许的范围之内。近似解可以通过数值方法来获得，所以研究非线性方程的数值解法有着重要的理论意义和实际应用价值。
对于非线性函数f(x)，如在x=r时，有f(r)=0，那么称x=r为函数f(x)的零点，也叫做方程的根。求解方程就是计算该方程的所有零点。
非线性方程求零点需要解决的问题有：1. 零点的存在性：方程是否有零点，如果有零点，有几个零点？ 2. 零点的隔离：找出有零点的区域，把有零点区域分成较小的子区域，每个子区域有一个零点，将有零点区域内的任一点都看成该零点的一个初始近似值；3. 零点的精确化：对已知零点的初始近似值，逐步精确化，以得到非线性方程的可接受近似解。
现在有许多算法可用来求解非线性方程，如二分法简单易行，但收敛较慢，仅有线性收敛速度，而且该方法不能用于求偶数重根或复根，但可以用来确定迭代法的初始值；牛顿法是方程求根中常用的一种迭代方法，除具有简单迭代法的优点外，还具有二阶收敛速度，但牛顿法对初始值选取比较苛刻（必须充分靠近方程的根），否则牛顿法可能不收敛；弦截法是牛顿法的一种修改，虽然比牛顿法收敛慢，但因它不需计算函数的导数，故有时宁可用弦截法而不用牛顿法，弦截法也要求初始值必须选取得充分靠近方程的根，否则也可能不收敛。
求解一元非线性方程f(x)=0的二分法，是一种简单有效的方法，逐次把有根区间分半，直到找到根或有根区间的长度小于给定精度为止。
在二分法中，假定非线性函数f(x)在区间(c，d)上连续。如果存在两个实数a和b属于区间(c，d)，使得f(a)*f(b)<0成立，也就是说f(a)和f(b)异号，说明在区间(a，b)内至少有一个零点，即含该方程的一个解。然后，我们计算f[(a+b)/2]。此时，假设f(a)<0，f(b)>0成立。我们可以根据f[(a+b)/2]的值来判断方程解的位置：如果f[(a+b)/2]=0，该点就是零点，为所求的解；如果f[(a+b)/2]<0，则表示在区间 ((a+b)/2, b) 内有零点，(a+b)/2=>a，重复前面的步骤来进行判断；如果f[(a+b)/2]>0，则表示在区间 (a，(a+b)/2) 内有零点， b=> (a+b)/2，重复前面的步骤来进行判断。
这样，通过上述步骤就可以不断接近零点。由于非线性方程在很多时候都没有精确解，因此我们可以设置一个精度，当f(x)小于该精度时就认为找到了零点，也就是找到了方程的解。这种通过每次把f(x)的零点所在区间收缩一半的方法，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值。
非线性方程的数值算法很多，像解线性方程组一样，有直接法和迭代法之分，但主要的方法是迭代法。迭代法是一种逐次逼近的方法。首先要求所构造的迭代公式收敛，即导数的绝对值小于1，且其值越小收敛速度越快，此法用的比较广泛，速度比较快。使用这一方法一般至少要知道根的一个近似值x₀，然后将原方程f(x)=0改变成与它同解但便于迭代的形式x=P(x)，利用迭代公式x_k+1=P(x_k)，k=0，1，2，……，就能求出一系列逐步精确的近似值。例如常用的迭代法有：
1、牛顿迭代法：给出x₀为初始近似值；
2、割线迭代法，需给出x₀，x₁为两个初始近似值。
评价一个迭代公式的优劣，除去收敛条件之外，主要是看它的效能指标，即达到规定的精确度所花费的代价。因此如何构造收敛的迭代公式，分析公式的收敛速度和收敛条件，以及加快收敛的技术，这些都是迭代法要研究的课题。牛顿迭代具有较高的收敛速度和简单灵活等优点，而且可以推广到求解非线性方程组，拟牛顿法就是具有较高效能指标的求解非线性方程组的通行方法。此外还有二次插值法、切比雪夫迭代法及艾特肯加速法等。
牛顿弦截法是牛顿法的一种改进，虽然比牛顿法收敛慢，但因它不需计算函数的导数，故有时宁可用弦截法而不用牛顿法，弦截法也要求初始值必须选取得充分靠近方程的根，否则也可能不收敛。弦截法是一种不必进行导数运算的求根方法，在迭代过程中不仅用到前一步 x_k处的函数值，而且还使用x_k-1处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。
为避免计算函数的导数 f′(x_k)，使用差商

？替代牛顿公式中的导数 f′(x_k) ,便得到迭代公式

？称为弦截迭代公式，相应的迭代法称为弦截法。可以证明，弦截法具有超线性收敛，它与前面介绍的一般迭代法一样都是线性化方法。一般迭代法在计算x_k+1时只用到前一步的值x_k，故称之为单点迭代法；而弦截法在求x_k+1时要用到前两步的结果x_k-1和x_k，使用这种方法必须给出两个初始近似根x₀ , x₁，这种方法称为多点迭代法。

在科学研究和工程设计中，经常遇到求解由非线性代数方程组构建的数学模型，这已不是一元非线性，而是多元非线性问题，和一元非线性相比，更加复杂多变，可以说求解时遇到的困难更多、更大。
为简单和统一起见，我们用函