数值分析笔记期末复习

第一章引论第一章引论 1 1 数值分析研究对象 数值分析研究对象 数值分析是计算数学的一个主要部分 计算数学是数学科学的一个分支 它研究用计 算机求解各种数学问题的数值计算方法及其理论与软件实现 2 2 数值分析特点 数值分析特点 面向计算机 要根据计算机特点设计切实可行的有效算法 有可靠的理论分析 能 任意逼近并达到精度要求 对近似计算要保证收敛性和数值稳定性 要有好的计算复 杂性 时间复杂性好是指节省时间 空间复杂性好是指节省存贮量 这也是建立算法 要研究的问题 要有数值试验 即任何一个算法除了从理论上要满足上述三点外 还要通过数值试验证明是行之有效的 3 3 数值分析实质 数值分析实质 是以数学问题为研究对象 不像纯数学那样只研究数学本身的理论 而是把理论与计 算紧密结合 着重研究数学问题的数值方法及理论 4 4 用计算机解决科学计算问题通常经历以下过程 用计算机解决科学计算问题通常经历以下过程 实际问题 数学模型 应用数学 数值计算方法 程序设计 上机计算结果 计算数 学 5 5 误差来源及分类 误差来源及分类 1 模型误差 从实际问题中抽象出数学模型 2 观测误差 通过测量得到模型中参数的值 通常根据测量工具的精度 可以知道 这类误差的上限值 3 截断误差 当数学模型得不到精确解时 要用数值计算方法求它的近似解 由此 产 生的误差称为 截断误差 或 方法误差 4 舍入误差 由于计算机字长有限 原始数据的输入及浮点数运算过程中都有可能 产 生误差 这样产生的误差称为舍入误差 6 6 五个关于误差的概念 五个关于误差的概念 1 绝对误差绝对误差 e x 2 绝对误差限绝对误差限 3 相对误差相对误差 r e x4 相对误差限相对误差限 r x 1 1 定义 定义 设某一量的准确值为 x 近 似值为 x 则 x 与 x 之差 叫做近似值 x 的绝对误差 简称误差 记为 ee xxx 2 2 性质 性质 1 绝对误差 e x 可正可 负 2 e x 的大小标志 着 x 的精确度 3 绝对 误差 e x 未知 3 3 判断 判断 1 1 定义 定义 若指定一个适当小的正数 使 则称 e xxx 为近似值 x 的绝对误差限 有时用表示近似值 xx x 的精度或准确值的所在范围 2 2 性质 性质 1 在实际问题中 绝对误差一 般是有量纲的 绝对误差限也 是有量纲的 2 绝对误差限是正的 有无穷 1 1 定义 定义 绝对误差与准确值之比 0 rr e xxx ee xx xx 称为 x 的相对 误差 2 2 性质 性质 1 相对误差是个无量纲量 值 小者精度高 2 由于准确值 x 未知 故实际 问题中 当 较小时 r e x 常取 r e x e x x 1 1 定义 定义 若指定一个适当小的正数 使 r x rr e x e xx x 则称为近似值 x 的相 r x 对误差限 2 2 性质 性质 当 较小时 可用下 r e x 式计算 绝对误差是误差的绝对值 错 多个 则比大的任意正数均 是绝对误差 限 r x x x 5 有效数字有效数字 1 定义 若近似值 x 的绝对误差限是某一位的半个单位 该位到 x 的第一位非零 数字一共有 n 位 则称近似值 x 有 n 位有效数字 或说 x 精确到该位 注意 近似值 后面的零不能随便省去 2 例题 取 x1 3 作为 的近似值 则 一个有效数字 0 1 1 0 141510 2 e 取 x2 3 14 作为 的近似值 则 三个有效数字 2 2 1 0 0015910 2 e 取 x3 3 1416 作为 的近似值 则 五个有效数字 4 3 1 0 0000073410 2 e 它们的误差都不超过末位数字的半个单位 3 性质 1 有效数字越多 则绝对误差越小 2 有效数字越多 则相对误差越小 有效数字的位数可刻画近似数的精确度 6 6 一元函数的误差估计 一元函数的误差估计 问题 设 y f x x 的近似值为 x 则 y 的近似值 y 的误差如何计算 e ydyfxdxfxe x e yfxe x rr x eyfxe x f x 故相应的误差限计算如下 yfxx rr x yfxx f x 7 7 二元函数的误差估计 二元函数的误差估计 问题 设 y f x1 x2 x1 x2 的近似值为 x1 x2 则 y 的误差如何计算 121212 e yyyf x xf x xdf xx rr dyfxe xx eyfxe x yf xf x 1212 12 12 f xxf xx e xe x xx 12121212 1212 1212 f x xf x xf xxf xx e ye xe xe xe x xxxx 故绝对误差限为 1212 12 12 f xxf xx yxx xx 8 8 多元函数的误差估计 多元函数的误差估计 1212 1 1 12 1 nn n n n n i i i f xxxf xxx e yyye xe x xx f xxx e x x 9 9 加减乘除运算的误差估计 加减乘除运算的误差估计 加法减法乘法除法 绝 对 误 差 1212 e xxe xe x 1212 e xxe xe x 122112 e x xx e xx e x 12112 2 22 xx e xx e x e xx 绝 对 误 差 限 1212 xxxx 1212 xxxx 122112 x xxxxx 2112 1 2 22 xxxxx xx 相 对 误 差 12 12 12 r e xe x e xx xx 12 12 12 r e xe x e xx xx 1212 rrr e x xe xe x 1 12 2 rrr x ee xe x x 相 对 误 差 限 12 12 12 r xx xx xx 12 12 12 r xx xx xx 1212 rrr x xxx 1212 rrr xxxx 10 10 算法的数值稳定性概念及 算法的数值稳定性概念及运算运算 1 定义 初始数据的误差或计算中的舍入误差在计算过程中的传播 因算法不同而异 一个算法 如果计算结果受误差的影响小 就称该算法具有较好的数值稳定性 11 11 设计算法的五个原则 设计算法的五个原则 一一 要避免相近两数相减要避免相近两数相减 x x x x lnlnln 1 x x x sin sin2cos sin 22 xxx 23 11 1 26 x exxx 二二 要防止大数要防止大数 吃掉吃掉 小数 注意保护重要数据小数 注意保护重要数据 2 9 1 4 10 2 bsign bbac x a 9 122 9 1 10 1 10 cc xxx aa x 求和时从小到大相加 可使和的误差减小 若干数相加 采用绝对值较小者先加的算法 结果的相对误差限较小 0000 54321 100 4 100 3 100 4 1054322y 三三 注意简化计算步骤 减少运算次数 避免误差积累 秦九韶 注意简化计算步骤 减少运算次数 避免误差积累 秦九韶 432 4 0 06250 4251 2151 9122 1296 0 06250 425 1 125 1 912 2 1296 P xxxxx xxxx 四四 要避免绝对值小的数作除数要避免绝对值小的数作除数 2112 1 2 22 xxxxx xx 1 cossin sin1 cos xx xx 1 1 x xxx xx 五五 设法控制误差的传播设法控制误差的传播 许多算法具有递推性 递推法运算过程较规律 但多次递推必然导致误差的积累 1 1 1 2 3 9 1 nn EnE n Ee 1 11 1 n nn e Ene En e E 1 1 n n E E n 1 1 nn e Ee E n 1 1 n e Ee E n 第二章第二章 逼近问题逼近问题 1 1 函数逼近 函数逼近 1 插值问题 求一条曲线严格通过数据点 2 曲线拟合问题 求一条曲线在一定意义下靠近数据点 2 2 插值问题 插值问题 1 定义 求一个简单函数 x 作为f x 的近似表达式 以满足 0 1 ii xyin 我们称这样的问题为插值问题 并称 x 为 f x 的插值函数 f x 为被插函数 x0 x1 x2 xn 是插值节 基 点 是插值原则 0 1 ii xyin 3 3 插值多项式 插值多项式 1 1 定义 定义 求一个次数不超过 n 的多项式使满足插值原则 2 012 n nn P xaa xa xa x 条件 称 Pn x 为 f x 的 n 次插值多项式 0 1 nii P xyin 2 2 定理 定理 在 n 1 个互异节点处满足插值原则且次数不超过 n 的多项式 Pn x 存在并且唯一 注 若不将多项式次数限制为 n 则插值多项式不唯一 也是一个插值多项式 其中可以是任意多项式 0 n ni i P xP xp xxx p x 4 4 插值问题插值问题 拉格朗日差值牛顿插值 0 0 0 nn n n i i i L xy lxy lx yl x 0010 001 n nn Nx f xf x xxx f xxxxxx 二次插值基函数 02 1 1012 01 2 2021 xxxx l x xxxx xxxx lx xxxx 011 011 0 i iin iiiiiin n j j ij j i l x xxxxxxxx xxxxxxxx xx xx 1 0 iiij l xl x 一阶差商 ji ij ji f xf x f x x xx k 阶差商 01 02011 1 k kkk kk f x xx f xxxf x xx xx 零阶差商 ii f xf x 1 差商与节点的排列次序无关 称为差商的 对称性 2 高阶差商可由低阶差商反复作一阶差商得 到 计算具有递推性 3 若f x 在 a b 上存在n阶导数 则 01 n n f f x xxa b n nn R xf xL x 1 1 101 1 n nn nn f R xx n xxxxxxx 为了使得 n 1 x 尽可能小一些 插值基 点的选取原则是 使x尽可能位于区间Ix 的中部 这里Ix是包含x以及所用基点的 最小闭区间 1 1 01 00 1 n nn nn nn f R xx n f x xxx f x xxxxxx 1 计算量省 便于程序设计 2 具有承袭性的插值公式 便于理论分析 埃尔米 特差值 插值条件中除函数值插值条件外 还有导数值插值条件 即已知 2n 2 个条件 求 一个次数不超过 2n 1 的多项式H2n 1 x 解法 1 基函数法 解法 2 承袭法 分段低 次插值 原因 原因 当插值基点无限加密时 Pn x 也只能在很小范围内收敛 这一现象称为 龙格 Runge 现象 它表明通过增加基点来提高逼近程度是不宜的 定义 定义 设在 a b 上给出插值条件 求一个折线插值函数Ih x 满足 xix0 x1 xn f xi f0f1 fn 1 Ih x 是 a b 上的连续函数 2 Ih xk fk k 0 1 n 3 Ih x 在每个小区间 xk xk 1 上是线性函数 则称Ih x 为分段线性插值函数 数学表达 数学表达 1 1 11 kk hkk kkkk xxxx Iff xxxx 1 kk xxx 性质 性质 1 分段线性插值多项式是分段函数 2 可以预见 但n充分大时 Ih x 能很好逼近f x 3 Ih x 有一个缺点 在插值点处有尖点 即一阶导数不连续 不够光滑 解决办法 解决办法 三次埃尔米特插值 三次样 条插值 两种构造方法 5 5 最小二乘法 最小二乘法 1 定义 已知 一组实验数据 xi yi i 0 1 m 且观测数据有误差 求 自变量 x 与因变量 y 之间的函数关系y F x 不要求y F x 经过所有点 而只要求在给定点上误差按某种标准最小 0 1 iii F xyim 2 度量标准 1 使残差的最大绝对值为最小 maxmax min iii ii eyF x 2 使残差的绝对值之和为最小 min i i e 3 使残差的平方和为最小 2 min i i e 3 最小二乘法 多项式拟合 01 n n F xaa xa xnm 已知 一组数据 xi yi i 0 1 m 求 在次数不超过n的多项式中找一个函数 使误差平方和最小 即 yFx 22 00 min mm iiii F xn ii FxyF xy 是次多项式 这里 01 n n F xaa xa xnm 解 故 解得 3 2 01 0 ii i F xya a 01 0 01 1 0 0 a a a a a a 01 a a 4 最小二乘法 非多项式拟合 参数线性 001 1 1 nn F xaxaxaxnm 已知 一组数据 xi yi i 0 1 m 求 在函数类中找一个函数 使误差 01 n spanxxx ySx 平方和最小 即 22 00 min mm iiii S x ii SxyS xy 这里 001 1 nn S xaxaxaxnm 已知 一组数据 xi yi 且每个点对应权因子wi 0 i 1 2 m 求 在函数类中找一个函数 使误 01 n spanxxx ySx 差平方和最小 即 22 00 min mm iiiiii S x ii w Sxyw S xy 这里 001 1 nn S xaxaxaxnm 最小二乘法 非多项式拟合 参数非线性 01 01 01 01 3 43 2 n aaa n aa a F xxxx xx F xNO ax 或 第三章第三章 定积分定积分 1 1 求解定积分问题方法 求曲边梯形面积 求解定积分问题方法 求曲边梯形面积 旧 1 牛顿 莱布尼兹公式 b a f x dxF bF a 需要寻求原函数的困难 已知点离散 新 2 机械求积公式 多项式机械求积公式 解决原函数的困难 0 n b kk a k f x dxA f x 中矩形公式 解决原函数的困难 2 b a ab f x dxba f 梯形公式 解决原函数的困难 2 b a ba f x dxf bf a 插值型求积公式 解决离散问题 0 n bbb nkk aaa k f x dxL x dxf xlx dx 2 2 代数精度 代数精度 1 目的 数值求积方法是近似方法 为了保证精度 我们自然希望公式能对 尽可能多 的函 数准确成立 这就提出了所谓代数精度的概念 2 定义 若某个求积公式对于次数 m 的多项式均能够准确成立 但对于 m 1 次多项式就不 一定准确 则称该求积公式有 m 次代数精度 若某个求积公式对于 1 x xm 均能够准确成立 但对于 xm 1 就不准确成立 则称该求积公式有 m 次代数精度 3 定理 当 n 为偶数时 牛顿 柯特斯公式至少有 n 1 次代数精度 注 在实际应用时 出于对计注 在实际应用时 出于对计 算复杂性和计算速度的考虑 我们常常使用低阶偶数求积公式 代替高一阶的奇数求积公算复杂性和计算速度的考虑 我们常常使用低阶偶数求积公式 代替高一阶的奇数求积公 式 式 3 3 插值求积公式 插值求积公式 1 定理 具有 n 1 个求积节点的机械求积公式至少有 n 次代数精度的充分必要条件是 它是插值型的 试总结证明机械求积公式是插值型求积公式的方法 试总结证明机械求积公式是插值型求积公式的方法 2 求积公式的余项 若求积公式的代数精度为 m 则余项形如其中 K 1 0 n b m kk a k R ff x dxA f xKf 是不依赖于 f x 的待定参数 3 3 牛顿 牛顿 柯特斯求积公式柯特斯求积公式 梯形 辛普森 柯特斯梯形 辛普森 柯特斯 1 定义定义 牛顿牛顿 柯特斯柯特斯 0 n b n nkk a k f x dxIbaCf x 00 nn bb kkkk aa kk f x dxA f xf xlx dx 000 11 1 n k nn bbn jn kk a a j j kj j kj k xx Clx dxdxtj dt babaxxnk nk 梯形公式梯形公式辛甫生辛甫生 Simpson 公式公式柯特斯柯特斯 Cotes 公式公式 2 ba Sf af b 4 62 baab Sf aff b 01 234 7 32 90 12 32 7 ba Cf xf x f xf xf x 一阶 2 次代数精度 令令 f x x2二阶 3 次代数精度 令令 f x x4四阶 5 次代数精度 3 12 T f Rba 4 4 1802 S ba ba Rf 6 6 2 9454 c baba RICf 4 4 复化求积公式 复化求积公式 1 定义 为了提高精度通常可把积分区间分成若干子区间 再在每个子区间上用低阶求 积公式 这种方法称为复化求积法 复化求积法就是先用低阶的牛顿 柯特斯公式求得每个子区间 xk xk 1 上的积 分 Ik 然后再求和 用 作为所求积分 I 的近似值 即 1 0 n k k I 1 0 n k k II 复化梯形公式复化梯形公式复化辛甫生公式复化辛甫生公式复化柯特斯公式复化柯特斯公式 11 1 00 2 nn nkkk kk h TIf xf x 1 1 2 2 n nk k h Tf af xf b 1 2 1 0 1 0 4 6 2 n k k n n k k f af x h S f xf b 11 11 00 42 11 3 01 4 7 32 12 90 32 14 7 nn n kk kk nn k k kk h Cf af xf x f xf xf b 3 1 0 12 n Tn n k k RIT h f 3 1 0 2 1 12 12 n k k h nf n ba h f 1 4 4 0 180 2 n nk k hh ISf 4 4 1802 bah f a b 复化辛甫生公式精度优于复化梯复化辛甫生公式精度优于复化梯 形公式形公式 6 6 2 9454 n bah ICf a b 5 5 高斯求积公式 高斯求积公式 1 1 定义 定义 机械求积公式含有 2n 2 个待定参数 0 n b kk a k f x dxA f x 若适当选择这些参数使求积公式具有 2n 1 次代数精度 则这类公式 0 1 kk xA kn 称为高斯公式 中矩形公式是 2 2 高斯点定义 高斯点定义 高斯公式的求积节点称为高斯点 3 求一点的高斯公式求一点的高斯公式 设一点高斯公式为则其代数精度应为 00 b a f x dxA f x 212 0 11n 4 求二点的高斯公式求二点的高斯公式 再设两点高斯公式为代数精度应为 0011 b a f x dxA f xA f x 212 1 13n 5 高斯点的性质 高斯点的性质 定理 对于插值型求积公式 4 1 其节点是高斯点的充要条件是以这 0 1 k x kn 些点为零点的多项式与任意次数不超过 n 的多项式 P x 均 01 n xxxxxxx 正交 即 证明看习题 0 b a P xx dx 6 高斯高斯 勒让得公式勒让得公式 特别地 取 a b 1 1 其上高斯公式为 下面求对应的高 1 1 0 n kk k f x dxA f x 斯点 对于任意求积区间 a b 如何求 作变换可以化到区间 1 1 上 这 22 baab xt 时 1 1 222 b a babaab f x dxftdt 7 带权的高斯公式带权的高斯公式 1 定义 求积公式若该公式具有 2n 1 次代数精度 则 0 n b kk a k x f x dxA f x 称这类公式为带权的高斯公式 上述 x 0 是权函数 2 定理 是高斯点的充要条件是是 0 1 k x kn 01 n xxxxxxx 区间 a b 上关于 x 的正交多项式 3 特别 若 a b 1 1 权函数是所建立的高斯公式为 2 1 1 x x 切比雪夫 高斯公式 xk是切比雪夫多项式的零点 1 21 0 1 n kk k f x A f x x 第四章第四章 解线性方程组解线性方程组 1 1 分类 分类 系数矩阵为低阶稠密矩阵系数矩阵为低阶稠密矩阵 阶数大约不超过 阶数大约不超过 150150 直接法直接法 经过有限步算术运算 可求得方程组的精确解的方法 一般 用于解系数矩阵为低阶稠密矩阵 一般形式 11 112211 21 122222 1 122 nn nn nnnnnn a xa xa xb a xa xa xb a xa xa xb 矩阵形式 Axb 111 1 n nnn aa A aa 1 n x x x 1 n b b b 系数矩阵为大型稀疏矩阵系数矩阵为大型稀疏矩阵 阶数高且零元素较多 阶数高且零元素较多 迭代法 用某种极限过程去逐步 逼近精确解的方法 一般用于解系数 矩阵为大型稀疏矩阵 2 2 范数 范数 向量范数矩阵范数 类 型 在在R Rn n上的向量上的向量x x x x1 1 x xn n T T R Rn n在在 R Rn n n n上的矩阵 上的矩阵A A a aij ij 定 义 设对任意向量 x Rn 按一定的规则有一实数与 之对应 记为 x 若 x 满足 1 0 00 xxx 当且仅当时才有 正定性 2 xxR 齐次性 3 n xyxyx yR 三角不等式 则称 x 为向量的范数 设对任意矩阵 A Rn n 按一定的规则有一实数与 之对应 记为 A 若 A 满足 1 000 AAA 当且仅当时才有 正定性 2 cAcAcR 齐次性 3 ABAB 三角不等式 4 ABA B 相容性 则称 A 为矩阵的范数 称为 范数或最大范数 1 max i i n xx 绝对值最大的元素 称为 1 范数 1 1 n i i xx 称为 2 范数 1 2 2 2 1 n i i xx 称为 p 范数 1 1 n p p i p i xx 所有值绝对值的 P 次方求和 再开 P 次方 称为 范数或行范数 1 1 max n ij i n j Aa 所有元素绝对值之和最大的一行 称为 1 范数或列范数 1 1 1 max n ij j n i Aa 所有元素绝对值之和最大的一列 称为 2 范数 max 2 T xA A ATA 的最大特征值开平方 称为 Frobennius 范数 1 2 2 1 n ij F i j Ax 所有元素平方和开平方 性 质 定义 定义 如果 Rn中有两个范数 x s 与 x t 存在常 数 m M 0 使对任意 n维向量x有 则称这两个范数等价 sts m xxM x 性质 性质 对两种等价范数而言 某向量序列在其中一 种范数意义下收敛时 则在另一种范数意义下也收 敛 定理 定理 Rn上的任意两个范数等价 注 今后研究向 量序列的收敛性时 可在任何一种范数意义下研究 3 3 病态病态 方程组方程组 1 1 定义 定义 当一个方程组 由于系数矩阵 A 或右端常数项 b 的微小变化 引起方程组 Ax b 解的 巨大变化 则称此方程组为 病态 方程组 矩阵 A 称为 病态 矩阵 否则称方程组为 良态 方程 组 A 为 良态 矩阵 2 2 如何划分 如何划分 病态病态 的程度 的程度 条件数 设 A 为非奇异阵 称 cond A v A 1 v A v v 1 2 为矩阵 A 的条件数 b 1 cond xbb AAA xbb A cond 1 cond A A xA A x A A 则系数矩阵 A 的条件数刻划了方程组的 病态 程度 条件数愈大 方程组的 病态 程度愈大 也就愈难得到方程组的比较准确的解 当矩阵 A 的条件数相对地小 则方程组 是 良态 的 4 4 线性方程组解法线性方程组解法 向量序列的收敛性矩阵序列的收敛性矩阵序列的收敛性 定义 1设 x k 为 Rn中的向量序列 x Rn 如果其中 lim 0 k k xx 为向量范数 则称序列 x n 收 敛于 x 记为 lim k k xx 设 A k 为 n 阶方阵序列 A 为 n 阶 方阵 如果其中 为 lim 0 k k AA 矩阵范数 则称序列 A n 收敛于 A 记为 lim k k AA 定理 1Rn中的向量序列 x k 收敛于 Rn中的设 A k aij k 1 2 A 向量 x 当且仅当 12 12 lim 1 2 k ii k kkkkT n T n xxin xxxx xx xx aij 均为 n 阶方阵 则矩阵序列 A n 收敛于 矩阵 A 的充要条件为 lim 1 2 k ijij k aai jn 高斯 直接 消去 法 基本思想基本思想 用逐次消去未知数的方法把原来方程组 AX b 化为与其等价的三角形方程组 而求解三角形 方程组就容易了 高斯消去法的特点 消元和回代不同步 使用高斯消去法的条件 使用高斯消去法要求在每 步消元时 0 k kk a 定理定理 约化的主元素 i 1 2 n 的充要 0 k kk a 条件是矩阵 A 的顺序主子式 0 1 2 i Din 定理 6 如果 n 阶矩阵 A 的所有顺序主子式均不为 零 则可通过高斯消去法 不进行交 换两行的初等变换 将方程组约化为三 角形方程组 定理 6 如果 A 为 n 阶非奇异矩阵 则可通过高斯 消去法 及交换两行的初等变换 将方程组 Ax b 化为三角形方程组 1 1 1 1 1 111211 2 2 2 2 2222 n n nn n nnn xaaab xaab xab 1 1 2 2 1 nn nnnn n kkk kkkjjkk j k xba xbaxa knn 推论 推论 如果 A 的顺序主子式不等于 0 则 1 111 1 k2 3 n k kkkk aD aDD 直 接 消 去 法 主元 素法 在采用高斯消去法解方程组时 小主元可能产 生麻烦 故应避免采用绝对值小的主元素 对一般矩阵 最好每一步选取系数矩阵 或 消元后的低阶矩阵 中绝对值最大的元素作 为主元素 以使高斯消去法具有较好的数值 稳定性 列主元素法 列主元素法 选主元时仅考虑按列选取 然后换行使之变到主元 位置上 再进行消元计算 列主元消去法的特点 1 能够得到较高精度要求的 解 2 计算量大大减少 完全主元素法 完全主元素法 其中 y1 y2 yn为 1112111 22222 n n nnnn aaayb aayb ayb 未知数 x1 x2 xn调换后的次序 第一步 首先在 A 中选取绝对值最大的元素作为主元素 然后交换到第 一行 第一列的位置 再进行第一次消元 完全主元 素消去法的缺点 在选主元素时要花费较多机器时间 时时纪录 x 顺序的变化情况 1 1 2 2 1 nnnn n kkkjjkk j k yba yba ya knn 高斯 约当 消去 法 高斯 约当消去法定义 则同时消去对角线上方和下方的元素 高斯 约当消去法的特点 1 消元和回代同时进行 2 乘除法的次数要比高斯消去法大 所以通常用 于同时求解系数矩阵相同的多个方程组或求逆矩阵 1 1 2 2 10 0 01 0 00 1 n n n n n xb xb xb 直接三角 分解法 ALU 定理 矩阵的 LU 分解 设 A 为 n 阶矩阵 如果 A 的顺序主子式 i 1 2 n 1 则 A 可分解为一个 单位下三角矩阵 L 和一个上三角矩阵 U 的 乘积 且这种分解是唯一的 注 若 A 实现 了 LU 分解 则 Ax b LU x b Ly b Ux y 111213 212223 313233 100 100 100 uuu AluuLU llu 单位下三角阵单位下三角阵 上三角阵上三角阵 100111 010041 211002 ALU 解得 1 2 3 1006 0105 2111 y y y 1 2 3 6 5 6 y y y 解得 11 22 33 111 041 002 xy xy xy 1 2 3 1 2 3 x x x 平方根法 A LDLT A LLT 平方根法适用于适用于系数矩阵为对称正定阵的方 程组的求解 定理定理 1 1 对称阵的三角分解定理对称阵的三角分解定理 设 A 为 n 阶对称阵 且 A 的所有顺序主子式 均 不为零 则 A 可唯一分解为 A LDLT其中 L 为单位下三角阵 D 为对角阵 定理定理 2 2 对称正定阵的三角分解定理对称正定阵的三角分解定理 设 A 为 n 阶对称阵 且 A 的所有顺序主子式 均 大于零 则存在一个非奇异下三角阵 L 使 A LLT 当限定 L 的对角元素为正时 这种 分解是唯一的 Cholesky 分解分解 11213 21223 31323 00 00 00 1001 1001 1001 T D LL LlLL ll 11111213 21222223 31322333 00 00 00 T llll LllLll llll 直 接 三 角 法 追赶法 A LU 追赶法适用于系数矩阵为三对角阵的方程组 的求解 利用系数矩阵的特点 可以将 A 分解为两个 三角阵的乘积 A LU 其中 L 为下三角矩阵 U 为单位上三角矩阵 11 222 3 1n nn bc abc Aa c ab 11 2122 12 0 0 0 nnnn l ll L lll 1213 23 1 01 001 UU UU 11 222 3 1 1 1 1 n nn 雅 克 比 迭 代 法 一般形式 11 112211 21 122222 1 122 nn nn nnnnnn a xa xa xb a xa xa xb a xa xa xb 11221111 221 12222 1 122 1 nn nn nnnn nnnnn xa xa xba xa xa xba xa xa xaxba 0 0 0 0 12 1 1 1 T n n kk iiijj i ii j i xxxx xba x a 初始向量 矩阵形式 将方程组记为 Ax b 其中 A 非奇异且 aii 0 I 1 2 n 将 A 分裂为 A D 其中 11121 22212 12 00 00 00 n n nnnn aaa aaa DLU aaa 0 0 0 0 12 1 0 T n kk xxxx xB xf 初始向量 高 斯 塞 德 尔 11221111 221 12222 1 122 1 nn nn nnnn nnnnn xa xa xba xa xa xba xa xa xaxba 0 0 0 0 12 1 1 1 11 1 T n in kkk iiijjijj jj i ii xxxx xba xa x a 初始向量 将方程组记为 Ax b 其中 A 非奇异且 aii 0 I 1 2 n 将 A 分裂为 A D 其中 11 22 nn a a D a 21 12 0 0 0 nn a L aa 121 2 0 0 0 n n aa a U 0 0 0 0 12 1 1 1 T n kk xxxx xDLUxDLb 初始向量 迭 代 法 超 松 弛 x k 1 x k x 1 时 称为超松弛法 简称 SOR 法 用分解式 A D 则可写为 1 1 1 1 kk xDLDU x DLb 注 1 松弛法是 G S 法的一种加速方法 迭 1 1 1 11 1 1 2 kk iii in kkk iiijjijj jj i ii xxx xba xa x a in 2 具有计算公式简单 程序设计容易 3 但需要选择较好的加速因子 5 5 迭代法敛散性判断方法迭代法敛散性判断方法 预备 定义 定义定义 1 1 称迭代公式中的矩阵 B 为迭代矩阵 1 kk xBxf 定义定义 2 设 A 为 n 阶方阵 i i 1 n 为 A 的特征值 称特征值模的最大值为矩 阵 A 的谱半径 记为 1 max i i n A 定义定义 2 称为矩阵 A 的谱 12 n 定义定义 3 Ak AA A 的谱为 k 1 2 12 kkk n 定义定义 3 Ak AA A 的谱半径为 1 max kkk i i n AA 已知 定理 定理定理 1 设 A 为任意 n 阶方阵 为任意由向量 范数诱导出的矩阵的范数 则 AA 定理定理 2 设 A 为 n 阶方阵 则对任意正数 存在一种矩阵范数 使得 AA 定理定理 3 设 A 为 n 阶方阵 则的充要条件为lim0 k k A 1A 辅助 定义 定义 定义 若 n 阶方阵 A aij 满足且至少有一个 i 1 1 2 n iiij j j i aain 值 使上式中不等号严格成立 则称 A 为弱对角占优阵 若对所有 i 不等号均严 格成立 则称 A 为严格对角占优阵 定义 定义 如果矩阵 A 不能通过行的互换和相应列的互换成为形式其中 1112 22 0 AA A A11 A22为方阵 则称 A 为不可约 收敛设有线性方程组设有线性方程组 Ax bAx b 下列结论成立 下列结论成立 判断 条件 1 若 A 为严格对角占优阵或不可约弱对角占优阵 则 Jacobi 迭代法和 Gauss Seidel 迭代法均收敛 2 若 A 为严格对角占优阵 0 1 则松弛法收敛 3 若 A 为对称正定阵 0 2 则松弛法收敛 即 若 A 是对称正定阵 则松 弛法收敛的充要条件为 0 2 推论 推论 若迭代矩阵满足 M 1 则迭代公式产生的向量序列 x k 收敛 定理 定理 对任意初始向量 x 0 和右端项 g 由迭代格式 x k 1 Mx k g 产生的向量 序列收敛的充要条件为 1M 推论 推论 松弛法收敛的必要条件是 0 1 称 x 是 m 重根 2 2 求根的两个步骤 求根的两个步骤 1 确定根的初始近似值 称之为初始近似根 一般为一个包含根的区间 称为 有根区 间 逐步扫描法 原理 设f x 在 a b 连续 且f a f b 0 则由连续函数的性 质知f x 0 在 a b 内至少有一个根 若f x 在 a b 上单调 则f x 0 在 a b 上有且仅有一个根 2 根的精确化 根据根的初始近似值按某种方法逐步精确化 直至满足预先要求的精度为 止 二分法 简单迭代法 牛顿迭代法 弦截法 2 2 分类 分类 二分法 原理 若 f C a b 且 f a f b 0 则 f 在 a b 上必有一 根 x 实施 将方程根的区间平分为两个小区间 然后判断根在哪个小区间 舍去无 根的区间 而把有根区间再一分为二 再判断根属于哪个更小的区间 如此周 而复始 直到求出满足精度要求的近似根 停止 或 11kk xx 2 f x 误差分析 对于给定的精度 可估计二分法所需的步数 k 2 k k ba xx 优点 简单 对 f x 要求不高 只要连续即可 缺点 无法求复根及偶重根 收敛慢 简单迭 代法 基本思想 基本思想 f x 0 同解变形 x g x 构造公式 xk 1 g xk 给初值 x0 若 xk x 且 g x 连续 x 就是 f x 0 的根 区间收敛 区间收敛 设方程 x g x 有根 x g x 可微 若 I 当 x a b 时 g x a b II 0 L 1 使得 g x L 1 对 x a b 成立 则任取 x0 a b 由 xk 1 g xk 得到的序列收敛于 g x 在 a 0 k k x b 上的唯一不动点 注 1 定理中的 L 1 非常重要 否则不能保证收敛 且 L 越小 收敛越快 注 2 为恰当估计 可以把有根区间取得适当小 g x 补充 补充 1 迭代是否收敛除了依赖于迭代函数外 还依赖于有根区间 2 设方程 x g x 在区间 a b 内有根 若总有 则迭代公式对任 1g x 意 a b 上的初值均发散 局部收敛 局部收敛 定义 定义 设 x 是 g x 的不动点 若存在 x 的某 邻域 B x x x 对 迭代产生的序列且收敛到 x 则称局部收敛 0 xB k xB 1 kk xg x 定理 设 x 是 g x 的不动点 若 g x 在 x 的某 邻域连续 且有 g x 1 时 超线性收敛 p 2 时 平方收敛 定理 定理 设 x 为 x g x 的不动点 若 p 2 p g xCBx 且 则 xk 1 g xk 在内 p 阶收敛 1 0 p g xgx Bx 牛顿迭 代法 原理 将非线性方程线性化原理 将非线性方程线性化 泰勒展开泰勒展开 2 0000 2 f f xf xfxxxxx 1 k kk k f x xx fx 局部收敛性局部收敛性 设 f C2 a b 若 x 为 f x 在 a b 上的根 且 f x 0 则存 在 x 的邻域使得任取初值Newton s Method 产生的序列 Bx 0 xBx xk 收敛到 x 且满足有 1 2 lim 2 k k k xxfx xxfx 只要就有 p 2 重根是线性收敛的 1 2 lim 2 k k k efx efx 0fx 注 注 1 牛顿法要求初值充分接近根以保证局部收敛性 2 牛顿迭代法的主要优点是收敛较快 是平方收敛的缺点是公式中需要求 f x 的导数 若 f x 比较复杂 则使用牛顿公式就大为不便 弦截法针对问题针对问题 重根问题 n f xxxq x 问题问题 1 1 若 Newton s Method 是否仍收敛 0fx K1 K1 有局部收敛性 但重数 n 越高 收敛越慢 问题问题 2 2 如何加速重根的收敛 K2 K2 将求 f 的重根转化为求另一函数的单根 令则 f 的重根 f x x fx 的单根 下山法 下山法 原理 原理 若由 xk 得到的 xk 1 不能使 f 减小 则在 xk 和 xk 1 之间找一个更好 的点 使得 1 时就是 Newton s Method 公式 1k x 1 kk f xf x 当 1 代入效果不好时 将 减半计算 1 1 kk kkkk kk f xf x xxxx fxfx 弦截法弦截法 Newton s Method 一步要计算 f 和 f 相当于 2 个函数值 比较费时 现 用 f 的值近似 f 可少算一个函数值 需要需要 2 2 个初值个初值 x x0 0 和和 x x1 1 切线斜率 割线斜率 1 1 kk k kk f xf x fx xx 1 1 1 kkk kk kk f xxx xx f xf x 弦截法与牛顿法相比较弦截法与牛顿法相比较 相同之处 都是线性化方法 不同之处 牛顿法在计算 xk 1 时只用到前一步的值 xk 故这种方法称为单点迭 代法 而弦截法在求 xk 1 时要用到前两步的值 xk 和 xk 1 因此这种方法称为 多点迭代法 弦截法的收敛速度弦截法的收敛速度 与牛顿法相比 弦截法的收敛速度也是比较快的 可以证明 弦截法具有超线 性收敛速度 收敛阶为即 1 15 1 618 2 p 1 1 618 0 k k xx ck xx 第第 6 6 章章 解常微分方程解常微分方程 1 1 定义 定义 理论上可以证明 只要函数理论上可以证明 只要函数 f x y 适当光滑适当光滑 关于关于 y 满足李普希兹满足李普希兹 00 yf x y y xy Lipschitz 条件条件则初值问题的解存在唯一 则初值问题的解存在唯一 f x yf x yL yy 2 2 两种解 两种解 一般解 解析 解 y y xi 在