第六章 回归问题——线性方程组求解的迭代法.doc_第1页
第六章 回归问题——线性方程组求解的迭代法.doc_第2页
第六章 回归问题——线性方程组求解的迭代法.doc_第3页
第六章 回归问题——线性方程组求解的迭代法.doc_第4页
第六章 回归问题——线性方程组求解的迭代法.doc_第5页
已阅读5页,还剩13页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第六章 回归问题 线性方程组求解的迭代法6.1 回归问题6.1.1 问题的引入在数理统计中,把研究对象的全体称为总体,而把组成总体的每个单元称为个体,要了解总体的规律性,必须对其中的个体进行统计观测。但若对全部个体进行观测,这样能对总体有充分的了解,但实际上行不通,而且也不经济。所以对整体进行随机抽样观测,再根据抽样观察的结果来推断总体的性质成为一种重要的方法。许多数理统计建模的实际问题中,一个随机变量与另一个随机变量的关系不是线性关系,而是曲线关系,那么如何确定回归方程呢?下表给出了某种产品每件平均单价(元)与批量(件)之间的关系的一组数据,试确定与的函数关系。表6.1.1 已知数据2025303540506065707580901.811.701.651.551.481.401.301.261.241.211.201.186.1.2 模型的分析先将表6.1.1中的数据进行曲线拟合,然后根据经过拟合的曲线形状确定回归方程的次数。用MATLAB做出拟合图如下,由下图知,可建立二次回归多项式模型。图6.1.1 散点图6.1.3 模型的假设 假设上表给出的数据是真实的,且以上数据是随机抽取的可以较准确地推断单位与批量的关系,假设单价与批量的函数关系是一个多项式函数,可用多项回归来建立模型。6.1.4 模型的建立 根据模型的分析,可以建立多项式模型,令,则回归方程可写成,这是一个二元线性回归模型。且,其中:6.2 线性方程组迭代法概述迭代法:即用某种极限过程逐步逼近线性方程组精确解的方法。迭代法具有需要计算机存储较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点,但有收敛性或收敛速度的问题。迭代法是解大型稀疏矩阵方程组的重要方法。 迭代法能保持矩阵的稀疏性,具有计算简单、编制程序容易的优点,并在许多情况下收敛较快。故能有效地解一些高阶方程组。迭代法的基本思想是构造一串收敛到解的序列,即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法。对线性方程组,其中,非奇异矩阵,。构造其形如的同解方程组,其中为阶方阵,。任取初始向量,代入迭代公式产生向量序列,当充分大时,作为方程组的近似解,这就是求解线性方程组的单步定长线性迭代法。称为迭代矩阵。6.3 迭代法6.3.1 Jacobi迭代法对,设,(6.3.1),将改写成: (6.3.2)又将分裂为:,则(6.3.1)等价于 (6.3.3)其中应选择为一个非奇异阵,并使容易求解。对应(6.3.3)可构造一个迭代过程:初始向量, (6.3.4)特别地,若选取,则,从而(6.3.1)化为:可得:Jacobi迭代公式:(初始向量),其中: (6.3.5)称为Jacobi迭代的迭代矩阵。Jacobi迭代的分量形式:引进记号:为第次近似,由(6.3.5)有: (6.3.6)Jacobi迭代公式简单,由公式(6.3.5), (6.3.6)可知,每迭代一次只需计算一次矩阵与向量乘法,计算机中只需要两组工作单元用来保存及且可用来控制迭代终止。由迭代计算公式可知,迭代法一个重要特征是计算过程中原来矩阵数据始终不变。例6.3.1 用Jacobi迭代法求下面线形方程组,其精确解是:。解 先将转化为等价方程组:迭代公式:选取初始向量,经10次迭代解:,误差为:。6.3.2 Gauss-Seidel迭代法在(6.3.3)中选取(下三角阵),则,从而(6.3.1)化为等价的: (6.3.7)可得Gauss-Seidel迭代公式:初始向量,其中称为Gauss-Seidel迭代矩阵。G-S迭代法的分量形式为:记,有迭代公式(6.3.9), (6.3.9) Gauss-Seidel迭代法每迭代一次只需计算一次矩阵与向量的乘法,但G-S迭代法比Jacobi迭代法有一个明显的优点,那就是计算机上仅需一组工作单元用来保存分量(或分量)当计算出就冲掉旧的分量。由G-S迭代公式(6.3.9)可看出在的一步迭代中,计算分量时利用了已计算出来的新分量。因此,G-S迭代法可以看作是Jacobi迭代法的一个修正。例6.3.2 用G-S方法解下面方程组,其精确解为:,解 由(6.3.9)可得本题G-S迭代公式为:经5次迭代得:,。 从此例可见, G-S迭代法比Jacobi迭代法收敛快(初始向量相同,达到同样精度,所须迭代步数较少),但这个结论对的矩阵满足某些条件才是对的,甚至有这样的线性方程组,用Jacobi方法是收敛的,而用G-S迭代法却是发散的。如线性方程组:,此例用Jacobi迭代法收敛而G-S迭代法却发散。简要分析如下:,特征方程。6.3.3 迭代法的收敛性定义6.3.1 设有矩阵序列及,如果成立,则称收敛于。记为。例如,矩阵序列,当时,(当时)。矩阵序列收敛的概念可以用任何矩阵范数来描述。下面介绍向量、矩阵的范数定义、常用的范数形式以及相关性质。定义6.3.2 (向量范数)如果的某个实值函数,(1)正定性: (2),为实数(3)三角不等式:,则称为上的一个向量范数(或向量的模)。利用三角不等式容易证明:(4)。在中,三角不等式即为三角形两边长之和大于第三边长。如下图:|x+y| |y|x|定义6.3.3 设 ,定义上四种常用向量范数如下:(1)向量的1范数:(2)向量的范数:(3)向量的2范数:(4)向量的p范数: 易证明:它们均满足向量范数定义6.3.1,且前三种向量范数均为第四种的向量范数的特例。其中例6.3.3 设计算。解 定理6.3.1 设非负实值函数为上任一向量范数,则是分量的连续函数。定理6.3.2(范数等价性)设为上任意两种范数,则存在常数,使得:,。定理6.3.3 在中,(时)其中为向量的任一种范数。定义6.3.4 (矩阵的范数)若矩阵的某个非负实值函数满足条件:(1) 正定性: (2) 正齐次性:(3) 三角不等式:(4) 则称为上的一个矩阵范数或模。如果将矩阵看成向量空间中的元素,则由向量2范数定义有:。这就是矩阵的Frobenius范数, 明显它满足上面定义。 在大多数与估算有关的问题中,矩阵和向量会同时参与讨论,所以希望引进一种矩阵的范数。它和向量范数相联系且和向量范数是相容的,即:定义6.3.5 (矩阵的算子范数)设给出一种向量范数(如,相应地定义一种矩阵的非负函数:(最大比值)易验证:满足前一矩阵范数的定义。因此是上的一个范数,称之为的算子范数。定理6.3.4 设是上的一个向量范数,则是上的矩阵范数,且满足相容条件:。定理6.3.5 设则:(1) (称为的行范数)(2) (称为的列范数)(3) (称为的2范数)其中表示的最大特征值。在计算上,(1),(2)比较容易,而(3)比较困难,但(3)在理论分析上十分有用。定理6.3.6 充要条件是 ,我们要考虑迭代法收敛性,即要研究在什么条件下使误差向量趋于零向量。即。定理6.3.7 设,则(零矩阵),的充要条件是:。定理6.3.8 (迭代法基本定理)设有方程组,对于任意初始向量及任意,解此方程组的迭代法(即)收敛的充要条件是:。此定理应用时要计算谱半径,不太方便。将其修改成如下的形式:定理6.3.9 (迭代法收敛的充分条件)设有方程组,且为由迭代法产生的序列,为初始任意向量。若迭代矩阵的某种范数满足,则:(1) 收敛于方程组的唯一解。(2) 。(3) 误差估计:。证明 (1)由于,即可逆,有唯一解。设为,。引进误差向量,即得误差的递推公式:,于是,时。(2)由迭代公式有,又则,即,利用此递推式即可得误差估计。例6.3.4 考察用Jacobi方法求解线性方程组的收敛性。解 则Jacobi迭代矩阵为:故解此方程组的Jacobi方法收敛。下面考察迭代法的收敛速度。,设有个线性无关的特征向量,相应的特征值为,由(线性表示,基)。可以看出当愈小时,。愈快,即愈快,故可用来刻划迭代法的收敛快慢。现在来确定迭代次数,使,取对数得:。定义6.3.6 称为迭代法的收敛速度。由此可见,愈小,愈大,则所需的迭代次数就越少。而较大时,矩阵特征值计算比较困难,基本定理的条件比较难验证,所以最好建立与矩阵元素直接有关的条件来判断迭代法的收敛性。由于,所以可用作为上界的一种估计,这样的结果即为迭代法收敛的充分性条件(如上面的定理)。由这个充分性条件的结果(3)可见,越小,收敛越快。另外,由其结果(2)可知:若则。因此可以用作为控制迭代终止的条件。但要注意当时,较大,尽管很小,却有可能误差向量模很大,迭代法收敛很慢。而且此充分性条件的结果(3)可以用来事先确定需要迭代多少次才能保证。定理6.3.10 解方程组的G-S迭代法收敛的充分必要条件是,为G-S迭代矩阵。定义6.3.7 (对角占优矩阵)设(1) 若,即的每一行对角元素绝对值严格大于同行其他元素绝对值之和。则称为严格对角占优矩阵。(2) 若,且至少有一个不等式严格成立,则称为弱对角占优矩阵。定义6.3.8 (可约与不可约矩阵)设,当时,如果存在阶排列矩阵使成立。其中为阶子矩阵,为阶子矩阵(),则称矩阵为可约的。若不存在排列矩阵使上式成立,则称为不可约矩阵。当为可约矩阵,则可经过若干行列重排化为两个低阶方程组求解。事实上,由化为:,设,其中为维向量。 于是,求解化为求解:,另外为可约矩阵的充要条件:存在指标集使定理6.3.11(对角占优定理):若为严格对角占优阵或为不可约弱对角占优阵,则是非奇异阵。证明 (1)为严格对角占优阵,采用反证法。若,则有非零的解,设为。设由齐次方程中的第个方程得:,则可得: (6.3.10)即有:这与严格对角占优阵矛盾,故。(2)为不可约弱对角占优阵,采用反证法。设使。并令使(6.3.11)(由弱对角占优定义)成立。再定义下标集合:在(6.3.10)中取,将导致与(6.3.11)得矛盾。故(空集合)。对任意,有(由(6.3.10)),由此可见,当时有。否则,上式就与为弱对角占优阵矛盾。 但对任意和,必有,因而从而为可约矩阵,这与为不可约矩阵假设矛盾。定理6.3.12 若为严格对角占优矩阵或为不可约对角占优矩阵,则对任意的初始向量,方程组的Jacobi迭代法和G-S迭代法均收敛。且G-S迭代法比Jacobi迭代法收敛速度快。证明 设为不可约对角占优矩阵,先证明G-S迭代法收敛。由弱对角占优阵假设知,而G-S迭代矩阵为,又,即,记。则:下面来证明当时,这是因为为不可约阵,则也不可约,由为弱对角矩阵,可得:且至少有一个不可约等式严格成立,这表明当时,为不可约弱对角占优矩阵,于是由前一个定理可知当时,这一结论表明的根满足:,即,故G-S法收敛。在同一条件下,对于Jacobi方法()完全类似于上可证。当为严格对角占优阵时,证明方法完全类似。6.3.4 超松弛代法 逐次超松弛迭代法(Successive Over Relaxation Method.简称为SOR法)是Gauss-Seidel法的一种加速方法。这是解大型矩阵方程组的有效方法之一,具有计算公式简单、程序设计容易、占用计算机内存较少等优点,但需要选择好的加速因子,即最佳的加速因子。 对(6.3.12)其中为奇异矩阵,且设,分解: (6.3.13)设已知第次迭代向量,及第次迭代向量的分量,现在来计算分量:先用G-S迭代法求出辅助量(预测) (6.3.14)再取为与的某种平均值(即加权平均),即将(6.3.14)代入(6.3.15)即得解的逐次超松弛迭代公式: (6.3.16)其中称为松弛因子,或写为: (6.3.17)显然时,解(6.3.12)的SOR法即为Gauss-Seidel迭代法。 SOR法中每迭代一次,主要计算量是计算一次矩阵与向量乘法。由(6.3.16)可见在计算机上用SOR法解方程组只需一组工作单位元,以便存放近似解。迭代计算时,可用来控制迭代终止。当时,称(6.3.16)为低松弛法;当时,称(6.3.16)为超松弛法。例6.3.5 用SOR法解:其精确解为。解 取,则SOR迭代公式为:取,第11次迭代结果为:对取其它值,迭代次数如下表,由此例可见,松弛因子选择得好,会使SOR迭代的收敛大大加速。本例中,是最佳松弛因子。表6.3.1 结果表松弛因子满足误差的迭代次数1.0221.1171.2121.3*11*最少迭代次数1.4141.5171.6231.7331.8531.9109下面考察SOR迭代公式的矩阵形式,由(6.3.16)可改写为: (6.3.17)由,则:即,由于对任意均为奇异阵(设而为下三角阵,且对角线元素为0)则:因此,若,则SOR迭代公式为: (6.3.18)其中,称为SOR方法的迭代矩阵,应用关于迭代法的收敛性定理于(6.3.18)可得:定理6.3.13 对,且则解方程组的充要条件是:。引进超松弛法的想法是希望能选择松弛因子使迭代过程(6.3.16)收敛较快,也就是应选择因子使。 下面考虑对于方程组(6.3.12)(),超松弛因子在什么范围内取值才可能收敛。定理6.3.14 (必要条件)对,()的SOR方法若收敛,则:。证明 由SOR法收敛及上定理,知,设的特征值为则:,即,而,因此,即:。此结果表明要使SOR法收敛,松弛因子必须在中。那么,反过来,若选取在中,SOR法是否一定收敛呢?定理6.3.15 (充分条件)若为对称正定矩阵,且,则解(6.3.12)的SOR法必收敛。证明 若能证明在定理条件下,对的任一特征值有:,则定理得证。事实上,设为对应的的特征向量。即:,即。亦即:,为找的表

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论