教学手册(曹奇英数值算法与实现)060328

数值算法与实现教学手册计算机科学与技术学院曹奇英2006年2月目录一、教学大纲……………………………………1二、教学日历……………………………………6三、课程教案……………………………………9四、实验指导书……………………………………44第1页共53页教学大纲第2页共53页数值算法与实现NumericalAlgorithm&implementation一基本信息课程代码：【130171】课程学分：2学分面向专业：计算机科学与技术类课程性质：【选修】开课院系：计算机学院使用教材：主教材【无】参考教材【数值计算方法与C语言工程函数库，科学出版社】【IntroductiontoNumericalComputation，JamasS.Vanaergraft】【计算方法与实习，东南大学出版社】先修课程：【先修过任何一种高级语言课程和高等数学】二课程简介数值算法与实现是计算机科学与技术专业和软件工程专业的选修课，主要以数值方法为对象，介绍相关数值方法的程序实现技术，包括计算搜索算法、插值逼近方法、随机计算方法和自适应计算方法。三选课建议适合计算机应用和软件工程专业二年级以上学生选修。四课程内容绪论0.1数值算法的概念0.2数值算法的描述方法和度量0.3数值算法的稳定性第一章计算搜索算法1.1黄金分割搜索1.2二分搜索1.3迭代搜索1.4爬山方法第二章插值逼近方法2.1Lagrange与Newton插值的关系2.2Newton插值算法的实现2.3三次自然样条2.4用BP神经网络实现函数逼近第三章随机计算方法3.1均匀分布随机数的生成算法3.2正态随机函数的生成算法3.3蒙特卡罗方法第四章自适应计算方法4.1数值积分的计算模型4.2数值积分的自适应计算方法4.3求解常微分方程的离散化模型4.4常微分方程的自适应求解算法五课程的地位和任务本课程为计算机专业和软件工程专业本科二年级以上学生的一门选修课，它在学生已具第3页共53页备一定的计算机程序设计能力和高等数学知识的基础上，以数值方法的算法实现为主线，循序渐进地讲解数值算法的基本思想和程序实现方法。通过学习这门课程，培养学生实现数值算法的能力，使学生能够了解数值算法方面的知识，锻炼学生的实践动手能力。六课程的基本要求1.掌握数值算法的基础知识。2.掌握数值算法实现方法。3.实验要求数据可视化。七课程内容的重点本课程重点要求掌握数值算法以及程序实现。八先修课程高级程序设计语言，高等数学。九对学生能力培养的要求和方法1.掌握数值算法基础。2.使学生具有数值算法的实现能力。十学时分配建议课程内容学时数（学时）上机实验（课内）上机实验（课外）数值算法与实现201212总计3212十一、教学方法和考试说明1.教学方法采用课堂教学与实验教学相结合的教学方式。2.考试方式考试成绩由实验(30%)和期末测验(70%)组成。第4页共53页教学日历第5页共53页东华大学教学日历2005—2006学年课程名称：《数值算法与实现》任课教师：曹奇英考查第周使用班级：计算机04教研室主任：史有群考试第17周答疑时间：周二中午3：00-4：20答疑地点：计算机学院221室日期周次讲课内容分章和分节的名称课内时数课外时数习题课、课堂讨论、课堂练习内容课内时数课外时数实验、设计和实践环节名称课内时数课外时数1§0数值计算的基本概念222§1计算搜索算法.1.1黄金分割搜索1.2二分搜索223黄金分割搜索算法二分搜索算法2241.3迭代搜索1.4爬山方法225迭代搜索算法爬山算法226§2插值逼近方法2.1Lagrange与Newton插值的关系2.2Newton插值算法的实现227Newton插值算法2282.3三次自然样条229三次自然样条算法22102.4用BP神经网络实现函数逼近2211BP神经网络2212§3随机计算方法3.1均匀分布随机数的生22周数17周讲课18学时练习2学时实验12学时机动2学时合计34学时第6页共53页成算法3.2正态随机函数的生成算法3.3蒙特卡罗方法13§4自适应计算方法4.1数值积分的计算模型4.2数值积分的自适应计算方法22144.3求解常微分方程的离散化模型4.4常微分方程的自适应求解算法2215自适应算法2216机动217测验2注：经过平衡的教学日历一式四份，一份教师和教研室，一份存系，一份送教务处，一份送有关班级。第7页共53页课程教案东华大学教案第8页共53页课程名称数值算法与实现授课专业全校各专业班级2—4年级课程编号【130171】课程类型必修课校级公共课（）；基础或专业基础课（）；专业课（√）选修课限选课（）；任选课（√）授课方式课堂讲授（√）；实践（）上机（√）；案例讨论（）考核方式考试（）；考查（√）；上机（）；论文（）课程教学总学时数32学时学分数2学时分配课堂讲授18学时；实践课12学时教材名称无作者出版社参考书1【IntroductiontoNumericalComputation】2【计算方法与实习】3【数值计算方法与C语言工程函数库】JamasS.Vanaergraft东南大学出版社科学出版社授课教师曹奇英职称教授单位计算机学院授课时间注：表中（）选项请打“√”东华大学教案第9页共53页周次第一周，第1次课章节名称§0绪论授课方式课堂讲授（√）；实践课（）教学时数2时间分配授课要点课程目的意义、内容简介从方法论的角度讲解数值算法的核心思想，使学生了解掌握数值算法的设计与实现方法。引入数据可视化的观点，通过上机实践，将各种数值算法以图形的方式展现出来，使学生深刻理相应的基本概念和基本方法。课程教学安排授课18学时，上机12学时，随堂考试2学时课程的学习方法课堂学习与上机实践相结合，加强上机实践动手能力，通过上机实验的结果（动态图形显示）的分析反过来深刻理解数值算法的基本思想方法。§0绪论数值算法的基本概念、算法的基本性质、算法描述方法、算法效率、误差。适定性的概念：问题的适定性、算法的适定性。第一学时第二学时东华大学教案第10页共53页教学重点与难点数值算法的相关概念适定性的概念通过解方程5.1001.1499.032yxyx问题和计算积分等实例，使学生深刻理解适定性的概念。课堂讨论与练习通过师生互动讨论算法的概念。参考资料参考网站，通过互联网查找有关算法概念和适定性资料备注dxexx1020东华大学教案第11页共53页周次第二周，第2次课章节名称§1计算搜索算法.1.1黄金分割搜索1.2二分搜索授课方式课堂讲授（√）；实践课（）教学时数2时间分配授课要点§1计算搜索算法.一般搜索的基本思想逐步缩小搜索空间和搜索过程的稳定性1.1黄金分割搜索黄金分割点的确定（理论分析）搜索条件黄金分割搜索算法算法稳定性分析1.2二分搜索二分搜索的基本思想二分搜索算法算法稳定性分析第一学时第二学时东华大学教案第12页共53页教学重点与难点重点是迭代与离散化的基本思想难点：黄金分割点的确定课堂讨论与练习布置上机实验题目：黄金分割搜索算法的设计与实现二分搜索算法的设计与实现要求学生在课下进行精心准备，编写相应的程序，可以节省实验课上的程序调试时间。参考资料参考网站《数值算法与实现》实验指导书数值算法理论与实现论坛=51备注东华大学教案第13页共53页周次第三周，第3次课章节名称搜索算法上机实习（1）授课方式课堂讲授（）；实践课（√）教学时数2时间分配授课要点1黄金分割搜索算法上机实验用黄金分割搜索算法求cos(x),x∈[-π/2,π/2]的最大值，设计出具体的程序，使之能够动态演示搜索过程。2二分搜索算法上机实验用二分搜索算法求x=2sinx的所有根，设计出具体的程序，使之能够动态演示搜索过程。第一学时第二学时东华大学教案第14页共53页教学重点与难点重点是算法实现、调试难点：输出结果的可视化。课堂讨论与练习上机辅导与讨论。参考资料参考网站《数值算法与实现》实验指导书数值算法理论与实现论坛=51备注东华大学教案第15页共53页周次第四周，第4次课章节名称§1计算搜索算法.1.3迭代搜索1.4爬山搜索授课方式课堂讲授（√）；实践课（）教学时数2时间分配授课要点§1计算搜索算法.1.3迭代搜索迭代公式的构造)(10nnXXX给定初始值迭代稳定性的条件1迭代中止条件与迭搜索算法举例1.4爬山搜索二分搜索的基本思想二分搜索算法算法稳定性分析第一学时第二学时东华大学教案第16页共53页教学重点与难点重点是迭代的构造方法和算法难点：爬山迭代的原理和数学模型课堂讨论与练习布置上机实验题目：爬山迭代搜索算法的设计与实现要求学生在课下进行精心准备，编写相应的程序，可以节省实验课上的程序调试时间。参考资料参考网站《数值算法与实现》实验指导书数值算法理论与实现论坛=51备注东华大学教案第17页共53页周次第五周，第5次课章节名称搜索算法上机实习（2）授课方式课堂讲授（）；实践课（√）教学时数2时间分配授课要点爬山迭代搜索算法上机实验用爬山法求f(x,y)=1/(x2+y2+2)的最大值，设计出具体的程序，使之能够动态演示爬山搜索过程。东华大学教案第18页共53页教学重点与难点重点是算法实现、调试难点：输出结果的可视化。课堂讨论与练习上机辅导与讨论。参考资料参考网站《数值算法与实现》实验指导书数值算法理论与实现论坛=51备注东华大学教案第19页共53页周次第六周，第6次课章节名称§2插值逼近方法2.1Lagrange与Newton插值的关系2.2Newton插值算法的实现授课方式课堂讲授（√）；实践课（）教学时数2时间分配授课要点§2插值逼近方法2.1Lagrange与Newton插值的关系一、拉格朗日插值问题存在性、唯一性二、拉格朗日插值公式nknkiiikikxxxxyxf0,0)(三、拉格朗日插值算法四、算法效率五、提高算法效率的途径1、计算多项式的秦九韶算法2、拉格朗日插值公式与牛顿插值的关系设Pn(x)=Pn-1(x)+Qn(x)则Qn(x)=Pn(x)=Pn-1(x)=an(x-x0)(x-x1)(x-xn-1)得到Nn(x)=Pn(x)=a0+a1(x-x0)++an(x-x0)(x-x1)(x-xn-1)an=nknkiiikkxxy0,012.2Newton插值算法的实现一、计算插值系数的算法二、算法效率三、牛顿插值算法四、牛顿插值算法的算法效率第一学时第二学时东华大学教案第20页共53页教学重点与难点教学重点是基于秦九韶多项式快速计算算法的牛顿插值算法和插值系数计算的算法。教学难点：拉格朗日插值公式与牛顿插值公式的关系的推导。课堂讨论与练习从多项式计算算法的算法效率讨论入手，引入秦九韶算法。布置拉格朗日插值和牛顿插值对比实验，要求学生在课下进行精心准备，编写相应的程序。参考资料参考网站《数值算法与实现》实验指导书数值算法理论与实现论坛=51备注东华大学教案第21页共53页周次第七周，第7次课章节名称插值算法上机实习（1）授课方式课堂讲授（√）；实践课（）教学时数2时间分配授课要点Lagrange与N