h(1 f ( xn1, y( xn1 )) f ( xn , y( xn )) 1 f ( xn1, y( xn1 )))
y( xn1 ) ( y( xn ) y( xn1 ))
h(1 y( xn1 ) y( xn ) 1 y( xn1 ))
另一种迭代格式
xk (1 lnxk ) xk 1 xk 1
0 3.000000000 1 3.147918433
2 3.146193441 3 3.146193221
五
常微分方程数值解
局部截断误差 重要概念 方法精度 重要构造方法 单步法 线性多步法 差分构造 积分构造 泰勒展式构造
1
I BGS
2 0 0 0 a 1 1 1 0 0 0 2 1 a 1 0 0 0
1
2 0 a 1 1 0 0 2 2 a 0 0 0 2 a 1 1 2 2 a
T
cos sin 令 R 使得 sin cos
2
f x x

2
2 2
dx 4 A B C
整理得:
AC
2A B 4 8 2 A 3
f x x
4
64 4 4 x dx A C 2 5
2 4
4
32 A 5 8 2 32 3 5
12
5
10 A 9
并推导其局部截断误差主项。
解
y( xn1 ) y( xn h)
2 3 4 h h h (4) 5 y( xn ) hy ( xn ) y ( xn ) y ( xn ) y ( xn ) O(h ) 2 6 24
y( xn1 ) y( xn h)
预备知识
范数 内积 正交多项式 最佳一致逼近
函数逼近
最佳平方逼近 最小二乘拟合 函数逼近方法 三角函数逼近 帕德逼近
例1 求g(x)=x 在P1[0,1]中的最佳平方逼近元
解法一
这是C[0,1]上的最佳平方逼近问题. 取０＝１, １＝x, P1[0,1]＝span{1,x} 记 p1(x)=a０＋a１x (０,0)=1，(０,1)=1/2， (1,1)=1/3 (０,g)=2/3， (1,g)=2/5. 所以，关于a０，a１为未知数的法方程组为
令 得
I BGS 0 1 3 2a 1 0 2 2
2a 1
1 1 a 2 2
四
非线性方程求根
二分法 不动点迭代法及收敛性理论
求根法 牛顿迭代法 弦截法 插值型迭代 抛物线法
例5 用一般迭代法求方程x-lnx＝2在区间(2, )内的根， 要求|xk-xk-1|/|xk|<=10-8 解 令f(x)=x-lnx-2 f(2)<0, f(4)>0,故方程在(2,4)内至少有一个根 又
1 f ( x ) 1 0 x ∈(2, ) x
因此f(x)=0在(2, )内仅有一个根x* 将方程化为等价方程：x＝2＋lnx
1 g ( x ) 2 ln x | g( x ) || | 0.5 x ∈(2, 4) x
因此， x0(2, ), xk+1＝2＋lnxk产生的序列 xk 收敛于x* 取初值x0＝3.0,计算结果如下： k xi 0 3.000000000 5 3.145702209 10 3.146191628 1 3.098612289 6 3.146037143 11 3.146192714 2 3.130954362 7 3.146143611 12 3.146193060 3 3.141337866 8 3.146177452 13 3.146193169 4 3.144648781 9 3.146188209 14令: 1 1 0 1 0 1 1 2 2 1 1 3 1 1 得: 8 8 2
1 1 1 0 此时: 6 6 2 2
1 1 1 1 0 24 24 6 6 48
所以当:
1 2
3 1 8
1 1 8
1 3 1 yn1 ( yn yn1 ) h( f n1 f n f n1 ) 2 8 8
为三阶多步公式.
1 4 (4) h y ( xn ) 局部截断误差主项为: 48
六
特 征 值 及 特 征 向 量 解 法
(1) 线性方程组
2 x ax x b 1 2 3 1 x1 x2 2 x3 b2 x1 ax2 x3 b3
Jacobi 迭代
b1 k 1 a 1 (k ) (k ) x2 x3 x1 2 2 2 k 1 k (k ) x x 2 x 2 1 3 b2 k 1 k (k ) x3 x1 ax2 b3 (2) 线性方程组
f ( xn1 , y( xn1 )) y( xn1 ) y( xn h)
2 3 h h (4) 4 y ( xn ) hy ( xn ) y ( xn ) y ( xn ) O(h ) 2 6
线性多步公式局部截断误差
R xn1 y( xn1 ) ( y( xn ) y( xn1 ))
三
线性方程组
Gauss消去法 矩阵三角分解法 直接法 追赶法 向量和矩阵范数 矩阵条件数
三
线性方程组
迭代格式
基本概念 收敛条件 雅可比迭代
迭代法
高斯-塞德尔迭代 SOR迭代
迭代收敛速度
例3
设线性方程组
Ax b 的系数矩阵为:
2 a 1 1 1 2 1 a 1
解
(1)写出Jacobi 迭代法的迭代格式 (2)确定a的取值范围，使方程组对 应的Gauss-Seidel迭代收敛。
2 3 4 h h h y( xn ) hy( xn ) y( xn ) y( xn ) y (4) ( xn ) O(h5 ) 2 6 24
y( xn )
2 3 4 h h h [ y( xn ) hy( xn ) y( xn ) y( xn ) y (4) ( xn ) O(h5 )] 2 6 24
计算方法复习
典型概念例题
零
绪论
分类 误 差 及 算 法 舍入 截断 绝对 度量 相对 有效数字 一元函数 算法 传播 n元函数
误差
一
插值与逼近
工具
差商 差分 插值基函数 存在唯一性 误差估计 插值公式 Hermite插值 分段线性 分段三次Hermite插值 三次样条插值
插值法
多项式插值
分段多项式 插值
2 3
(1 2 ) y( xn )
(1 1 1 1 )hy( xn ) 1 2 ( 1 1 )h y( xn ) 2 2 1 1 3 1 ( )h y( x )
6
24 24 6 6
n 6 2 2 1 1 4 (4) 1 ( )h y ( xn )
16 B 9
10 C 9
5 5
f x x f x x
2 6
5 6

2
2
x dx 0 A C
5
128 8 12 6 6 2 x dx 7 A C 2 3 52
所以代数精确度为5次.
2
因为代数精确度为2×3=5次,是高斯型求积公式.
2 3 h h (4) 4 h1[ y ( xn ) hy ( xn ) y ( xn ) y ( xn ) O(h )] 2 6
hy( xn )
h1[ y( xn ) hy( xn ) h y( xn ) h y (4) ( xn ) O(h4 )] 2 6
a 20.1007
dI 2 (at s )t 2 i i i 2a ti 2 ti si da i 1 i 1 i 1
n
n
n
所求运动方程为: 20.1007t s 0
二
数值积分
数值求积思想 代数精度 插值型求积公式 收敛及稳定性
梯形公式 辛普森公式
基本概念 数 值 积 分 N-C公式
特征值特征向量
特征值特征向量正交相似 反射 变换 平面旋转 QR分解 幂法 迭代法 反幂法
重要概念
雅可比法
变换法 QR法
先看一个简单的例子. a11 a12 是二阶实对称矩阵, 即a =a , 其特 设 A 21 12
a21 a22
征值为λ1, λ2.
1 R AR 2
1 2 a0 2 a1 3 1 1 2 a0 a1 3 5 2
解得a０=4/15，a１＝4/5 即p1(x)=4/5x+4/15 为P1[0,1]中对g(x)= x的最佳平方逼近元.
例1
观测物体过原点的直线运动,得到所示数据, 求运动方程. 0 0.9 10 1.9 30 3.0 50 3.9 80 5.0 110
时间t/s
距离s/m 0 解
作直线模型: at+s=0 n为观测点数
定义残差向量:
V (at1 s1, at2 s2 ,
2
2
, atn sn )T
I (a) V
(ati si )
i 1
n
2
dI 2 53.63a 2 1078 所以: da 令: dI 2 53.63a 2 1078 0 da
2 3 4 h h h y( xn ) hy( xn ) y( xn ) y( xn ) y (4) ( xn ) O(h5 ) 2 6 24