2021-03-11-数值分析-Day14-RungeKutta方法-线性多步方法

7.5 - 7.7 Runge-Kutta方法 单步高阶方法构造思路 设 \(y(x)\) 是一阶常微分方程初值问题的精确解,Taylor展开得: \[ \begin{aligned} \displaystyle y(x_{n+1})&=y(x_n)+y'(x_n)h+\frac{y''(x_n)}{2!}h^2+\dots+\frac{y^{(p)}(x_n)}{p!}h^p+\frac{y^{({p+1})}(x_n)}{(p+1)!}h^{p+1}\\ &=y(x_n)+hf(x_n,y(x_n))+\frac{h^2}{2!}f^{(1)}(x_n,y(x_n))+\dots+\frac{h^p}{p!}f^{(p-1)}(x_n,y(x_n))+O(h^{p+1})\end{aligned} \] 因此可建立节点处近似值 \(y_n\) 满足的差分公式: \[ \left\{\begin{array}{l}\displaystyle y_{n+1}=y_n+hf(x_n,y_n)+\frac{h^2}{2!}f^{(1)}(x_n,y_n)+\dots+\frac{h^p}{p!}f^{(p-1)}(x_n,y_n)\\y_0=\alpha,\quad n=0,1,\dots,N-1\end{array}\right. \] 称之为 \(\mathbf p\) 阶Taylor展开方法。 其中: \(\begin{array}{l}\displaystyle f^{(1)}(x,y)=\frac{\partial f(x,y)}{\partial x}+\frac{\partial f(x,y)}{\partial y}f(x,y)\\\displaystyle f^{(2)}(x,y)=\frac{\partial^2f}{\partial x^2}+2\frac{\partial^2f}{\partial x\partial y}f+\frac{\partial^2 f}{\partial y^2}f^2+\frac{\partial f}{\partial x}\frac{\partial f}{\partial y}+\left(\frac{\partial f}{\partial y}\right)^2f\\\dots\end{array}\) 计算过于复杂,很少直接使用 减少Taylor展开次数得: \[ y(x_{n+1})=y(x_n)+hy'(\xi)=y(x_n)+hf(\xi,y(\xi)),\quad x_n\le\xi\le x_{n+1} \] 构造差分方法即利用适当的函数值来近似计算 \(f(\xi,y(\xi))\) 。 Euler方法用 \(K_1\) 作为其近似,其 \(y_{n+1}\) 表达式与精确解的Taylor展式前 \(2\) 项一致。为 \(1\) 阶方法。 改进Euler方法用 \(K_1,K_2\) 的线性组合作为其近似,其 \(y_{n+1}\) 表达式与精确解的Taylor展式前 \(3\) 项一致。为 \(2\) 阶方法。 能否增加计算 \(f(x,y)\) 的次数来提高方法阶数? Runge-Kutta方法 \[ \left\{\begin{array}{l} y_{n+1}=y_n+h(\lambda_1K_1+\lambda_2K_2+\dots+\lambda_pK_p)\\ K_1=f(x_n,y_n)\\ K_2=f(x_n+\alpha_2h,y_n+h\beta_{21}K_1)\\ \dots\\ K_p=f(x_n+\alpha_ph,y_n+h\sum\limits_{i=1}^{p-1}\beta_{pi}K_i) \end{array}\right....

2021-03-10-数值分析-Day13-差分公式

7.1 - 7.4 差分公式 一阶常微分方程初值问题 一阶常微分方程初值问题的一般形式为: \[ \left\{\begin{array}{l}\displaystyle\frac{dy}{dx}=f(x,y),\quad a\le x\le b\\y(a)=\alpha\end{array}\right. \] 其中 \(f(x,y)\) 为已知函数, \(\alpha\) 为给定的值。 在许多数学模型中,上述方程通常以 \(x\) 描述时间,而定解条件 \(y(a)=\alpha\) 则给出了函数 \(y(x)\) 在初始时刻的取值。因此称为初值问题。 问题: + 上述方程何时存在唯一解 + 如何计算 \(y(x)\) Lipschitz条件: 若函数 \(f(x,y)\) 在区域 \(\{a\le x\le b,\ m<y<M\}\) 上连续,满足 \[ \forall y,\bar{y},\ |f(x,y)-f(x,\bar{y})|\le L|y-\bar{y}| \] 其中 \(L>0\) 为Lipschitz常数(此处Lipschitz常数可以 \(\ge1\) ),则初值问题在初始时刻 \(a\) 的某个邻域上存在唯一解。 (不满足Lipschitz条件时,不一定存在唯一解。) 构造一阶常微分方程初值问题数值解法 假设初值问题的解 \(y=y(x)\) 唯一存在且足够光滑。对求解区域 \([a,b]\) 做等距剖分 \(a=x_0<x_1<x_2<\dots<x_n<\dots<x_N=b\) 。称 \(h=(b-a)/N\) 为剖分步长, \(x_n=a+nh,\ n=0,1,\dots,N\) 为剖分节点。数值解法即求精确解 \(y(x)\) 在剖分节点 \(x_n\) 上的值 \(y(x_n)\) 的近似值 \(y_n\) 。...

2021-03-09-数值分析-Day12-续数值积分-数值微分

续:6.1 - 6.11 数值积分 复化求积公式 Newton-Cotes求积公式的精度随着求积节点数的增加而增加,但求积节点数 \(\ge8\) 时,Newton-Cotes公式数值不稳定。实际应用中,将积分区间分成若干个小区间分别求积分再求和,即复化求积公式的基本思想。 在区间 \([a,b]\) 上,取等距节点 \(x_k=a+kh,\ k=0,1,\dots,n\) , 由定积分的区间可加性得 \(\displaystyle\int_a^bf(x)dx=\sum_{k=1}^n\int_{x_{k-1}}^{x_k}f(x)dx\) 。 若在每个小区间 \(x_{k-1},x_k\) 用梯形公式,则有复化梯形公式 \(T_n\) : \[ \displaystyle I=\int_a^bf(x)dx\approx T_n=\frac{h}{2}\sum_{k=1}^n\left[f(x_{k-1})+f(x_k)\right]=\frac{h}{2}\left[2\sum_{k=1}^{n-1}f(x_k)+f(a)+f(b)\right] \] 复化梯形公式的的误差为: \[ \begin{array}{l}\displaystyle I-T_n=-\frac{h^3}{12}[f''(\xi_1)+\dots+f''(\xi_n)]=-\frac{h^2(b-a)}{12}f''(\eta),\quad\eta\in(a,b)\\\displaystyle \left|I-T_n\right|\le\frac{(b-a)^3}{12n^2}\max_{a\le x\le b}|f''(x)|\end{array} \] 可知复化梯形公式收敛,且要使得误差 \(\le\varepsilon\) ,只要 \(\left|I-T_n\right|\le\varepsilon\) 或 \(\displaystyle n>\sqrt{\frac{(b-a)^3\max_{a\le x\le b}|f''(x)|}{12\varepsilon}}\) 。 同理,复化Simpson公式 \(S_n\) : \[ \displaystyle I=\int_a^bf(x)dx\approx S_n=\frac{h}{6}\left[4\sum_{k=1}^nf(x_{k-\frac{1}{2}})+2\sum_{k=1}^{n-1}f(x_k)+f(a)+f(b)\right] \] 复化Simpson公式的误差为: \[ \begin{array}{l}\displaystyle I-S_n=-\frac{h^4(b-a)}{2880}f^{4}(\eta),\quad\eta\in(a,b)\\\displaystyle \left|I-S_n\right|\le\frac{(b-a)^5}{2880n^4}\max_{a\le x\le b}|f^{(4)}(x)|\end{array} \] 可知收敛,且要使得误差 \(\le\varepsilon\) ,只要 \(\left|I-S_n\right|\le\varepsilon\) 或 \(\displaystyle n>\sqrt[4]{\frac{(b-a)^5\max_{a\le x\le b}|f^{(4)}(x)|}{2880\varepsilon}}\) 。 同理,复化Cotes公式 \(C_n\) :...

2021-03-08-数值分析-Day11-插值型数值积分

6.1 - 6.11 数值积分 牛顿-莱布尼茨公式: \(\displaystyle\int_a^bf(x)dx=F(b)-F(a)\) 问题:很多函数找不到原函数;很多函数只知道离散的点值而无表达式。 【例】弧长积分: \(L=\displaystyle\int_a^b\sqrt{1+(f'(x))^2}dx\) 由定积分的定义 \(\displaystyle I=\int_a^bf(x)dx=F(b)-F(a)=\lim_{\Delta x\to0}\sum_{i=0}^nf(x_i)\Delta x_i\) ,可以想到利用被积函数在区间 \([a,b]\) 上一些离散节点 \(x_k\) 处的函数值 \(f(x_k)\) 的线性组合来得到近似积分值: \(\displaystyle I=\sum_{k=0}^nA_kf(x_k)\) 。则得求积公式的一般形式: \(\displaystyle\int_a^bf(x)dx\approx\sum_{k=0}^nA_kf(x_k)\) ,其中 \(\{x_k\}\) 为求积点, \(A_k\) 为求积系数。或表示为 \(\displaystyle\int_a^bf(x)dx=\sum_{k=0}^nA_kf(x_k)+R[f]\) ,其中 \(R[f]\) 为求积公式的误差或余项。 积分中值定理:在 \([a,b]\) 内存在一点 \(\xi\) ,有 \(\displaystyle\int_a^bf(x)dx=(b-a)f(\xi)\) 。 问题: \(\xi\) 未知 取特殊点为 \(\xi\) 求近似解: 左矩形求积公式: \(\displaystyle\int_a^bf(x)dx\approx f(a)(b-a),\quad R[f]=\frac{(b-a)^2}{2}f'(\xi)\ (\xi\in(a,b))\) 右矩形求积公式: \(\displaystyle\int_a^bf(x)dx\approx f(b)(b-a),\quad R[f]=-\frac{(b-a)^2}{2}f'(\eta)\ (\eta\in(a,b))\) 中矩形求积公式: \(\displaystyle\int_a^bf(x)dx\approx f(\frac{a+b}{2})(b-a),\quad R[f]=-\frac{(b-a)^3}{24}f''(\eta)\ (\eta\in(a,b))\) 代数精度 若求积公式 \(\displaystyle\int_a^bf(x)dx\approx\sum_{k=0}^nA_kf(x_k)\) 对 \(f(x)=x^j\ (j=0,1,\dots,m)\) 都精确成立,但对 \(f(x)=x^{m+1}\) 不精确成立。即: \(\left\{\begin{array}{l}\displaystyle\int_a^bx^jdx=\sum_{k=0}^nA_kx_k^j\quad j=0,1,\dots,m\\\displaystyle\int_a^bx^{m+1}dx\approx\sum_{k=0}^nA_kx_k^{m+1}\end{array}\right....

2021-03-07-数值分析-Day10-三次样条插值-最小二乘拟合

续:5.8 - 5.10 三次样条插值 三转角方法 考虑第一种一般边界条件: \(S'(x_0)=f_0',\ S'(x_n)=f_n'\) ,即已知两端点一阶导数值。 令 \(m_i=S'(x_i),\ i=0,1,\dots,n\) ,利用三次Hermite插值,得到 \(S(x)=\displaystyle \sum_{j=0}^n[y_j\alpha_j(x)+m_j\beta_j(x)]\) ,其中 \(\alpha_j(x),\ \beta_j(x)\) 为分段三次Hermite插值的基函数。再由边界条件得 \(S'(x_0)=f_0',\ S'(x_n)=f_n'\) 即可解出 \(m_i\) 在各插值点的取值。记 \(\displaystyle \lambda_i=\frac{h_{i+1}}{h_i+h_{i+1}},\ \mu_i=1-\lambda_i=\frac{h_i}{h_i+h_{i+1}},\ g_i=3(\lambda_if[x_{i-1},x_i]+\mu_if[x_i,x_{i+1}])\) , 最终解得: \[ \begin{array}{c}\lambda_im_{i-1}+2m_i+\mu_im_{i+1}=g_i\\ \begin{pmatrix} 2 &\mu_1 & & & & \\ \lambda_2 &2 &\mu_2 & & & \\ &\ddots &\ddots &\ddots & & \\ & &\ddots &\ddots &\ddots & \\ & & &\lambda_{n-2} &2 &\mu_{n-2} \\ & & & &\lambda_{n-1} &2 \end{pmatrix} \begin{pmatrix} m_1 \\ m_2 \\ \vdots \\ \vdots \\ m_{n-2} \\ m_{n-1} \end{pmatrix}= \begin{pmatrix} g_1-\lambda_iy_0' \\ g_2 \\ \vdots \\ \vdots \\ g_{n-2} \\ g_{n-1}-\mu_{n-1}y_n' \end{pmatrix} \end{array} \] 利用大型稀疏矩阵线性方程数值解法,解出 \(m_i\) ,即解得 \(x\in[x_{i-1},x_i]\) 时,有:...

2021-03-06-数值分析-Day09-分段插值-三次样条函数

5.6 - 5.7 分段插值 Runge现象:在一组等间插值点上使用具有高次多项式的多项式插值时出现的区间边缘处的振荡问题。 分段Lagrange插值 分段线性插值 通过相邻两个插值点作线性插值。已知节点 \(a=x_0<x_1<\dots<x_n=b\) ,记 \(h_k=x_{k+1}-x_k,\ h=\max\limits_{0\le k\le n-1}h_k\) ,记分段插值函数为 \(I_h(x)\) ,为 \(n-1\) 段折线。 余项估计有 \(|f(x)-I_h(x)|\le \displaystyle\frac{\max\limits_{a\le x\le b}|f''(x)|}{8}h^2\) ,说明分段线性插值函数具有一致收敛性。 分段二次插值 相邻三个插值点作二次插值。 课程中以线性插值中两邻点中间值,作为补充条件,即取 \(x_{i-0.5}=(x_i+x_{i-1})/2\) 作为每组中的第三个插值点,使得两点间距为 \(h_k/2\) 。按照这种方式得到余项估计 \(|f(x)-I_h(x)|\le \displaystyle\frac{\max\limits_{a\le x\le b}|f'''(x)|}{72\sqrt{3}}h^3\) 。 PS:个人认为应直接取连续三个插值点,即 \(\{x_0,x_1,x_2\}\ \{x_2,x_3,x_4\}\ \{x_4,x_5,x_6\}\ \dots\) 作为插值点进行二次插值。 分段Lagrange插值的问题:区间内出现不可导点 分段Hermite插值 设节点 \(a\le x_0<x_1<\dots<x_n\le b,\ h_i=x_i-x_{i-1}\ (i=1,2,\dots,n)\) ,给出插值条件: \(y_k=f(x_k),\ y'_k=f'(x_k),\ (k=0,1,\dots,n)\) 。则每区间 \([x_{i-1},x_i]\) 具有四个插值条件。构造三次多项式 \(H_3^{(i)}(x)\) : \[ \begin{array}{c}H_3^{(i)}(x)=\varphi_{i-1}(x)y_{i-1}+\varphi_i(x)y_i+\psi_{i-1}(x)y'_{i-1}+\psi_i(x)y'_i\\ \left\{\begin{aligned} &\varphi_{i-1}(x_{i-1})=1 &&\varphi_{i-1}(x_i)=0 &&\varphi'_{i-1}(x_{i-1})=0 &&\varphi'_{i-1}(x_i)=0\\ &\varphi_i(x_{i-1})=0 &&\varphi_i(x_i)=1 &&\varphi'_i(x_{i-1})=0 &&\varphi'_i(x_i)=0\\ &\psi_{i-1}(x_{i-1})=0 &&\psi_{i-1}(x_i)=0 &&\psi'_{i-1}(x_{i-1})=1 &&\psi'_{i-1}(x_i)=0\\ &\psi_i(x_{i-1})=0 &&\psi_i(x_i)=0 &&\psi'_i(x_{i-1})=0 &&\psi'_i(x_i)=1\\ \end{aligned}\right....

2021-03-05-数值分析-Day08-Lagrange插值-Newton插值

5.1 - 5.3 插值的引入与Lagrange插值 插值的定义 设函数 \(y=f(x)\) 在区间 \([a,b]\) 上连续,给定 \(n+1\) 个点: \(a\le x_0<x_1<\dots<x_n\le b\) 。 已知 \(f(x_k)=y_k(k=0,1,\dots,n)\) ,在函数类 \(P\) 中寻找一函数 \(\varphi(x)\) 作为 \(f(x)\) 的近似表达式,使满足: $(x_k)=f(x_k)=y_k, k=0,1,2,,n $ 。则称 \(y=f(x)\) 为被插值函数,称 \(\varphi(x)\) 为插值函数。称 \(x_0,x_1,\dots,x_n\) 为插值节点; \(\varphi(x_k)=f(x_k)=y_k,\ k=0,1,2,\dots,n\) 为插值条件,寻求插值函数的方法称为插值方法。 在构造插值函数时,函数类 \(P\) 的不同选取,对应不同的插值方法,这里主要讨论函数类为代数多项式的插值方法,即多项式插值。若用 \(P_n\) 表示所有次数不超过 \(n\) 的多项式函数类,则若 \(p_n(x)\in P_n\) ,则 有\(p_n(x)=a_0+a_1x+\dots+a_nx^n\) ,由 \(n+1\) 个系数唯一确定。若 \(p_n(x)\) 满足插值条件,即 \(\left\{\begin{array}{l}a_0+a_1x_1+\dots+a_nx_1^n\\a_0+a_1x_2+\dots+a_nx_2^n\\\dots\\a_0+a_1x_n+\dots+a_nx_n^n\end{array}\right.\) 。令 \(\{a_0,a_1,\dots,a_n\}\) 为元,则该方程系数行列式为 \(\begin{vmatrix}1&x_0&\cdots&x_0^n\\1&x_1&\cdots&x_1^n\\\vdots&\vdots&\ddots&\vdots\\1&x_n&\cdots&x_n^n\end{vmatrix}\) ,由范德蒙行列式得: \(\begin{vmatrix}1&x_0&\cdots&x_0^n\\1&x_1&\cdots&x_1^n\\\vdots&\vdots&\ddots&\vdots\\1&x_n&\cdots&x_n^n\end{vmatrix}=\begin{vmatrix}1&1&\cdots&1\\x_0&x_1&\cdots&x_n\\\vdots&\vdots&\ddots&\vdots\\x_0^n&x_2^n&\cdots&x_n^n\end{vmatrix}=\prod\limits_{0\le<j\le n}(x_j-x_i)\neq0\) ,因此该方程有解。 由此得定理:满足上述条件的插值问题, \(p_n(x)\) 存在且唯一。 Lagrange插值 线性插值 最简单的插值问题:已知两点 \((x_0,y_0)\ (x_1,y_1)\) 。通过此两点的插值多项式是一条直线,即两点式: \(\displaystyle L_1(x)=\frac{x-x_1}{x_0-x_1}y_0+\frac{x-x_0}{x_1-x_0}y_1\) 。称 \(L_1(x)\) 为线性插值函数。...

2021-03-04-数值分析-Day07-Newton迭代法

4.11 - 15 牛顿迭代法 Newton迭代法 泰勒级数: \(\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{f^{(n)}(a)}{n!}(x-a)^n\) 泰勒展开公式: \(\displaystyle f(x)=\sum_{n=0}^n\frac{f^{(n)}(a)}{n!}(x-a)^n+R_n(x)\) 皮亚诺型余项: \(R_n(x)=o[(x-a)^n]\) ,即当 \(x\to a\) 时,余项为 \((x-a)^n\) 的高阶无穷小 拉格朗日型余项: \(R_n(x)=\displaystyle\frac{f^{(n+1)}(\theta)}{(n+1)!}(x-a)^{(n+1)},\ \theta\in(a,x)\) 积分型余项: \(R_{n}(x)=\displaystyle\int_{a}^{x}{\frac{f^{{(n+1)}}(t)}{n!}}(x-t)^{n}\,dt\) 原理:将非线性方程线性化——Taylor展开 取 \(x_0\) 作为初始近似值,将 \(f(x)\) 在 \(x_0\) 处做一阶Taylor展开: \[ \begin{array}{c}f(x)=f(x_0)+f'(x_0)(x-x_0)+\displaystyle{f''(\xi)}{2!}(x-x_0)^2,\quad \xi\in(x_0,x)\\ 0=f(x^*)\approx f(x_0)+f'(x_0)(x-x_0)\quad\Rightarrow\quad x^*\approx x_0-\displaystyle\frac{f(x_0)}{f'(x_0)}\\ \left\{\begin{array}{l}x_1=x_0-\displaystyle\frac{f(x_0)}{f'(x_0)}\\ x_{k+1}=x_k-\displaystyle\frac{f(x_k)}{f'(x_k)}\quad\leftarrow\ \textbf{Newton迭代公式}\end{array}\right.\end{array} \] Newton迭代法的收敛性 定理:设 \(f\in C^2[a,b]\) (二阶连续可微),若 \(x^*\) 为 \(f(x)=0\) 在 \([a,b]\) 上的根,且 \(f'(x^*)\neq0\) ,则Newton迭代法是二阶收敛的,且有 \(\displaystyle\lim_{k\to\infty}\frac{x_{k+1}-x^*}{(x_k-x^*)^2}=\frac{f''(x^*)}{2f'(x^*)}\) 。 初值的选取:令 \(c=\displaystyle\frac{\max|f''(x)|}{2\min|f'(x)|}\) ,则有: \[ c|x_{k+1}-x^*|\le(c|x_{k}-x^*|)^2\le(c|x_{k-1}-x^*|)^4\le\dots\le\le(c|x_{k+1}-x^*|)^{2^{k+1}} \] 因此, \(c|x_0-x^*|=1\ \Rightarrow\ |x_0-x^*|\le\displaystyle\frac{2\min|f'(x)|}{\max|f''(x)|}\) 时,Newton迭代法收敛。 Newton下山法 调整 \(x_0\) 的选取来使得Newton迭代法满足收敛条件。...

2021-03-03-数值分析-Day06-非线性方程的迭代解法及收敛性

4.1-3 非线性方程简介及二分法:略 4.4 - 10 简单迭代法的构造与收敛性 构造简单迭代法 \[ \begin{array}{c}\begin{aligned} f(x)=0\quad&\Leftrightarrow\quad x=\varphi(x)\\ f(x)的根\quad&\Leftrightarrow\quad\varphi(x)的不动点 \end{aligned}\end{array} \] 其中 \(x_{k+1}=\varphi(x_k),\quad (k=0,1,2,\dots)\) 称为迭代格式, \(\varphi(x)\) 称为迭代函数。 简单迭代法的收敛条件 几何解释:求方程 \(x=\varphi(x)\) 的根,就是求直线 \(y=x\) 和曲线 \(y=\varphi(x)\) 的交点的横坐标。(图略。) 如果 \(x_{k+1}=\varphi(x_k)\) 收敛,则迭代函数 \(y=\varphi(x)\) 的曲线走势平坦,即 \(\left|\varphi'(x)\right|<1\) ; 如果 \(x_{k+1}=\varphi(x_k)\) 发散,则迭代函数 \(y=\varphi(x)\) 的曲线走势陡峭,即 \(\left|\varphi'(x)\right|\ge1\) ; 迭代法收敛的判定定理:设函数 \(\varphi(x)\) 满足条件: \[ \begin{array}{l}(1)\quad \forall x\in[a,b],\ a\le\varphi(x)\le b;\\ (2)\quad \exists0\le L<1,\ \begin{array}{l}\forall x,y\in[a,b],\ |\varphi(x)-\varphi(y)|\le L|x-y|\\或\ |\varphi'(x)\le L<1|\end{array}\end{array} \] 则 \(\forall x_0\in[a,b]\) ,由 \(x_{k+1}=\varphi(x_K)\) 得到的序列 \(\{x_k\}_{k=0}^\infty\) 收敛于 \(\varphi(x)\) 在 \([a,b]\) 上的唯一不动点。并且由误差估计式: \(\begin{array}{l}\displaystyle\left|x^*-x_k\right|\le\frac{1}{1-L}\left|x_k-x_{k-1}\right|\\\displaystyle\left|x^*-x_k\right|\le\frac{L^k}{1-L}\left|x_1-x_0\right|\end{array}\) 。由第一式分析误差;由第二式得到结论 \(L\) 越小,收敛越快 。...

2021-03-02-数值分析-Day05-SOR-迭代法收敛性

续:3.1 - 6 迭代法 逐次超松弛迭代法(SOR迭代法) 选取分裂矩阵 \(M\) 为带参数的下三角阵: \(M=\displaystyle\frac{1}{\omega}(D-\omega L),\ B=I-M^{-1}A,\ f=M^{-1}b\) ,其中 \(w>0\) 为可选择的松弛因子。 构造迭代法,迭代矩阵为: \(L_\omega=I-\omega(D-\omega L)^{-1}A=(D-\omega L)^{-1}((1-\omega)D+\omega U)\) 。 则解 \(Ax=b\) 的SOR方法即为: \(\begin{array}{l}\left\{\begin{array}{l}x^{(0)}\\x^{(k+1)}=L_\omega x^{(k)}+f\quad(k=0,1,\dots)\end{array}\right.\\其中\begin{array}{l}L_\omega=(D-\omega L)^{-1}((1-\omega)D+\omega U),\\f=\omega(D-\omega L)^{-1}b\end{array}\end{array}\) 。 推导得: \(\begin{array}{l}(D-\omega L)x^{(k+1)}=((1-\omega)D+\omega U)x^{(k)}+\omega b\\或Dx^{(k+1)}=Dx^{(k+1)}+\omega(b+Lx^{(k+1)}+Ux^{(k)}-Dx^{(k)})\end{array}\) 。 分量计算公式为: \(\displaystyle x_i^{(k+1)}=x_1^{(k)}+\omega(b_i-\sum_{j=1}^{i-1}a_{ij}x_j^{(k+1)}-\sum_{j=i}^{n}a_{ij}x_j^{(k)})/a_{ii}\) 。 可令 \(\Delta x_i=\omega(b_i-\sum_{j=1}^{i-1}a_{ij}x_j^{(k+1)}-\sum_{j=i}^{n}a_{ij}x_j^{(k)})/a_{ii}\) ,则 \(x_i^{(k+1)}=x_i^{(k)}+\Delta x_i\) 。 Gauss-Seidel迭代法是SOR迭代法的一个特殊形式(系数 \(\omega=1\) )。 当 \(\omega<1\) 时,称为超松弛法;当 \(\omega>1\) 时,称为低松弛法。 计算机中,常用 \(\max\limits_{1\le i\le n}|\Delta x_i|=\max\limits_{1\le i\le n}\left|x_i^{(k+1)}-x_i^{(k)}\right|<\varepsilon\) 或者 \(\left\|r^{(k)}\right\|=\left\|b-Ax^{(k)}\right\|\) 作为迭代终止条件。 迭代法的收敛性 设 \(Ax=b\) ,其中 \(A\in R^{n\times n}\) 为非奇异矩阵,记 \(x^*\) 为原方程组精确解,且设有等价的方程组: \(Ax=b\Leftrightarrow x=Bx+f\) ,则 \(x^*=Bx^*+f\) 。设有一阶定常迭代法 \(x^{(k+1)}=Bx^{(k)}\) 。引进误差向量 \(\varepsilon^{(k)}=x^{(k)}\) ,得到误差向量递推公式 \(\varepsilon^{(k+1)}=B\varepsilon^{(k)}\ \Rightarrow\ \varepsilon^{(k)}=B^k\varepsilon^{(0)}\) 。则研究问题从 \(\varepsilon^{(k)}\to0\) 转换为 \(B^k\to0\) 。...