数值分析：解线性方程组的直接法-1 完整版

解线性方程组的直接法/*DirectMethodforSolvingLinearSystems*/求解§1高斯消元法/*GaussianElimination*/

高斯消元法：思路首先将A化为上三角阵/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=§1GaussianElimination–TheMethod消元记Step1：设，计算因子将增广矩阵/*augmentedmatrix*/第i行

mi1

第1行，得到其中Stepk：设，计算因子且计算共进行？步n

1回代Whatif?Nouniquesolutionexists.Whatif?Thenwemustfindthesmallestintegerk

iwith,andinterchangethek-throwwiththei-throw.Whatifwecan’tfindsuchk

?Nouniquesolutionexists.定理

若A的所有顺序主子式

/*determinantofleadingprincipalsubmatrices*/

均不为0，则高斯消元无需换行即可进行到底，得到唯一解。注：事实上，只要A

非奇异，即A1

存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。§1GaussianElimination–TheMethod

选主元消去法/*PivotingStrategies*/例：单精度解方程组/*精确解为和*/8个8个用GaussianElimination计算：8个小主元/*Smallpivotelement*/

可能导致计算失败。§1GaussianElimination–PivotingStrategies

全主元消去法/*CompletePivoting*/每一步选绝对值最大的元素为主元素，保证。Stepk:①选取②Ifik

k

then交换第k行与第ik

行;Ifjk

k

then交换第k列与第jk

列;③消元注：列交换改变了xi

的顺序，须记录交换次序，解完后再换回来。

列主元消去法/*PartialPivoting,ormaximalcolumnpivoting*/省去换列的步骤，每次仅选一列中最大的元。§1GaussianElimination–PivotingStrategies例：

注：列主元法没有全主元法稳定。例：注意：这两个方程组在数学上严格等价。

标度化列主元消去法/*ScaledPartialPivoting*/对每一行计算。为省时间，si

只在初始时计算一次。以后每一步考虑子列中最大的aik

为主元。注：稳定性介于列主元法和全主元法之间。§1GaussianElimination–PivotingStrategies§1GaussianElimination–PivotingStrategies实际应用中直接调用GaussElimination

解3阶线性方程组的结果：结合全主元消去后的结果：

高斯-若当消去法/*Gauss-JordanMethod*/与GaussianElimination的主要区别：

每步不计算mik

，而是先将当前主元akk(k)

变为1;

把akk(k)

所在列的上、下元素全消为0;Hey!Isn’titbetterthanGaussianElimination?Whatmakesyousayso?Obviouslywenolongerneedthebackwardsubstitution!You’dbetterwaittillwegothroughthenextsectiontodrawyourconclusion…§1GaussianElimination–Gauss-JordanMethod

运算量

/*AmountofComputation*/§1GaussianElimination–AmountofComputation由于计算机中乘除/*multiplications/divisions*/

运算的时间远远超过加减/*additions/subtractions*/运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。

GaussianElimination:Stepk：设，计算因子且计算共进行n

1步(n

k)次(n

k)2

次(n

k)次(n

k)(n

k+2)

次消元乘除次数：1次(n

i+1)次回代乘除次数：GaussianElimination的总乘除次数为，运算量为级。§1GaussianElimination–AmountofComputation

CompletePivoting:比GaussianElimination多出比较，保证稳定，但费时。

PartialPivoting:比GaussianElimination只多出比较，略省时，但不保证稳定。

ScaledPartialPivoting:比GaussianElimination多出除法和比较，比列主元法稳定。但若逐次计算si(k)，则比全主元法还慢。

Gauss-JordanMethod:运算量约为。故通常只用于求逆矩阵，而不用于解方程组。求逆矩阵即。HW:p.42#1p.43#6§1GaussianElimination–AmountofComputationLab05.MatrixInversion UseGauss-JordanMethodwithPartialPivotingtofindtheinverseofagivenmatrix.Input Thereareseveralsetsofinputs.Foreachset: The1stlinecontainsaninteger100

n

0whichisthesizeofamatrix.n=

1signalstheendoffile. The2ndlinecontainsn

nrealnumberswhicharetheentriesofthematrix.Thenumbersareseparatedbyspacesornewlines.OutputEachentryoftheinversematrixistobeprintedasintheCfprintf:fprintf(outfile,"%16.8e

",a);/*here

representsaspace*/§1GaussianElimination–AmountofComputationTheentriesofann

nmatrixaretobeprintedinthefollowingformat:Ifthematrixisnotinvertable,printthemessage“The

matrix

is

singular.\n”.Theoutputsoftwotestcasesmustbeseperatedbyablankline.SampleInput

3–3

8

52

–7

41

9

–620

10

2–1Sample