数值分析重要公式最终修改版03
1、Doolittle 分解法
设A 的各阶主子式非奇异,那么
A = LDU = L (DU ) = LU 1 (Doolittle 分解, L为单位下三角阵)
= (LD ) U = L 1U (Crout 分解, U 为单位上三角
阵) 。
例1 用Doolittle 分解法解方程组: ⎪
G G =-(D +L ) -1U ,C =(D +L ) b ,x (0) 为初始向量(矩阵形式)
例题0
构造收敛的Gauss –Seidel 迭代格式说明收敛理由
-1
⎧x 1+2x 2-x 3=3
⎨x 1-x 2+5x 3=0⎪4x +x -2x =2
23⎩1
行变换系数矩阵主对角线元素按行严格占优迭代格式收敛,
(k +1)
x 1=-
解 记
2(k ) 1k 8
x 2-x 3+555
⎛12-1⎫
A = 1-15⎪
,
⎛3⎫
b = 0⎪
设
(k +1) x 2=
1(k +1) 1k 5
x 1-x 3+424
⎝41-2⎪⎭
⎝2⎪⎭
⎛1⎫⎛u A =LU = l ⎪ 11u 12u 13⎫
211 ⎝l ⎪ 31l 321⎭
u 22u ⎪23⎝u ⎪33⎪⎭
由矩阵相等得
⎛1
⎫⎛12-1⎫L = 1
1⎪,
-3
6⎪,从而
⎪ ⎪
U =
⎝47/3
1⎪⎭
⎝-12⎪⎭
由
Ly =b , 解得:⎛ y 1⎫⎪
⎛Ux =y , 解得:
y ⎪= 3⎫;由
-3⎪
2⎪⎝y 3⎪⎭ ⎝-3⎪⎭
⎛ x 1⎫⎛1/4⎫
x ⎪⎪= 3/2⎪ 2⎪⎝x 3⎪⎭ ⎝1/4⎪⎭
(1) Jacobi迭代格式 x (k +1) =G k ) J x (+C ,k =0, 1, 2,
G J =-D -1(L +U ) ,C =D -1b ,x (0) 为初始向
量(矩阵形式)
A=D+L+U例 设 Ax =b 其中
⎛4-1⎫A = -1
4-1⎪,
b =⎛ 3⎫J )
,
⎝
-1
4⎪ 2⎪
试求
⎭
3⎪ρ(G ⎝⎭
ρ(G G ) ,ρ(G S ) (ω=
31
30
) 解:
A =D +L +U ,
⎛⎫,
⎛⎫,
D =
4
4
⎪L =
0 -1
⎪ ⎪⎝
4⎪⎭
⎪⎝
-1
⎪⎭
⎛-1⎫,
G J =-D -1
(L +U ) =
U =
-1⎪ ⎪⎝
0⎪⎭
求 ⎛1x (k +1) (k +1) (k +1)
⎫1, x 2, x 3
10
1⎪ ⎪⎝
10⎪⎭
2 Gauss–Seidel 迭代法
(1)迭代格式
x
(k +1)
=G (k )
G x
+C ,k =0, 1, 2,
x (k +1)
15x (k +1) 3(k +1) 93=-
1+
10x 2+10
(x (0), x (0)(0)T
12, x 3) 任选;k=0,1,2….
例题1:确定
λ 并求代数精度
⎰
4
-4
f (x ) dx =λ1f (-2) +λ2f (0)+λ3f (2)
令f (x ) =1, x , x 2 求 λ
例题2
三次样条函数
s (x )
【0,1】
x 3+2x -1且
s (1)=0, s (2)=1求s (x ) 在【1,2】表达式
设
s (x ) =Ax 3+Bx 2+Cx +D
S 1(0)=S (0)
S ' 1(0)=S (0) S '' 1(0)=S (0) S 1(1)=0求A B C D
例
题
3
梯
形
法
求
初
值
公
式
y 1
n +1=y n +2
h [f (t n , y n ) +f (t n +, y 1n +) ] 1
=y 1
n +
2
h (t n -y n +t n +1-y n +1) 例题4
合曲线
y =ax +b
Φ1=span {1, x }ϕ0(x ) =1,ϕ1(x ) =x
A= A T = AA T = A T
y = A T A ⎡⎣b a ⎤⎦
=A T y b= a= 2散点拟合f (x ) =a a 1
0+
x
例1 已知
试求它的最小二乘拟合曲线(。
解:(1)取直角坐标系,描点,由图可知,这些点位于一条双曲线附近。取
Φ1
3>0,∴σ=5, b =(1, -σ, 0) T
1⎧1⎫
=span ⎨1, ⎬,即ϕ0(x ) =1,ϕ1(x ) =;
x ⎩x ⎭
v =
(ϕ0, ϕ0)
=4,(ϕ0, ϕ1) =(ϕ1, ϕ0) =∑
i =03
3
1x i
a -b T
(0, 2, 1) T H =I -2v 1v 1= =5a -b 2
=1.842857,
(2) 得 HAH
'
1
(ϕ1, ϕ1) =∑2
i =0x i (f , ϕ1) =∑
i =03
3
=1.310408,(
f , ϕ0) =∑y i
i =0
=16,
例题7
判断收敛及收敛速度 ϕ(x )
m +1
y i x i
e k +1=ϕ(s ) -ϕ(k ) =(-1)
ϕm (s -θe k )
m !
e k m 0
=11.542857
(3) 解方程组
4a 0+1. 842857a 1=16⎧
⎨
a 0+1. 310408a 1=11. 542857⎩1. 842857
,a =9. 041247 a =-0. 165433
*
(m )
e k +1ϕ(s ) (m )
lim = 因ϕ(s ) >0所以{x k }有m k →∞e m ! k
阶收敛速度1.Newton 迭代格式
*
1
x k +1=x k -
f (x k ) f '(x k )
,k =0, 1, 2,
ϕ*(x ) =-0. 165433+
例5
设
9. 041247
x
f (x ) =sin x , x ∈[0, π],ρ(x ) =1
x 0为初值,f '(x k ) ≠0
,求它在
令
f (x ) =x 3-x -5
f (1)
f (2)>0
Φ2=span 1, x , x
解
:
{
2
}上的最佳平方逼近多项式。
ϕ0(x ) =1
π
f (1)f (2)
,
f '' (x ) ≥6
,
ϕ1(x ) =x
f ' (x ) ≥2≠0f ' (x ) =3x 2-1≥2 f '' (x ) =6x ≥6 所
以在
ϕ2(x ) =x 2(f , φ0) =⎰sin xdx = (f , φ1) ,(f , φ2) ,
[1, ]2只
有一个实根 x 0=2∈[1,2]
f (2)f '' (2)=1*12=12>0至少平方收敛
例题8
(φ0, φ0) ,(φ0, φ1) =⎰0
解方程组
π
xdx (φ, φ) (φ, φ) (φ, φ)
,02,12,22
angrange 拉格朗日插值多项式
n
n k
i =0i ≠k
L n (x ) =
3. 141593a 0+4. 934802a 110. 335426a 2=2. ⎧
⎪
a 0+10. 335426a 1+24. 352273a 2=3. 141593⎨4. 934802
⎪a 0+24. 352273a 1+61. 203937a 2=5. 869603⎩10. 335426
*⇒a 0=-0. 050454
∑y (∏x
k =0
x -x i 注: n =1时,线性插值公式,
) -x k i
,
或
L 1(x ) =
*
a 1=1. 312215
,
x -x 0x -x 1
y 0+y 1
x 0-x 1x 1-x 0
, a =-0. 417691
*
2
y ≈y 0+
3
*i
y 1-y 0
(x -x 0)
x 1-x 0
ϕ(x ) =∑a p i (x ) =
*
i =0
n =2时,二次插值(或抛物线插值)公式:
L 2(x ) =y 0Newton
例题6
Householder 做正交相似变换化为三对角矩
⎛1 A = 3
4⎝
312
4⎫⎪2⎪1⎪⎭
(x -x 0)(x -x 2) (x -x 0)(x -x 1) (x -x 1)(x -x 2)
+y 1+y 2
(x 0-x 1)(x 0-x 2) (x 1-x 0)(x 1-x 2) (x 2-x 0)(x 2-x 1)
插
值
多
项
式
阵取
s 1=(0,3,-
4) T
P n (x ) =f (x 0) +f [x 0, x 1](x -x 0) +f [x 0, x 1, x 2](x -x 0)(x -x 1) +, +f [x 0,.., x n ](x -x 0)(x -x 1)..(x -x n -1)
c 1=--5
f (x ) =P n +1(x ) =P n (x ) +f ⎡⎣x 0, x 1, ..., x n , x ⎤⎦(x -x 0)(x -x 1)..(x -x n )
插值公式余项(即截断误差)
u 1=s 1-c 1e 2=(0,3,4)T +5(0,1,0) T =(0,8,4)T 2u 1u 1T
H 1=I -T 因为H 1s 1=c 1e 2=(0,-5,0) T
u 1u 1
R n (x =)
⎡f ⎣0
x , 1
,
x . n ⎤⎦. . -x ,
x -, 0x (-x 1) n =x (
x
f (x ) -P n (x )
max f (n +1) (t )
R n (x ) ≤
t ∈I x
A (2)=H 1AH 1=
方法二1)a =(1, 3, 4)
T
(n +1)!
(x -x 0)(x -x 1)..(x -x n )
,
σ=±32+42=±5,
例题9
复化梯形公式计算T 1 T 2 T 4
T =⎰
sin x
dx 0x
13
T m +1-T m
4
m=0
T 1=
b -a
将[a , b ] n 等分,x i =a +ih ,i =0, 1, , n ,h =,
n
在每个子区间上应用梯形公式
时
T 0=
b -a
[f (a ) +f (b ) ]2
m=1,
I =⎰
T 1=
b
a
n -1
h
f (x ) dx ≈[f (a ) +f (b ) +2∑f (x i ) ]=T n
2i =0
1
T 0+h 1f (a +h 1) 2
m=2,
m=3,
b -a
[f (a ) -f (b ) ]2
2
1
T 2=T 1+h 2∑f (a +(2i -1) h 2)
2i =1
b -a ⎡b -a ⎤
T 2=f (a ) +2f () +f (b ) ⎥⎢4⎣2⎦
4
1
T 3=T 2+h 3∑f (a +(2i -1) h 3)
2i =1
m=4,
1-0 ⎡T 4=f (0)+f (1)+2[f (0.25)+f (0.5)+f (0.75)]⎤⎣⎦8
得复化梯形公式:
8
1
T 4=T 3+h 4∑f (a +(2i -1) h 4)
2i =1
I =⎰
b
a
Euler 法求初值 n -1
例题11 h
f (x ) dx ≈[f (a ) +f (b ) +2∑f (x i ) ]=T n ,
2原始Euler 法y n +1=y n +hf (t n , y n ) =y n +ht n -hy n 局i =0
复化梯形公式的截断误差:
R T =-
h (b -a ) h
''f (ξ) =-f ''(ξ) ,∑12k =012
3n -12
h 2''
y (t n ) +o (h 3) 部截断误差R n +1=2
ξ∈(x k , x k +1) (3)
复化抛物线公式:
向后Euler 法
y n +1=y n +hf (x n +1, y n +1) =
复化抛物线公式的截断误差:
h 2
R n +1=y ''(t n ) +o (h 3) n -1n -1
h 2≈[f (a ) +f (b ) +2∑f (x i ) +4∑f (x 1) ]=S n ,
i +*6i =0i =02p 求最佳逼近元素的步骤:
a
5
R (n ) =I -S =-(b -a ) f
2n
2880n 4
(4)
I =⎰f (x ) dx
b
1
(y n +hx n +1) 截断误差1-h
(ξ) ,
span {1, x } 所以ϕ0(x ) =1 ϕ1(x ) =x (ϕ0, ϕ0) =1 (ϕ0, ϕ1) = 1/2 (ϕ1, ϕ1) =1/3 (ϕ0, f ) =2/3 (ϕ1, f ) =2/5⎡1
⎢⎢⎢1⎢2⎣
1⎤⎡2⎤
⎢3⎥⎥c ⎡⎤20
=⎢⎥⎥⎢⎥1⎥⎣c 1⎦⎢2⎥⎢⎥⎥3⎦⎣5⎦
例1 若用复化梯形公式和复化抛物线公式计算积分间要等分多少才能保证有5位有效数字?
解 由余项公式
(n )
R 1(
⎰0e dx ,问积分区
1x
(2)求解方程组(4)
(b -a ) 3(b -a ) 5(n )
f ) =-f ''(ξ), R 2(f ) =-f
12n 22880n 4
(4)
(ξ), ξ∈(a , b )
***T
得:a *=(a 0, a 1, , a n ) p *=c 0+c 1x
因为 f (x ) = f '(x ) = … = e x , b – a = 1 故
(3)将a *代入(1)式即得
p *=
1
|
R 1(n )
e e (n )
|≤, R (f ) ≤ 或 2
12n 22880n 4
– 4
4
1/2
44
+x 155
1
δ=(f -*p , =
f ) (-f , *f )
p
由 | R | ≤ 10/2, 得 n ≥ (e ⨯10/6) =68 (梯形公式),
44
=⎰xdx -⎰(+x 00155
或 n ≥ (e ⨯104/1440)1/4 =2.1(抛物线公式, 因区间是2n , 实际上还要乘以2, 故6等分即可).
例题10
3
Simpson 公式
逐次分半复化梯形公式
⎰
1
1
dx 截断误差不超过x
⎰
b
a
f (x dx ≈
b -a ⎡a +b ⎤
f a +) f +f b ⎥截断误⎢6⎣2⎦
(
a
10-2步长 h m =b - m
2
2
1
T m =T m -1+h m ∑f (a +(2i -1) h m ),(m =1,2,.....)
2i =1
m -1
5
(b -a ) 差R 2=-f (4)(η) η∈(a , b ) 3次代数精度 2880
梯形公式⎰f (x ) dx ≈
a
b
b -a
[f (a ) +f (b ) ]截断误差2
(b -a ) 3
R 1=-f ''(η) η∈(a , b ) 1次代数精度
12