下载文档原格式
数值计算方法思考题第一章 预篇1．什么是数值分析？它与数学科学和计算机的关系如何？2．何谓算法？如何判断数值算法的优劣？3．列出科学计算中误差的三个来源，并说出截断误差与舍入误差的区别。
4．什么是绝对误差与相对误差？什么是近似数的有效数字？它与绝对误差和相对误差有何关系？5．什么是算法的稳定性？如何判断算法稳定？为什么不稳定算法不能使用？6．判断如下命题是否正确：（1）一个问题的病态性如何，与求解它的算法有关系。
（2）无论问题是否病态，好的算法都会得到好的近似解。
（3）解对数据的微小变化高度敏感是病态的。
（4）高精度运算可以改善问题的病态性。
（5）用一个稳定的算法计算良态问题一定会得到好的近似值。
（6）用一个收敛的迭代法计算良态问题一定会得到好的近似值。
（7）两个相近数相减必然会使有效数字损失。
（8）计算机上将1000个数量级不同的数相加，不管次序如何结果都是一样的。
7．考虑二次代数方程的求解问题ax 2 + bx + c = 0.下面的公式是熟知的aac b b x 242-±-=. 与之等价地有ac b b c x 422--=.对于 a = 1, b = -100 000 000 , c = 1应当如何选择算法？8．指数函数有著名的级数展开++++=!3!2132x x x e x如果对x < 0用上述的级数近似计算指数函数的值，这样的算法结果是否会好？为什么？9．考虑数列x i , i = 1,…, n , 它的统计平均值定义为∑==n i i x x x 11 它的标准差2112)(11⎥⎦⎤⎢⎣⎡--=∑-n i i x x n σ 数学上它等价于2112211⎥⎥⎦⎤⎢⎢⎣⎡⎪⎪⎭⎫ ⎝⎛--=∑=n i i x n x n σ 作为标准差的两种算法，你如何评价它们的得与失？第二章 非线性方程求根1．判断如下命题是否正确：(a) 非线性方程的解通常不是唯一的；(b) Newton 法的收敛阶高于割线法；(c) 任何方法的收敛阶都不可能高于Newton 法；(d) Newton 法总是比割线法更节省计算时间；(e) 如果函数的导数难于计算，则应当考虑选择割线法；(f) Newton 法是有可能不收敛；(g) 考虑简单迭代法x k +1 = g (x k )，其中x * = g (x *)。
4. 线性方程组求解4．用雅格比法与高斯－赛德尔迭代法解下列方程组Ax =b ，研究其收敛性，上机验证理论分析是否正确，比较它们的收敛速度，观察右端项对迭代收敛有无影响。
(1)A 行分别为A 1=[6,2,-1],A 2=[1,4,-2],A 3=[-3,1,4]； b 1=[-3,2,4]T , b 2=[100,-200,345]T ,(2) A 行分别为A 1=[1,0.8,0.8],A 2=[0.8,1,0.8],A 3=[0.8,0.8,1]；b 1=[3,2,1] T , b 2=[5,0,-10]T ,(3)A 行分别为A 1=[1,3],A 2=[-7,1]；b =[4,6]T , （1）雅可比法A 为所求方程组的系数矩阵，将系数矩阵()n n ij A a R ⨯=∈分为三部分，即111212221211000000n n nn n n a a a a a a A a a a --⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪-- ⎪ ⎪ ⎪=-- ⎪ ⎪ ⎪ ⎪⎪ ⎪--⎝⎭⎝⎭⎝⎭D L U ≡--构造迭代方程，选取M 为A 的对角元素部分，即选取M D =，A D N =-,由此构造得到解AX b =的雅可比迭代法如下：()()()01,,0,1,,k k x xBx f k +⎧⎨=+=⎩ 初始向量(4-1)其中()111B I D A D L U J f D b ---=-=+≡=，，J 为雅可比迭代矩阵。
若A 为n 阶矩阵，迭代公式如下：()()()()()()()00001211,,,()/1,2,,;0,1,T n n k k ii ij j ii j j ix x x x x b a x a i n k +=≠⎧=⎪⎪⎪=-⎨⎪⎪==⎪⎩∑初始向量表示迭代次数(4-2) 在运行程序时首先需要手动输入矩阵A ，阶数n 、向量b 和初始向量x 0，根据式(4-2)不断迭代可求解得近似解。
实验4 解线性方程组的迭代法一、稀疏矩阵的生成和运算实验内容：稀疏矩阵相关命令的熟悉。
实验要求：1、熟悉sparse、full、nnz、spy等命令的使用方法.（实验报告）注意：spy使用时要加上输入参数，直接运行spy会出现与本课程无关的结果。
2、了解sprand命令的用法。
3、熟悉speye、condest、normest、spdiags等命令的使用方法，并生成107阶的三对角矩阵：（实验报告）二、大型稀疏线性方程组的求解实验内容：用不同的迭代法求解n阶大型稀疏矩阵Ax=b（n=1e+4）。
实验要求：（1）数学问题的生成：(a)使用sprand命令生成，稀疏度0.001，并通过spy观察矩阵的结构；(b)运行PPT第21页的两段代码，分别生成A，运行结果有什么区别？注意：如果用稠密方式生成矩阵，可能会导致内存不够。
（2）增大矩阵阶数到1e+6，使用MATLAB自带的pcg与“\”运算，以及分别Gauss消去法、Jacobi迭代法和Gauss-Seidel迭代法分别求解以下Sx=b，看看运算时间对比：（实验报告）b为全1向量，S为以下代码所生成：m=1000,n=m*m;eone=ones(m,1);s=spdiags([-eone,8*eone,-eone],[-1,0,1],m,m);E=speye(m);a1=blkdiag(kron(E,s));a2=spdiags([ones(n,1)],[m],n,n);A=a1-a2-a2';注意：pcg命令只适用于对称正定矩阵三、病态的线性方程组的求解实验内容：考虑方程组Hx=b的求解，其中系数矩阵H为Hilbert矩阵，首先给定解（例如取为各个分量均为1）再计算出右端b的办法给出确定的问题。
实验要求：（1）设定n=6，分别用Gauss消去法、Jacobi迭代法和Gauss-Seidel迭代法求解方程组，其各自的结果如何？各方法的误差比较如何？（实验报告）（2）逐步增大问题的维数100、1000、3000，仍然用上述的方法来解它们，计算的结果如何？计算的结果说明了什么？（实验报告）。
解线性方程组的迭代法Haha送给需要的学弟学妹摘要:因为理论的分析表明，求解病态的线性方程组是困难的，但是实际情况是否如此，需要我们来具体检验。
系数矩阵H 为Hilbert 矩阵，是著名的病态问题。
因而决定求解Hx b =此线性方程组来验证上述问题。
详细过程是通过用Gauss 消去法、J 迭代法、GS 迭代法和SOR 迭代法四种方法求解Hx b =线性方程组。
关键词：病态方程组、Gauss 消去法、J 迭代法、GS 迭代法、SOR 迭代法目录：一、问题背景介绍二、建立正确额数学模型 三、求解模型的数学原理1、Gauss 消去法求解原理2、Jacobi 迭代法求解原理3、G-S 迭代法求解原理4、SOR 迭代法求解原理5、Jacobi 和G-S 两种迭代法收敛的充要条件 四、计算过程（一）Hilbert 矩阵维数n=6时1、Gauss 消去法求解2、Jacobi 迭代法求解3、G-S 迭代法求解4、SOR 迭代法求解（二）Hilbert 矩阵维数n=20、50和100时1、G-S 迭代法求解图形2、SOR 迭代法求解图形 五、编写计算程序 六、解释计算结果1、Gauss 消去法误差分析2、G-S 迭代法误差分析3、SOR 迭代法误差分析G-S 迭代法与SOR 迭代法的误差比较 七、心得体会正文：一、问题背景介绍。
理论的分析表明，求解病态的线性方程组是困难的。
实际情况是否如此，会出现怎样的现象呢？二、建立正确的数学模型。
考虑方程组Hx b =的求解，其中系数矩阵H 为Hilbert 矩阵，,,1(), , ,1,2,,1i j n n i j H h h i j n i j ⨯===+-这是一个著名的病态问题。
通过首先给定解（为方便计算，笔者取x 的各个分量等于1），再计算出右端,b Hx =这样Hx b =的解就明确了，再用Gauss 消去法、J 迭代法、GS 迭代法和SOR 迭代法四种方法分别求解,Hx b =将求解结果与给定解比较，而后求出上述四种方法的误差，得出哪种方法比较好。
第4章解线性方程组的迭代法用迭代法求解线性方程组与第4章非线性方程求根的方法相似，对方程组进行等价变换，构造同解方程组(对可构造各种等价方程组，如分解，可逆，则由得到)，以此构造迭代关系式（4.1）任取初始向量，代入迭代式中，经计算得到迭代序列。
若迭代序列收敛，设的极限为，对迭代式两边取极限即是方程组的解，此时称迭代法收敛，否则称迭代法发散。
我们将看到，不同于非线性方程的迭代方法，解线性方程组的迭代收敛与否完全决定于迭代矩阵的性质，与迭代初始值的选取无关。
迭代法的优点是占有存储空间少，程序实现简单，尤其适用于大型稀疏矩阵；不尽人意之处是要面对判断迭代是否收敛和收敛速度的问题。
可以证明迭代矩阵的与谱半径是迭代收敛的充分必要条件，其中是矩阵的特征根。
事实上，若为方程组的解，则有再由迭代式可得到由线性代数定理，的充分必要条件。
因此对迭代法(4.1)的收敛性有以下两个定理成立。
定理4.1迭代法收敛的充要条件是。
定理4.2迭代法收敛的充要条件是迭代矩阵的谱半径因此，称谱半径小于1的矩阵为收敛矩阵。
计算矩阵的谱半径，需要求解矩阵的特征值才能得到，通常这是较为繁重的工作。
但是可以通过计算矩阵的范数等方法简化判断收敛的工作。
前面已经提到过，若||A||p矩阵的范数，则总有。
因此，若，则必为收敛矩阵。
计算矩阵的1范数和范数的方法比较简单，其中于是，只要迭代矩阵满足或，就可以判断迭代序列是收敛的。
要注意的是，当或时，可以有，因此不能判断迭代序列发散。
在计算中当相邻两次的向量误差的某种范数小于给定精度时，则停止迭代计算，视为方程组的近似解（有关范数的详细定义请看3.3节。
）4.1雅可比（Jacobi）迭代法4.1.1 雅可比迭代格式雅可比迭代计算元线性方程组（4.2）写成矩阵形式为。
若将式（4.2）中每个方程的留在方程左边，其余各项移到方程右边；方程两边除以则得到下列同解方程组：记，构造迭代形式或（4.3）迭代计算式（4.3）称为简单迭代或雅可比迭代。
任取初始向量，由式（4.3）可得到迭代向量序列雅可比迭代矩阵设由，得到等价方程：记不难看出，正是迭代式（4.3）的迭代矩阵，是常数项向量。
于是式（4.3）可写成矩阵形式：（4.4）其中：雅可比迭代算法下面描述解线性方程组的雅可比迭代算法，为了简单起见，在算法中假定矩阵满足雅可比迭代要求，即，并设由系数矩阵构造迭代矩阵是收敛的。
1．定义和输入系数矩阵与常数项向量的元素。
2．FOR i：=1，2，…，n{ //假定，形成常数项向量FOR j:=1,2,…,n} //形成迭代矩阵元素3．// 赋初始值，x1和x2分别表示和4．WHILEx1:=x2x2:=B*x1+g // FOR u:=1,2,…,n// s:= g[u];// FOR v:=1,2,…,n s:=s+b[u][v]*x1[v]; // x2[u]:=s；ENDWHILE5．输出方程组的解例4.1用雅可比方法解下列方程组：解：方程的迭代格式：或雅可比迭代收敛。
取初始值，计算结果由表4.1所示。
表4.1 计算结果0 1 1 11 -1.5 1.6 0.9 0.252 -1.25 2.08 1.09 0.483 -0.915 2.068 1.017 0.3354 -0.9575 1.9864 0.9847 0.08165 -1.01445 1.98844 0.99711 0.056956 -1.00722 2.00231 1.0026 0.013877 -0.997543 2.00197 1.00049 0.009687方程组的准确解是4.1.2 雅可比迭代收敛条件对于方程组，构造雅可比迭代格式其中，。
当迭代矩阵的谱半径时，迭代收敛，这是收敛的充分必要条件。
迭代矩阵的某范数时，迭代收敛。
要注意的是范数小于1只是判断迭代矩阵收敛的充分条件，当迭代矩阵的一种范数||B||>1，并不能确定迭代矩阵是收敛还是发散。
例如，，则，但它的特征值是0.9和0.8。
是收敛矩阵。
当方程组的系数矩阵具有某些性质时，可直接判定由它生成的雅可比迭代矩阵是收敛的。
定理4.3若方程组的系数矩阵，满足下列条件之一，则其雅可比迭代法是收敛的。
（1）为行对角占优阵，即（2）为列对角占优阵，即证明：（1）雅可比迭代矩阵其中（2）为列对角优阵，故为行对角占优阵，由系数矩阵构造的迭代矩阵为行对角占优阵，则有又得到而，得由系数矩阵构造的雅可比迭代矩阵收敛。
（如矩阵既是行对角占优阵，也是列对角占优阵）定理4.4若方程组系数矩阵为对称正定阵，并且也为对称正定，则雅可比迭代收敛。
4.2 高斯-塞德尔（Gauss-Seidel）迭代法高斯-赛德尔迭代计算在雅可比迭代中，用的值代入方程（4.2）中计算出的值，的计算公式是事实上，在计算前，已经得到的值，不妨将已算出的分量直接代入迭代式中，及时使用最新计算出的分量值。
因此的计算公式可改为：即用向量计算出的值，用向量计算出的值，用向量计算出的值，这种迭代格式称为高斯—塞德尔迭代。
对于方程组AX=y ，如果由它构造高斯-塞德尔迭代和雅可比迭代都收敛，那么，多数情况下高斯—塞德尔迭代比雅可比迭代的收敛效果要好，但是情况并非总是如此。
构造方程组的高斯-塞德尔迭代格式的步骤与雅可比类似，设将式（4.1）中每个方程的留在方程的左边，其余各项都移到方程的右边；方程两边除以，得到下列同解方程组：记，对方程组对角线以上的取第步迭代的数值，对角线以下的取第步迭代的数值，构造高斯—塞德尔迭代形式：（4.5）例4.2用高斯-塞德尔方法解方程组：解：方程的迭代格式：取初始值有时，时，计算结果如表4.2所示。
表4.2 计算结果1234000－2.5 2.1 1.14 2.5－0.88 2.0040.9876 1.62－1.0042 1.9984 1.00060.1242－1.0005 2.0002 1.00000.0037 高斯—塞德尔迭代矩阵设写成等价矩阵表达式：构造迭代形式：有（4.6）则高斯-塞德尔迭代式（4.4）为（4.7）称为高斯-塞德尔迭代矩阵。
高斯-塞德尔迭代算法高斯—塞德尔迭代的程序实现与雅可比迭代步骤大致相同，对于方程组，在前面的雅可比算法中，假定雅可比迭代矩阵为表示表示,其迭代核心部分是。
下面的算法给出由和计算的过程，省略了形成迭代矩阵和对初始化的部分。
雅可比迭代的核心部分：WHILEfor(u:=1;u<=n,u++) x1[u]:=x2[u]for(i:=1;j<=n;j++){ s:=g[i];for(j:=1;i<=n;i++){ s:=s+b[i]x2[j]} //注意x2[j]}ENDWHILE在高斯-赛德尔迭代计算中并不需要形成迭代矩阵，由式（4.5）可知在计算中只要形成矩阵在程序中令向量。
它的核心部分是计算迭代式，计算中只需及时将放到的位置上。
高斯-塞德尔迭代的核心部分：WHILEfor(u:=1;u<=n;u++) x1[u]:=x2[u]for(i:=1;j<=n;j++){ s:=g[i];for(j:=1;j<=n;j++){ s:=s+b[i]x2[ j ]} //注意x2[j]x2[i]:=s }ENDWHILE上列算法是在假定迭代收敛的前提下，使用当型（WHILE）结构控制循环。
更一般地，可将上列算法中WHILE循环改为FOR循环，通过控制循环次数和观测计算误差终止循环。
届将上列算法中WHILE语句改为WHILE 循环次数这时在程序中要增加循环变量的设定和运算。
判断高斯塞德尔迭代收敛的方法与判断雅可比迭代收敛类似，一方面从高斯-塞德尔迭代矩阵获取信息，当或的某种范数时，迭代收敛；另一方面，直接根据方程组系数矩阵的特点作出判断。
定理4.5若方程组系数矩阵A为列或行对角优时，则高斯塞德尔迭代收敛。
定理4.6若方程组系数矩阵A为对称正定阵，则高斯塞德尔迭代收敛。
例4.3方程组中，,证明当时Gauss-Seidel法收敛，而Jacobi迭代法只在时才收敛。
解：对法，因为是对称矩阵，因此只要证时正定即可，由顺序主子得而得于是得到时故对称正定，法收敛。
对法，可根据定理4.2，由于迭代矩阵即是法收敛的充要条件，故法只在时才收敛。
当时，法收敛，而，法不收敛，此时不是正定的。
4.3 逐次超松弛（SOR）迭代法逐次超松弛迭代计算方程组的雅可比迭代形式记其中是下三角矩阵，是上三角矩阵。
得高斯-塞德尔的迭代形式：记，有这样可视为的修正量，而恰是由加修正量而得，如果将改为)加上修正量乘一个因子，迭代格改为：整理得(4.8)这里为修正因子，称为松弛因子，而式（4.8）称为松弛迭代。
迭代的分量形式为(4.9)式（4.9）称为松弛迭代的计算格式。
例4.4给定方程组用SOR法求解,取解：用SOR迭代公式可得取初始值：如果用高斯-赛德尔迭代法迭代72次得：用SOR迭代法，只须迭代25次即得：逐次超松弛迭代算法下列算法假定迭代矩阵收敛，否则要在WHILE循环中增加判断条件。
1．定义和输入系数矩阵与常数项向量的元素，输入松弛因子的值。
2．FOR i:=1,2,…,n// 假定，形成常数项向量FOR}3．4. WHILE;}ENDWHILE5．输出.松弛迭代矩阵将式（4.9）中含有与的项分别放在方程两边：用代入上式，有则松弛因子为的迭代矩阵为其中定理4.7逐次超松弛迭代收敛的必要条件。
定理4.8若为正定矩阵，则当时，逐次超松弛迭代恒收敛。
以上定理给出了逐次超松弛迭代因子的范围。
对于每个给定的方程组，确定究竟取多少为最佳，这是比较困难的问题，对某些特定的方程组，我们可以得到一些理论结果。
通常，把的迭代称为亚松弛迭代，把的迭代称为高斯-塞德尔迭代，而把的迭代称为松弛迭代。
4.4 逆矩阵计算在线性代数中逆矩阵是按其伴随矩阵定义的，若则方阵可逆，且，其中为的伴随矩阵。
要计算个阶的列式才能得到一个伴随矩阵，在数值计算中因其计算工作量大而不被采用。
通常对做行的初等的效换，在将化成的过程中得到。
在数值计算中，这仍然是一种行之有效的方法。
由逆矩阵的定义令，有化为个方程组j是第个分量为1，其余分量为0的维向量。
或记为：。
用直接法或迭代法算出也就完成了逆矩阵计算。
如果依次对用高斯若尔当消元法，组合起来看有（当然也能组合起来做）：这正是在线性代数中用初等变换计算逆矩阵的方法。
由此可见，计算一个阶逆矩阵的工作量相当于解个线性方程组。
在数值计算中常常将计算矩阵逆的问题转化为解线性方程组的问题。
例如，已知方阵和向量有迭代关系式，在计算中不是先算出，再作与的乘积得到；而将作为线性方程组系数矩阵，求解方程组作为常驻数项解出。
4.5程序示例程序4.1用雅可比迭代求解方程组：算法描述输入系数矩阵及常数项向量c。
