平方根法追赶法
§5 平方根法 一、教学设计
1．教学内容：对称正定矩阵的Cholesky 分解法、三对角线矩阵分解的追赶法。
2．重点难点：Cholesky 分解法、追赶法。
3．教学目标：掌握对称正定矩阵的Cholesky 分解的计算过程，掌握三对角线矩阵分解的追赶法。 4．教学方法：讲授与讨论。
二、教学过程 §5 平方根法
在工程计算中，常遇到求解解对称再正定线性方程组问题，如应用有限元法解结构力学问题，应用差分方法解椭圆型偏微分方程等，最后都归结为求解系数矩阵为对称正定阵的线性方程组。根据系数矩阵的特殊性，是否有更好的解决方案（在存贮空间上的好处是显而易见的），算法上是否有所简化？
5－0对称正定矩阵及性质复习
定义：设n n R A ?∈，如果A 满足条件 （1）A A T =；（2）对任意非零向量n R ∈x ，有0>x x A T ，则称A 为对称正定矩阵。
定理1 （对称正定矩阵的性质）如果n n R A ?∈为对称正定矩阵，则
（1）A 为非奇异阵，且1-A 亦是对称正定阵；
（2）记k A 为A 的顺序主子阵，则k A 亦是对称正定阵),,2,1(n k =；
（3）A 的特征值),,2,1(0)(n i A i =>λ；
（4）A 的顺序主子式都大于零，即),,2,1(0)det(n k A k =>。
定理2 设n n R A ?∈为对称矩阵（判据）
（1）若A 的特征值),,2,1(0)(n i A i =>λ，则A 为对称正定矩阵； （2）若A 的顺序主子式都大于零，即),,2,1(0)det(n k A k =>，则A 为对称正定阵。
5－1 对称正定矩阵的三角分解
由前述定理 3.1知，若n 阶方阵A 的顺序主子式)1,,2,1
()d e t (-=n k A k 均不为零，则A 有唯一的三角分解LU A =，其中L 为单位下三角阵，U 为上三角阵。n 阶对称正定阵A 的顺序主子式都大于零，当然有LU 分解，进一步地，此时U L ,之间有什么关系？这对解方程组有用处。由LU A L U A T T T ===及分解的唯一性，想到若U 的主对角元素皆为1，就有可能获得一些结果。为此，再将U 分解
DR
u u u u u
u u u u u u u u u u U n n nn nn n n ≡???
??????
????????
??????
???
?
?
?
?=?????????
??
?=111222*********
11222
11211
易知),,2,1(0n i u ii => （用k k k U L A ,,分别记矩阵U L A ,,的k 阶
顺序主子阵，容易验证k k k U L A =于是
ii k
i i ii
k i k k k k k k u a U U L U L A ∏∏
=======1
)(1det det det )det(det ）
于是LDR LU A ==，所以
A DR L LU DL R LDR A T T T T =====)()()(，
即 )()(DR L DL R A T T ==
由分解的唯一性知：T R L =，R L T =，于是T LDL A = 自然地，若记
T nn D u u u D )(21
22
1121
=?
??????????
??
?=
则T T
T
L L LD LD L D LD A 1121
2121
21))((≡==，其中1L 是对角元为正数
的下三角阵。
定理5.1 （Cholesky 分解）
设A 是n 阶对称正定矩阵，则存在唯一的对角线元素全是正数的下三角形矩阵L ，使得T LL A =。称这种分解为Cholesky 分解。
有了这种分解后，解线性方程组b x =A 等价于解以下两个三角方程组b y =L ，y x =T L ，这将带来一些简便。下面讨论如何计算L 的元素。
5－2 平方根法
设n 阶对称正定矩阵A 有如下Cholesky 分解
T
nn ni ii nj ij jj n i j n i j nn ni
nj
n n ii
ij
i i jj
j j nn ni
nj n n in ii
ij
i i jn ji
jj
j j n i
j n i
j
LL l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l a a a a a a a a a a a a a a a a a a a a a a a a a =???
?
?
?
?
?
?
?
??
?
????????????
?????????????
?
?????????????=??
?
??????????
?????????????
222221112111
21
2
12122
2111212
121222222111112
11 比较等式两边的第1列对应元素，得到
11111111211121111111,,,,,n n i i a l l a l l a l l a l l ====
于是得到L 的第1列元素
),,3,2(,
/,
)(11112/11111n i l a l a l i i ===
比较等式两边的第2列（对角元及其以下）对应元素，得到 222221122222112222222121,,,,n n n i i i a l l l l a l l l l a l l l l =+=+=+ 于是 得到L 的第2列元素
),,4,3(,
,
)
(22
21
1222
/12212222n i l l l a l l a l i i i =-=-=
一般地，比较等式两边的第j 列（对角元以下）对应元素，得到
ij jj ij j j j i j i j i jj jj jj j j j j a l l l l l l l l a l l l l l l =++++=+++--1,1,22112211, 于是得到L 的第),,2,1(n j j =列元素
,)(1
1
2
/12∑-=-=j k jk
jj jj l a l 5.8
),,2,1(,1
1
n j j i l l l a l jj
j k jk
ik ij ij ++=-=
∑-= 5.9
电算时，可只存A 的下三角部分于二维数组A 中，且注意到当计算出L 的某一列元素后，A 的相应列元素在后续计算过程中不再起作用，故可将求得的L 的元素保存在A 的相应位置上。假设已得到L 的前1-j 列元素，从下图中注意观察L 的第j 列元素ij l 的计算过程。
??
??????????
?
??
?????-nn ni
nj
j n n ii
a a a l l a l l l
1
,1
11
完成矩阵A 的Cholesky 分解后，解b x =A ，化为解以下两个
三角形方程组
（1）b y =L ， ???
??
??=-==∑-=)
,,3,2(/1111
11n i l y l b y l b y ii i j j ij i i （5.10）
（2）y x =T L ， ???
??
??--=-==∑+=)1,2,,2,1(/1 n n i l x l y x l y x ii n i j j ji i i
nn
n n
（5.11）
称由公式（5.8）~（5.11）解对称正定线性方程组的方法为平方根法。
例：用平方根法解对称正定方程组
????
??????=????????????????????--0102/74/1114/114/171114
321x x x A= 4 -1 1
-1 17/4 11/4 1 11/4 7/2 计算L 的第1列
2 0 0 -1/2 17/4 0 1/2 11/4 7/2 计算L 的第2列
2 0 0 -1/2 2 0 1/2 3/2 7/2 计算L 的第3列
2 0 0 -1/2 2 0 1/2 3/2 1 Ly=b
2 0 0 0 -1/2 2 0 1 1/2 3/2 1 0
y=
0 1/2 -3/4 L'x=y
2 -1/2 1/2 0 0 2 3/2 1/2 0 0 1 -3/4 x=
25/64 13/16
-3/4
5－3 平方根法的数值稳定性
由（5.8）式知：),2,1(,
12n j a l jj j
k jk ==∑= 于是，),,2,1;,,2,1(},
{max 12j k n j a a l jj n
j jj jk ==≤≤≤≤ 上式说明在不选主元的平方根法中，分解过程中L 的元素有界，或者说在分解过程中产生的L 的元素jk l 的数量级不会增长，且),,2,1(,0n j l jj =>，再由（5.9）式知jj l 的值不会太小，否则ij l 的值将会很大，而这与上面的分析“L 的元素有界”相矛盾。可见，平方根法是数值稳定的。
为避免求平方根，还可将算法改进。(采用分解式)T LDL A =
§6 追赶法
在一些实际问题中，例如用差分法解二阶线性常微分方程边值问题，解热传导方程以及船体数学放样中建立三次样条函数等，都会要求解系数矩阵为对角占优的三对角线方程组
?????????
???????
??????????????????=????????????????????????????????????
???????????????????????????????
?--+---+----n n n i i i n n n i i i n n
n n n i i
i
f f f f f f f f f x x x x x x x x x b a c b a c b a c b a c b 12113211211321111
2
2
211
简记为f x =A 。其中A 满足下列条件：（称为对角占优的三对角线矩阵） （1）011>>c b
（2）)1,,3,2,0(,-=≠+≥n i c a c a b i i i i i （3）0>>n n a b
对于这个方程组，或许可以用前面介绍的Gauss 消去法、Doolittle 分解法等方法求解，但考虑到其系数矩阵的特殊性，我们设法建立更有效的快速算法――追赶法，它具有计算少，方法简单，算法稳定等特点。若能将A 进行Doolittle 分解A ＝LU ，那么此时L ，U 有什么特点呢？先提一下严格对角占优阵的性质。（我们讨论的仅是对角占优阵，用不到这些结论，仅作为阅读资料）
定理 设A 为n 阶方阵，且严格（行）对角占优阵，则A 为非奇异阵，且其各阶顺序主子式均不为0。 证明：（反证法）假设A 为奇异阵，则存在非零向量),,,(21n c c c =c 使得0=c A ，即
),,2,1(,
01
n i c a n
j j ij ==∑=
设0max 1>=≤≤j n
j r c c
则有r
n
r
j j rj n r
j j j rj r
rr c a c a c a )(||11∑∑≠=≠=≤=，两边约去r c 后，与题设（行）严
格对角占优矛盾！
我们这里讨论的对角占优的三对线矩阵不是严格对角占优阵，但由于其特殊的三对角，我们还是可以直接用归纳法很容易地证明下面定理
定理 设n 阶三对角阵A 满足条件（1）（2）（3），则其各阶顺序主子式均不等于0。从而可以有唯一分解A ＝LU 。
用Crout 法进行分解，易得上述定理中的L 是二对角线的下三角矩阵，U 是二对角线的上三角矩阵。对于一般的n 阶矩阵，可以通过把它们具体求出来加以验证（所谓构造法）。L 的对角元的为1时，属于Doolittle 分解，U 的对角元为1，属于Crout 分解。下面采用Crout 分解（有何好处？回代过程较简单），有
??
??????????????
?????????????????
?---n n
n n n i i
i
b a
c b a c b a c b a c b 111
2
2
211
??????????????????????????n n i i αγαγαγα 221??
?
??
?
???????
??
?
??
?
???
?
???
?
?---11
1
1111221
n i i i ββββββ
逐行比较第1行：11111,βαα==c b ，
i 行 i
列 i -1行 i 列
第2行，直到第i 行，222212222,,βααβγγ=+==c b a 比较位于)1,(),,(),1,(+-i i i i i i 处的元素得：
???
??-====+===-)
1,,2,1(),,3,2(),,3,2(111n i c b n i b n i a i i i
i i i i i i β
αααβγγ
从而解出
?????==-===-==-)
,,3,2()1,2,1(/)
,,3,2(,1
11n i a
n i c n i a b b i i
i
i i i i i i γαββαα （6.6）
i γ正好已处于i a 的位置上，故只需计算i i βα,，其次序为
n n n αβαβαβα→→→→→→→--112211
上述过程被称为“追”的过程。求得L ，U 后，解f x =A ，化
为解以下两个三角形方程组 （1）f y =L ，即
??
??
?
???
???
?
??????????????=????????????????????????????????????????????????????----n n i i n n i i n n i i f f f f f f y y y y y y a a a 11211121221 αααα
??
?==+=-)
,,3,2(11
11n i f y y a f y i i i i i αα 得
??
?
??=-==-)
,,3,2(/1
111n i y a f y f y i i i i i αα （6.8）
（2）y x =U ，
??
????????
???
???????????????=?????????????????
???
???????????????????????????????????
?-+--+--+-n n i i i n n i i i n i i
i y y y y y y y x x x x x x x 111211112111
1
2
111
1
11
ββββββ
即
??
?=-==++n
n i
i i i y x n i y x x )
1,,2,1(1 β
解得
??
?--=-==+)
1,2,,2,1(1
n n i x y x y x i i i i n n β （6.10）
由公式（6.6）（6.8）（6.10）求解方程组的方法称为追赶法。 注意：实际上，只要算出1,-i i y α，就可以算i y 了，而不必等求出所有的i i βα,后再求i y ，所以可将计算i y 归于“追”的过程，计算次序为
n
n n n n y y y y →→→→→→→→→→→---αβαβαβα111222111
存贮空间：可以用四个一维数组存放方程组的三条对角线元素和右端项，按行仔细分析计算的过程得知，产生的i i i y ,,βα可依次覆盖i i i f c b ,,，最后，i x 覆盖i y
例：用追赶法解线性方程组。解为（21/38，-25/38，33/38，-11/38）
?
????
???????=????????????????????????010131132132134321x x x x 解：首先判断系数矩阵是一个对角占优的三对角阵。应用追
赶法求解得。
(A f)=
3 1 0 0 1 2 3 1 0 0 0 2 3 1 1 0 0 1 3 0 计算第1行
3 1/3 0 0 1/3 2 3 1 0 0 0 2 3 1 1 0 0 1 3 0 计算第2行
3 1/3 0 0 1/3 2 7/3 3/7 0 -2/7 0 2 3 1 1 0 0 1 3 0 计算第3行
3 1/3 0 0 1/3 2 7/3 3/7 0 -2/7 0 2 15/7 7/15 11/15 0 0 1 3 0 计算第4行
3 1/3 0 0 1/3 2 7/3 3/7 0 -2/7 0 2 15/7 7/15 11/15 0 0 1 38/15 -11/38 Ux=y
1 1/3 0 0 1/3 0 1 3/7 0 -2/7 0 0 1 7/15 11/15 0 0 0 1 -11/38
稳定性分析：对于对角占优的三对角阵，归纳法不难证明，追赶法过程中产生的i i βα,满足：（1）)1,,2,1(,10-=< n n n n n i i i i i i a b a b n i a b a b c +≤≤-<-=+≤≤-≤<αα0),1,,2,1(0 证明：显然101 1 1<= i i i i i i i i i i c a b a b a b ≥->-≥-=--11ββα 则有10<= i i c αβ， 至于（2）显然。 目录 摘要 (2) 0 引言 (3) 1 预备知识 (3) 1.1 T LL分解理论 (3) 1.2 Cholesky分解法 (4) 1.3 算法描述 (5) 2改进的平方根法 (6) 3T LDL分解算法描述 (7) 4 应用举例 (8) 5 程序实现 (10) 5.1 程序码源 (10) 5.2 实例计算 (12) 6 结束语 (13) 参考文献 (14) 致谢 (15) 改进的平方根法及其程序实现 摘要: 针对对称正定方程组的解法,本文先对Cholesky分解法进行了分析研究,在此基础上给出了改进的平方根法(即T LDL分解法),此方法有效地避免了原平方根法开方运算所带来的误差和不便,并通过算法描述、实例计算,用C程序实现了T LDL分解,进一步提高了矩阵运算的速度和精度. 关键词: 对称正定矩阵, 平方根法, T LDL分解, 算法 Improved Methods of Square Root and Realization of Its Program Abstract: Aiming at studying solutions of symmetric positive definition matrix in linear equations. Initially, the text has conducted a series of analyses and researches towards decomposition proposed by Cholesky. Then based on theses researches and analyses, it offers the improved methods of square–root (also called T LDL decom- position), which effectively avoid some errors and inconvenience brought by the process of extracting root. At the same time, it achieves the T LDL decomposition through the means of algorithm description, example calculation as well as applicat- ion of C program, further enhancing the speed and accuracy in matrix operation. Key words: Symmetric positive definition matrix, method of square root, T LDL decomposition, algorithm 0 引言 很多工程中的科学计算,例如应用有限元法解结构力学问题时,最后往往归结为求解系数矩阵为对称正定方程组解的问题.由于对称正定矩阵各阶顺序主 在求解线性方程组时,直接解法有顺序高斯消元法、列主元高斯消元法、全主元高斯消元法、高斯约当消元法、消元形式的追赶法、LU分解法、矩阵形式的追赶法，当我们遇到对称正定线性方程组时，我们就要用到平方根法(对称LLT 分解法)来求解，为了熟悉和熟练运用平方根法求解线性方程组，下面对运用平方根法求解线性方程组进行解析。 一、运用平方根法求解线性方程组涉及到的定理及定义 我们在运用平方根法求解线性方程组时，要判定线性方程组Ax=b的系数矩阵A是否是对称正定矩阵，那么我们就要了解正定矩阵的性质和如下定理及定义： 1、由线性代数知，正定矩阵具有如下性质： 1) 正定矩阵A是非奇异的 2) 正定矩阵A的任一主子矩阵也必为正定矩阵 3) 正定矩阵A的主对角元素均为正数 4) 正定矩阵 A的特征值均大于零 5) 正定矩阵A的行列式必为正数 定义一线性方程组Ax=b的系数矩阵A是对称正定矩阵，那么Ax=b是对称正定线性方程组。 定义二如果方阵A满足A=AT，那么A是对称阵。 2.1.4 平方根法和改进的平方根法 如果A是n阶对称矩阵，由定理2还可得如下分解定理： 定理2 若A为n阶对称矩阵，且A的各阶顺序主子式都不为零，则A可惟一分解为：A＝LDLT，其中L为单位下三角阵，D为对角阵。 证明因为A的各阶顺序主子式都不为零，所以A可惟一分解为：A＝LU 因为，所以可将 U分解为： 其中 D为对角矩阵，U1为单位上三角阵．于是：A＝LDU1＝L(DU1) 因为A为对称矩阵，所以，A＝AT＝U1TDTLT＝U1T(DLT)，由 A的 LU分解的惟一性即得：L＝U1T，即U1＝LT，故A＝LDLT。 工程技术中的许多实际问题所归结出的线性方程组，其系数矩阵常有对称正定性，对于具有此类特殊性质的系数矩阵，利用矩阵的三角分解法求解是一种较好的有效方法，这就是对称正定矩阵方程组的平方根法及改进的平方根法，这种方法目前在计算机上已被广泛应用。 定理3 对称矩阵A为正定的充分必要条件是A的各阶顺序主子式大于零。 2 对称正定矩阵的三角分解 定理 (Cholesky分解)设A为n阶对称正定矩阵，则存在惟一的主对角线元素都是正数的下三角阵L，使得：A＝LLT。 分解式A＝LLT称为正定矩阵的Cholesky分解，利用Cholesky分解来求解系数矩阵为对称正定矩阵的方程组AX＝b的方法称为平方根法。 设A为4阶对称正定矩阵，则由定理 4知，A＝LLT，即： 将右端矩阵相乘，并令两端矩阵的元素相等，于是不难算得矩阵L的元素的计算公式为： 一败涂地、 解线性方程组（线性矩阵方 程） 解线性方程组是科学计算中最常见的问题。所说的“最常见”有两方面的含义： １）问题的本身是求解线性方程组； ２）许多问题的求解需要或归结为线性方程组的求解。 关于线性方程组 B A x B Ax 1-=?= （１） 其求解方法有两类： １） 直接法：高斯消去法（Gaussian Elimination ）； ２） 间接法：各种迭代法（Iteration ）。 １、高斯消去法 １） 引例 考虑如下（梯形）线性方程组： ()?? ???==+==+-=?????? ??=????? ????????????--??????==-=+-5.01 41315 .3221122004301211214322332321321332321x x x x x x x x x x x x x x x 高斯消去法的求解思路：把一般的线性方程组（１）化成（上或下）梯形的形式。 ２）高斯消去法——示例 考虑如下线性方程组： ???? ? ??-=????? ????????????---??????=++-=-+-=+-306015129101.2001.221113*********.2001.221321321321321x x x x x x x x x x x x １） 第一个方程的两端乘 1 2 加到第二个方程的两端，第一个方程的两端乘 －１加到第三个方程的两端，得 ???? ? ??-=????? ????????????--3060031110001.0001.0011 1321x x x ２） 第二个方程的两端乘001 .010 - 加到第三个方程的两端，得 ???? ? ??-=????? ????????????--60600311010001.0001.0011 1321x x x ３）从上述方程组的第三个方程依此求解，得 ()??? ??==+-==+-=600300001.031000 2401 13 32321x x x x x x ３）高斯消去法的不足及其改进——高斯（全、列）主元素消去法 在上例中，由于建模、计算等原因，系数2.001而产生0.0005的误差，实际求解的方程组为 ????? ??-=????? ????????????---306015129101.20005.22111321x x x ?????===?70.4509.30142.2565 3 2 1x x x 注：数值稳定的算法 高斯列主元素消去法就是在消元的每一步选取（列）主元素—一列中绝对值最大的元取做主元素，高斯列主元素消去法是数值稳定的方法。 列主元素消去法的基本思想：在每轮消元之前，选列主元素（绝对值最大的元素）,使乘数1≤ik l . 列主元素消去法的步骤：设已经完成第1步到第1-k 步的按列选主元、交换两行、消元计算，得到矩阵 §5 平方根法 一、教学设计 1．教学内容：对称正定矩阵的Cholesky 分解法、三对角线矩阵分解的追赶法。 2．重点难点：Cholesky 分解法、追赶法。 3．教学目标：掌握对称正定矩阵的Cholesky 分解的计算过程，掌握三对角线矩阵分解的追赶法。 4．教学方法：讲授与讨论。 二、教学过程 §5 平方根法 在工程计算中，常遇到求解解对称再正定线性方程组问题，如应用有限元法解结构力学问题，应用差分方法解椭圆型偏微分方程等，最后都归结为求解系数矩阵为对称正定阵的线性方程组。根据系数矩阵的特殊性，是否有更好的解决方案（在存贮空间上的好处是显而易见的），算法上是否有所简化？ 5－0对称正定矩阵及性质复习 定义：设n n R A ?∈，如果A 满足条件 （1）A A T =；（2）对任意非零向量n R ∈x ，有0>x x A T ，则称A 为对称正定矩阵。 定理1 （对称正定矩阵的性质）如果n n R A ?∈为对称正定矩阵，则 （1）A 为非奇异阵，且1-A 亦是对称正定阵； （2）记k A 为A 的顺序主子阵，则k A 亦是对称正定阵),,2,1(n k =； （3）A 的特征值),,2,1(0)(n i A i =>λ； （4）A 的顺序主子式都大于零，即),,2,1(0)det(n k A k =>。 定理2 设n n R A ?∈为对称矩阵（判据） （1）若A 的特征值),,2,1(0)(n i A i =>λ，则A 为对称正定矩阵； （2）若A 的顺序主子式都大于零，即),,2,1(0)det(n k A k =>，则A 为对称正定阵。 5－1 对称正定矩阵的三角分解 由前述定理 3.1知，若n 阶方阵A 的顺序主子式)1,,2,1 ()d e t (-=n k A k 均不为零，则A 有唯一的三角分解LU A =，其中L 为单位下三角阵，U 为上三角阵。n 阶对称正定阵A 的顺序主子式都大于零，当然有LU 分解，进一步地，此时U L ,之间有什么关系？这对解方程组有用处。由LU A L U A T T T ===及分解的唯一性，想到若U 的主对角元素皆为1，就有可能获得一些结果。为此，再将U 分解 DR u u u u u u u u u u u u u u u U n n nn nn n n ≡??? ?????? ???????? ?????? ??? ? ? ? ?=????????? ?? ?=111222********* 11222 11211 易知),,2,1(0n i u ii => （用k k k U L A ,,分别记矩阵U L A ,,的k 阶 顺序主子阵，容易验证k k k U L A =于是 ii k i i ii k i k k k k k k u a U U L U L A ∏∏ =======1 )(1det det det )det(det ） 于是LDR LU A ==，所以 A DR L LU DL R LDR A T T T T =====)()()(， 即 )()(DR L DL R A T T == 由分解的唯一性知：T R L =，R L T =，于是T LDL A = 自然地，若记 数值分析课后习题部分参考答案 Chapter 1 （P10）5. 求2的近似值* x ，使其相对误差不超过%1.0。 解： 4.12=。 设* x 有n 位有效数字，则n x e -??≤10 105.0|)(|* 。 从而，1 105.0|)(|1* n r x e -?≤。 故，若%1.010 5.01≤?-n ，则满足要求。 解之得，4≥n 。414.1* =x 。 （P10）7. 正方形的边长约cm 100，问测量边长时误差应多大，才能保证面积的误差不超过12 cm 。 解：设边长为a ，则cm a 100≈。 设测量边长时的绝对误差为e ，由误差在数值计算的传播，这时得到的面积的绝对误差有如下估计:e ??≈1002。按测量要求，1|1002|≤??e 解得，2 105.0||-?≤e 。 Chapter 2 （P47）5. 用三角分解法求下列矩阵的逆矩阵： ???? ? ??--=011012111A 。 解：设()γβα=-1 A 。分别求如下线性方程组： ????? ??=001αA ，????? ??=010βA ，???? ? ??=100γA 。 先求A 的LU 分解（利用分解的紧凑格式）， ???? ? ??-----3)0(2)1(1)1(2)0(1)1(2)2(1)1(1)1(1 )1(。 即，? ??? ? ??=121012001L ，??? ?? ??---=300210111U 。 经直接三角分解法的回代程，分别求解方程组， ????? ??=001Ly 和y U =α，得，???? ? ??-=100α； ???? ? ??=010Ly 和y U =β，得，???????? ??=3231 31β； ???? ? ??=100Ly 和y U =γ，得，；???????? ??--=3132 31γ。 所以，??????? ? ? ?---=-313 2132310 313101A 。 （P47）6. 分别用平方根法和改进平方根法求解方程组： ????? ? ? ??=??????? ????????? ??----816 2115153114015052 31214321x x x x 解: 平方根法： 先求系数矩阵A 的Cholesky 分解（利用分解的紧凑格式）， 笔算开平方方法 一． 拿出一个数，以小数点为分界，两位为一节，从最高位开始开平方。 我们就拿256吧 两位一节，先看最高的是2,那最大开平方就是1，写下1,剩余1。 第二步就是重点了！ 再取两个下来，也就是56。前面还有1,组合成156。 将第一次的开平方数1,先扩大20倍，得到２０,加上可以取的最大值，这个最大值是什么最大呢？也就是x*(20+x)<=156的最大x,可以取６,也正好是６,所以开平方的结果是１６。 再拿个比较大的数：15625 这个数，我们还是两位一节，看最高位１，那就写１，没剩余。 第二步：再取两个下来，也就是５６,我们先将１扩大２０倍，再用刚才的方法，取最大的x，可以取２，那就写２,剩余56-2*(20+2)=56-44=12 第三步：再取两个下来，也就是２５,和刚才剩余的12组成1225,那我们再对刚才的开平方数12，再扩大20倍，得到240,再求最大的开平方数，正好是５,没有剩余。 所以结果是125 如果有剩余，那小数点后也是两位两位地加，也就是一次加两个0,方法和前面一样，对前面已开出来的先扩大20倍，再取最大开方数，一直到你所要的准确度。 二． 1．将被开方数的整数部分从个位起向左每隔两位划为一段，用撇号分开（竖式中的11’56），分成几段，表示所求平方根是几位数； 2．根据左边第一段里的数，求得平方根的最高位上的数（竖式中的3）； 3．从第一段的数减去最高位上数的平方，在它们的差的右边写上第二段数组成第一个余数（竖式中的256）； 4．把求得的最高位数乘以20去试除第一个余数，所得的最大整数作为试商（20×3除256，所得的最大整数是4，即试商是4）； 5．用所求的平方根的最高位数的20倍加上这个试商再乘以试商．如果所得的积小于或等于余数，试商就是平方根的第二位数；如果所得的积大于余数，就把试商减小再试（竖式中（20×3+4）×4=256，说明试商4就是平方根的第二位数）； 6．用同样的方法，继续求平方根的其他各位上的数． 如遇开不尽的情况，可根据所要求的精确度求出它的近似值． 例如求的近似值（精确到0.01），可列出上面右边的竖式，并根据这个竖式得到 笔算开平方运算较繁，在实际中直接应用较少，但用这个方法可求出一个数的平方根的具有任意精确度的近似值． 实例 例如，A=5：5介于2的平方至3的平方;之间。我们取初始值2.1，2.2，2.3，2.4，2.5，2.6，2.7，2.8，2.9都可以，我们最好取中间值2.5。 第一步：2.5+（5/2.5-2.5)1/2=2.2；即5/2.5=2，2-2.5=-0.5，-0.5×1/2=-0.25，2.5+(-0.25)=2.25，取2位数2.2。 第二步：2.2+(5/2.2-2.2)1/2=2.23；即5/2.2=2.27272，2.27272-2.2=-0.07272，-0.07272×1/2=-0.03636，2.2+0.03636=2.23。取3位数2.23。 第三步： 2.23+(5/2.23-2.23)1/2=2.236。即5/2.23=2.2421525，,2.2421525-2.23=0.0121525，,0.0121525×1/2=0.00607，,2.23+0.006=2.236.，取4位数。每一步多取一位数。这个方法又叫反馈开方，即使你输入一个错误的数值， 笔算开平方法的计算步骤如下： 1．将被开方数的整数部分从个位起向左每隔两位划为一段，用撇号分开，分成几段，表示所求平方根是几位数；小数部分从最高位向后两位一段隔开，段数以需要的精度+1为准。 2．根据左边第一段里的数，求得平方根的最高位上的数。 3．从第一段的数减去最高位上数的平方，在它们的差的右边写上第二段数组成第一个余数。 4．把求得的最高位数乘以20去试除第一个余数，所得的最大整数作为试商 5．用商的最高位数的20倍加上这个试商再乘以试商．如果所得的积小于或等于余数，试商就是平方根的第二位数；如果所得的积大于余数，就把试商减小再试，得到的第一个小于余数的试商作为平方根的第二个数。 6．用同样的方法，继续求平方根的其他各位上的数。 如遇开不尽的情况，可根据所要求的精确度求出它的近似值． 笔算开平方运算较繁，在实际中直接应用较少，但用这个方法可求出一个数的平方根的具有任意精确度的近似值． 我国古代数学的成就灿烂辉煌，早在公元前一世纪问世的我国经典数学著作《九章算术》里，就在世界数学史上第一次介绍了上述笔算开平方法．据史料记载，国外直到公元五世纪才有对于开平方法的介绍． 手工开根号法,只适用于任何一个整数或者有限小数开二次方. 因为网上写不出样式复杂的计算式,所以只能尽量书写,然后通过口述来解释: 假设一个整数1456456,开根号首先要从个位开始,每两位数做个标记,这里用'表示,那么标记后变成1'45'64'56.然后根据你要开的小数位数在小数点后补0,这里的举例开到整,则补2个0,(原因等明白该做法后自会理解),解法如下: 解法中需要说明的几个问题: 1,算式中的....没有意义,是因为网上无法排版,为了能把版式排得整齐点而加上的 2,为了区别小数点，所以小数点用。表示，而所有的.都是为了排版需要 3、除了1'45'64'56中的'有特殊意义，在解题中有用处外，其他的'都是为了排版和对起位置，说明数字来源而加的，取消没有任何影响 ...........1..2..0..6。8 .........----------------------- .....1../..1'45'64'56.00.. (1) (1) ............-------- .......22..|.45.. (2) (44) ..............-------- ........240.|.1'64.. (3) 手动开平方方法（最新方案） 虽然现在开方可以直接用符号表示，但考试中如果出一道开方让你写数值的题目怎么办呢？在最新的数学研究中，有一种最新的开平方法。 如有下题： 1522756=（） 开方步骤如下： （一）分位 把一个平方数分为几段。 1.从最低位（个位）开始。 2.每两个数为一位。 3.最高位可以是一位数。 1522756分为：1|52|27|56 分位后，1522756被分为了4段，开方结果为四位数（这里是完全平方数，没有小数）（二）开方 开方运算和除法类似，每运算1次都有一个递减过程。运算时也是从高位至低位。 如1|52|27|56先算1，再算52…… 格式如下： 平方根 52 | |1 56 | 27 运算过程 和除法类似，平方根写在横线上面，运算过程写在下面。 平方定义，12=1 所以如下： 1 52 | |1 56 | 27 1 ——————— 5 2 这第一步与除法佷像，但是是一次落2位，也就是1段。 下面的运算就与除法有些差别了，这是计算中非常麻烦的部分。 这一步骤叫：造数 首先，将已开出的平方根部分×2，得到1×2=2 然后，我们须要假设下一个我们要开出的平方根是A，A的范围是0~9中任何一个自然数。下面就需要我们去试一试了，我们要在0~9中找出一个数作为A的值，前提是：要使前面一步算出的2与A合为一个新数，就是以A为个位，2为十位，合成2A（注意：这里不指2和A相乘，如果A=6，那么这个数为26），并且2A×A最接近而不超过前面落下的52。下一步就是试数，经试验A=2合适，也就得到22×2=44。 这一步的44就是结果了，下一位平方根为A，也就是2，得到： 解：由图可知a<0，b>0，a-b<0 ∴ () 2a b a b a b a b a =----=---+=- 其实平方根与立方根是可以笔算算出来的，当你身边没有计算机的时候，掌握此类的算法十分有用。 至于怎样算，可以归纳为如下两条公式：平方根，20m+n ；立方根， 300m^2+30mn+n^2。 怎样去理解呢，很简单。模板是按除法的模式。以开平方为例，譬如要求72162的平方根，先要从个位开始将它分块，每两位一块，即7，21，62这样分。然后开始试商，从最高为试起，先来7，什么数的平方小于7的呢？明显是2。然后用7减去2的平方，得出的数字3为余数，将要在下一步与后两位数字合起来用来进行下一步运算。第二步，此时被除的变成了321，此时公式开始派上用场，上一步试出来的商2即为m ，至于n 呢，当然是第二步要试的商啦，而除数就是公式20m+n ，切记商与除数的积不要大过被除数。具体到刚才的数字，除数是321，而被除数则是20×2+n，即40几，要n×（20×2＋n ）小于等于321，最合适的就是n=6，即46×6=276，再用321减去276得出结果45用于第三步的试商。第三步，也像第二步一样试商，只不过此时的被除数变成4562，除数m=20×26+n，n 是第三步要试的商。由n×（20×26+n）小于等于4562得出第三步的试商n=8，第四步开始棘手了，因为个位之前的已经试完了，此时，应从小数点之后的十分位开始，如一开始一样，每两位分成一块，这之后，就可以按前面的方法一直试下去了。 至于立方根，也是与平方根一样的思路，只不过比平方根复杂一点。与平方根的区别主要有三点，一、分块变为每三位一块，如刚才的72162，要分为72，162；二、除数变成300m^2+30mn+n^2；三、余数的区别，平方根的余数肯定要比除数小的，不然说明试的商不合适，例如上面的题目，第二步余数45小于除数46，第三步余数338小于除数528；而立方根就有点不同，它在第二步开始试商的时候，得出来的余数是有可能比除数大的，而且经实践得出，这可能性不低，至于到了第三步，余数又开始回归正常了，即必定小于除数，否则试商有误。 浅析线性方程组的平方根解法 在求解线性方程组时, 直接解法有顺序高斯消元法、列主元高斯消元法、全主元高斯消元法、高斯约当消元法、消元形式的追赶法、LU分解法、矩阵形式的追赶法，当我们遇到对称正定线性方程组时，我们就要用到平方根法（对称LLT 分解法）来求解，为了熟悉和熟练运用平方根法求解线性方程组，下面对运用平方根法求解线性方程组进行解析。一、运用平方根法求解线性方程组涉及到的定理及定义 我们在运用平方根法求解线性方程组时，要判定线性方程组Ax=b 的系数矩阵A 是否是对称正定矩阵，那么我们就要了解正定矩阵的性质和如下定理及定义： 1、由线性代数知，正定矩阵具有如下性质： 1）正定矩阵A 是非奇异的 2）正定矩阵A的任一主子矩阵也必为正定矩阵 3）正定矩阵A的主对角元素均为正数 4）正定矩阵A 的特征值均大于零 5）正定矩阵A的行列式必为正数 定义一线性方程组Ax=b的系数矩阵A是对称正定矩阵，那么Ax=b是对称正定线性方程组。 定义二如果方阵A满足A=AT那么A是对称阵。 2.1.4 平方根法和改进的平方根法 如果A是n阶对称矩阵，由定理2还可得如下分解定理： 定理2若A为n阶对称矩阵，且A的各阶顺序主子式都不为零，则A可惟一分解为：A= LDLT,其中L为单位下三角阵，D为对角阵。 证明因为A的各阶顺序主子式都不为零，所以A可惟一分解为：A= LU 因为，所以可将U 分解为： i DU i 其中D 为对角矩阵，Ui 为单位上三角阵?于是：A = LDU 仁L(DUI) 因为A 为对称矩阵，所以，A = AT = UITDTL 七U 仃(DLT),由A 的LU 分解的惟一 性即得：L = UIT,即 Ui = LT ,故 A = LDLT 工程技术中的许多实际问题所归结出的线性方程组，其系数矩阵常有对称正定 性，对于具有此类特殊性质的系数矩阵，利用矩阵的三角分解法求解是一种较好 的有效方法，这就是对称正定矩阵方程组的平方根法及改进的平方根法， 这种方 法目前在计算机上已被广泛应用。 定理3对称矩阵A 为正定的充分必要条件是A 的各阶顺序主子式大于零。 2对称正定矩阵的三角分解 定理(Cholesky 分解)设A 为n 阶对称正定矩阵，则存在惟一的主对角线元素 都是正数的下三角阵L ,使得：A = LLT 。 分解式A = LLT 称为正定矩阵的Cholesky 分解，利用Cholesky 分解来求解系数 矩阵为对称正定矩阵的方程组AX ^ b 的方法称为平方根法。 设A 为4阶对称正定矩阵，则由定理 4 知，A = LLT ，即： a ii a i2 a i3 a i4 l ii 0 0 0 l ii l 2i l 3i l 4i a 21 a 22 a 23 a 24 l 2i l 22 0 0 0 l 22 l 32 l 42 a 3i a 32 a 33 a 34 l 3i l 32 l 33 0 0 l 33 l 43 a 4i a 42 a 43 a 44 l 4i l 42 l 43 144 l 44 将右端矩阵相乘， 并令两端矩阵的元素相等， 于是不难算得矩阵 L 的元素的计算 公式为: 平方根法的计算框图见图 用平方根法求解系数矩阵对称正定的线性方程组时，计算过程是数值稳定 U ii U 22 U l2 U in U ii 1 U nn U 2n U 22 U nn 平方根1 教学目的： 1、使学生理解数的平方根的概念，能运用根号表示一个数的平方根； 2、掌握用平方运算求某些数的平方根的方法； 教学重点和难点： 重点：平方根的概念及求某些数的平方根的方法； 难点：平方根的概念；关键：对符号“”意义的理解。 学法指导： 根据教师为主导，学生为主体的原则，始终贯穿“激发情趣—手脑并用—启发诱导—反馈矫正”的教学方法。 教法指导： 1、针对八年级学生的认知特点，体现“以学生发展为本”的教育理念，发展学生的个性特长，让学生学会学习。本堂课主要采用引探式和启发式的教学方法，教师引导为辅，学生自主思考解决问题为主。 2、数学概念的学习比较抽象、枯燥，用多媒体辅助教学，增加课堂的趣味性，提高学生的学习积极性。 教学过程： 一、引入新课： 我们学习了有理数的加、减、乘、除和乘方运算，但在现实生活中，有些问题仅运用这五种运算是无法解决的。例如已知正方形一边长是4厘米，那么它的一条对角线的长是多少厘米?解决这个问题就要运用一种新的运算方法，这种运算叫做开方。这节课我们就要学习开方运算和平方根。 可以先预练1—20的平方计算。 二、新课学习： 1、知识设疑： （1）计算：42；(－4)2； (0.8)2；(－0.8)2 （2）如果已知一个数的平方等于16 2、知识形成： 知识点一： 我们可以设这个数为x，则2x＝16，问题归结为求x。这个问题可以通过乘方运算来解决。 因为42＝16所以x ＝4 ， 可以表示为(±4)2 ＝16。 因为4或－4的平方都等于16，我们把4及－4叫做16的平方根。 概括1：一般地，如果一个数的平方等于a ，这个数就叫做a 的平方根(或二次方根)。就是 说，如果x 2＝a,那么x 就叫做a 的平方根。 如：23与－23都是529的平方根。 因为(±23)2＝529，所以±23是529的平方根。 问：（1）16，49，100，1 100都是正数，它们有几个平方根?平方根之间有什么关系? （2）0的平方根是什么? 概括2：一个正数有两个平方根，它们互为相反数；0有一个平方根，它是0本身；负数 没有平方根。 知识点二： 概括3：求一个数a(a ≥0)的平方根的运算，叫做开平方。 开平方运算是已知指数和幂求底数。平方与开平方互为逆运算。一个数可以是正数、负数或者是0，它的平方数只有一个，正数或负数的平方都是正数，0的平方是0。但一个正数的平方根却有两个，这两个数互为相反数，0的平方根是0。负数没有平方根。 因为平方与开平方互为逆运算，因此我们可以通过平方运算来求一个数的平方根，也可以通过平方运算来检验一个数是不是另一个数的平方根。 知识点三： （1）625的平方根是多少？这两个平方根的和是多少？ －7和7是哪个数的平方根？ 正数m 的平方根怎样表示？ （2）下列各数的平方根各是什么？ 64； 0； (－0.4)2 ； )3 2 1( （3）已知正方形的面积等于a, 3、例题讲解： 例1、求下列各数的平方根： (1)81； (2)1916； (3)0.09。 实验名称：改进平方根法 学院：___数学学院______________________ 班级 姓名： 学号： 实验日期 2015 年 05 月 26 日 自评成绩：97 一、实验目的 (1)熟练掌握改进平方根法和共轭梯度法的迭代过程 (2)尝试使用自己熟悉的计算机语言解决数学中的问题 (3)通过上机实验来巩固课本中所学的知识 二、实验内容与结果 题目1：改进平方根法 源程序1 #include cin>>a[i][j]; } } for(j=0;j 数值计算方法 09医软（1）班 本组实验同学：刘康康秦强梅世友马蕾乔琼 任务分配：刘康康：分析平方根法解对称矩阵的思想，并写出推导过程 秦强：利用c++实现算法，并写出程序 梅世友：调试并运行程序 马蕾：根据解方程组的方法写出流程图 乔琼：负责word的排版（解题流程，程序截图等） 一．实验名称 平方根法解对称方程组 二．实验目的 理解平方根法解对称方程组的基本思想，原理以及公式的推导过程，和用c++实现算法 三．理论分析推导和程序实现 （一）、理论分析推导 设A为对称矩阵，且A的所有顺序主子式均不为0，由定理4（P178）可知，A可以唯一地分解为A=LU，其中L为单位下三角矩阵，U为上三角矩阵，为了利用A的对称性，再将U进行分解，即 ????????????nn n n u u u u u u 22211211=????????????nn u u u 2211??????? ?????????---1///1//1)1,1(),1(22222231111112n n n n n n u u u u u u u u u u 或写成 U=D u ~ 其中D 为对角矩阵，U1为单位上三角矩阵。于是 A=LU=LD u ~ （2.12） 又 A=A '=u '~D L '(A 'L '分别表示A.L 的转置矩阵) 由分解的唯一性，得u '~ =L 。由（2.12）知 A=LD L ' 且这种分解是唯一的。 如果A 是对称正定的，利用代数知识可以证明ii u （i=1，2，…，n ）皆大于零。事实上，将A=LU 按分块形式写出，有 k k k U L A =（k=1,2,…，n)， 其中 k A =??????????kk k k k a a a a a a 2111211，k L =????????????????-11111,2121k k k k l l l l ， c语言编的改进平方根法求解线性方程组 2010-12-18 12:12 #include 平方根的计算方法 上面的太复杂拉,其实很简单: 智能ABC输入法的词库文件存储为计算机上的两个文件“Tmmr.rem”和“User.rem”。不知道你说的是不是这类型的文件，因为WINDOWS 关闭计算机时是要关闭输入法的，如果发现词库错误的话，可能有上述提示，建议把正在使用的输入法删除再安装一次 就是 智能ABC输入法的问题. 你说的记忆文件是指输入法的记忆文件。一般出现这个错误不要紧~不影响日常使用。 你还是使用微软拼音2003吧，智能、紫光、拼音加加都出现很多问题，这些输入法本身就有问题。相反微软拼音2003却没有那么多的问题，就是因为它整合兼容windows所有版本，微软的操作系统使用微软的输入法就不会出现问题，即使有问题也是偶尔发生的。备份一下字库如果不是专业打字人员就用微软拼音常见硬件术语手册 作者：佚名文章来源：本站原创点击数：30 更新时间：2006-2-27 常见硬件术语手册 一、CPU术语解释 3DNow!：(3D no waiting)AMD公司开发的SIMD指令集，可以增强浮点和多媒体运算的速度，它的指令数为21条。 ALU：(Arithmetic Logic Unit，算术逻辑单元)在处理器之中用于计算的那一部分，与其同级的有数据传输单元和分支单元。 BGA：(Ball Grid Array，球状矩阵排列)一种芯片封装形式，例：82443BX。 BHT：(branch prediction table，分支预测表)处理器用于决定分支行动方向的数值表。 BPU：(Branch Processing Unit，分支处理单元)CPU中用来做分支处理的那一个区域。 Brach Pediction：（分支预测）从P5时代开始的一种先进的数据处理方法，由CPU来判断程序分支的进行方向，能够更快运算速度。 CMOS：（Complementary Metal Oxide Semiconductor，互补金属氧化物半导体）它是一类特殊的芯片，最常见的用途是主板的 平方根法和改进平方根法求解线性方程组例题 与程序 2、数学原理 1、平方根法解n阶线性方程组Ax=b的choleskly方法也叫做平方根法，这里对系数矩阵A是有要求的，需要A是对称正定矩阵，根据数值分析的相关理论，如果A对称正定，那么系数矩阵就可以被分解为的形式，其中L是下三角矩阵，将其代入Ax=b 中，可得：进行如下分解：那么就可先计算y,再计算x，由于L 是下三角矩阵，是上三角矩阵，这样的计算比直接使用A计算简便，同时你应该也发现了工作量就转移到了矩阵的分解上面，那么对于对称正定矩阵A进行Cholesky分解，我再描述一下过程吧：如果你对原理很清楚那么这一段可以直接跳过的。设，即其中第1步，由矩阵乘法，故求得一般的，设矩阵L的前k-1列元素已经求出第k步，由矩阵乘法得于是 2、改进平方根法在平方根的基础上，为了避免开方运算,所以用计算；其中，；得按行计算的元素及对元素公式对于、、计算出的第行元素后，存放在的第行相置，然后再计算的第行元素，存放在的第行、的对角元素存放在的相应位置、对称正定矩阵按分解和按分解计算量差不多，但分解不需要开放计算。求解, 的计算公式分别如下公式。 3、程序设计 1、平方根法function [x]=pfpf(A,b)%楚列斯基分解求解正定矩阵的线性代数方程 A=LL’ 先求LY=b 再用L’X=Y 即可以求出解 X[n,n]=size(A);L(1,1)=sqrt(A(1,1));for k=2:n L(k,1)=A(k,1)/L(1,1);endfor k=2:n-1 L(k,k)=sqrt(A(k,k)- sum(L(k,1:k-1)、^2)); for i=k+1:n L(i,k)=(A(i,k)- sum(L(i,1:k-1)、*L(k,1:k-1)))/L(k,k); endendL(n,n)=sqrt(A(n,n)-sum(L(n,1:n-1)、^2));%解下三角方 程组Ly=b 相应的递推公式如下，求出y矩阵y=zeros(n,1);%先 生成方程组的因变量的位置，给定y的初始值for k=1:n j=1:k-1; y(k)=(b(k)-L(k,j)*y(j))/L(k,k);end%解上三角方程组L’X=Y 递推公式如下，可求出X矩阵x=zeros(n,1);U=L;%求上对角矩阵 for k=n:-1:1 j=k+1:n; x(k)=(y(k)- U(k,j)*x(j))/U(k,k);end >> A=[4,2,-4,0,2,4,0,02,2,-1,- 2,1,3,2,01,14,1,-8,-3,5,6 0,-2,1,6,-1,-4,-3,32,1,-8,- 1,22,4,-10,-34,3,-3,-4,4,11,1,-4 0,2,5,-3,-10,1,14,2 0,0,6,3,-3,-4,2,19];>> b=[0;-6;20;23;9;-22;-15;45];>> x=pfpf(A,b)x =1 21、1481 60、1528 10、91202、018 课题名称： 课题一解线性方程组的直接方法 解决的问题： 给定三个不同类型的线性方程组，用适当的直接法求解。 采用的数值方法： 对第一个普通的线性方程组，采用了高斯顺序消去法和高斯列主元消去法。对第二个正定线性方程组，采用了平方根法。对第三个三对角线性方程组，采用了追赶法。 算法程序： (1)普通的线性方程组 ①顺序消去法 #include {0,2,-1,3,-4,2,5,3,0,1}, {16,10,-11,-9,17,34,2,-1,2,2}, {4,6,2,-7,13,9,2,0,12,4}, {0,0,-1,8,-3,-24,-8,6,3,-1} }; float b[10]= {5,12,3,2,3,46,13,38,19,-21}; float x[10]= {0}; float Aik,S,temp; int i,j,k; int size=10; for(k=0; k改进的平方根法及其程序实现
线性方程组的平方根解法
矩形运算方法
平方根法追赶法
数值分析课后习题部分参考答案
笔算开平方方法
笔算开平方法的计算步骤
手动开平方方法(最新方案)
算平方根的简便方法
线性方程组的平方根解法
平方根与立方根(教案)
改进平方根法的C++实现
对称矩阵的平方根法
c语言编的改进平方根法求解线性方程组
平方根的计算方法
平方根法和改进平方根法求解线性方程组例题与程序
数值分析列主元高斯消去顺序高斯平方根法追赶法