解线性方程组基思想

解线性方程组基思想

————————————————————————————————作者：————————————————————————————————日期：

四：基本方法

基本思路将在解题的过程中得到体现。

1．（求线性方程组的唯一解或特解），这类问题的求法分为两类：一类主要用于解低阶稠

密矩阵——直接法；一类是解大型稀疏矩阵——迭代法。

1.1利用矩阵除法求线性方程组的特解（或一个解）

方程：AX=b，解法：X=A\b，(注意此处’\’不是’/’)

例1-1 求方程组的解。

解: A = ; = ；b=(1,0,0,0,1)’

由于>>rank(A)=5,rank( )=5 %求秩，此为R（A）=R（）>=n的情形，有唯一解。

>>X= A\b %求解X =(2.2662, -1.7218, 1.0571,-0.5940, 0.3188)’ 或用函数rref

求解，>>sv=rref(A:b);所得sv的最后一列即为所要求的解。

1．2 利用矩阵的LU、QR和cholesky分解求方程组的解

这三种分解，在求解大型方程组时很有用。其优点是运算速度快、可以节省磁盘空间、节省内存。

I) LU分解又称Gauss消去分解，可把任意方阵分解为下三角矩阵的基本变换形式（行交换）和上三角矩阵的乘积。即A=LU，L为下三角阵，U为上三角阵。

则：A*X=b 变成L*U*X=b

所以X=U\(L\b) 这样可以大大提高运算速度。命令[L，U]=lu (A)

在matlab中可以编如下通用m 文件：

在Matlab中建立M文件如下

% exp1.m

A;b;

[L，U]=lu (A);

X=U\(L\b)

II）Cholesky分解

若A为对称正定矩阵，则Cholesky分解可将矩阵A分解成上三角矩阵和其转置的乘积，即：其中R为上三角阵。

方程A*X=b 变成所以

在Matlab中建立M文件如下

% exp2.m

A;b;

[R’，R]=chol(A);

X=R\(R’\b)

III）QR分解

对于任何长方矩阵A，都可以进行QR分解，其中Q为正交矩阵，R为上三角矩阵的初等变换形

式，即：A=QR

方程A*X=b 变形成QRX=b

所以X=R\(Q\b)

上例中[Q, R]=qr(A)

X=R\(Q\B)

在Matlab中建立M文件如下

% exp3.m

A;b;

[Q，R]=qr(A);

X=R\(Q\b)

2．求线性齐次方程组的通解(A*X=0)

在Matlab中，函数null用来求解零空间，即满足A•X=0的解空间，实际上是求出解空

间的一组基（基础解系）。

在Matlab中建立M文件如下

% exp4.m

format rat %指定有理式格式输出

A;b=0;

r=rank(A);

bs=null(A，‘r’); %一组基含(n-r)个列向量

% k ,k ,……,k

% X= k *bs(:,1)+ k *bs(:,2)+……+ k *bs(:,n-r) 方程组的通解

pretty(X) %让通解表达式更加精美

3 求非齐次线性方程组的通解（A*X=b）

非齐次线性方程组需要先判断方程组是否有解，若有解，再去求通解。

因此，步骤为：

第一步：判断AX=b是否有解，(利用基本思路的第一条)

若有解则进行第二步

第二步：求AX=b的一个特解

第三步：求AX=0的通解

第四步：AX=b的通解为：AX=0的通解加上AX=b的一个特解。

在Matlab中建立M文件如下

% exp4.m

clear all

A;b; %输入矩阵A,b

[m,n]=size(A);

R=rank(A);

B=[A b];

Rr=rank(B);

format rat

if R==Rr&R==n % n为未知数的个数，判断是否有唯一解

x=A\b;

elseif R==Rr&R

x=A\b %求特解

C=null(A, r ) %求AX=0的基础解系,所得C为n-R列矩阵，这n-R列即为对

%应的基础解系

% 这种情形方程组通解xx=k(p)*C(:,P)(p=1…n-R)

else X= No solution! % 判断是否无解

end

第3章线性方程组的迭代解法

3.1实验目的

理解线性方程组计算机解法中的迭代解法的求解过程和特点，学习科学计算的方法和简单的编程技术。

3.2概念与结论

1.n阶线性方程组

如果未知量的个数为n ,而且关于这些未知量x1,x2, …,x n的幂次都是一次的(线性的)那末, n 个方程

a11x1+a12x2+ …+a1n x n=b1

┆┆┆(1)

a n1x1+a n2x2+ …+a nn x n=

b n

构成一个含n个未知量的线性方程组,称为n阶线性方程组。其中,系数a11,…,a1n,a21, …,a2n, …,a n1, …,a nn和b1, …,b n都是给定的常数。

方程组(1)也常用矩阵的形式表示,写为

Ax=b

其中,A是由系数按次序排列构成的一个n阶矩阵,称为方程组的系数矩阵,x和b都是n维向量,b称为方程组的右端向量。

2. n阶线性方程组的解

使方程组(1)中每一个方程都成立的一组数x1*,x2*, …,x n*称为式(1)的解,把它记为向量的形式,称为解向量.

3. 向量范数的三种常用范数 4．矩阵的四种常用范数

5.谱半径

设 n ?n 阶矩阵A 的特征值为λ i (i=1,2,3……n),则称

ρ (A) = MAX | λi | 1≤i ≤ n

为矩阵A 的谱半径.

矩阵范数与谱半径之间的关系为: ρ (A) ≤ ||A|| 6.严格(行)对角占优阵A 如果 矩阵 A=(a ij )满足 n

?????????

?

??==

==

∑∑=≤≤∞=n n

k k

k

n k n

k k

x x x x x x x x x x M M M 211

2

211

1max .

21

122221112111

2

1111

11max max

最大特征值是行范数

列范数A A A a a a a a a a a a A a A a A a A T nn n n n n n k kj

n j f n

k jk

n j n

k kj n j λλ

=?

???

??

???

??====∑∑∑∑===≤≤∞=≤≤ΛΛΛM ΛΛΛΛΛΛΛΛΛΛΛΛ

|a ii | > ∑ |a ij | i=1,2,……n, j=1,j ≠i

则称方阵A 是严格(行)对角占优的. 7.收敛定理

对任意初始向量x (0)及任意右端向量 g ，由迭代x (k+1) =B x (k) +g 产生的迭代向量序列{x (k)}收敛的充要条件是谱半径ρ（B ）<1 8.收敛判别条件 判别条件1：

若||B||<1, 则迭代x (k+1) =B x (k) +g 对任何初始向量x (0)都收敛. 判别条件2：

如果A 为严格对角占优阵，则其 Jacobi 迭代和Seidel 迭代对任何初始向量x (0)都收敛。

判别条件3：

如果A 为对称正定阵，则其 Seidel 迭代对任何初始向量x (0)都收敛。 9.迭代法的误差估计

若||B||<1，则对迭代格式 x (k+1) =B x (k) +g 有

3.3 程序中Mathematica 语句解释

a*matrix 数a 与矩阵matrix 相乘

matrix1+matrix2 矩阵matrix1和矩阵matrix2相加（注意矩阵的大小相同） matrix1.matrix2 矩阵matrix1和矩阵matrix2相乘(注意矩阵乘法的规则) Transpose[matrix] 求矩阵matrix 转置 Inverse[matrix] 求矩阵(方阵) matrix 的逆

)

()1(*)()1()(*)(1.

21.1o k

k k k k x x B

B

x x x x B B x x --≤

---≤--

DiagonalMatrix[list] 使用列表list 中的元素生成一个对角矩阵. IdentityMatrix[n] 生成n 阶单位矩阵

Max[x] 求向量x 中元素的最大值

3.4 方法、程序、实验

解线性方程组的迭代法是将线性方程组 Ax=b 化为等价线性方程组 x=Bx+f 再由矩阵迭代格式

x (k+1)=Bx (k)+f

构造向量序列{x (k)}来求线性方程组解的。如果得出的向量序列{x (k)}收敛至某个向量x *，则可得该向量x *就是所求方程组 Ax=b 的准确解.

线性方程组的迭代法主要有Jocobi 迭代法、Seidel 迭代法和超松弛(Sor)迭代法。

1. Jocobi 迭代法

1) Jocobi 迭代法的构造过程

假设a ii ≠0，依次在第i 个方程解出x i , i=1,2,?,n 并令 c ij = -a ij /a ii (i ≠j) ， g i = b i /a ii

就得到如下Jocobi 迭代格式：

x 1(k+1)= c 12x 2(k)+c 13x 3(k)+???? +c 1n x n (k)+g 1 x 2(k+1)=c 21x 1(k) +c 23x 3(k)+???? +c 2n x n (k)+g 2

。。。。。。。。。。。。。。。。。。。。。。。。。。。。

x n (k+1)=c n1x 1(k) +c n2x 2(k)+???? +c n(n-1)x n-1(k) + g n 若令

???

???

? ??=???

????

??=???????

??=n n n n n n J g g g g x x x x c c c c c c B M M Λ

ΛΛΛΛΛΛ21212

1221

112000

则有Jocobi 迭代的矩阵格式：

x (k+1) = B J x (k) +g J

B J 称为Jocobi 迭代矩阵。

Jocobi 迭代可以写成如下紧凑格式：

在给定初始迭代向量x (0)后就可以进行Jocobi 迭代求解了。

2) Jacobi 迭代算法

1.输入变量个数n 、初值向量x （0）

、迭代精度eps 、系数矩阵A 、常数项b 和迭代最大次数nmax

2 For i=1,2,…,n

2.1 如果|a ii |

3. Bj ? E-D -1A

4. g j ? D -1b

5.For k=1,2,…,nmax

5.1 x ?Bj.x0+ g j

5.2 如果||x-x0||

? x

6. 如果||x-x0||>eps ,输出迭代失败，终止。

3) Jacobi 迭代法程序

Clear[a,b,x]; nmax=500;

n=Input[“线性方程组阶数n=”]; a=Input["系数矩阵A="]； b=Input["常数项b="]；

x0=Input["输入迭代初值向量x0"]； eps1=0.000001;

eps=Input["输入精度控制eps="]；

n

i n

i

j j ii

i k j ii

ij

k i

a b x a a x ,,2,11)()

1(Λ=≠=+∑

-

-=

Do[If[Abs[a[[i,i]]]

If[t1==1,

Print["Jacobi迭代法失效"],

d=DiagonalMatrix[Table[a[[i,i]],{i,1,n}]];

d1=Inverse[d];

bj=IdentityMatrix[n]-d1.a;

gj=d1.b;

Do[ x=bj.x0+gj;

err=Max[Abs[x-x0]];

Print["x=",x//N," i=",i," err=",err//N];

If[N[err]

{i,1,nmax}];

If[err>=eps,Print["迭代失败"]]

]

说明本程序用于求线性方程组Ax=b的解。程序执行后，先通过键盘输入线性方程组阶数n、系数矩阵A、常数项b、迭代初值向量x0和输入精度控制eps，程序即可给出每次迭代的次数和对应的迭代向量序列x(k),其中最后输出的结果即为所求的根。如果迭代超出500次还没有求出满足精度的根则输出迭代失败提示，如果出现主对角线元素a ii=0给出Jacobi迭代法失效提示。

程序中变量说明

x0：存放初始向量和迭代过程中的向量x（k）

x: 存放迭代过程中的向量x（k+1）

nmax:存放迭代允许的最大次数

err:存放误差||x-x0||

t1:临时变量

注：迭代最大次数可以修改为其他数字。

4)例题与实验

例1.用Jacobi 迭代法解如下线性方程组

5x1+2x2+x3= -12

-x1+4x2+2x3= 20

2x1-3x2+10x3= 3

要求误差||x(k+1)-x(k)|| <10-4，并用取不同初值的方法实验观察迭代收敛的情况。

解：执行Jacobi迭代法程序后在输入的四个窗口中按提示分别输入:

3、{{5, 2, 1}, {-1, 4, 2}, {2, -3, 10}}、{-12, 20, 3}、{0, 0, 0}、0.0001

每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果：

x={-2.4, 5., 0.3} i=1 err=5.

x={-4.46, 4.25, 2.28} i=2 err=2.06

x={-4.556, 2.745, 2.467} i=3 err=1.505

x={-3.9914, 2.6275, 2.0347} i=4 err=0.5646

x={-3.85794, 2.9848, 1.88653} i=5 err=0.3573

x={-3.97123, 3.09225, 1.96703} i=6 err=0.113286

x={-4.03031, 3.02368, 2.02192} i=7 err=0.0685705

x={-4.01386, 2.98146, 2.01316} i=8 err=0.042216

x={-3.99522, 2.98995, 1.99721} i=9 err=0.0186374

x={-3.99542, 3.00259, 1.99603} i=10 err=0.0126367

x={-4.00024, 3.00313, 1.99986} i=11 err=0.0048186

x={-4.00122, 3.00001, 2.00099} i=12 err=0.00312067

x={-4.0002, 2.9992, 2.00025} i=13 err=0.00102319

x={-3.99973, 2.99983, 1.9998} i=14 err=0.000625697

x={-3.99989, 3.00017, 1.99989} i=15 err=0.00034136

x={-4.00005, 3.00008, 2.00003} i=16 err=0.000155236

x={-4.00004, 2.99997, 2.00003} i=17 err=0.000106099

x={-4., 2.99997, 2.} i=18 err=0.0000414468

此结果说明迭代18次，求得误差为err=0.0000414468的近似解，最后显示的近似解向量为x={-4., 2.99997, 2.}，它表示所求解为

x1=-4，x2=2.99997，x3=2 。

本题的准确解为

x1=-4，x2=3，x3=2 。

如果将如上输入的初值改为{21, -18, 30}，执行Jacobi迭代法程序后得如下输出结果：

x={-1.2, -4.75, -9.3} i=1 err=39.3

x={1.36, 9.35, -0.885} i=2 err=14.1

x={-5.963, 5.7825, 2.833} i=3 err=7.323

x={-5.2796, 2.09275, 3.22735} i=4 err=3.68975

x={-3.88257, 2.06642, 1.98375} i=5 err=1.39703

x={-3.62332, 3.03749, 1.69644} i=6 err=0.97106

x={-3.95428, 3.24595, 1.93591} i=7 err=0.330963

x={-4.08556, 3.04347, 2.06464} i=8 err=0.202475

x={-4.03032, 2.94629, 2.03015} i=9 err=0.0971858

x={-3.98455, 2.97734, 1.98995} i=10 err=0.0457716

x={-3.98893, 3.00889, 1.99011} i=11 err=0.0315451

x={-4.00158, 3.00771, 2.00045} i=12 err=0.0126504

x={-4.00318, 2.99938, 2.00263} i=13 err=0.00833246

x={-4.00028, 2.99789, 2.00045} i=14 err=0.00289753

x={-3.99925, 2.99971, 1.99942} i=15 err=0.0018145

x={-3.99977, 3.00048, 1.99976} i=16 err=0.000770763

x={-4.00014, 3.00018, 2.0001} i=17 err=0.000375926

x={-4.00009, 2.99992, 2.00008} i=18 err=0.000261658

x={-3.99998, 2.99994, 1.99999} i=19 err=0.000107579

x={-3.99997, 3.00001, 1.99998} i=20 err=0.0000714045

从计算结果可以看到虽然所取的初值不同，但迭代总是收敛相同的结果。考察本题系数矩阵可以发现它是严格对角占优矩阵，由收敛判别法，Jacobi迭代对任意初值都是收敛的，我们通过实际计算验证了这个结果。

例2.通过Jacobi 迭代序列观察用Jacobi 迭代法解如下线性方程组

x1+2x2+2x3= -12

-x1+4x2+x3= 20

2x1-3x2+x3= 3

的收敛性。

解：执行Jacobi迭代法程序后在输入的四个窗口中按提示分别输入:

3、{{1, 2, 2}, {-1, 4, 1}, {2, -3, 1}}、{-12, 20, 3}、{0, 0, 0}、0.0001

每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果：

x={-12., 5., 3.} i=1 err=12.

x={-28., 1.25, 42.} i=2 err=39.

x={-98.5, -12.5, 62.75} i=3 err=70.5

x={-112.5, -35.3125, 162.5} i=4 err=99.75

…………………………………………….

{246.719, -120.176, 696.719} i=8 err=763.5

x={-1165.09, -107.5, -850.965} i=9 err=1547.68

x={1904.93, -73.5303, 2010.67} i=10 err=3070.02

x={-3886.28, -21.4355, -4027.45} i=11 err=6038.12

x={8085.77, 40.2917, 7711.26} i=12 err=11972.1

x={-15515.1, 98.6279, -16047.7} i=13 err=23758.9

x={31886.1, 138.141, 31329.1} i=14 err=47401.2

x={-62946.5, 144.247, -63354.7} i=15 err=94832.5

x={126409., 107.068, 126329.} i=16 err=189683.

x={-252883., 25.0775, -252494.} i=17 err=379292.

x={504925., -92.4305, 505845.} i=18 err=758339.

…………………………………….

通过观察迭代过程中的误差是不断变大的特点可以知道本题的Jacobi 迭代序列是不收敛的，因此，本题线性方程组不能用Jacobi 迭代法求解。这个实验说明并不是每个线性方程组都能用Jacobi 迭代法求解。

2.Seidel迭代

1) Seidel迭代的构造过程

为了加快收敛速度，同时节省计算机的内存，对Jocobi迭代作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：

x1(k+1)= c12x2(k)+c13x3(k)+????+c1n x n(k)+g1

x2(k+1)=c21x1(k+1)+c23x3(k)+????+c2n x n(k)+g2

。。。。。。。。。。。。。。。。。。。。。。。。。。。。

x n (k+1)=c n1x 1(k+1) +c n2x 2(k+1)+????+c n(n-1)x n-1(k+1) + g n

如上迭代可以写成如下紧凑格式： 这样所得的迭代法就称为Seidel 迭代法。

利用Ax=b 及A=L+D+U,其中D 为对角矩阵,L,U 分别为严格下，上三角矩阵．则有Seidel 迭代法的矩阵形式为

x (k+1)= B s x (k)+g s 其中：B s =-(L+D)-1U ，g s =D -1b Seidel 迭代矩阵为 B s =-(L+D)-1U 。

在给定初始迭代向量x (0)后就可以进行Seidel 迭代求解了。 Jacobi 迭代和Seidel 迭代格式可表述为统一形式:

2) Seidel 迭代算法

1.输入变量个数n 、初值向量x （0）

、迭代精度eps 、系数矩阵A 、常数项b 和迭代最大次数nmax

2. For i=1,2,…,n

2.1 如果|a ii |

3.For i=1,2,…,nmax 3.1 For i=1,2,…,n

3.2 如果||x (k+1)-x (k)||∝

? x (k+1)

4. 如果||x-x0||∝

ii

n

i j k j

ij i j k j ij i k i

a x a x a

b x ∑∑+=-=++-

-=

1

)

(1

1

)

1()

1(g

Bx x k k +=+)()1(ii

n

i j k j

ij

i j k j ij i k i

a x

a x a

b x ∑∑+=-=++-

-=

1

)(1

1

)

1()

1(

3) Seidel 迭代法程序

Clear[a,b,x];

nmax=500;

n=Input[“线性方程组阶数n=”];

a=Input["系数矩阵A="]；

b=Input["常数项b="]；

x0=Input["输入迭代初值向量x0"]；

eps1=0.000001;

eps=Input["输入精度控制eps="]；

x=x0;

Do[If[Abs[a[[i,i]]]

If[t1==1,

Print["Seidel迭代法失效"],

Do[ Do[u1=Sum[a[[i,j]]*x[[j]],{j,1,i-1}];

u2=Sum[a[[i,j]]*x0[[j]],{j,i+1,n}];

x[[i]]=(b[[i]]-u1-u2)/a[[i,i]],

{i,1,n}];

err=Max[Abs[x-x0]];

Print["x=",x//N," k=",k," err=",err//N];

If[N[err]

{k,1,50}];

If[err>=eps,Print["迭代失败"]]

]

说明本程序用于求线性方程组Ax=b的解。程序执行后，先通过键盘输入线性方程组阶数n、系数矩阵A、常数项b、迭代初值向量x0和输入精度控制eps，程序即可给出每次迭代的次数和对应的迭代向量序列x(K),其中最后输出的结果即为所求的根。如果迭代超出500次还没有求出满足精度的根则输出迭代失败提示，如果出现主对角线元素a ii=0给出Jacobi迭代法失效提示。

程序中变量说明

x0：存放初始向量和迭代过程中的向量x（k）

x: 存放迭代过程中的向量x（k+1）

nmax:存放迭代允许的最大次数

err:存放误差||x-x0||∝

t1,u1,u2:临时变量

注：迭代最大次数可以修改为其他数字

4)例题与实验

例3.用Seidel 迭代法解如下线性方程组

5x1+2x2+x3= -12

-x1+4x2+2x3= 20

2x1-3x2+10x3= 3

要求误差||x(k+1)-x(k)||∝<10-4。

解：执行Seidel迭代法程序后在输入的四个窗口中按提示分别输入:

3、{{5, 2, 1}, {-1, 4, 2}, {2, -3, 10}}、{-12, 20, 3}、{0, 0, 0}、0.0001

每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果：

x={-2.4, 4.4, 2.1} k=1 err=4.4

x={-4.58, 2.805, 2.0575} k=2 err=2.18

x={-3.9335, 2.98787, 1.98306} k=3 err=0.6465

x={-3.99176, 3.01053, 2.00151} k=4 err=0.0582625

x={-4.00451, 2.99812, 2.00034} k=5 err=0.0127509

x={-3.99931, 3., 1.99986} k=6 err=0.00519946

x={-3.99997, 3.00007, 2.00002} k=7 err=0.000659841

x={-4.00003, 2.99998, 2.} k=8 err=0.0000916628

此结果说明迭代8次，求得误差为err=0.0000916628的近似解，最后显示的近似解向量为x={-4.00003, 2.99998, 2.}，与本题的准确解为x1=-4.，x2=3.，x3=2. 误差很小。注意到本题在同样迭代误差和初值前提下，用Jacobi 迭代需要18次迭代才获得具有同样精度的解，这说明，在都收敛的前提下，Seidel 迭代比Jacobi 迭代收敛快。

例4.设线性方程组为

x1+2x2-2x3= 1

x1+x2+x3= 1

2x1+2x2+x3= 1

考察用Jacobi迭代法和Seidel 迭代法求解该线性方程组的收敛情况。如果收敛，给出误差满足||x(k+1)-x(k)||∝<10-4的解。

解：执行Seidel迭代法程序后在输入的四个窗口中按提示分别输入:

3、{{1, 2, -2}, {1,1,1}, {2,2,1}}、{1,1,1}、{0, 0, 0}、0.0001

每次输入后用鼠标点击窗口的“OK”按扭，得如下输出部分结果：

………………………………………..

x={-5123., 5379., -511.} k=9 err=3072.

x={-11779., 12291., -1023.} k=10 err=6912.

x={-26627., 27651., -2047.} k=11 err=15360.

x={-59395., 61443., -4095.} k=12 err=33792.

x={-131075., 135171., -8191.} k=13 err=73728.

x={-286723., 294915., -16383.} k=14 err=159744.

x={-622595., 638979., -32767.} k=15 err=344064.

………………………………………………………..

x={-8.05018?1016, 8.10648?1015, -1.1259?1015} k=50 err=4.13768?1016

通过观察迭代过程中的误差是不断变大的特点可以知道本题的Seidel 迭代序列是不收敛的，因此，本题线性方程组不能用Seidel 迭代法求解。

执行Jacobi迭代法程序后在输入的四个窗口中按提示分别输入:

3、{{1, 2, -2}, {1,1,1}, {2,2,1}}、{1,1,1}、{0, 0, 0}、0.0001

每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果：

x={1., 1., 1.} i=1 err=1.

x={1., -1., -3.} i=2 err=4.

x={-3., 3., 1.} i=3 err=4.

x={-3., 3., 1.} i=4 err=0

此结果说明迭代4次，求得误差为err=0的近似解，最后显示的近似解向量为

x={-3., 3., 1.}，与本题的准确解为x1=-3.，x2=3.，x3=1.相同。

本次实验说明Seidel 迭代与Jacobi 迭代不是包含与被包含关系，Seidel 迭代不能取代Jacobi 迭代。

2.5思考与提高

1.在例题中如果选用||x (k+1)-x (k)||1

2.设y (k+1)是利用Seidel 迭代法由x (k)算出的下一个向量 ，人们又构造出如下称为超松弛迭代格式（Sor 迭代格式）： x (k+1)= x (k)+ω?x= x (k)+ω( y (k+1) –x (k))=(1-ω )x (k)- ωy (k+1)

其中ω称为松弛因子。研究由此编制程序进行求解一个线性方程组的迭代计算情况，运算中要选用不同的松弛因子进行尝试。

3．在解线性方程组时，是否Seidel 迭代法总比Jacobi 迭代法收敛的快？ 4.分析Jacobi 迭代法程序的编程优缺点，你能给出哪些改进？ 5.分析Seidel 迭代法程序的编程优缺点，你能给出哪些改进？

2.6练习

1． 用 Seidel 迭代法求如下线性方程组的解 要求误差||x (k+1)-x (k)||∝<10-8。 2． 用Jacobi 迭代法法解线性方程组

3. 用ω=1.25和0.5的超松弛方法解线性方程组

?????

????-=-+--=++++=-+-+=+-+--=-+-+3322

224343238

243214225432154321

543215422153321x x x x x x x x x x x x x x x x x x x x x x x x x

?????

?

? ??-=??????? ????????? ??-----1102151012402170

183131204321x x x x ????

?????=-=-+-=-+-=-+-=-0

2020202125

4

5434323212

1

x x x x x x x x x x x

x x

要求误差||x(k+1)-x(k)|| <10-8

【免费下载】线性方程组的解空间

第六章 向量空间 6.1 定义和例子 6.2 子空间 6.3 向量的线性相关性 6.4 基和维数 6.5 坐标 6.6 向量空间的同构 6.7 矩阵的秩齐次线性方程组的解空间返回教案总目录6.7矩阵的秩，齐次线性方程组的解空间一、教学思考 1、矩阵的秩与线性方程组解的理论在前面已经有过讨论，本节运用向量空间的有关理论重新认识矩阵的秩的几何意义，讨论线性方程组解的结构。2、注意：齐次线性方程组（含n 个未知量）的解的集合构成n F 的子空间，而非齐次线性方程组的解的集合非也。3、注意具体方法：1）证矩阵的行空间与列空间的维数相等；2）求齐次线性方程组的基础解系。 二、内容要求 1、内容：矩阵的秩的几何意义，齐次线性方程组的解空间。 2、要求：理解掌握矩阵的秩的几何意义，齐次线性方程组的基础解系的求法。三、教学过程 1、矩阵的秩的几何意义几个术语：设)(F M A n m ?∈，????? ??=mn m n a a a a A 1111，A 的每一行看作n F 的一个元素，叫做A 的行向量，用),2,1(m i i =α表示；由),2,1(m i i =α生成的n F 的子空间),,(1m L αα 叫做矩阵A 的行空间。 类似地，A 的每一列看作m F 的一个元素，叫做A 的列向量；由A 的n 个列向量生成的m F 的子空间叫做矩阵A 的列空间。注：)(F M A n m ?∈的行空间与列空间一般不同，分别是n F 与m F 的子空间；下证其维数相同。 引理6.7.1设)(F M A n m ?∈，1）若PA B =，P 是一个m 阶可逆矩阵，则B 与A 有相同的行空间；2）若AQ C =，Q 是一个n 阶可逆矩阵，则C 与A 有相同的列空间。分析：设()()()m m ij n m ij n m ij p P b B a A ???===,,，),2,1(m i i =α是A 的行向量，),2,1(m j j =β是B 的行向量；只需证这两组向量等价。

MATLAB代码 解线性方程组的迭代法

解线性方程组的迭代法 1.rs里查森迭代法求线性方程组Ax=b的解 function[x,n]=rs(A,b,x0,eps,M) if(nargin==3) eps=1.0e-6;%eps表示迭代精度 M=10000;%M表示迭代步数的限制值elseif(nargin==4) M=10000; end I=eye(size(A)); n=0; x=x0; tol=1; %迭代过程 while(tol>eps) x=(I-A)*x0+b; n=n+1;%n为最终求出解时的迭代步数tol=norm(x-x0); x0=x; if(n>=M) disp('Warning:迭代次数太多，可能不收敛！'); return; end end 2.crs里查森参数迭代法求线性方程组Ax=b的解 function[x,n]=crs(A,b,x0,w,eps,M) if(nargin==4) eps=1.0e-6;%eps表示迭代精度 M=10000;%M表示迭代步数的限制值 elseif(nargin==5) M=10000; end I=eye(size(A)); n=0; x=x0; tol=1; %迭代过程 while(tol>eps) x=(I-w*A)*x0+w*b; n=n+1;%n为最终求出解时的迭代步数tol=norm(x-x0); x0=x;

if(n>=M) disp('Warning:迭代次数太多，可能不收敛！'); return; end end 3.grs里查森迭代法求线性方程组Ax=b的解 function[x,n]=grs(A,b,x0,W,eps,M) if(nargin==4) eps=1.0e-6;%eps表示迭代精度 M=10000;%M表示迭代步数的限制值 elseif(nargin==5) M=10000; end I=eye(size(A)); n=0; x=x0; tol=1;%前后两次迭代结果误差 %迭代过程 while(tol>eps) x=(I-W*A)*x0+W*b;%迭代公式 n=n+1;%n为最终求出解时的迭代步数tol=norm(x-x0); x0=x; if(n>=M) disp('Warning:迭代次数太多，可能不收敛！'); return; end end 4.jacobi雅可比迭代法求线性方程组Ax=b的解 function[x,n]=jacobi(A,b,x0,eps,varargin) if nargin==3 eps=1.0e-6; M=200; elseif nargin<3 error return elseif nargin==5 M=varargin{1}; end D=diag(diag(A));%求A的对角矩阵 L=-tril(A,-1);%求A的下三角阵

线性方程组解的几何意义

设有三元非齐次线性方程组 线性方程组解的几何意义 ???????=++=++=++,,,)1(22221111m m m m d z c y b x a d z c y b x a d z c y b x a 我们来讨论一下三元非齐次线性方程组解的几何意义.

2) 有唯一解这时方程组(1) 中的m 个方?? ???=+--=--=+,423, 32,123z y x y x z x 该方程组有唯一解.817,21,4 7??? ??--则方程组(1) 的解有以下三种情况: 1) 无解这时方程组(1) 中的m 个方程所表示的平面既不交于一点, 也不共线、共面. 程所表示的平面交于一点. 例如

其几何意义如图3 -11 所示. 2x-y=-3 3x+2z=-1 x-3y+2z=4 图3-11

交直线所确定.3) 有无穷多组解 这时又可分为两种情形:情形一自由变量, 基础解系中有两个向量，其一般解的形式为 γ=c 1η1+ c 2η2+ γ0(c 1, c 2为任意常数).这时方程组的所有解构成一个平面, 而这个平面是由过点γ0且分别以η1、η2为方向向量的两条相A 的秩=A 的秩= 1 .此时，有两个γ=c 1η1+ c 2η2+ γ0 称为平面的参数方程.

例如, 设保留方程组为 x + y + z = 3, 则可求得其通解为 . 11110101121???? ? ??+????? ??-+????? ??-=c c x

则过点P (1,1,1) 分别以(1,-1,0)T , (1,0,-1)T 为方向,1 10111:,0 11111:21--=-=--=--=-z y x L z y x L 则这两条相交直线L 1, L 2所确定的平面的方程即向量的两直线的方程分别为 为x + y + z = 3 . 如图3-12

线性方程组的解法

线性方程组的解法 1 引言 在科学研究和大型工程设计中出现了越来越多的数学问题，而这些问题往往需要求数值解。在进行数值求解时，经离散后，常常归结为求解形如Ax= b的大型线性方程组。而如插值公式，拟合公式等的建立，微分方程差分格式的构造等，均可归结为求解线性方程组的问题．在工程技术的科学计算中，线性方程组的求解也是最基本的工作之一．因此，线性方程组的解法一直是科学和工程计算中研究最为普遍的问题，它在数值分析中占有极其重要的地位。20世纪50年代至70年代，由于电子计算机的发展，人们开始考虑和研究在计算机上用迭代法求线性方程组Ax =b的近似解，用某种极限过程去逐渐逼近精确解，并发展了许多非常有效的迭代方法，迭代法具有需要计算机存储单元少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点。例如Jacobi方法、Gauss—Seidel 方法、SOR方法、SSOR 方法，这几种迭代方法是最常用的一阶线性定常迭代法。 2 主要算法 20世纪50年代至70年代，人们开始考虑和研究用迭代法求解线性方程组。 Ax = b (1) 的近似解，发展了许多有效的方法，其中有Jacobi方法、Gauss—Seidel方法，SOR方法、SSOR方法，这几种迭代方法均属一阶线性定常迭代法，即若系数矩阵A的一个分裂：A =M-N ；M 为可逆矩阵，线性方程组(1)化为： (M－N)X =b； →M X = NX + b； →X= M -1NX+ M-1b 得到迭代方法的一般公式： X（k+1）=HX（k）+d （2） 其中：H =MN-1，d=M-1b，对任意初始向量X（0） 一阶定常迭代法收敛的充分必要条件是: 迭代矩H的谱半径小于1，即ρ(H) < 1；又因为对于任何矩阵范数恒有ρ(H)≤‖H‖，故又可得到收敛的一个充分条件为：‖H‖< 1。 2.1 Jacobi迭代法 若D为A的对角素构成的对角矩阵，且对角线元素全不为零。系数矩阵A的一个分解：A =

常微分方程的解线性方程组的迭代法

实验五 解线性方程组的迭代法 【实验内容】 对1、设线性方程组 ?? ? ? ?? ? ? ?? ? ? ?? ? ? ??-=???????????????? ?????????????????? ? ?--------------------------211938134632312513682438100412029137264 2212341791110161035243120 536217758683233761624491131512 013012312240010563568 0000121324 10987654321x x x x x x x x x x ()T x 2,1,1,3,0,2,1,0,1,1*--= 2、设对称正定系数阵线性方程组 ?? ? ????? ??? ? ? ??---=????????????? ??????????????? ??---------------------4515229 23206019243360021411035204111443343104221812334161 2065381141402312122 00240424 87654321x x x x x x x x ()T x 2,0,1,1,2,0,1,1*--= 3、三对角形线性方程组

?? ? ?? ? ????? ??? ? ? ??----=???????????????? ?????????????????? ??------------------5541412621357410000000014100000000141000000001410000000014100000000141000000001410000000014100000000 14100000000 1410987654321x x x x x x x x x x ()T x 1,1,0,3,2,1,0,3,1,2*---= 试分别选用Jacobi 迭代法，Gauss-Seidol 迭代法和SOR 方法计算其解。 【实验方法或步骤】 1、体会迭代法求解线性方程组，并能与消去法加以比较； 2、分别对不同精度要求，如54310,10,10---=ε由迭代次数体会该迭代法的收敛快慢； 3、对方程组2，3使用SOR 方法时，选取松弛因子ω=0.8，0.9，1，1.1，1.2等，试看对算法收敛性的影响，并能找出你所选用的松弛因子的最佳者； 4、给出各种算法的设计程序和计算结果。 程序： 用雅可比方法求的程序： function [x,n]=jacobi(A,b,x0,eps,varargin) if nargin==3 eps=1.0e-6; M=200;

解线性方程组的基本思想

四：基本方法 基本思路将在解题的过程中得到体现。 1．（求线性方程组的唯一解或特解），这类问题的求法分为两类：一类主要用于解低阶稠 密矩阵——直接法；一类是解大型稀疏矩阵——迭代法。 1.1利用矩阵除法求线性方程组的特解（或一个解） 方程：AX=b，解法：X=A\b，(注意此处’\’不是’/’) 例1-1 求方程组的解。 解: A = ; = ；b=(1,0,0,0,1)’ 由于>>rank(A)=5,rank( )=5 %求秩，此为R（A）=R（）>=n的情形，有唯一解。 >>X= A\b %求解X =(2.2662, -1.7218, 1.0571,-0.5940, 0.3188)’ 或用函数rref 求解，>>sv=rref(A:b);所得sv的最后一列即为所要求的解。 1．2 利用矩阵的LU、QR和cholesky分解求方程组的解 这三种分解，在求解大型方程组时很有用。其优点是运算速度快、可以节省磁盘空间、节省内存。 I) LU分解又称Gauss消去分解，可把任意方阵分解为下三角矩阵的基本变换形式（行交换）和上三角矩阵的乘积。即A=LU，L为下三角阵，U为上三角阵。 则：A*X=b 变成L*U*X=b 所以X=U\(L\b) 这样可以大大提高运算速度。命令[L，U]=lu (A) 在matlab中可以编如下通用m 文件： 在Matlab中建立M文件如下 % exp1.m A;b; [L，U]=lu (A); X=U\(L\b) II）Cholesky分解 若A为对称正定矩阵，则Cholesky分解可将矩阵A分解成上三角矩阵和其转置的乘积，即：其中R为上三角阵。 方程A*X=b 变成所以 在Matlab中建立M文件如下 % exp2.m A;b; [R’，R]=chol(A); X=R\(R’\b) III）QR分解 对于任何长方矩阵A，都可以进行QR分解，其中Q为正交矩阵，R为上三角矩阵的初等变换形 式，即：A=QR 方程A*X=b 变形成QRX=b 所以X=R\(Q\b)

线性方程组的迭代法及程序实现

线性方程组的迭代法及程序实现 学校代码:11517 学号:200810111217 HENAN INSTITUTE OF ENGINEERING 毕业论文 题目线性方程组的迭代法及程序实现 学生姓名 专业班级 学号 系 (部)数理科学系 指导教师职称 完成时间 2012年5月20日河南工程学院 毕业设计(论文)任务书 题目:线性方程组的迭代法及程序实现专业:信息与计算科学学号 : 姓名一、主要内容: 通过本课题的研究,学会如何运用有限元方法来解决线性代数方程组问题,特别是Gaussie-Seidel迭代法和Jacobi迭代法来求解线性方程组。进一步学会迭代方法的数学思想,并对程序代码进行解析与改进,这对于我们以后学习和研究实际问题具有重要的意义。本课题运用所学的数学专业知识来研究,有助于我们进一步掌握大学数学方面的知识,特别是迭代方法。通过这个课题的研究,我进一步掌握了迭代方法的思想,以及程序的解析与改进,对于今后类似实际问题的解决具有重要的意义。

二、基本要求: 学会编写规范论文,独立自主完成。 运用所学知识发现问题并分析、解决。 3.通过对相关资料的收集、整理,最终形成一篇具有自己观点的学术论文,以期能对线性方程组迭代法的研究发展有一定的实践指导意义。 4.在毕业论文工作中强化英语、计算机应用能力。 完成期限: 2012年月指导教师签名:专业负责人签名: 年月日 目录 中文摘要....................................................................................Ⅰ英文摘要 (Ⅱ) 1 综述 1 2 经典迭代法概述 3 2.1 Jacobi迭代法 3 2.2 Gauss?Seidel迭代法 4 2.3 SOR(successive over relaxation)迭代法 4 2.4 SSOR迭代法 5 2.5 收敛性分析5 2. 6 数值试验 6 3 matlab实现的两个例题8 3.1 例1 迭代法的收敛速度8 3.2 例 2 SOR迭代法松弛因子的选取 12致谢16参考文献17附录19

数值分析5-用Jacobi迭代法和Gauss-Seidel迭代法求解线性方程组

作业六：分别编写用Jacobi迭代法和Gauss-Seidel迭代法求解线性方程组Ax=B的标准程序，并求下列方程组的解。 可取初始向量 X(0) =(0，0，0)’； 迭代终止条件||x(k+1)-x(k)||<=10e-6 （1） = （2） = Jacobi迭代法： 流程图 开 始 判断b中的最大值 有没有比误差大 给x赋初值 进行迭代 求出x，弱到100次还没到，警告不收 结束

程序 clear;clc; A=[8,-1,1;2,10,01;1,1,-5]; b=[1;4;3]; e=1e-6; x0=[0;0;0]'; n=length(A); x=zeros(n,1); k=0; r=max(abs(b)); while r>e for i=1:n d=A(i,i); if abs(d)100 warning('不收敛'); end end x=x0;

程序结果（1）

（2）

Gauss-Seidel迭代法： 程序 clear;clc; %A=[8,-1,1;2,10,01;1,1,-5]; %b=[1;4;3]; A=[5,2,1;-1,4,2;2,-3,10]; b=[-12;20;3]; m=size(A); if m(1)~=m(2) error('矩阵A不是方阵'); end n=length(b); %初始化 N=0;%迭代次数 L=zeros(n);%分解A=D+L+U,D是对角阵，L是下三角阵，U是上三角阵U=zeros(n); D=zeros(n); G=zeros(n);%G=-inv(D+L)*U d=zeros(n,1);%d=inv(D+L)*b x=zeros(n,1); for i=1:n%初始化L和U for j=1:n if ij U(i,j)=A(i,j); end end end for i=1:n%初始化D D(i,i)=A(i,i); end G=-inv(D+L)*U;%初始化G d=(D+L)\b;%初始化d %迭代开始 x1=x; x2=G*x+d; while norm(x2-x1,inf)>10^(-6)

解线性方程组基思想

解线性方程组基思想

————————————————————————————————作者：————————————————————————————————日期：

四：基本方法 基本思路将在解题的过程中得到体现。 1．（求线性方程组的唯一解或特解），这类问题的求法分为两类：一类主要用于解低阶稠 密矩阵——直接法；一类是解大型稀疏矩阵——迭代法。 1.1利用矩阵除法求线性方程组的特解（或一个解） 方程：AX=b，解法：X=A\b，(注意此处’\’不是’/’) 例1-1 求方程组的解。 解: A = ; = ；b=(1,0,0,0,1)’ 由于>>rank(A)=5,rank( )=5 %求秩，此为R（A）=R（）>=n的情形，有唯一解。 >>X= A\b %求解X =(2.2662, -1.7218, 1.0571,-0.5940, 0.3188)’ 或用函数rref 求解，>>sv=rref(A:b);所得sv的最后一列即为所要求的解。 1．2 利用矩阵的LU、QR和cholesky分解求方程组的解 这三种分解，在求解大型方程组时很有用。其优点是运算速度快、可以节省磁盘空间、节省内存。 I) LU分解又称Gauss消去分解，可把任意方阵分解为下三角矩阵的基本变换形式（行交换）和上三角矩阵的乘积。即A=LU，L为下三角阵，U为上三角阵。 则：A*X=b 变成L*U*X=b 所以X=U\(L\b) 这样可以大大提高运算速度。命令[L，U]=lu (A) 在matlab中可以编如下通用m 文件： 在Matlab中建立M文件如下 % exp1.m A;b; [L，U]=lu (A); X=U\(L\b) II）Cholesky分解 若A为对称正定矩阵，则Cholesky分解可将矩阵A分解成上三角矩阵和其转置的乘积，即：其中R为上三角阵。 方程A*X=b 变成所以 在Matlab中建立M文件如下 % exp2.m A;b; [R’，R]=chol(A); X=R\(R’\b) III）QR分解 对于任何长方矩阵A，都可以进行QR分解，其中Q为正交矩阵，R为上三角矩阵的初等变换形 式，即：A=QR 方程A*X=b 变形成QRX=b 所以X=R\(Q\b)

求解线性方程组——超松弛迭代法(c)

求解线性方程组——超松弛迭代法 #include #include using namespace std; float *one_array_malloc(int n); //一维数组分配float **two_array_malloc(int m,int n); //二维数组分配float matrix_category(float* x,int n); int main() { const int MAX=100;//最大迭代次数 int n,i,j,k; float** a; float* x_0; //初始向量 float* x_k; //迭代向量 float precision; //精度 float w; //松弛因子 cout<<"输入精度e:"; cin>>precision; cout<>n; a=two_array_malloc(n,n+1); cout<>a[i][j]; } } x_0=one_array_malloc(n); cout<>x_0[i]; } x_k=one_array_malloc(n);

cout<<"输入松弛因子w (1>w; float temp; //迭代过程 for(k=0;k

线性方程组的解空间

第六章 向量空间 6、1 定义与例子 6、2 子空间 6、3 向量的线性相关性 6、4 基与维数 6、5 坐标 6、6 向量空间的同构 6、7 矩阵的秩齐次线性方程组的解空间 返回教案总目录 6、7矩阵的秩,齐次线性方程组的解空间 一、教学思考 1、矩阵的秩与线性方程组解的理论在前面已经有过讨论,本节运用向量空间的有关理论重新认识矩阵的秩的几何意义,讨论线性方程组解的结构。 2、注意:齐次线性方程组(含n 个未知量)的解的集合构成n F 的子空间,而非齐次线性方程组的解的集合非也。 3、注意具体方法:1)证矩阵的行空间与列空间的维数相等;2)求齐次线性方程组的基础解系。 二、内容要求 1、内容:矩阵的秩的几何意义,齐次线性方程组的解空间。 2、要求:理解掌握矩阵的秩的几何意义,齐次线性方程组的基础解系的求法。 三、教学过程 1、矩阵的秩的几何意义 几个术语:设)(F M A n m ?∈,??? ? ? ??=mn m n a a a a A ΛΛΛ ΛΛ 1111,A 的每一行瞧作n F 的一个元素,叫做A 的行向量,用),2,1(m i i Λ=α表示;由),2,1(m i i Λ=α生成的n F 的子空间 ),,(1m L ααΛ叫做矩阵A 的行空间。 类似地,A 的每一列瞧作m F 的一个元素,叫做A 的列向量;由A 的n 个列向量生成的m F 的子空间叫做矩阵A 的列空间。 注:)(F M A n m ?∈的行空间与列空间一般不同,分别就是n F 与m F 的子空间;下证其维数相同。 引理6、7、1设)(F M A n m ?∈, 1)若PA B =,P 就是一个m 阶可逆矩阵,则B 与A 有相同的行空间; 2)若AQ C =,Q 就是一个n 阶可逆矩阵,则C 与A 有相同的列空间。 分析:设() ()()m m ij n m ij n m ij p P b B a A ???===,,,),2,1(m i i Λ=α就是A 的行向

Gauss-Seidel迭代法求解线性方程组

Gauss-Seidel迭代法求解线性方程组

一． 问题描述 用Gauss-Seidel 迭代法求解线性方程组 由Jacobi 迭代法中，每一次的迭代只用到前一次的迭代值。使用了两倍的存储空间，浪费了存储空间。若每一次迭代充分利用当前最新的迭代值，即在计算第i 个分量 ) 1(+k i x 时，用最新分量 ) 1(1 +k x ， ???+) 1(2 k x ) 1(1 -+k i x 代替旧分量 ) (1 k x ， ???) (2 k x ) (1 -k i x ，可以起 到节省存储空间的作用。这样就得到所谓解方程组的Gauss-Seidel 迭代法。 二． 算法设计 将A 分解成U D L A --=，则b x =A 等价于b x =--U)D (L 则Gauss-Seidel 迭代过程 ) ()1()1(k k k Ux Lx b Dx ++=++ 故 ) ()1()(k k Ux b x L D +=-+ 若设1 )(--L D 存在，则 b L D Ux L D x k k 1)(1)1()()(--+-+-= 令 b L D f U L D G 11)()(---=-=，

则Gauss-Seidel 迭代公式的矩阵形式为 f Gx x k k +=+) () 1( 其迭代格式为 T n x x x x ) ()0()0(2)0(1)0(，，，???= (初始向量)， ) (1 1 1 1 1 )()1()1(∑∑-=-+=++--=i j i i j k j ij k j ij i ii i i x a x a b a x )210i 210(n k ???=???=，，，；，，， 或者 ?? ???--=???=???==?+=∑∑-=-+=+++) (1)210i 210(111 1)()1()1()()1(i j i i j k j ij k j ij i ii i i i k i k i x a x a b a x n k k x x x ，，，；，，， 三． 程序框图

数值计算_第4章 解线性方程组的迭代法

第4章解线性方程组的迭代法 用迭代法求解线性方程组与第4章非线性方程求根的方法相似，对方程组进行等价变换，构造同解方程组(对可构造各种等价方程组， 如分解，可逆，则由得到)，以此构造迭代关系式 （4.1） 任取初始向量，代入迭代式中，经计算得到迭代序列。 若迭代序列收敛，设的极限为，对迭代式两边取极限 即是方程组的解，此时称迭代法收敛，否则称迭代法发散。我们将看到，不同于非线性方程的迭代方法，解线性方程组的迭代收敛与否完全决定于迭代矩阵的性质，与迭代初始值的选取无关。迭代法的优点是占有存储空间少，程序实现简单，尤其适用于大型稀疏矩阵；不尽人意之处是要面对判断迭代是否收敛和收敛速度的问题。 可以证明迭代矩阵的与谱半径是迭代收敛的充分必要条件，其中是矩阵的特征根。事实上，若为方程组的解，则有 再由迭代式可得到

由线性代数定理，的充分必要条件。 因此对迭代法(4.1)的收敛性有以下两个定理成立。 定理4.1迭代法收敛的充要条件是。 定理4.2迭代法收敛的充要条件是迭代矩阵的谱半径 因此，称谱半径小于1的矩阵为收敛矩阵。计算矩阵的谱半径，需要求解矩阵的特征值才能得到，通常这是较为繁重的工作。但是可以通过计算矩阵的范数等方法简化判断收敛的 工作。前面已经提到过，若||A||p矩阵的范数，则总有。因此，若，则必为收敛矩阵。计算矩阵的1范数和范数的方法比较简单，其中 于是，只要迭代矩阵满足或，就可以判断迭代序列 是收敛的。 要注意的是，当或时，可以有，因此不能判断迭代序列发散。

在计算中当相邻两次的向量误差的某种范数小于给定精度时，则停止迭代计算，视为方程组的近似解（有关范数的详细定义请看3.3节。） 4.1雅可比（Jacobi）迭代法 4.1.1 雅可比迭代格式 雅可比迭代计算 元线性方程组 （4.2） 写成矩阵形式为。若将式（4.2）中每个方程的留在方程左边，其余各项移到方程右边；方程两边除以则得到下列同解方程组： 记，构造迭代形式

迭代法解线性方程组

迭代法解线性方程组作业 沈欢00986096 北京大学工学院，北京100871 2011年10月12日 摘要 由所给矩阵生成系数矩阵A和右端项b，分析系数矩阵A，并用Jacobi迭代法、GS迭代法、SOR(逐步松弛迭代法)解方程组Ax=b 1生成系数矩阵A、右端项b,并分析矩阵A 由文件”gr900900c rg.mm”得到了以.mm格式描述的系数矩阵A。A矩阵是900?900的大型稀 疏对称矩阵。于是，在matlaB中，使用”A=zeros(900,900)”语句生成900?900的零矩阵。再 按照.mm文件中的描述，分别对第i行、第j列的元素赋对应的值，就生成了系数矩阵A，并 将A存为.mat文件以便之后应用。 由于右端项是全为1的列向量，所以由语句”b=ones(900,1)”生成。 得到了矩阵A后，求其行列式，使用函数”det(A)”,求得结果为”Inf”,证明行列式太大，matlaB无法显示。由此证明，矩阵A可逆，线性方程组 Ax=b 有唯一解。 接着，判断A矩阵是否是对称矩阵(其实，这步是没有必要的，因为A矩阵本身是对称矩阵，是.mm格式中的矩阵按对称阵生成的)。如果A是对称矩阵，那么 A?A T=0 。于是，令B=A?A T,并对B求∞范数。结果显示： B ∞=0,所以，B是零矩阵，也就是：A是对称矩阵。 然后，求A的三个条件数： Cond(A)= A ? A?1 所求结果是，对应于1范数的条件数为：377.2334;对应于2范数的条件数为：194.5739;对应 于3范数的条件数为：377.2334; 1

从以上结果我们看出，A是可逆矩阵，但是A的条件数很大，所以，Ax=b有唯一解并且矩阵A相对不稳定。所以，我们可以用迭代方法来求解该线性方程组，但是由于A的条件数太大迭代次数一般而言会比较多。 2Jacobi迭代法 Jacobi迭代方法的程序流程图如图所示： 图1:Jacobi迭代方法程序流程图 在上述流程中，取x0=[1,1,...,1]T将精度设为accuracy=10?3，需要误差满足： error= x k+1?x k x k+1

高斯-赛德尔迭代法解线性方程组精选.

数值分析实验五 班级： 10信计二班 学号：59 姓名：王志桃 分数： 一．实验名称 高斯-赛德尔迭代法解线性方程组 二．实验目的 1. 学会利用高斯赛德尔方法解线性方程组 2. 明白迭代法的原理 3. 对于大型稀疏矩阵方程组适用于迭代法比较简单 三．实验内容 利用Gauss-Seidel 迭代法求解下列方程组 ?????=++=-+=+-36123633111420238321 321321x x x x x x x x x ， 其中取→=0)0(x 。 四、算法描述 由Jacobi 迭代法中，每一次的迭代只用到前一次的迭代值，若每一次迭代充分利用当前最新的迭代值，即在计算第i 个分量)1(+k i x 时，用最新分量)1(1+k x ，???+)1(2k x )1(1-+k i x 代替旧分量)(1k x ，???)(2k x )(1-k i x ，就得到所谓解方程组的Gauss-Seidel 迭代法。 其迭代格式为 T n x x x x )()0()0(2)0(1)0(，，，???= (初始向量)， )(11111)()1( ) 1(∑∑-=-+=++--=i j i i j k j ij k j ij i ii i i x a x a b a x )210i 210(n k ???=???=，，，；，，， 或者写为 ?? ???--=???=???==?+=∑∑-=-+=+++)(1)210i 210(1111)( )1()1()()1(i j i i j k j ij k j ij i ii i i i k i k i x a x a b a x n k k x x x ，，，；，，， 五、 编码 #include #include

线性方程组解的判定

第四节 线性方程组解的判定 从本节开始，讨论含有n 个未知量、m 个方程的线性方程组的解。 11112211211222 22 11 22n n n n m m mn n m a x a x a x b a x a x a x b a x a x a x b +++=??+ ++= ????+++=? （13—2） 主要问题是要判断出方程组（13-2）何时有解？何时无解？有解时解有多少？如何求出方程组的解。 线性方程组有没有解，以及有怎样的解，完全决定于方程组的系数和常数项。因此，将线性方程组写成矩阵形式或向量形式，以矩阵或向量作为讨论线性方程组的工具，将带来极大的方便。 方程组（13-2）中各未知量的系数组成的矩阵11121212221 2 n n m m mn a a a a a a A a a a ? ?? ? ? ?=?? ?? ? ? 称为方程组（13-2）的系数矩阵。由各系数与常数项组成的矩阵，称为增广矩阵，记作A ，即 11121121 222212 n n m m mn m a a a b a a a b A a a a b ?? ????=??? ??? 方程组（13-2）中的未知量组成一个n 行、1列的矩阵（或列向量），记作X;常数项组成一个m 行、1 列的矩阵(或列向量），记作b ，即12n x x X x ??????=?????? ,12 m b b b b ?? ????=?????? 由矩阵运算，方程组(13-2)实际上是如下关系111212122212 n n m m mn a a a a a a a a a ? ?? ? ? ? ?? ?? ? ? 12n x x x ???????????? =12m b b b ???????????? 即 AX=b

线性方程组解的判定与解的结构

***学院数学分析课程论文 线性方程组解的判定与解的结构 院系数学与统计学院 专业数学与应用数学（师范） 姓名******* 年级 2009级 学号200906034*** 指导教师 ** 2011年6月

线性方程组解的判定与解的结构 姓名****** （重庆三峡学院数学与计算机科学学院09级数本？班） 摘 要：线性方程组是否有解，用系数矩阵和增广矩阵的秩来刻画．在方程组有解且有 多个解的情况下，解的结构就是了解解与解之间的关系． 关键词：矩阵； 秩； 线性方程组； 解 引言 通过系数矩阵和增广矩阵的秩是否相同来给出判定线性方程组的解的判别条件．在了解了线性方程组的判别条件之后，我们进一步讨论解的结构．对于齐次线性方程组，解的线性组合还是方程组的解．在线性方程组有无穷个解时可用有限多个解表示出来．另外以下还涉及到线性方程组通解的表达方式． 1 基本性质 下面我们分析一个线性方程组的问题，导出线性方程组有解的判别条件． 对于线性方程组 1111221121122222 1122n n n n s s sn n s a x a x a x b a x a x a x b a x a x a x b ++???+=??++???+=???????++???+=? (1) 引入向量 112111s αααα??????=?????????，122222s αααα??????=?????????，…12n n n sn αααα??????=????????? ，12s b b b β?? ?? ??=??????? ?? 方程（1）可以表示为 1122n n x x x αααβ++???+= 性质 线性方程组⑴有解的充分必要条件为向量β可以表成向量组α1,α2,…，αn 的线性组合. 定理1 线性方程组⑴有解的充分必要条件为它的系数矩阵

实验解线性方程组的基本迭代法实验

数值分析实验报告

0 a 12 K a 1,n 1 K a 2,n 1 U O M 则有： 第一步： Jacobi 迭代法 a 1n a 2n M , 则有： A D L U a n 1,n Ax b A A x D b L U (D L U)x b Dx (L U)x b x D (L U)x D b 令 J D (L U) 则称 J 为雅克比迭代矩阵 f D b 由此可得雅克比迭代的迭代格式如下： x (0) , 初始向量 x (k 1) Jx (k) f ,k 0,1,2,L 第二步 Gauss-Seidel 迭代法 Ax b (D L U )x b (D L)x Ux b x (D L) Ux (D L) b A D L U a 11 a 12 L a 1n a 11 A a 21 a 22 L a 2n a 22 M MM MO a n1 a n2 L a nn a 11 得到 D a 22 O a nn 由 a 21 0 M M O a n 1,1 a n 1,2 L 0 a nn a n1 a n2 L a n,n a 21 L M M O a n 1,1 a n 1,2 L a n1 a n2 L a n,n 1 a 12 K a 1,n 1 a 1n 0 K a 2,n 1 a 2n O M M a n 1,n 10

令 G (D L) U ，则称G 为Gauss-Seidel 迭代矩阵 f (D L) b 由此可得 Gauss-Seidel 迭代的迭代格式如下： x (0) , 初始向量 第三步 SOR 迭代法 w0 AD L U 1 ( D 1 wL ((1 w)D wU )) (D 1 wL) ((1 w)D wU ) w w w 令M w 1 (D wL), N 1 ((1 w)D wU )则有：A MN w w Ax b AM L W N M (M N )x b Mx Nx b x M Nx M b N M, 令W f Mb 带入 N 的值可有 L W ((1 w)D wU) (D wL) 1((1 w)D wU) (D wL) f 1 b w 1(D wL) 1b 1 (D wL) w 称 L W 为 SOR 迭代矩阵，由此可得 SOR 迭代的迭代格式如下： x (0) ,初始向量 二、算法程序 Jacobi 迭代法的 M 文件： function [y,n]=Jacobi(A,b,x0,eps) %************************************************* %函数名称 Jacobi 雅克比迭代函数 %参数解释 A 系数矩阵 % b 常数项 % x0 估计解向量 x (k 1) Gx (k) f ,k 0,1,2,L (k 1) f,k 0,1,2,L

线性方程组的解空间

第六章 向量空间 6.1 定义和例子 6.2 子空间 6.3 向量的线性相关性 6.4 基和维数 6.5 坐标 6.6 向量空间的同构 6.7 矩阵的秩齐次线性方程组的解空间 返回教案总目录 6.7矩阵的秩，齐次线性方程组的解空间 一、教学思考 1、矩阵的秩与线性方程组解的理论在前面已经有过讨论，本节运用向量空间的有关理论重新认识矩阵的秩的几何意义，讨论线性方程组解的结构。 2、注意：齐次线性方程组（含n 个未知量）的解的集合构成n F 的子空间，而非齐次线性方程组的解的集合非也。 3、注意具体方法：1）证矩阵的行空间与列空间的维数相等；2）求齐次线性方程组的基础解系。 二、内容要求 1、内容：矩阵的秩的几何意义，齐次线性方程组的解空间。 2、要求：理解掌握矩阵的秩的几何意义，齐次线性方程组的基础解系的求法。 三、教学过程 1、矩阵的秩的几何意义 几个术语：设)(F M A n m ?∈，???? ? ??=mn m n a a a a A 1111，A 的每一行看作n F 的一 个元素，叫做A 的行向量，用),2,1(m i i =α表示；由),2,1(m i i =α生成的n F 的子空间),,(1m L αα 叫做矩阵A 的行空间。 类似地，A 的每一列看作m F 的一个元素，叫做A 的列向量；由A 的n 个列向量生成的m F 的子空间叫做矩阵A 的列空间。 注：)(F M A n m ?∈的行空间与列空间一般不同，分别是n F 与m F 的子空间；下证其维数相同。 引理6.7.1设)(F M A n m ?∈， 1）若PA B =，P 是一个m 阶可逆矩阵，则B 与A 有相同的行空间； 2）若AQ C =，Q 是一个n 阶可逆矩阵，则C 与A 有相同的列空间。 分析：设()()()m m ij n m ij n m ij p P b B a A ???===,,，),2,1(m i i =α是A 的行向量，),2,1(m j j =β是B 的行向量；只需证这两组向量等价。

解线性方程组的直接法和迭代法

数值分析方法中方程求解的直接法和迭代法 第3章 解线性方程组的直接法 一、 消元法 1. 高斯消元法(加减消元)：首先将A 化为上三角阵，再回代求解。 11121121222212n n n n nn n a a a b a a a b a a a b ?? ? ? ? ??? (1)(1)(1)(1)(1)11 121311(2)(2)(2)(2)222322 (3)(3)(3)3333()()000 00 n n n n n nn n a a a a b a a a b a a b a b ?? ? ? ? ? ? ?? ? 步骤如下： 第一步：1 11 1,2,,i a i i n a -? +=第行第行 11121121222212 n n n n nn n a a a b a a a b a a a b ?? ? ? ? ??? 111211(2)(2)(2)2222 (2)(2)(2)2 00n n n nn n a a a b a a b a a b ?? ? ? ? ??? 第二步：(2)2 (2)222,3, ,i a i i n a -?+=第行第行 111211(2)(2)(2)2222 (2)(2)(2)200n n n nn n a a a b a a b a a b ?? ? ? ? ?? ? 111213 11 (2)(2)(2)(2) 222322 (3)(3)(3) 33 33(3)(3)(3) 3 00000n n n n nn n a a a a b a a a b a a b a a b ?? ? ? ? ? ? ?? ? 类似的做下去，我们有： 第k 步：() ()k ,1, ,k ik k kk a i i k n a -?+=+第行第行。 n －1步以后，我们可以得到变换后的矩阵为：