1、科学计算的背景科学计算的背景非线性方程求根算法非线性方程求根算法线性方程组求解直接法线性方程组求解直接法线性方程组求解迭代法线性方程组求解迭代法科学计算方法科学计算方法与计算机有机结合科学计算方法与计算机有机结合 构造出强有力的工作平台构造出强有力的工作平台数值分析数值分析研究用计算机求解研究用计算机求解1969年年, Apollo 登月计划实现登月计划实现1981年年,Columbia号航天飞机号航天飞机发射成功发射成功数学问题的方法数学问题的方法(算法算法)和理论和理论方程组求解、方程求根、数据插值、方程组求解、方程求根、数据插值、数据拟合、数值积分、微分方程求解数据拟合、数值积分、微分方
2、程求解von Neumann1994年年, GPS完全投入使用完全投入使用例例1: 圆内接正多边形边长计算圆内接正多边形边长计算Pi方法方法评价算法的主要指标评价算法的主要指标:速度和精度速度和精度简单迭代算法简单迭代算法:nnLn sin 3/ )4(22nnnLLL n L error192 3.1414524 1.4e-004384 3.1415576 3.5e-005 3.1415926 4.6e-010例例2. 通信卫星覆盖地球面积通信卫星覆盖地球面积数学模型数学模型实际问题实际问题获取数据获取数据数值方法、程序数值方法、程序数据结果数据结果将地球考虑成一将地球考虑成一个球体个球体,
3、 设设R为地为地球半径球半径,h为卫星为卫星高度高度,D为覆盖面为覆盖面在切痕平面上的在切痕平面上的投影投影(积分区域积分区域) DdxdyyxRR222 假设某一数据的准确值为假设某一数据的准确值为 x* *, ,其近似值其近似值为为 x，则称则称 )(,)()(*0 xxxxxxexer而称而称为为 x 的的相对误差相对误差误差的有关概念误差的有关概念 e( (x)= )= x - - x* * 为为 x 的的绝对误差绝对误差如果存在一个适当小的正数如果存在一个适当小的正数 ，使得使得 xxxe)( 则称则称为为绝对误差限绝对误差限。 称称r为为相对误差限相对误差限。 如果存在一个适当小的
4、正数如果存在一个适当小的正数r ，使得使得 rrxxxxxexe )()(mnaaax10021 .十进制浮点数表示十进制浮点数表示一台微机价格一台微机价格:￥3999.00, 浮点数表示浮点数表示:0.3999104地球半径地球半径: 6378137m, (6.378137e+006) 浮点数表示浮点数表示: 0.6378137107光速光速: 2.99792458e+008 浮点数表示浮点数表示: 0.299792458109尾数部尾数部阶码部阶码部有效数字概念有效数字概念: :取取 的有限位数如下的有限位数如下( ( 3.1415926) )取取 x1 = = 3，误差限不超过误差限不超
5、过0.5;取取 x2 = = 3.14, ,误差限不超过误差限不超过0.005 ;若近似值若近似值 x 的绝对误差限是某一位上的半个的绝对误差限是某一位上的半个单位，该位到单位，该位到 x 的第一位非零数字一共有的第一位非零数字一共有 n 位，则称近似值位，则称近似值 x 有有 n 位有效数字位有效数字. . 取取 x3 = = 3.1416, ,误差限不超过误差限不超过0.00005 ; r d 例例4.4.水中浮球问题水中浮球问题 有一半径有一半径r =10 cm的球体的球体,密密度度 =0.638.球体浸入水中后球体浸入水中后,浸入水中的深度浸入水中的深度d 是多少是多少？ 根据阿基米德
6、定律根据阿基米德定律,物体排开水的质量就是水物体排开水的质量就是水对物体的浮力对物体的浮力。 334rM ddxxrrV022)( 整理得整理得: d 3 3 r d 2 + 4 r 3 = 0 05101520-2000-10000100020003000由由 =0.638, r = 10.代入代入,得得d 3 30 d 2 + 2552 = 0 令令 f (x) = x 3 30 x 2 + 2552 ,函数图形如下所示函数图形如下所示求解方程求解方程 f(x)=0,即即是求函数是求函数 f(x)的零的零点点. f(x) 的零点所的零点所在区间为在区间为:0, 20roots(1 -30
7、0 2552)ans = 26.3146 11.8615 -8.1761第一步第一步:对根进行隔离对根进行隔离,找出隔根区间找出隔根区间,或在隔根或在隔根区间内确定一个解的近似值区间内确定一个解的近似值x0;设设f(x) = 0的根为的根为 x*,通过迭代计算通过迭代计算,产生序列产生序列: x0 x1 x2 xn 用数值方法求非线性方程的根用数值方法求非线性方程的根, ,分两步进行分两步进行:第二步第二步:逐步逼近逐步逼近,利用近似解利用近似解x0 (或隔根区间或隔根区间) 通过通过迭代算法迭代算法得到更精确的近似解得到更精确的近似解.*limxxnn 只须只须已知方程已知方程 f(x)=0
8、有一隔根有一隔根区间区间a, b,且且f(x)满足满足f(a)f(b)0,则先将则先将a , b等等分为两个小区间分为两个小区间,判断根属判断根属于哪个小区间于哪个小区间,舍去无根区舍去无根区间保留有根区间间保留有根区间a1, b1;二分法迭代二分法迭代把区间把区间a1, b1 一分为二一分为二, ,进一步判断根属于哪个更进一步判断根属于哪个更小的区间小的区间 a2, b2,如此不断二分以缩小区间长度如此不断二分以缩小区间长度 . .a, bx0=0.5(a+b)a1,b1=a,x0a1,b1=x0,bx1=0.5(a1+b1)f(a1) f(b1) 0已知已知f(x)=0在在a,b内有一根内
9、有一根,且且f(a)f(b)0(1)计算计算: yaf(a) , x00.5(a+b), y0f(x0) 判断判断,若若y0=0,则则x0是根是根,否则转下一步否则转下一步;(2)判断判断,若若y0ya0,则则a1a, b1 x0 否则否则 a1x0, b1b, ya y0二分法迭代将得到一系列隔根区间二分法迭代将得到一系列隔根区间 ,2211nnbabababa定理定理2.22.2 设设x*是是 f(x)=0在在a, b内的唯一根内的唯一根,且且 f(a)f(b)0,则二分计算过程中则二分计算过程中, 各区间的中点数列各区间的中点数列 ), 2 , 1 , 0( )(21 nbaxnnn性质
10、性质:1. f(an)f(bn) 0,Cx x2 C = 0令令 f(x) = x2 C , 则则xxf2)( nnnnxCxxx221 211nnnxCxx 19/46由此可知由此可知, 平方根迭代具有平方根迭代具有 2 阶收敛速度阶收敛速度 nnnxCxCx21)(21 CCxCxnnn21|lim21 CxCxCxnnn 21122)(21221CxxCCxxxnnnnn Cxnn lim20/46f0 f0, f”0 f0, f”0 f0, f” DX(k+1) = (U+L)X(k) + bX(k+1)=D-1(U+L)X(k)+D-1b记记BJ = D-1(U+L) X(k+1)=
11、BJX(k)+fJ34/46雅可比迭代矩阵雅可比迭代矩阵 0002122111212211nnnnnnJaaaaaaaaaB 0/0/02122222211111112nnnnnnnnJaaaaaaaaaaaaB nnnJabababf/22211135/46例例10 131581079321321321xxxxxxxxx15/ )13()1(2)1(1)1(3 kkkxxx9/ )7()(3)(2)1(1kkkxxx 10/ )8()(3)1(1)1(2kkkxxx 15/ )13(10/ )8(9/ )7(213312321xxxxxxxxx 000)0(3)0(2)0(1xxx误差限误差
12、限5e-0045e-0055e-0065e-007赛德尔迭代次数赛德尔迭代次数5567雅可比迭代次数雅可比迭代次数67910高斯高斯- -赛德尔迭代法赛德尔迭代法36/46高斯高斯- -赛德尔迭代法矩阵表示赛德尔迭代法矩阵表示 138715111101119321xxx AX = b 15110101009M 000100110NA = M N MX(k+1)= NX (k)+ b37/46injjijbxa 1(i = 1,2,n)高斯高斯- -赛德尔赛德尔迭代法计算格式迭代法计算格式 nijkjijijkjijiiikixaxabax1)(11)1()1(1(i = 1,2,n; k =1
13、,2,)取初始向量取初始向量x(0)=x1(0) x2(0) xn(0)T, 做迭代计算做迭代计算38/46A X = b (MN )X = b记记 (k) = X(k) X* ( k = 0, 1, 2, 3, )则有则有 (k+1) = B (k) ( k =0, 1, 2, 3, )计算格式计算格式: X(k+1) = B X(k) + f ( B = M-1N ) X(k+1) X*= B(X(k) X*) 设方程组的精确解设方程组的精确解为为 X*,则有则有X* = B X* + f 39/46平面点列平面点列: *limyxyxkkk0)()(lim2*2* yyxxkkkXkRn
14、 : X1, X2, , Xk , *limXXkk 0|lim2* XXkk 11yx 22yx kkyx0|lim* XXkk40/46证证: 由由 (k) = B (k-1),得得 | (k)| | B| | (k-1)| ( k = 1, 2, 3, )0lim)( kk 所以所以命题命题 若若|B|1,则迭代法则迭代法 X(k+1) =B X(k) +f 收敛收敛| (k)| | B|k | (0)| 0|lim|lim)0()( kkkkB| B| 141/46定理定理4.3 若若Ax=b的系数矩阵的系数矩阵A是严格对角占优是严格对角占优矩阵矩阵,则则Jacobi迭代和迭代和Sei
15、del迭代均收敛迭代均收敛定理定理4.2 :设设X*为方程组为方程组 AX=b 的解的解若若|B|1,则对迭代格式则对迭代格式 X(k+1) = B X(k) + f 有有|1|*|)1()()( kkkXXBBXX(1)|1|*|)0()1()(XXBBXXkk (2)42/46 yyuxuxuyuyxuuyyxx sin), 1(0)1 ,()0 ,(), 0(1,0, 0例例11.平面平面温度场问温度场问题题:令令 h = 1/(n+1) , xj= jh, yj = jh ( i , j = 0,1, , n+1 )记记 ui,j= u(xi , yj ), ( i , j = 0,1
16、, , n+1 )02221,1,2, 1, 1 huuuhuuujiijjijiijji迭代格式迭代格式)(41)(1,)1(1,)(, 1)1(, 1)1(,kjikjikjikjikjiuuuuu ( i, ,j = 1, , ,n )u0, j = 0, jjnyu sin, 1 ui, 0 = 0, ui, n+1 = 043/46结点数结点数n2 102 202 402迭代次数迭代次数 182 606 2077CPU时间时间(s) 0.97 4.328 58.531误差误差 0.0023 6.4274e-4 1.6814e-4高斯高斯- -赛德尔迭代法实验赛德尔迭代法实验( (误差
17、限误差限10-8) ):24681012246810120510150102000.5144/46)1(1)(11)1()()1( nijkjijijkjijiiikikixaxabaxx (i=1,2, n; k = 1,2,3, )迭代格式迭代格式超松驰迭代方法超松驰迭代方法SOR(successive overrelaxation)Prof. David M. Young1954 美国数学科学学报美国数学科学学报45/46)(41)(1,)1(1,)(, 1)1(, 1)1(,kjikjikjikjikjiuuuuu Seidel迭代格式迭代格式SOR迭代格式迭代格式)(4)1()(1,
18、)1(1,)(, 1)1(, 1)()1(,kjikjikjikjikijkjiuuuuuu 最佳松驰因子最佳松驰因子h sin12 02221,1,2, 1, 1 huuuhuuujiijjijiijji平面温度场的计算问题平面温度场的计算问题46/46结点数结点数n2 102 202 402迭代次数迭代次数 182 606 2077CPU时间时间(s) 0.97 4.328 58.531误差误差 0.0023 6.4274e-4 1.6814e-4高斯高斯- -赛德尔迭代赛德尔迭代 ( (误差限误差限10-8) ):SOR迭代实验迭代实验( (误差限误差限10-8) ):结点数结点数n2 102 202 402迭代次数迭代次数 40 74 137CPU时间时间(s) 0.11 0.6560 4.9530 误差误差 0.0023 6.4306e-4 1.6944e-447/46人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。48/46
