第三章 线性代数方程组的解法 在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如: (蓝色)建筑工程中的结构力学问题;

Slides:



Advertisements
Similar presentations
一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
Advertisements

第五节 函数的微分 一、微分的定义 二、微分的几何意义 三、基本初等函数的微分公式与微分运算 法则 四、微分形式不变性 五、微分在近似计算中的应用 六、小结.
第九章 常微分方程数值解法 §1 、引言. 微分方程的数值解:设方程问题的解 y(x) 的存在区间是 [a,b] ,令 a= x 0 < x 1
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
常系数线性微分方程组 §5.3 常系数线性方程组. 常系数线性微分方程组 一阶常系数线性微分方程组 : 本节主要讨论 (5.33) 的基解矩阵的求法.
第 4 章 数值微积分. 4.1 内插求积 Newton-Cotes 公式 第 4 章 数值微积分 4.1 内插求积 Newton-Cotes 公式.
计算机数学基础(下) --数值分析 教师:孙继荣 电话: 028 -
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
§3.4 空间直线的方程.
第四章 向量组的线性相关性 §1 向量组及其线性组合 §2 向量组的线性相关性 §3 向量组的秩 §4 线性方程组的解的结构.
3.4 空间直线的方程.
代数方程总复习 五十四中学 苗 伟.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
§1 二阶与三阶行列式 ★二元线性方程组与二阶行列式 ★三阶行列式
18.2一元二次方程的解法 (公式法).
6.9二元一次方程组的解法(2) 加减消元法 上虹中学 陶家骏.
一、二阶行列式的引入 用消元法解二元线性方程组. 一、二阶行列式的引入 用消元法解二元线性方程组.
第三章 函数逼近 — 最佳平方逼近.
第三章 解线性方程组的直接法 (3.1) AX = b.
§1 线性空间的定义与性质 ★线性空间的定义 ★线性空间的性质 ★线性空间的子空间 线性空间是线性代数的高等部分,是代数学
第一章 行列式 第五节 Cramer定理 设含有n 个未知量的n个方程构成的线性方程组为 (Ⅰ) 由未知数的系数组成的n阶行列式
恰当方程(全微分方程) 一、概念 二、全微分方程的解法.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
§4.3 常系数线性方程组.
第三章 导数与微分 习 题 课 主要内容 典型例题.
2-7、函数的微分 教学要求 教学要点.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
第2章 Z变换 Z变换的定义与收敛域 Z反变换 系统的稳定性和H(z) 系统函数.
第二章 矩阵(matrix) 第8次课.
线性代数机算与应用 李仁先 2018/11/24.
中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月
计算机数学基础 主讲老师: 邓辉文.
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
第一章 行 列 式 在初等数学中,我们用代入消元法或加减消元法求解 二元和三元线性方程组,可以看出,线性方程组的解完
第四章 向量组的线性相关性.
第四模块 函数的积分学 第三节 第二类换元积分法.
§4 迭代法的收敛性 /* Convergence of Iterative methods */
第四节 线性方程组解的结构 前面我们已经用初等变换的方法讨论了线性方程组的解法, 并建立了两个重要定理: 第四节 线性方程组解的结构 前面我们已经用初等变换的方法讨论了线性方程组的解法, 并建立了两个重要定理: (1) n个未知数的齐次线性方程组Ax.
第八章 线性方程组 的迭代解法.
第二十二章 曲面积分 §1 第一型曲面积分 §2 第二型曲面积分 §3 高斯公式与斯托克斯公式.
线性代数 第二章 矩阵 §1 矩阵的定义 定义:m×n个数排成的数表 3) 零矩阵: 4) n阶方阵:An=[aij]n×n
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
第16讲 相似矩阵与方阵的对角化 主要内容: 1.相似矩阵 2. 方阵的对角化.
§3 向量组的秩.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
第13讲 非齐次线性方程组的结构解, 线性空间与线性变换
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
第五章 相似矩阵及二次型.
线性代数 第十一讲 分块矩阵.
建模常见问题MATLAB求解  .
2.2矩阵的代数运算.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
线 性 代 数 厦门大学线性代数教学组 2019年5月12日4时19分 / 45.
计算方法(B) 主讲:张明波 Tel: (O),
§2 方阵的特征值与特征向量.
第五节 线性方程组有解判别定理 一、线性方程组的向量表示形式 二、线性方程组有解判别定理 三、一般线性方程组的解法 四、线性方程组的求解步骤.
第三章 线性方程组的解法 3.1 引言 3.2 解线性方程组的消去法 3.3 解线性方程组的矩阵分解法 3.4 解线性方程组的迭代法.
在发明中学习 线性代数概念引入 之四: 矩阵运算 李尚志 中国科学技术大学.
第三节 函数的微分 3.1 微分的概念 3.2 微分的计算 3.3 微分的应用.
定义5 把矩阵 A 的行换成同序数的列得到的矩阵,
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
教学大纲(甲型,54学时 ) 教学大纲(乙型, 36学时 )
第10章 代数方程组的MATLAB求解 编者.
第六章 线性方程组的迭代法 — Jacobi, G-S and SOR.
第6章 解线性方程组的迭代法 直接法得到的解是理论上准确的,但是我们可以看得出,它们的计算量都是n3
第2章 线性代数方程组.
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
《偏微分方程》第一章 绪论 第一章 绪论 1.1.
§4.5 最大公因式的矩阵求法( Ⅱ ).
第三章 线性方程组 §4 n维向量及其线性相关性(续7)
Presentation transcript:

第三章 线性代数方程组的解法 在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如: (蓝色)建筑工程中的结构力学问题; 第三章 线性代数方程组的解法 在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如: (蓝色)建筑工程中的结构力学问题; 用最小二乘法求实验数据的曲线拟合问题; 用差分法或者有限元法解常微分方程,偏微分方程边值问题。 大型线性方程组 计算量大 高效率、高精度算法

直接法 线性代数方程组的解法 迭代法 Gauss消去法 三角分解法 …… Jacobi迭代法 Gauss-Seidel迭代法 超松弛迭代法

设有线性方程组 记

§1 直接法 上三角方程组 4

写出矩阵形式为: 上三角矩阵 5

若uii≠0(i=1,2,……n),则由下至上依次可算得 回代过程 方法简单、计算量小 6

1.1 Gauss消元法 线性代数方程组 三角形方程组 回代求解 例 用高斯消元法解方程组 Step1: 用第一个方程消去后两个方程中的x1

Step2: 用第二个方程消去第三个方程中的x2 上三角方程组 Step3: 回代求解 Step1 Step2 消元过程 Step3 回代过程

考虑方程组 增广矩阵表示

第一次消元 条件:

第二次消元 条件:

第k次消元 条件:

第n-1次消元(最后一次消元)

回代求解

Gauss消元法能进行的条件: 约化主元素 (去掉箭头边框)充要条件 矩阵A的顺序主子式 即

例 用高斯消去法解线性方程组 16

解 回代得

1.2 列主元消元法 ≠0 (k=1,2,……n-1); 高斯消去法的问题: 顺序消元法 若 很大,舍入误差会放大。 主元消元法: 若 很大,舍入误差会放大。 顺序消元法 主元消元法: 与高斯消去法相似; 防止舍入误差的增长; 选绝对值最大的作为约化主元,进行列或行交换。 完全主元消元法 行主元消元法 列主元消元法 行、列交换 列交换 行交换 18

具体过程: 设k步消元得到: 19

在进行第k+1步消元前,选出第k+1列中位于对角线及其以下元素绝对值中的最大值者,即使得 将第t行和第k行互相交换; 再按高斯消元法进行第k步消元; 20

例 用列主元高斯消去法解线性方程组 21

解 回代得

1.3 矩阵的三角(LU)分解法 基本思想 下角阵 上三角阵 ①由下三角方程组 LY=b 求 Y ②由上三角方程组 UX=Y 求 X

Doolittle分解 Crout分解 追赶法 平方根法 A为一般稠密矩阵 常用三角分解法 A为三对角线矩阵 A为对称正定矩阵

1.3.1 Doolittle分解法 高斯消元法 消元 若

单位下三角阵 上三角阵 Doolittle分解 Gauss消元法,实质是将系数矩阵进行Doolittle分解!

证明Doolittle分解的唯一性 设对于矩阵A,同时有两种Doolittle分解 分解唯一 (定理3.12) 单位下三角阵 上三角阵

Doolittle分解法

A第一行 A第一列 A第二行 A第二列

L和U的计算公式

例 用Doolittle分解法解线性方程组

求解 ① LY=b Y=(14,-10,-72)T X=(1,2,3)T ② UX=Y

1.3.2 Crout分解法 下三角阵 单位上三角阵 利用矩阵乘法,可以逐一求出L和U中的各个元素!

1.3.3 追赶法 常微分方程边值问题 热传导方程 三次样条函数 …… 三对角线方程

Gauss消元法 u1 q1 第一次消元

u2 q2

第二次消元

u3 …… q3

第n-1次消元

回代求解 “追”:按公式顺序求出ui,qi 消元 回代 “赶”:按公式逆序求出xn,xn-1 …… x2,x1

例 用追赶法解线性方程组

1.3.4 平方根法 要求: A为对称正定矩阵 A对称正定 再分解

A对称 分解唯一性

①根据矩阵乘法确定 中的元素 ②求解

例 用平方根法解线性方程组 解: A是对称正定矩阵,可用平方根法求解

直接法:经过有限步算术运算,可求得方程组的精确解的方法。多应用于阶数较低的线性代数方程组。 线性代数方程组的数值解法: 直接法:经过有限步算术运算,可求得方程组的精确解的方法。多应用于阶数较低的线性代数方程组。 迭代法:用某种极限过程去逐步逼近线性方程组精确解,可求得方程组的近似解的方法。多应用于求解大型线性代数方程组。 51

§2 向量和矩阵的范数 为了研究线性方程组近似解的误差估计和迭代法的收敛性,我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量——向量和矩阵的范数。 52

2.1向量的范数 对空间直角坐标系任意向量 其长度为: 它满足如下三个条件: ①对任意向量X,|X|≥0,|X|=0当且仅当X =0; 非负性 ②对任意常数c和向量X ,有|c X |=|c|·| X |; 齐次性 ③对任意向量X和Y,有| X + Y |≤| X | + | Y |。 三角不等式 推广

定义1 设N(X)=||X||是定义在Rn上的实函数,如果它满足如下条件: 向量范数的定义 定义1 设N(X)=||X||是定义在Rn上的实函数,如果它满足如下条件: ①非负性 对任意向量X,||X||≥0,||X||=0当且仅当X =0; ②齐次性 对任意常数c和向量X ,有||c X ||=||c||·|| X ||; ③三角不等式 对任意向量X和Y,有|| X + Y ||≤|| X || +|| Y ||。 则称N(X)=||X||为Rn上向量X的范数 54

最常用的是三种向量范数 向量的1-范数: 向量的2-范数: 向量的∞-范数: 示例结果:12,5倍根号10,5 例 求 的三种范数。 55

2.2矩阵的范数 定义2 矩阵A∈Rn×n,设N(A)=||A||是矩阵A的实函数,如果它满足如下条件: ①非负性 对任意矩阵A,||A||≥0,||A||=0当且仅当A =0; ②齐次性 对任意常数c和矩阵A ,有||c A ||=|c|·|| A ||; ③三角不等式 对任意矩阵A和B,有|| A + B ||≤|| A || + || B ||; ④矩阵乘法不等式 对任意矩阵A和B,有||AB|| ≤|| A || || B ||。 则称N(A)=||A||为Rn×n上矩阵A的范数

向量 X 矩阵 A 向量范数 ||X|| 矩阵、向量相乘的相容性 协调 矩阵范数 ||A|| || AX ||≤||A|| ||X||

矩阵A的r范数 矩阵的1-范数: 矩阵的2-范数: 矩阵的∞-范数: 列模 谱模 行模 表示 的最大特征值

例 求矩阵的1-范数,2-范数,∞-范数 解:

2.3 矩阵的条件数 例 病态方程组

① 仅b有扰动

② 仅A有扰动

条件数 常用的条件数 定义4 若 ,AX=b为病态方程组; 若 相对的小,AX=b为良态方程组。

例 判断如下方程组的性态 解: >>1 该方程组是病态方程组

方程组可能病态的情形: ① 用选主元消去法消元过程中出现小主元; ②系数行列式的绝对值相对很小; ③系数矩阵的各元素间在数量级上相差很大且无 规律; ④出现了相对很大的解。

§3 迭代法 非线性方程求根 f (x) = 0 x = g (x) 等价变换 线性代数方程组求根 等价变换 初始向量

迭代公式 迭代矩阵 收敛 迭代序列 发散

例 求解线性方程组 解: 将原方程组改写为 迭代格式

精确解

设线性方程组的一般形式为

依此类推,线性方程组可化为

Jacobi迭代法 等价

3.1 Jacobi迭代法 分量形式 矩阵形式 例 用Jacobi迭代法求解方程组,误差不超过10-4

解: ①分量形式 ②矩阵形式

依此类推 X4 = 3.0241 1.9478 0.9205 ε = 0.1573 X5 = 3.0003 1.9840 1.0010 ε = 0.0914 X6 = 2.9938 2.0000 1.0038 ε = 0.0175 X7 = 2.9990 2.0026 1.0031 ε = 0.0059 X8 = 3.0002 2.0006 0.9998 ε = 0.0040 X9 = 3.0003 1.9999 0.9997 ε = 7.3612×10-4 X10 = 3.0000 1.9999 0.9999 ε = 2.8918×10-4 X11 = 3.0000 2.0000 1.0000 ε = 1.7669×10-4 X12 = 3.0000 2.0000 1.0000 ε = 3.0647×10-5 迭代次数 为12次

分析Jacobi迭代法的迭代过程,其分量形式为

Gauss-Seidel迭代法

3.2 Gauss-Seidel迭代法 分量形式 矩阵形式

用Gauss-Seidel迭代法求解方程组,误差不超过10-4。 例 用Gauss-Seidel迭代法求解方程组,误差不超过10-4。 解: ①分量形式

②矩阵形式

依此类推 X3 = 3.00981 1.99681 0.99589 ε = 0.04650 X4 = 2.99983 1.99969 1.00016 ε = 0.01124 X5 = 2.99984 2.00007 1.00006 ε = 0.00040 X6 = 3.00001 2.00000 0.99999 ε = 0.00020 X7 = 3.00000 2.00000 0.99999 ε = 0.00001 迭代次数为7次

迭代法收敛的充要条件 定理 迭代法收敛的充要条件是 ,其中B迭代矩阵, 为迭代矩阵的谱半径,定义为

例 分别用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组,判断其收敛性。 解: ①Jacobi迭代法 收敛

②Gauss-Seidel迭代法 收敛

3.3 超松弛迭代法(SOR方法) 松弛因子 分量形式

矩阵形式 低松弛法 超松弛法

例 用迭代法解方程组,要求精确到0.001 解: ①Jacobi迭代法 迭代公式 取初始向量

②Gauss-Seidel迭代法 取初始向量

③SOR迭代法 取初始向量