方程求根的迭代法

§4.1 引 言

绪论中讲到方程求根得二分法，但二分法收敛速度慢，有必要掌握新的方法。 §4.1.1迭代法的思想

迭代法是一种逐次逼近法，使用某个固定公式（迭代公式）反复校正，逐步精确，直到满足精度。

迭代法求根分两步： 1） 猜测初值 2）迭代

如求解初值问题00'

)(),,(y x y y x f y ==用梯形公式

111[(,)(,)2

n n n n n n h y y f x y f x y +++≈+

+ （1）

看作关于1+n y 的函数方程，按欧拉公式提供猜测值),()

0(1n n n n y x hf y y +=+，代入（1）得

)],(),([2

)

0(11)

1(1+++++

=n n n n n n y x f y x f h y y

若)

1(1+n y 仍不满足要求，则将它代入（1）式，继续得到校正值)

2(1+n y ，写成迭代公式

)],(),([2

)

(11)

1(1

k n n n n n k n y x f y x f h y y ++++++

= （2）

一般地，为了求一元非线性方程0)(=x f 的根，可以先将其转换为如下的等价形式

()x x ?= （3）

式（3）中连续函数()x ?称为迭代函数，其右端含未知数，不能直接求解。先用根的某个猜测值0x 代入（3），构造迭代公式：()k k x x ?=+1。如果迭代值k x 有极限，则称迭代收敛，极限值k k x x ∞

→=lim *

就是方程（3）的根。

几何意义P127图4-1

为使迭代法有效，必须保证它的收敛行，()x ?满足什么条件，才能保证收敛？以最简单的线性迭代()d kx x +=?，可以看出收敛的充分必要条件()1'

<=k x ?。几何意义P127

图4-2,3,4,5。

§4.1.3 压缩映像原理

设*

x 是方程()x x ?=的根，则由微分中值定理

))(()()(*

'*1*

k k k x x

x x x x

-=-=-+ε???，如果存在10<≤L ，使得

],[b a x ∈有()

k k x x L x x L x -≤-?≤+*

1*'

?

，则迭代误差0e L e k

k ≤，由于10<≤L ，

故0→k e ，即迭代收敛。

需注意，上述过程中需保证一切迭代值k x 全落在],[b a ，为此要求对任意],[b a x ∈，总有],[)(b a x ∈?。

综上，压缩映像原理：

定理 1 设()x ?在],[b a 上具有连续的一阶导数，满足条件： （1）对任意],[b a x ∈，总有],[)(b a x ∈?。 映内性

（2）存在10<≤L ，使得对于任意],[b a x ∈成立()L x ≤'

?。 压缩性

则迭代过程()k k x x ?=+1对于任意初值],[0b a x ∈均收敛于方程()x x ?=的根*

x ，且

有下列误差估计式：

)

8(1)

7(1101*1*

x x L

L

x x x x L x x k

k k k k --≤

---≤-+

证明：

由k k x x L x x -≤-+*

1*

有

k k k k k k x x L x x x x x x x x ---≥---≥-++*

*

1*

*

1

从而有k k k x x

L x x --≥-+*

1)1(，（7）式得证

()111'

)()(--+-≤-=-?≤k k k k k k x x L x x x x L x ???

011x x L x x k k k -≤-+，结合（7）式得01*

1x x L

L

x x k

k --≤

-

由（7）式知只要1,+k k x x 的偏差足够小，就能保证迭代值1+k x 足够准确，可用k

k x x -+1来控制迭代过程是否结束。流程图见P128图4－6。

例1 P130 P142题3，5，6，7

注意迭代函数的选择，同一方程，可以采用不同的迭代函数，但迭代函数可能不收敛，或收敛缓慢，迭代函数的选择非常重要。

§4.1.3 迭代过程的局部收敛性

在方程求根的迭代法中，迭代函数()x x ?=的确定，至关重要，它直接影响着迭代法的收敛性。但在实际应用中，同一个方程可以等价导出不同的迭代函数，而且要严格地利用定理1的条件判断迭代公式在整个区间],[b a 内收敛（全局收敛）也非常困难，因此常常判

断迭代公式的局部收敛性。

通常在根*

x 的邻近考察。如果存在邻域δ≤-?*

:x

x ，使得迭代过程对于任意初值

?∈0x 均收敛，这种收敛性称为局部收敛性。

定理 2 设()x ?在()x x ?=的根*

x 邻近有一阶导数，且成立()1*

'

?，则迭代过程

()k k x x ?=+1在*

x 邻近具有局部收敛性。

证：存在充分小邻域δ≤-?*

:x x ，使()1'

<≤L x ?，L 为某个定数，根据微分中值定理：

))(()()(*

'

*

x x x x -=-ε???，注意到()*

*x

x ?=，又当?∈x 时?∈ε，故有

δ?≤-≤-≤-x x x x L x

x *

**

)(，即),()(*

δ?x x ?∈

由定理1知()k k x x ?=+1对于任意?∈0x 均收敛。 例2 P131

§4.1.4 收敛速度

迭代误差*

x x e k k -=，当∞→k 时C e

e p

k

k →+1，称迭代过程为P 阶收敛的，P ＝1称

线性收敛，P ＝2称为平方收敛。

对于在根*

x 邻近收敛的迭代公式()k k x x ?=+1，由于))((*

'

1*

k k x x x x -=-+ε?，式

中ε介于k x 和*

x 之间，故有

∞→→+k x e e k

k ),(*'1?，若0)(*

'≠x ?，则为线性收敛。

若0)(*

'

=x ?，将()k x ?在*

x 处进行泰勒展开有：

()2

*'

'*

)(2

)

()(x x x x k k -+

=ε???，又()k k x x ?=+1，()*

*

x

x ?=，由上式知

∞→→

+k x e e k

k ,2

)

(*

''2

1?，表明当0)(*'=x ?，0)(*

''≠x ?时平方收敛。

故有下述论断：

定理 3 设()x ?在()x x ?=在根*

x 的邻近有连续的二阶导数，且()1'

0)(*'≠x ?时线性收敛；当0)(*'=x ?，0)(*

''≠x ?时平方收敛。

例 P146题3

§4.2 迭代过程的加速

§4.2.1 迭代公式的加工

迭代过程收敛缓慢，计算量将很大，需要进行加速。

设k x 是根*

x 的某个近似值，用迭代公式校正一次得()k k x x ?=+1，假设)('x ?在所考

察得范围内变化不大，其估计值为L ，则有：

k k k k x L L

x L x x x L x x --

-≈

?-≈-++111

)(1*

*

1*

有迭代公式k k k x L

L x L

x ---=++1111

1，是比1+k x 更好的近似根。这样加工后的计算过程为：

迭代()k k x x ?=+1 改进k k k x L

L

x L x --

-=++111

11

合并的])([111

k k k Lx x L

x --=+? 例3 P133 §4.2.1 埃特金算法

上述加速方法含有导数()x '

?，不便于计算。设将迭代值()k k x x ?=+1再迭代一次，又

得()

11~++=k k x x ?，由于)(~1*1*++-≈-k k x x L x x

又)(*1*k k x x L x x -≈-+，消去L 得

k

k k k k k k k k k x x x x x x x x x x x x x x x +---≈?--≈--++++++++112

111*1**1*1*2~)~(~~ 计算过程如下： 迭代()k k x x ?=+1 迭代()

11~++=k k x x ? 改进k

k k k k k k x x x x x x x +---

=++++++112

11112~)

~(~

§4.3 牛顿法

§4.3.1 公式的导出

对于方程0)(=x f ，设已知它的近似根k x ，函数)(x f 在k x 处可用一阶泰勒展开来近

似))(()()('

k k k x x x f x f x p -+=，取0)(=x p 的根作为0)(=x f 的新的近似根，记作

1+k x ，则：)

()('

1k k k k x f x f x x -

=+，这就是牛顿公式，相应的迭代函数是)

()()('

x f x f x x -

=?

牛顿法是一种逐步线性化方法，将非线性方程0)(=x f 的求根问题归结为计算一系列

0))(()('

=-+k k k x x x f x f 的根。

牛顿法几何意义是：(牛顿法亦称切线法，直线经过))(,(k k x f x 、)0,(1+k x ) ，流程图P136 图4－9

例5： P137

牛顿法收敛很快。其迭代公式2

'

'

''

'

)]

([)()()()

()()(x f x f x f x x f x f x x =

?-

=??假定*

x 是

0)(=x f 的单根，即0)(*=x f ，0)(*'≠x f ，则由上式知0)(*

'=x ?。故牛顿法至少平

方收敛

定理4 牛顿法在0)(=x f 的单根*

x 附近为平方收敛。(局部收敛)

证：1）由2

'

'

''

)]

([)()()(x f x f x f x =

?知10)(*

'<=x ?，故其局部收敛。

2）2

*'

*

'*)(2

)())(()()(k k k k x x f x x x f x f x f -+

-+=ε

1'

''

1)()()()

()(++-=-?-=k k k k k k k k k x x f x x f x f x f x f x x

代入得2

*'

1*

'*)(2

)())(()(0k k k x x f x x x f x f -+

-==+ε

由上式得)

(2)(lim

*

'

*

''2

1x f x f e e k

k k →

+∞

→，故单根时平方收敛。

但当*

x 是0)(=x f 的重根时，牛顿法线性收敛。 因)()

()(*x g x x x f m

-=，其中)(x g 有二阶导数，且0)(*'≠x g

)

()()()()()

()()()

()

()()()()('

*

*

'

*1

**

'

x g x x x mg x g x x x x g x x x g x x m x g x x x x f x f x x m m m

-+--

=-+---

=-=-?2

'

*

2

'

'2

*

'

*

'

]

)

()

()(1[)

()()()

()(2)

()11()(x mg x g x x x g m x g x x x mg x g x x m

x -+-+-+-=

?

故)11()(*'m

x -

=?，当m>1时0)(*

'

≠x ?，且有1)(*

'

§4.3.2 开方公式

给定正数c ，用牛顿法解二次方程c x =2

的计算公式)(2

11k

k k x C x x +

=

+，设k x 是近似

根，则

k

x C 也是近似根，它们的算术平均将是更好的近似值。

定理5 开方公式对于任意给定初值00>x 均为平方收敛。 证明：2

11)(21)(21c x x c x x C x x k k

k k

k k -

=

-

?+

=

++（15）

2

11)

(21)(2

1c x x c x x C x x k k

k k

k k +

=

+

?+

=

++

两式相除得

k

c

x c x c

x c x c x c x c x c x k k k k k k 2

002

11)

(

)(

+

-=+

-?

+

-=+

-++

令c

x c x q +

-=

00，则由上式得c q

q x k

k

k 2

211-+=

对任意00>x ，总有1

，收敛性得证。

由（15），迭代误差c x e k k -

=，有

c

e

e k

k 212

1→

+，迭代过程为平方收敛。

§4.3.3牛顿下山法

例7 P138

为防止迭代发散，通常对迭代过程附加一项要求，即保证函数单调下降：)()(1k k x f x f <+，称为下山法。将牛顿法与下山法结合，在下山法保证函数值稳定下降

得前提下，用牛顿法加快收敛速度。

由牛顿法有)

()('

1k k k k x f x f x x -

=+，与前一步的近似值k x 适当加权平均作为新值1+k x ：

)

()()1('

111k k k k k k k x f x f x x x x x λ

λλ-=?-+=+++

其中，10≤<λ称为下山因子，选取适当的下山因子10≤<λ使单调条件成立。下山因子的选择，可从1=λ开始反复折半，一旦单调性条件成立，称下山成功。如果单调性条件始终不成立，则下山失败，需要重新选择初值进行计算。

牛顿法的收敛性强烈依赖于初值0x 的选择，实际计算中，可先采用二分法，求得足够精确的近似值0x ，再用牛顿法。 §4.4 弦截法

牛顿法的收敛速度快，但需要提供导数值)('

k x f ，如果)(x f 比较复杂，导数的计算困难，为避免求导数，改用差商

0)

()(x x x f x f k k --替换牛顿法中的导数，得到：

)()

()()(001x x x f x f x f x x k k k k k ---

=+ （19）

该公式的几何意义如图，用差商代替弦线的斜率，称为弦截法。

迭代函数)()

()()()(00x x x f x f x f x x ---

=?，求导得

*0*

*

'0

*

0*

'*

')

()()

(1)()

()(1)(x x x f x f x f x x x f x f x ---

=-+

=?

当0x 充分接近*x 时1)(0*

'<

1

1)

()(----k k k k x x x f x f 替代牛顿公式中的导数，得

)()

()()(111--+---=k k k k k k k x x x f x f x f x x

称为快速弦截法。是一种两步法。

迭代法求解线性方程组的研究

迭代法求解线性方程组的研究 【摘要】:本文总结了解线性方程组的三个迭代法，Jacobi 迭代法，Gauss-seidel 迭代法，SOR 迭代法，并且介绍了现代数值计算软件MATLAB 在这方面的应用，即分别给出三个迭代法的数值实验。 【关键字】:Jacobi 迭代法 Gauss-seidel 迭代法 SOR 迭代法 数值实验 一． 引言 迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法，它是解高阶稀疏方程组的重 要方法。 迭代法的基本思想是用逐次逼近的方法求解线性方程组。 设有方程组 b Ax = …① 将其转化为等价的，便于迭代的形式 f Bx x += …② (这种转化总能实现，如令b f A I B =-=,), 并由此构造迭代公式 f Bx x k k +=+)() 1( …③ 式中B 称为迭代矩阵，f 称为迭代向量。对任意的初始向量) 0(x ，由式③可求得向量序列 ∞0)(}{k x ，若*) (lim x x k k =∞ →，则*x 就是方程①或方程②的解。此时迭代公式②是收敛的，否则称为发散的。构造的迭代公式③是否收敛，取决于迭代矩阵B 的性质。 本文介绍三种解线性方程组的最主要的三种迭代法：Jacobi 迭代法，Gauss-Seidel 迭代法和SOR 迭代法。本文结构如下：第二部分介绍Jacobi 迭代法及其数值实验，第三部分介绍Gauss-Seidel 迭代法及其数值实验，第四部分介绍SOR 迭代法及其数值实验，第五部分总结。 二． 雅克比（Jacobi ）迭代法 1. 雅克比迭代法的格式 设有方程组

),,3,2,1(1 n i b x a j j n j ij ==∑= …① 矩阵形式为b Ax =,设系数矩阵A 为非奇异矩阵，且),,3,2,1(,0n i a ii =≠ 从式①中第i 个方程中解出x ，得其等价形式 )(1 1 1j n j j ij ii i x a b a x ∑≠=-= …② 取初始向量),,,() 0()0(2)0(1) 0(n x x x x =，对式②应用迭代法，可建立相应的迭代公式： )(11 1)() 1(∑≠=++-=n j j i k j ij ii k i b x a a x …③ 也可记为矩阵形式： J x J k F B x k +==) () 1( …④ 若将系数矩阵A 分解为A=D-L-U ，式中 ???? ? ? ? ??=nn a a a D 2211， ?? ? ?? ?? ? ??=--00 00121323121nn n n a a a a a a L ， ?? ? ??? ? ? ? ?=--00 00122311312n n n n a a a a a a D 。 则方程Ax=b 变为 b x U L D =--)( 得 b x U L Dx ++=)( 于是 b D x U L D x 1 1 )(--++=

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

第五章 解线性方程组的迭代法 本章主要内容： 迭代法收敛定义，矩阵序列收敛定义，迭代法基本定理，雅可比迭代法，高斯-塞德尔迭代法，系数矩阵为严格对角占优阵的采用雅可比迭代、高斯-塞德尔迭代的收敛性。 教学目的及要求： 使学生了解迭代法收敛定义，迭代法基本定理，掌握雅可比迭代法、高斯-塞德尔迭代法。 教学重点： 雅可比迭代法，高斯-塞德尔迭代法。 教学难点： 迭代法基本定理的证明以及作用。 教学方法及手段： 应用严格的高等代数、数学分析知识，完整地证明迭代法基本定理，讲清雅可比迭代法与高斯-塞德尔迭代法的关系，介绍雅可比迭代法与高斯-塞德尔迭代法在编程中的具体实现方法。 在实验教学中，通过一个具体实例，让学生掌握雅可比迭代法与高斯-塞德尔迭代法的具体实现，并能通过数值计算实验，揭示高斯-塞德尔迭代法是对雅可比迭代法的一种改进这一事实。 教学时间： 本章的教学的讲授时间为6学时，实验学时4学时。 教学内容： 一 迭代法定义 对于给定的线性方程组x Bx f =+，设它有唯一解*x ，则 **x Bx f =+ (6.1) 又设(0)x 为任取的初始向量，按下述公式构造向量序列 (1)(),0,1,2,k k x Bx f k +=+=L (6.2) 这种逐步代入求近似解的方法称为迭代法（这里B 与f 与k 无关）。如果() lim k k x →∞ 存在 （记为*x ），称此迭代法收敛，显然*x 就是方程组的解，否则称此迭代法发散。 迭代法求方程近似解的关键是是讨论由(6.1)式所构造出来的向量序列() {} k x 是否收敛。为此，我们引入误差向量 (1)(1)*k k x x ε++=- 将(6.2)式与(6.1)式相减，我们可得 (1)*()*()k k x x B x x +-=- (1)(),0,1,2,k k B k εε+==L 递推下去，得 ()(1)2(2)(0)k k k k B B x B x εε--====L

求解线性方程组——超松弛迭代法(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

线性方程组的迭代求解java

线性方程组的迭代求解 摘要 迭代法是一种逐次逼近方法，在使用迭代法解方程组时，其系数矩阵在计算过程中始终不变。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行。迭代法具有循环的计算方法，方法简单，适宜解大型稀疏矩阵方程组 本文总结了解线性方程组的三个迭代法，Jacobi迭代法，Gauss-Seidel迭代法，SOR 迭代法，并且介绍了软件JA V A在这方面的应用。 关键词： Jacobi迭代法；Gauss-Seidel迭代法；SOR迭代法；计算

SOLUTION OF LINEAR EQUATIONS OF ITERATION WITH THE EXPERIMENTAL ABSTRACT Iteration is a kind of method to solve questions by step-by-step approximation. When we are getting the solution of linear equations by using iteration, the coefficient matrix is always staying the same in computation process. Computer could operate fastly so that it is suitable for operating again and again. Iteration is easy to operate to solve the large matrix equations by using a calculate method called circulation. This summary understanding of linear equations three kind of iteration, Jacobi iteration, Gauss-Seidel iteration, successive over relaxation method ,and introduce modern software JA V A in this respect. Key words:Jacobi iteration; Gauss-Seidel iteration; Successive Over Relaxation method ; calculating

方程求根的迭代法

§4.1 引 言 绪论中讲到方程求根得二分法，但二分法收敛速度慢，有必要掌握新的方法。 §4.1.1迭代法的思想 迭代法是一种逐次逼近法，使用某个固定公式（迭代公式）反复校正，逐步精确，直到满足精度。 迭代法求根分两步： 1） 猜测初值 2）迭代 如求解初值问题00' )(),,(y x y y x f y ==用梯形公式 111[(,)(,)2 n n n n n n h y y f x y f x y +++≈+ + （1） 看作关于1+n y 的函数方程，按欧拉公式提供猜测值),() 0(1n n n n y x hf y y +=+，代入（1）得 )],(),([2 ) 0(11) 1(1+++++ =n n n n n n y x f y x f h y y 若) 1(1+n y 仍不满足要求，则将它代入（1）式，继续得到校正值) 2(1+n y ，写成迭代公式 )],(),([2 ) (11) 1(1 k n n n n n k n y x f y x f h y y ++++++ = （2） 一般地，为了求一元非线性方程0)(=x f 的根，可以先将其转换为如下的等价形式 ()x x ?= （3） 式（3）中连续函数()x ?称为迭代函数，其右端含未知数，不能直接求解。先用根的某个猜测值0x 代入（3），构造迭代公式：()k k x x ?=+1。如果迭代值k x 有极限，则称迭代收敛，极限值k k x x ∞ →=lim * 就是方程（3）的根。 几何意义P127图4-1 为使迭代法有效，必须保证它的收敛行，()x ?满足什么条件，才能保证收敛？以最简单的线性迭代()d kx x +=?，可以看出收敛的充分必要条件()1' <=k x ?。几何意义P127 图4-2,3,4,5。 §4.1.3 压缩映像原理 设* x 是方程()x x ?=的根，则由微分中值定理 ))(()()(* '*1* k k k x x x x x x -=-=-+ε???，如果存在10<≤L ，使得 ],[b a x ∈有() k k x x L x x L x -≤-?≤+* 1*' ? ，则迭代误差0e L e k k ≤，由于10<≤L ， 故0→k e ，即迭代收敛。

π计算方法,二元一次和二元二次方程求根公式,一元n次方程

π的计算方法 如图，这是一个正五边形和它的外切圆。AD平分∠EDB，AC⊥交于BD与点C.已知外切圆的半径为5cm。求正五边形的周长？ 根据题目可以求出∠EDB= ? = - 108 5 180 * 2 5） （ ∵AD为∠EDB角平分线 ∴∠ADC=∠EDA=108*(1/2)=54° ∵AD=5cm,∠ADC=54° ∴CD=cos54°*5cm ∴BD=2CD=2*cos54°*5cm ∴C[正五边形] =2*cos54°*5cm*5=50*cos54° 如图，这是一个正n边形和它的外切圆。AD平分∠EDB，AC⊥交于BD与点C.已知外切圆的半径为rcm。求正n边形的周长与它的外切圆直径之比？根据题目可以求出∠ EDB= ?- n n180 * 2） （ ∵AD为∠EDB角平分线

∴∠ADC=∠EDA=n n n 2180*2n 21*180*2）（）（-=- ∵AD=rcm,∠ADC=n 2180*2-n ）（ ∴CD=r n *)2180*2-n cos(）（ ∴BD=2CD=2*r n *)2180*2-n cos(）（ ∴C[正五边形]=2*n **)2180*2-n cos(r n ）（ ∴π=n r n r n C C n *)2n 180*2)-(n cos(2*2**)2180*)2n ((cos =-=≈它外切圆直径 直径边形正圆（180单位为°）

)2180)2n (tan(*)2180)2n (tan(na n *)2180)2n (tan(2*a 5.0*)2180)2n (tan(5.0*)2180)2n (tan()2180)2n (tan(5.02180)2n (,180)2n (a 5.0,a n n a n n a C a n n G a n GH n a HG AH HG n FAG BAF AG n BAF HF AH AF H AF GH G AF FG AG AF n G n n AFG n -=-≈≈∴=-=-∴-=∴-==-=∠∴∠-=∠==∴∴⊥∴==直径边形周长外接正π直径为圆平方中点 为等腰三角形三线合一 的切线 为圆边形的内接圆。为正边形，圆已知；这是一个正边形一部分 为等腰△是正边形，△假设这是个正正多边形ΘΘΘΘΘ 二元一次方程的求根公式

SOR迭代法求解线性方程组

实验三：用SOR 迭代法求解线性方程组 ?????? ? ??=??????? ????????? ??----------74.012.018.168.072.012.006.016.012.001.103.014.006.003.088.001.016.014.001.076.04321x x x x 取初始点T x )0,0,0,0()0(=，松弛因子05.1=ω，精度要求610-=ε。 1，建立SOR.m 函数文件，此函数文件可调用，程序源码如下： function [x,n]=SOR(A,b,x0,w,eps,M) if nargin==4 eps= 1.0e-6;%精度要求 M = 200; elseif nargin<4 error; return elseif nargin ==5 M = 200; end if(w<=0 || w>=2) error; return; end D=diag(diag(A)); %求A 的对角矩阵 L=-tril(A,-1); %求A 的下三角阵 U=-triu(A,1); %求A 的上三角阵 B=inv(D-L*w)*((1-w)*D+w*U); f=w*inv((D-L*w))*b; x=B*x0+f; n=1; %迭代次数 while norm(x-x0)>=eps x0=x; x =B*x0+f; n=n+1; if(n>=M) disp('Warning: 迭代次数太多，可能不收敛！'); return; end end

2，输入矩阵。并根据要求调用函数，运行结果如下图所示： 即经过7次迭代算出结果，且求得： 1.27151.28440.48581.2843x ?? ? ?= ? ???

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

线性方程组的迭代法及程序实现 学校代码: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

差分方程的解法分析及MATLAB实现(程序)

差分方程的解法分析及MATLAB 实现（程序） 摘自：张登奇,彭仕玉.差分方程的解法分析及其MATLAB 实现[J]. 湖南理工学院学报.2014(03) 引言 线性常系数差分方程是描述线性时不变离散时间系统的数学模型,求解差分方程是分析离散时间系统的重要内容.在《信号与系统》课程中介绍的求解方法主要有迭代法、时域经典法、双零法和变换域 法[1]. 1 迭代法 例1 已知离散系统的差分方程为)1(3 1)()2(81)1(43)(-+=-+--n x n x n y n y n y ,激励信号为)()4 3()(n u n x n =,初始状态为21)2(4)1(=-=-y y ，.求系统响应. 根据激励信号和初始状态,手工依次迭代可算出24 59)1(,25)0(==y y . 利用MATLAB 中的filter 函数实现迭代过程的m 程序如下: clc;clear;format compact; a=[1,-3/4,1/8],b=[1,1/3,0], %输入差分方程系数向量,不足补0对齐 n=0:10;xn=(3/4).^n, %输入激励信号 zx=[0,0],zy=[4,12], %输入初始状态 zi=filtic(b,a,zy,zx),%计算等效初始条件 [yn,zf]=filter(b,a,xn,zi),%迭代计算输出和后段等效初始条件 2 时域经典法 用时域经典法求解差分方程:先求齐次解；再将激励信号代入方程右端化简得自由项,根据自由项形 式求特解；然后根据边界条件求完全解[3].用时域经典法求解例1的基本步骤如下. （1）求齐次解.特征方程为081432=+-αα,可算出4 1 , 2121==αα.高阶特征根可用MATLAB 的roots 函数计算.齐次解为. 0 , )4 1()21()(21≥+=n C C n y n n h （2）求方程的特解.将)()4 3()(n u n x n =代入差分方程右端得自由项为 ?????≥?==-?+-1,)4 3(9130 ,1)1()43(31)()43(1n n n u n u n n n 当1≥n 时,特解可设为n p D n y )4 3()(=,代入差分方程求得213=D . （3）利用边界条件求完全解.当n =0时迭代求出25)0(=y ,当n ≥1时,完全解的形式为 ,)4 3(213 )41()21()(21n n n C C n y ?++=选择求完全解系数的边界条件可参考文[4]选)1(),0(-y y .根据边界条件求得35,31721=-=C C .注意完全解的表达式只适于特解成立的n 取值范围,其他点要用 )(n δ及其延迟表示,如果其值符合表达式则可合并处理.差分方程的完全解为

数值计算_第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）中每个方程的留在方程左边，其余各项移到方程右边；方程两边除以则得到下列同解方程组： 记，构造迭代形式

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

一． 问题描述 用Gauss-Seidel 迭代法求解线性方程组 由Jacobi 迭代法中，每一次的迭代只用到前一次的迭代值。使用了两倍的存储空间，浪 费了存储空间。若每一次迭代充分利用当前最新的迭代值，即在计算第i 个分量) 1(+k i x 时， 用最新分量) 1(1 +k x ，???+) 1(2 k x ) 1(1 -+k i x 代替旧分量)(1k 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(，，，???= (初始向量)， )(1111 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 ，，，；，，， 三． 程序框图

差分方程求解

例题：已知差分方程51 (2)(1)()(+1)+0.5()66 x k x k x k r k r k +-++=，其中r (k )=1，k ≥0，x (0)=1， x (1)=2。 (1) 试由迭代法求其全解的前5项； (2) 分别由古典法求其零输入解、零状态解，以及全解； (3) 用Z 变换法求解差分方程。 解：注：解题过程中出现的下标“zi ”和“zs ”分别表示零输入条件和零状态条件。 1. 迭代法 题目中给出的条件仅仅是零输入初始条件，进行迭代求解时的初始条件应该是全解初始条件。 (1) 零输入初始条件 本题已给出零输入时的两个初始条件x zi (0)=1，x zi (1)=2。 (2) 零状态初始条件 取k =-2时，则51 (0)(1)(2)(1)0.5(2)66x x x r r --+-=-+-，得x zs (0)=0； 取k =-1 时，则51 (1)(0)(1)(0)0.5(1)66 x x x r r -+-=+-，求得x zs (1)=1。 (3) 全解初始条件 x (0)= x zi (0)+ x zs (0)=1； x (1)= x zi (1)+ x zs (1)=3。 (4) 根据求出的全解x (0)和x (1)，利用迭代法求解 取k =0时，则51(2)(1)(0)(1)0.5(0)66x x x r r -+=+，求得23(2)6x =； 取k =1时，则51(3)(2)(1)(2)0.5(1)66x x x r r -+=+，求得151 (3)36x =； 取k =2时，则51(4)(3)(2)(3)0.5(2)66x x x r r -+=+，求得941 (4)216 x =。 2. 古典法 (1) 零输入解 令输入为零，则得齐次方程 51 (2)(1)()066 x k x k x k +-++= (a) 根据差分方程定义的算子()()n d x k x k n =+，可得它的特征方程251 066 d d -+= 求得特征根为： 112d = ，21 3 d =

计算方法实验一 方程求根

山西大学计算机与信息技术学院 实验报告 姓名学号专业班级 课程名称计算方法实验实验日期 成绩指导老师批改日期 实验名称实验一方程求根 一、实验目的 用各种方法求任意实函数方程f(x)=0在自变量区间[a,b]上，或某一点附近的实根。并比较方法的优劣。 二、实验方法 (1)二分法 对方程f(x)=0在[a,b]内求根，将所给区间二分，在分点x= 2a b 判断是否f(x)=0，若是，则有根x=(b+a)/2。否则，继续判断是否f(a)* f(x)<0，若是，则令b=x，否则令a=x、重复此过程直至求出方程f(x)=0在[a,b]中的近似根为止。 (2)迭代法 将方程f(x)=0等价变换为x=φ（x）形式，并建立相应的迭代公式x k+1=φ（x k）。 (3)牛顿法 若已知方程f(x)=0的一个近似根x0，是函数f(x)在点x0附近可用一阶泰勒多项式 p1(x)=f(x )+f`(x0)(x-x0)来近似，因此方程f(x)=0可近似表示为f(x0)+f`(x0)(x-x0)=0。设f`(x0)≠0，则x=x0-f(x0)/f`(x0)。则x作为原方程新的近似根x1，然后x1将作为x0带入上式。迭代公式为x k+1=x k -f(x k)/f`(x k)。 三、实验内容 （1）在区间[0，1]上用二分法求方程ex+10x-2=0的近似根，要求误差不超过0.5x10-3。 （2）取初值x0=0，用迭代公式，x k+1= 10 k x e- 2，（k=0,1,2···）求方程e x+10x-2=0的 近似根。要求误差不超过0.5x10-3。 （3）取初值x0=0，用牛顿迭代法求方程e x+10x-2=0（k=0,1,2···）的近似根。要求误差不超过0.5x10-3。 四、实验程序 #include #include using namespace std;

迭代法

题目：Newton-Raphson 迭代法 （1）计算原理 （2）编出计算机程序 （3）给出算例（任意题型） (1)计算原理： 牛顿-拉夫森(Newton-Raphson)迭代法也称为牛顿迭代法，它是数值分析中最重要的方法之一，它不仅适用于方程或方程组的求解，还常用于微分方程和积分方程求解。 用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才能保证迭代法收敛呢？牛顿迭代法就是常用的方法之一，其迭代格式的来源大概有以下几种方式： 1设()[]2,f x C a b ∈，对()f x 在点[]0,x a b ∈，作泰勒展开： 略去二次项，得到()f x 的线性近似式：()()()()000f x f x f x x x '≈+- 由此得到方程()0f x =的近似根(假定()00f x '≠)，() () 000f x x x f x =-' 即可构造出迭代格式(假定()00f x '≠)：() () 1k k k k f x x x f x +=- ' 这就是牛顿迭代公式，若得到的序列{}k x 收敛于α，则α就是非线性方程的根。 2 牛顿迭代法 牛顿切线法，这是由于()f x 的线性化近似函数()()()()000l x f x f x x x '≈+-是曲线()y f x =过点()()00,x f x 的切线而得名的，求()f x 的零点代之以求() l x !2))((''))((')()(2 0000x x f x x x f x f x f -+ -+= ξ

的零点，即切线与x 轴交点的横坐标，如左图所示，这就是牛顿切线法的几何解释。实际上，牛顿迭代法也可以从几何意义上推出。利用牛顿迭代公式，由 k x 得到1k x +，从几何图形上看，就是过点()(),k k x f x 作函数()f x 的切线k l ，切线k l 与x 轴的交点就是1k x +，所以有()() 1 k k k k f x f x x x +'=-，整理后也能得出牛顿迭 代公式： 3 要保证迭代法收敛，不管非线性方程()0f x =的形式如何，总可以构造： 作为方程求解的迭代函数。因为： 而且 在根附近越小，其局部收敛速度越快，故可令： 若0(即根不是0的重根)，则由得： ， 因此可令 ，则也可以得出迭代公式： 。 4 迭代法的基本思想是将方程改写成等价的迭代形式，但随之而来的问题却是迭代公式不一定收敛，或者收敛的速度较慢。运用前述加速技巧，对于简单迭代过程 ，其加速公式具有形式： ，其中 记，上面两式可以合并写成： 这种迭代公式称作简单的牛顿公式，其相应的迭代函数是： 。 需要注意的是，由于是的估计值，若取，则实际上便是的估计值。假设，则可以用代替上式中的， 就可得到牛顿法的迭代公式： 。 )(')(1k k k k x f x f x x - =+)()()(x f x k x x x -==?)0)((≠x k )(')()()('1)('x f x k x f x k x --=?) ('x ?α0)('=α?≠)('αf α=)(x f 0)('=α?)('1 )(ααf k = )('1 )(x f x k = )(')(1k k k k x f x f x x - =+0)(=x f )(x x ?=)(1n n n x f x x +=+θθ?--= +1)(1n n n x x x ) (111n n n x x x --+=++θθ )(1 n n x x ?=+1-=θL L x f x x n n n )(1- =+L x f x x )()(- =?L )('x ?)()(x f x x +=?)('x ?)('x f 0)('≠x f )('x f L )(')(1n n n n x f x f x x - =+

用matlab实现线性常系数差分方程的求解

数字信号处理课程设计 题目：试实现线性常系数差分方程的求解 学院： 专业： 班级： 学号： 组员： 指导教师：

题目：用Matlab 实现线性常系数差分方程求解 一． 设计要求 1． 掌握线性常系数差分方程的求解 2． 熟练掌握Matlab 基本操作和各类函数调用 3． 结合Matlab 实现线性常系数差分方程的求解 二．设计原理 1．差分与差分方程 与连续时间信号的微分及积分运算相对应，离散时间信号有差分及序列求和运算。设有序列f(k),则称…,f(k+2),f(k+1),…,f(k －1),f(k －2),…为f(k)的移位序列。序列的差分可以分为前向差分和后向差分。一阶前向差分定义为 ()(1)()f k f k f k ?=+- （3.1—1） 一阶后向差分定义为 ()()(1)f k f k f k ?=-- （3.1—2） 式中Δ和Δ称为差分算子。由式（3.1—1）和式（3.1—2）可见，前向差分与后向差分的关系为 ()(1)f k f k ?=?- （3.1—3） 二者仅移位不同，没有原则上的差别，因而它们的性质也相同。此处主要采用后向差分，并简称其为差分。 由查分的定义，若有序列1()f k 、2()f k 和常数1a ，2a 则 1122112211221112221122[()()][()()][(1)(1)][()(1)][()(1)]()() a f k a f k a f k a f k a f k a f k a f k f k a f k f k a f k a f k ?+=+--+-=--+--=?+? （3.1—4） 这表明差分运算具有线性性质。 二阶差分可定义为 2()[()][()(1)]()(1) ()2(1)(2) f k f k f k f k f k f k f k f k f k ?=??=?--=?-?-=--+- （3.1—5） 类似的，可定义三阶、四阶、…、n 阶差分。一般地，n 阶差分

迭代法解线性方程组(C语言描述)

用Gauss-Seidel迭代法解线性方程组的C语言源代码：#include #include #include struct Line{ int L; struct Row *head; struct Line *next; }; struct Row{ int R; float x; struct Row *link; }; //建立每次迭代结果的数据存储单元 struct Term{ float x; float m; }; struct Line *Create(int Line,int Row){ struct Line *Lhead=NULL,*p1=NULL,*p2=NULL; struct Row*Rhead=NULL,*ptr1,*ptr2=NULL; int i=1,j=1; float X; while(i<=Line){ while(j<=Row+1){ scanf("%f",&X); if(X!=0||j==Row+1){ ptr1=(struct Row*)malloc(sizeof(Row)); if(ptr1==NULL){ printf("内存分配错误!\n"); exit(1); } ptr1->x=X; ptr1->R=j; if(ptr2==NULL){ ptr2=ptr1; Rhead=ptr1; } else{

ptr2->link=ptr1; ptr2=ptr1; } } j++; } if(ptr2!=NULL){ ptr2->link=NULL; ptr2=NULL; } if(Rhead!=NULL){ p1=(struct Line*)malloc(sizeof(Line)); if(p1==NULL){ printf("内存分配错误!\n"); exit(1); } p1->L=i; p1->head=Rhead; if(p2==NULL){ Lhead=p1; p2=p1; } else{ p2->next=p1; p2=p1; } } i++; Rhead=NULL; j=1; } if(p2!=NULL) p2->next=NULL; return Lhead; } struct Line *Change(struct Line*Lhead,int n){ struct Line*p1,*p2,*p3,*p; struct Row*ptr; int i=1,k,j; float max,t; if(Lhead==NULL){ printf("链表为空!\n");

非线性方程的简单迭代法和Steffensen迭代法

《数值计算方法》实验报告 实验名称：实验1 非线性方程的简单迭代法和Steffensen 迭代法 实验题目：分别用简单迭代法和Steffensen 迭代法求方程 010423=-+x x 在 [1, 2] 内的一个实根. 实验目的：理解并掌握简单迭代法和Steffensen 迭代法 基础理论：简单迭代法和Steffensen 迭代法 1）.简单迭代法的原理：将一元非线性方程：0)(=x f 改写成等价方程：)(x x ρ= ，对此，从某个初始值x0开始，对应式)(x x ρ= 构成迭代公式 ,...1,0),(1==+k x x k k ρ ，这样就可以确定序列 {}k x （k=0，1，2…）。如果 {}k x 有极限 *lim x x k k =∞→ ，由式 ,...1,0),(1==+k x x k k ρ 两边取极限可得 )(**x x ρ= ，可知 * x 为方程0)(=x f 的近似解。 2）Steffensen 迭代法的原理： 通过把改进的Aitken 方法应用于根据不动点迭代所得到的线性收敛序列，将收敛速度加速到二阶。

()???? ?????+---===+k k k k k k k k k k k x y z x y x x y z x y 2) ()(21ρρ []x x x x x x x +---=)(2)(()()(2ρρρρψ 实验环境：操作系统：Windows 7； 实验平台：Turbo C++ 实验过程：写出算法→编写程序→调试运行程序→计算结果 1）简单迭代法的算法： Input:初始近似值x0,精度要求del,最大迭代次数N Output:近似解x 或失败信息 1. n ←1 2. While n ≤N do; 3. x ←f(x0); 4. if | x-x0|

计算方法-方程求根实验

实验四 方程求根实验 一. 实验目的 （1）深入理解方程求根的迭代法的设计思想，学会利用校正技术和松弛技术解决某些实际的非线性方程问题，比较这些方法解题的不同之处。 （2）熟悉Matlab 编程环境，利用Matlab 解决具体的方程求根问题。 二. 实验要求 用Matlab 软件实现根的二分搜索、迭代法、Newton 法、快速弦截法和弦截法，并用实例在计算机上计算。 三. 实验内容 1. 实验题目 （1）早在1225年，古代人曾求解方程020102)(23=-++=x x x x f 并给出了高精度的 实根368808107.1*=x ，试用Newton 法和弦截法进行验证，要求精度610-=ε，并绘制方程的图形。 答：A.Newton 法： a ．编写文件Newton.m 、func4.m 内容如下所示：

b.运行，如下所示A为矩阵， 由上面可知，对于初值为5，运行7次即可得到所需的精度，验证结果为古人给出的解释正确的； c.作图，编写下面的文件photo1.m.然后运行即可： 注意下面中的x矩阵即为刚才计算出来的x系列，k为迭代的次数：

a．编写文件Chord.m内容如下所示： b．运行结果如下所示：

由上表可知，在精度为10^-6时有7位有效数字，古人的结果还是正确的 c．作图，在上面运行后，即运行newton法时写的photo1.m文件即可出现图像：

可以看到图中两条曲线基本重合； （2）取5.00=x ，用迭代法求方程x e x -=的根，然后用Aitken 方法加速，要求精度为 结果有4为有效数字。 答： a. 编写文件func7.m 和Aiken.m ，内容如下所示：

非线性方程求根问题

计算机学院上机实践报告 一、目的 1．通过本实验，帮助加深对非线性方程求根方法的构造过程的理解； 2．能将各种方法编写为程序并上机实现； 3．比较各种方法在求解同一非线性方程根时，在收敛情况上的差异。 二、容与设计思想 1．用二分法求方程f(x)=x3-2x-5=0在区间[2 , 3]的根。 2．方程f(x)=2x3-5x2-19x+42=0在x=3.0附近有根，试写出其三种不同的等价形式以构成三种不同的迭代格式，再用简单迭代法求根，观察这三种迭代是否收敛。 三、使用环境 1. 硬件环境 微型计算机（Intel x86系列CPU）一台 2. 软件环境 Windows2000/XP操作系统 VC++6.0或其它的开发工具。 四、核心代码及调试过程 1．用二分法求方程f(x)=x3-2x-5=0在区间[2 , 3]的根主要代码： void bisect(double a,double b,int max_B) { double root, ya,yb,yroot; int i,actual_B; ya=f(a);yb=f(b); if(ya*yb>0) { printf("method failed!\n"); exit(0); } for(i=1;i<=max_B;i++) { root=(a+b)/2;yroot=f(root); //取当前含根区间的中点 if(yroot==0) { a=root;b=root;} else if(yb*yroot>0) //取含根区间为[a,(a+b)/2]

{ b=root;yb=yroot;} Else //取含根区间为[(a+b)/2,b] { a=root;ya=yroot;} if(fabs(b-a)b)) { printf("re_select a proper initial value x0!\n"); exit(0); } if(fabs(x1-x0)