第一章1霍纳（Horner ）方法： n a 1-n a 2-n a ……2a 1a 0a输入=c+ n b *c c b n *1- c b *3 c b *2 c b *1n b 1-n b 2-n b 2b 1b 0bAnswer P （x ）=0b该方法用于解决多项式求值问题P （x ）=n a n x +1-n a 1-n x +2-n a 2-n x +……+2a 2x +1a x +0a2 注：p ˆ为近似值绝对误差：|ˆ|pp E p -=相对误差：|||ˆ|p pp R p -=有效数字:210|||ˆ|1d p p pp R -<-= （d 为有效数字，为满足条件的最大整数） 3 Big Oh(精度的计算)： O(h ⁿ)+O(h ⁿ)=O(h ⁿ);O(h m )+O(h n )=O(h r ) [r=min{p,q}]; O(h p )O(h q )=O(h s ) [s=q+p]; 第二章2.1 求解x=g(x)的迭代法 用迭代规则，可得到序列值｛｝。

设函数g 。

如果对于所有x ，映射y=g(x)的范围满足y ， 则函数g 在内有一个不动点; 此外，设定义在内，且对于所有x ，存在正常数K<1，使得，则函数g 在内有唯一的不动点P 。

定理2.3 设有（i ）g ，g ’，（ii ）K 是一个正常数，（iii ）。

如果对于所有如果对于所有x 在这种情况下，P 成为排斥不动点，而且迭代显示出局部发散性。

. 波尔查诺二分法(二分法定理)<收敛速度较慢>试值（位）法：<条件与二分法一样但改为寻求过点(a,f(a))和(b,f(b))的割线L 与x 轴的交点(c,0)>应注意越来越小，但可能不趋近于0，所以二分法的终止判别条件不适合于试值法.牛顿—拉夫森迭代函数：)(')()(1111-----==k k k k k p f p f p p g p 其中k=1,2,……证明：用泰勒多项式证明第三章线性方程组的解法 对于给定的解线性方程组Ax=b一Gauss Elimination （高斯消元法 ）第一步Forward Elimination 第二步 BackSubstitution二LU Factorization第一步 A = LU 原方程变为LUx=y ；第二步 令Ux=y,则Ly = b 由下三角解出y ； 第三步 Ux=y,又上三角解出x ；三Iterative Methods （迭代法）2n n 22221211n n 1212111b x a x a x a b x a x a x a =+++=+++nn nn 22n 11n 2n n 22221211n n 1212111b x a x a x a b x a x a x a b x a x a x a =+++=+++=+++初始值四 Jacobi Method1.选择初始值2.迭代方程为五Gauss Seidel Method1.迭代方程为00201,,,n x x x 00201,,,n x x x nnk n nn k n k n n k n k nn k k kn n k k a x a x a x a bx a x a x a bx a x a x a b x )()()(1122111222121212111212111--++++++-=++-=++-=k k k kn n k k kn n k k a x a x a bx a x a x a bx )()(1112221121212111212111++++++++-=++-=2.选择初始值 判断是否能用Jacobi Method 或者GaussSeidel Method 的充分条件（绝对对角占优原则）第四章 插值与多项式逼近·第一节 泰勒级数和函数计算一些常用函数的泰勒级数展开：for all x for all x for all x -1 -1for00201,,,nx x x定理4.1（泰勒多项式逼近）设，而是固定值。

如果，则有其中为用来近似的多项式：误差项形如C为x和之间的某个值。

推论4.1 如果为定理4.1给出的N次泰勒多项式，则=其中k=0,1,···，N定理4.2（泰勒级数）设在包含的区间（a , b）中是解析的。

设泰勒多项式趋近于一个极限则f(x)有泰勒级数展开·第二节插值计算假设函数在N+1个点（，），···，（，）处的值已知，其中值在区间上，并满足，可以构造经过这N+1个点的N次多项式，这种构造只需知道和的数值，而不需要高阶导数值。

可在整个区间上用多项式来逼近。

然而，如果需要知道误差函数，则需要知道及其值的范围，即统计和科学分析中经常出现函数只在N+1个点（，）处已知的情况，因此需要一种求在其他点上的近似值的方法。

如果已知值存在显著误差，则应该考虑第5章中的曲线拟合方法。

而如果确知（，）具有高精度，则应该考虑构造经过这些点的多项式函数。

当时，近似值称为“内插值”（interpolated value）；当或时，称为“外插值”（extrapolated value）。

在数值差分、数值积分以及绘制过给定点的曲线的软件算法中，都有用多项式来计算函数的近似值的情况。

·第三节拉格朗日逼近拉格朗日多项式过N+1个点（，），···，（，）的次数最高为N的多项式其中的基于节点（1）的拉格朗日系数多项式。

很容易看出，和不出现在式（1）的右端。

引入乘式表示法，式（1）可写为定理 4.3（拉格朗日多项式逼近）设，且为N+1个节点。

如果，则其中是可以逼近的多项式：误差项形如为区间内的某个值。

定理4.4（等距节点拉格朗日多项式的误差界）设定义在上，其中包含等距节点，并设，及其直到N+1阶导数分别在子区间，和上连续有界，即，对N=1,2,3，有其中对应于N=1,2和3，误差项式具有如下的界：当时有效当时有效当时有效精度与当h趋近于0时，收敛于0 的速度与收敛于0 的速度相同。

用表示，的误差界可表示为当时有效用代替上式中的，表示误差项的界大致为的倍数，即·第四节牛顿多项式牛顿多项式多项式称为具有N个中心的牛顿多项式，其中多项式可由通过递归关系得到。

其最高次项为，次数小于等于N。

定义4.1 函数的差商定义为：构造高次差商的递归公式为定理4.5（牛顿多项式）设，，，是区间内N+1个不同的数，存在唯一的至多N 次的多项式，具有性质其中j=0,1，，N该多项式的牛顿形式为其中 , 。

的差商表推论4.2（牛顿多项式） 设是定理4.5中给出的牛顿多项式，并用来逼近函数，即如果，则对每个,对应地存在内的数，使得误差项形如 第五章 曲线拟合感想：就是给你一堆数据点，求出一条拟合曲线一、 最小二乘曲线 （1） 误差:最大误差：|})({|max )(1k k Nk y x f f E -=≤≤∞平均误差：∑=-=Nkk k y x f Nf E 11|)(|1)( 均方根误差：2/112)|)(|1()(∑=-=Nkk k y x f Nf E（2） 最小二乘拟合线∑∑∑====+Nkk k Nk k N k k y x B x A x 1112)()(∑∑===+Nkk Nk k y NB A x 11)( （3） 最小二乘抛物线拟合∑∑∑∑=====++Nkk k Nk k N k k N k k x y C x B x A x 12121314)()()(∑∑∑∑=====++Nkk k Nk k N k k N k k x y C x B x A x 111213)()()( ∑∑∑====++Nkk Nk k Nk k y NC B x A x 1112)()(（4） 幂函数拟合)/()(121∑∑===Nk M k Nk k Mkx y x A（5） AxCey =的线性化令)ln(,),ln(C B x X y Y ===原方程则化为B AX Y +=二、 样条函数插值（1） 求线性样条函数：)/()(11k k k k k x x y y d --=++)(）(k k k k x x d y x S -+=1+≤≤k k x x x（2） 求三次样条曲线等间距方法： 先求间距h 112--==-=n n x x x x h列方程求解M i 22121)2(64h y y y M M M i i i i i i +++++-=++21-≤≤n i)("i i x s M =n i ≤≤1hy y h M h M x s i i i ik i )(63）(11'-+--=++11-≤≤n i)6/()(1h M M a i i i -=+2/i i M b =6/)2(/)(11h M M h y y c i i i i i +--=++ i i y d =得到三次样条曲线函数：11-≤≤n i端点约束 时用到的 公式 求出系数i i i i i i i i d x x c x x b x x a x s +-+-+-=)()()()(2311-≤≤n i因为太多，不知道以下内容需不需要 非等间距方法： 步骤：1）分别求出所有的k k k u d h ,,k k k x x h -=+11,2,1,0-=N k )(1kkk k h y y d -=+ 1,2,1,0-=N k )(61--=k k k d d u1,2,1-=N k2）看端点约束，列方程组求出k m（1）natural 样条，即已知0）(0"=x S 0）("=N x S ，求方程组：121110)(2u m h m h h =++k k k k k k k k u m h m h h m h =+++++--1111)(2其中2,2-=N k111222)(2------=++N N N N N N u m h h m h（2）紧压(clamped)样条，即已知）(0'x S ）(0'x S ，求方程组：))((3)223(0'0121110x S d u m h m h h --=++ k k k k k k k k u m h m h h m h =+++++--1111)(2其中2,2-=N k))((3)232(1'111222---------=++N N N N N N N N d x S u m h h m h （3）其它情况（包括以上两种情况）可以根据以下三条公式推出k k k k kk k d h m h m x S +--=+63）(1'k k m x S =）("k k k k k k k k u m h m h h m h =++++---1111)(23）根据求出的m 求系数k k y s =0,6)2(11,++-=k k k k k m m h d s22,kk m s =kkk k h m m s 613,-=+1） 最后求出三次样条函数k k k k k k k k y x x s x x s x x s x S +-+-+-=)()()(）(3,22,33, 1+≤≤k k x x x1,2,1,0-=N k数据线性化曲线0111a x a x a x a y m m m m ++++=-- 的正规方程 ∑∑∑∑∑===+=--==++++Nk mk k Nk mk Nk m kNk m km Nk m km x y x a xa xaxa110111112112∑∑∑∑∑=-=-==--=-=++++Nk m k k Nk m kNk m k Nk m km Nk m km x y xa x a xaxa11110111221112∑∑∑∑===--==++++Nk kN k k Nk m km Nk mkm y Na x a xax a10111111第七章 积分公式：[])x (f )x (f 2h)x (f c )x (f c )x (f c dx )x (f 101100i 1i i ba +=+=≈∑⎰=1 Simpson ’s 1/3-RuleSimpson ’s 3/8-Rule3 Composite Trapezoid Rule （其他的几个公式就按照Composite Trapezoid Rule 把1/3公式，3/8公式做多次累加就可以）4 Romberg Integration （利用此式列出倒三角形图案）第九章[])f(x )4f(x )f(x 3h f(x)dx 210b a++=⎰[])x (f )x (f 3)x (f 3)x (f 8h 33a-b h ; L(x)dx f(x)dx 3210b ab a+++==≈⎰⎰[])()(2)2f(x )f(x 2)f(x 2f(x)dx1i1b an n x f x f h++++++=-⎰3, 2, 1,k ;1441,1,1,=--=--+kk j k j k k j I I I常微分方程，形如00)( ; ),(y t y y t f dtdy== 欧拉法（Euler ’s method ）： h y y i i 1φ+=+（为导数，h 是步长） 误差分析：休恩法（Heun ’s method ）：h y t f y y i i i i ),(01+=+Predictor （预测）：h y t f y t f y y i i i i i i 2),(),(0111+++++= Corrector （校正）：（可多步校正）h y t f y y ),( 00001+=h y t f y t f y y 2),(),( 01100011++= h y t f y t f y y 2),(),( 11100021++= …… （h t t i i +=+1） 误差分析：Global discretization error(全局变量): ()()2h O y t y e k k k =-=Local discretization error:（局部变量）()()()311,h O y t h y t y k k k k k =--=∈++φFinal global error(F.G.E.)（最终全局变量）:()()()()2,h O y b y h b y E M =-=中点法（Midpoint method ）：hy t f y y y t f y hy t f y y i i i i i i i i i i i ),(),( ;2),(2/12/112/12/12/12/1++++++++=='+= Runge-Kutta method （龙格库塔方法）：nn i i k a k a k a hy y +++=+=+ 22111 φφ⎪⎪⎪⎩⎪⎪⎪⎨⎧+++=⋯⋯+++++=+=⋯⋯+++==⋯⋯⋯⋯⋯⋯++==+++=+=-----------+1,12,11,1111,122,111,11222122221212311111112122111),(),(),(),( n n n n n n n n n n i n i n i i i i i i n n i i q q q p h k q h k q h k q y h p t f k q q p h k q h k q y h p t f k q p h k q y h p t f k y t f k k a k a k a hy y φφ1a 2a +n a ++ =1Second order Runge-Kutta method （二阶龙格库塔方法）：⎩⎨⎧++==++=+),(),()( 11112122111h k q y h p t f k y t f k hk a k a y y i i i i i i⎪⎩⎪⎨⎧===+2/12/111121221q a p a a a Classical Third-order Runge-Kutta Method （经典三阶龙格库塔方法）： )2,( )21,21( ),(213121h k h k y h t f k h k y h t f k y t f k i i i i i i +-+=++== 3rd-Order Heun Method （三阶休恩）:⎪⎪⎪⎩⎪⎪⎪⎨⎧++=++== )32,32( )31,31( ),(23121h k y h t f k h k y h t f k y t f k i i i i i i Classical 4th-order Runge-Kutta Method:h k k k k y y h k y h t f k h k y h t f k h k y h t f k y t f k i i i i i i i i i i )22(61),()21,21( )21,21( ),(432113423121++++=⎪⎪⎪⎩⎪⎪⎪⎨⎧++=++=++==+System of Two first-order ODEs Euler ’s Method （一阶欧拉常微分方程组）:),,(),,(,2,12,21,2,2,11,11,1⎩⎨⎧+=+=++i i i i i i i i i i y y t hf y y y y t hf y y。