科学计算方法解读课件

科学计算的背景科学计算的背景非线性方程求根算法非线性方程求根算法线性方程组求解直接法线性方程组求解直接法线性方程组求解迭代法线性方程组求解迭代法科学计算方法科学计算的背景科学计算方法科学计算方法与计算机有机结合科学计算方法与计算机有机结合 构造出强有力的工作平台构造出强有力的工作平台数值分析数值分析研究用计算机求解研究用计算机求解1969年年,Apollo 登月计划实现登月计划实现1981年年,Columbia号航天飞机号航天飞机发射成功发射成功数学问题的方法数学问题的方法(算法算法)和理论和理论方程组求解、方程求根、数据插值、方程组求解、方程求根、数据插值、数据拟合、数值积分、微分方程求解数据拟合、数值积分、微分方程求解von Neumann1994年年,GPS完全投入使用完全投入使用科学计算方法与计算机有机结合数值分析研究用计算机求解19例例1:圆内接正多边形边长计算圆内接正多边形边长计算Pi方法方法评价算法的主要指标评价算法的主要指标:速度和精度速度和精度简单迭代算法简单迭代算法:n L error192 3.1414524 1.4e-004384 3.1415576 3.5e-005 3.1415926 4.6e-010例1:圆内接正多边形边长计算Pi方法评价算法的主要指标:速例例2.通信卫星覆盖地球面积通信卫星覆盖地球面积数学模型数学模型实际问题实际问题获取数据获取数据数值方法、程序数值方法、程序数据结果数据结果将地球考虑成一将地球考虑成一个球体个球体,设设R为地为地球半径球半径,h为卫星为卫星高度高度,D为覆盖面为覆盖面在切痕平面上的在切痕平面上的投影投影(积分区域积分区域)例2.通信卫星覆盖地球面积数学模型实际问题获取数据数值方法 假设某一数据的准确值为假设某一数据的准确值为 x*,其近似值其近似值为为 x，则称则称 而称而称为为 x 的的相对误差相对误差误差的有关概念误差的有关概念 e(x)=)=x -x*为为 x 的的绝对误差绝对误差 假设某一数据的准确值为 x*,其近似值而称为 x 的相对如果存在一个适当小的正数如果存在一个适当小的正数 ，使得使得 则称则称为为绝对误差限绝对误差限。称称r为为相对误差限相对误差限。如果存在一个适当小的正数如果存在一个适当小的正数r ，使得使得 如果存在一个适当小的正数，使得 则称为绝对误差限。十进制浮点数表示十进制浮点数表示一台微机价格一台微机价格:￥3999.00,浮点数表示浮点数表示:0.3999104地球半径地球半径:6378137m,(6.378137e+006)浮点数表示浮点数表示:0.6378137107光速光速:2.99792458e+008 浮点数表示浮点数表示:0.299792458109尾数部尾数部阶码部阶码部十进制浮点数表示一台微机价格:￥3999.00,尾数部阶码部有效数字概念有效数字概念:取取 的有限位数如下的有限位数如下(3.1415926)取取 x1=3，误差限不超过误差限不超过0.5;取取 x2=3.14,误差限不超过误差限不超过0.005;若近似值若近似值 x 的绝对误差限是某一位上的半个的绝对误差限是某一位上的半个单位，该位到单位，该位到 x 的第一位非零数字一共有的第一位非零数字一共有 n 位，则称近似值位，则称近似值 x 有有 n 位有效数字位有效数字.取取 x3=3.1416,误差限不超过误差限不超过0.00005;有效数字概念:取 x1=3，误差限不超过0.5;取 x2 r d 例例4.4.水中浮球问题水中浮球问题 有一半径有一半径r=10 cm的球体的球体,密密度度 =0.638.球体浸入水中后球体浸入水中后,浸入水中的深度浸入水中的深度d 是多少是多少？根根据据阿阿基基米米德德定定律律,物物体体排排开开水水的的质质量量就就是是水水对物体的浮力对物体的浮力。整理得整理得:d 3 3 r d 2+4 r 3 =0 例4.水中浮球问题 根据阿基米德定律,物体排开水的质量由由 =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 0 2552)ans=26.3146 11.8615 -8.1761由=0.638,r=10.代入,得d 3 30第一步第一步:对根进行隔离对根进行隔离,找出隔根区间找出隔根区间,或在隔根或在隔根区间内确定一个解的近似值区间内确定一个解的近似值x0;设设f(x)=0的根为的根为 x*,通过迭代计算通过迭代计算,产生序列产生序列:x0 x1 x2 xn 用数值方法求非线性方程的根用数值方法求非线性方程的根,分两步进行分两步进行:第二步第二步:逐步逼近逐步逼近,利用近似解利用近似解x0(或隔根区间或隔根区间)通过通过迭代算法迭代算法得到更精确的近似解得到更精确的近似解.只须只须第一步:对根进行隔离,找出隔根区间,或在隔根区间内确定一个解已知方程已知方程 f(x)=0有一隔根有一隔根区间区间a,b,且且f(x)满足满足f(a)f(b)0,则先将则先将a,b等等分为两个小区间分为两个小区间,判断根属判断根属于哪个小区间于哪个小区间,舍去无根区舍去无根区间保留有根区间间保留有根区间a1,b1;二分法迭代二分法迭代把区间把区间a1,b1 一分为二一分为二,进一步判断根属于哪个更进一步判断根属于哪个更小的区间小的区间 a2,b2,如此不断二分以缩小区间长度如此不断二分以缩小区间长度 .已知方程 f(x)=0有一隔根区间a,b,且f(x)满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内有一根内有一根,且且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 y0a,bx0=0.5(a+b)a1,b1=a,x0二分法迭代将得到一系列隔根区间二分法迭代将得到一系列隔根区间 定理定理2.22.2 设设x*是是 f(x)=0在在a,b内的唯一根内的唯一根,且且 f(a)f(b)0,则二分计算过程中则二分计算过程中,各区间的中点数列各区间的中点数列 性质性质:1.f(an)f(bn)0,x2 C=0令令 f(x)=x2 C,则则(n=0,1,2,)牛顿迭代格式给定初值19/46由此可知由此可知,平方根迭代具有平方根迭代具有 2 阶收敛速度阶收敛速度 由此可知,平方根迭代具有 2 阶收敛速度 20/46f0 f0,f”0 f0,f”0 f0,f”0 牛顿迭代法收敛的四种情况牛顿迭代法收敛的四种情况f0 f0,f”0 f0,21/46例例7.7.牛顿迭代法的收敛域问题牛顿迭代法的收敛域问题:用用牛牛顿顿迭迭代代法法求求解解复复数数方方程程 z3 1=0，该该方方程程在在复复平面上三个根分别是平面上三个根分别是z1=1选择中心位于坐标原点，边长选择中心位于坐标原点，边长为为2 2的正方形内的任意点作初始的正方形内的任意点作初始值，进行迭代，把收敛到三个值，进行迭代，把收敛到三个根的初值分为三类，并分别标根的初值分为三类，并分别标上不同颜色（例如红、黄、蓝）上不同颜色（例如红、黄、蓝）。对充分多的初始点进行实验，。对充分多的初始点进行实验，绘出牛顿迭代法对该方程的收绘出牛顿迭代法对该方程的收敛域彩色图敛域彩色图。例7.牛顿迭代法的收敛域问题:z1=1选择中心位于坐标22/46收敛到收敛到 z1 的牛顿迭代初值点集合的牛顿迭代初值点集合收敛到收敛到 z2 的牛顿迭代初值点集合的牛顿迭代初值点集合收敛到收敛到 z3 的牛顿迭代初值点集合的牛顿迭代初值点集合收敛到 z1 的牛顿迭代初值点集合收敛到 z2 的牛顿迭代初23/46在复平面内在复平面内,有一些例外点是牛顿迭代不收敛的初有一些例外点是牛顿迭代不收敛的初值点值点.这些例外点构成了茹利亚集这些例外点构成了茹利亚集(为纪念法国女为纪念法国女数学家数学家Julia).在复平面内,有一些例外点是牛顿迭代不收敛的初值点.这些例外24/46线性方程组的矩阵形式线性方程组的矩阵形式a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2an1x1+an2x2+annxn=bnA X=b(i=1,2,n)线性方程组求解线性方程组求解:1.直接方法直接方法;2.基本迭代法基本迭代法;3.子空间方法子空间方法X?b线性方程组的矩阵形式a11x1+a12x2+a25/46例例8x4=2,x3=4,x2=1,x1=3例8x4=2,x3=4,x2=1,x1=326/46解上三角方程组解上三角方程组计算计算：xn=bn/ann(a11ann0)xk=bk(ak,k+1xk+1+ak n)/ak k (k=n1,1)除法除法:n次次;乘法乘法:n(n-1)/2次次,乘、除法运算共乘、除法运算共 n(n+1)/2 次次,简记为简记为 O(n2)解上三角方程组计算：xn=bn/ann(a11an27/46消元过程消元过程(化一般方程组为上三角方程组化一般方程组为上三角方程组)消元过程(化一般方程组为上三角方程组)28/46增广矩阵增广矩阵 计算计算:m21 m31 m41T=a21 a31 a41T/a11 用用m21乘矩阵第一行加到矩阵第二行乘矩阵第一行加到矩阵第二行;用用m31乘矩阵第一行加到矩阵第三行乘矩阵第一行加到矩阵第三行;用用m41乘矩阵第一行加到矩阵第四行乘矩阵第一行加到矩阵第四行;增广矩阵 计算:m21 m31 m41T=a29/46实现第一轮消元实现第一轮消元实现第二轮消元、第三轮消元实现第二轮消元、第三轮消元消元过程乘除消元过程乘除法次数法次数:O(n3)实现第一轮消元实现第二轮消元、第三轮消元 消30/46例例9.特点特点:系数矩阵主系数矩阵主对角元均不为零对角元均不为零计算格式计算格式 X(1)=B X(0)+f取取 X(0)=例9.特点:系数矩阵主对角元均不为零计算格式 X(1)=31/46 X*1.0000 1.0000 1.0000 X(0)0 0 0 X(1)0.7778 0.8000 0.8667 X(2)0.96300.96440.9778 X(3)0.99290.99350.9952计算格式计算格式:X(k+1)=BX(k)+fX(0),X(1),X(n)X(4)0.99870.99880.9991X(n+1)B X(n)+f X*X(0)X(1)X(2)X32/46雅可比雅可比迭代法迭代法(i=1,2,n;k=1,2,)取初始向量取初始向量X(0)=x1(0)x2(0)xn(0)T,迭代计算迭代计算(i=1,2,n)雅可比迭代法(i=1,2,n;k=1,2,)取初33/46雅可比雅可比 迭代法的矩阵表示迭代法的矩阵表示将方程组将方程组AX=b 的系数矩阵的系数矩阵 A 分解分解 A=D U LAX=b =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)=BJX(k)+fJ雅可比 迭代法的矩阵表示将方程组AX=b 的系数矩阵 A34/46雅可比迭代矩阵雅可比迭代矩阵雅可比迭代矩阵35/46例例10误差限误差限5e-0045e-0055e-0065e-007赛德尔迭代次数赛德尔迭代次数5567雅可比迭代次数雅可比迭代次数67910高斯高斯-赛德尔迭代法赛德尔迭代法例10误差限5e-0045e-0055e-0065e-00736/46高斯高斯-赛德尔迭代法矩阵表示赛德尔迭代法矩阵表示 AX=bA=M N MX(k+1)=NX(k)+b高斯-赛德尔迭代法矩阵表示 AX=bA=M 37/46(i=1,2,n)高斯高斯-赛德尔赛德尔迭代法计算格式迭代法计算格式(i=1,2,n;k=1,2,)取初始向量取初始向量x(0)=x1(0)x2(0)xn(0)T,做迭代计算做迭代计算(i=1,2,n)高斯-赛德尔迭代法计算格式(i=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 A X=b (MN)X=b记 39/46平面点列平面点列:XkRn:X1,X2,Xk,平面点列:XkRn:X1,X2,40/46证证:由由(k)=B (k-1),得得|(k)|B|(k-1)|(k=1,2,3,)所以所以命题命题 若若|B|1,则迭代法则迭代法 X(k+1)=B X(k)+f 收敛收敛|(k)|B|k|(0)|B|1证:由(k)=B(k-1),得所以命题 若|41/46定理定理4.3 若若Ax=b的系数矩阵的系数矩阵A是严格对角占优是严格对角占优矩阵矩阵,则则Jacobi迭代和迭代和Seidel迭代均收敛迭代均收敛定理定理4.2:设设X*为方程组为方程组 AX=b 的解的解若若|B|1,则对迭代格式则对迭代格式 X(k+1)=B X(k)+f 有有(1)(2)定理4.3 若Ax=b的系数矩阵A是严格对角占优矩阵,则Ja42/46例例11.平面平面温度场问温度场问题题:令令 h=1/(n+1),xj=jh,yj=jh (i,j=0,1,n+1)记记 ui,j=u(xi,yj),(i,j=0,1,n+1)迭代格式迭代格式(i,j=1,n)u0,j=0,ui,0=0,ui,n+1=0例11.平面温度场问题:令 h=1/(n+1),43/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):结点数n2 102 44/46(i=1,2,n;k=1,2,3,)迭代格式迭代格式超松驰迭代方法超松驰迭代方法SOR(successive overrelaxation)Prof.David M.Young1954 美国数学科学学报美国数学科学学报(i=1,2,n;k=1,2,3,45/46Seidel迭代格式迭代格式SOR迭代格式迭代格式最佳松驰因子最佳松驰因子平面温度场的计算问题平面温度场的计算问题Seidel迭代格式SOR迭代格式最佳松驰因子平面温度场的计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-4结点数n2 102 47/46人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。人有了知识，就会具备各种分析能力，48/46科学计算方法解读课件