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\) 。...

2022-03-02-GAMES202高质量实时渲染-Lecture7-8-3DGI

Lecture 7-8 Real-time Global Illumination (3D GI) Introduction GI is complex Ray tracing … Hack方法:Blinn-Phong——统一大小的Ambient项 in RTR:直接光照 + 一次间接光照 一次间接光照:Q点接收到直接光照后,作为次级光源照射P点的结果 核心问题: 要计算间接光照需要知道 被直接光照照亮的表面有哪些? / 哪些是次级光源? 借助Shadow Map 每一个次级光源的“贡献”是多少? 求和 每一个次级光源作为一个Area Light Reflective Shadow Maps (RSM) 获得光源的Shadow Map,存储光源“可见”的深度/世界坐标/法线/Flux等(即Reflective Shadow Maps),视作多个多个点次级光源,eg. Reflective Shadow Maps为512*512,则有512*512个点光源。 次级光源的反射方向未知——假定次级光源物体材质均为Diffuse。(不假设接收物为Diffuse) Recall 一个Patch(Reflective Shadow Maps的一个像素)的“贡献 \[ \begin{array}{l}\begin{aligned}L_o(\mathrm p,\omega_0)&=\int_{\Omega_\mathrm{patch}}L_i(\mathrm p,\omega_i)V(\mathrm p,\omega_i)f_r(\mathrm p,\omega_i,\omega_0)\cos\theta_i\,\mathrm d \omega_i\\ &=\int_{A_\mathrm{patch}}L_i(\mathrm q\rightarrow \mathrm p)V(\mathrm p,\omega_i)f_r(\mathrm p,\mathrm q\rightarrow \mathrm p,\omega_0)\dfrac{\cos\theta_p\cos\theta_q}{\|q-p\|^2}\,\mathrm d A \end{aligned}\\\\ f_r=\dfrac{\rho}{\pi}\\ L_i=f_r\cdot\dfrac{\Phi}{\mathrm d A}\quad(\Phi\ \text{is the incident flux / energy}) \end{array} \] 故对每个Reflective Shadow Maps的像素只需存储其 \(\Phi\) , \(\mathrm d A\) 在积分中被约掉; 由于计算复杂、忽略次级光源的Visibility项。 则有:(原论文中为 \(P\rightarrow Q\) ,故论文中原式为下式中 \(q\) 换成 \(p\) ) \[ E_q(x,n)=\Phi_q\dfrac{\max\{0,\langle n_q|x-x_q\rangle \}\max\{0,\langle n|x_q-x\rangle \}}{\|x-x_q\|^4} \]...

2021-03-01-数值分析-Day04-Jacobi-GaussSeidel

3.1 - 6 迭代法 基本思想 对线性方程组 \(Ax=b\) ,当 \(A\) 为低阶稠密矩阵时,选主元Gauss消去/Doolittle分解均为有效方法。 工程应用中 \(A\) 常为高阶稀疏矩阵,适用迭代法求解:利好计算机存储与性能。 通法: 将 \(Ax=b\) 改写为 \(x=B_0x+f\) 任取初始值,如 \(x^{(0)}=(0,0,0)^T\) ,将其带入得到方程组解 \(x^{(1)}=B_0x^{(0)}+f\) 依次得: \(x^{(2)}=B_0x^{(1)}+f,\ x^{(2)}=B_0x^{(1)}+f,\ \dots,\ x^{(k)}=B_0x^{(k-1)}+f,\ \dots\) 即得向量序列 \(x^{(0)},x^{(1)},\dots,x^{(k)}\) ,迭代公式 \(x^{(k)}=B_0x^{(k-1)}+f\) 迭代次数较高时,向量序列 \(x^{(k)}\) 有可能收敛至逼近精确解的值(不一定)。 根据 \(x=Bx+f\) 变形方式的不同,存在多种迭代算法。 定义1: 对于给定方程组 \(x=Bx+f\) ,用公式 \(x^{k+1}=Bx^{(k)}+f,\ (k=0,1,2,3,\dots)\) 逐步代入求近似解的方法称为迭代法(或称为一阶定常迭代法,这里 \(B\) 与 \(k\) 无关)。 如果 \(\lim\limits_{k\to\infty}x^{(k)}=x^*\) ,即向量序列收敛至精确解序列,则称此迭代法收敛,否则称发散。 由于需要研究 \(\{x^{(k)}\}\) 的收敛性,引进误差向量 \(\varepsilon^{(k+1)}=x^{(k+1)}-x^*\) 。易得到: \(\varepsilon^{(k+1)}=B\varepsilon^{(k)}\) ,递推得: \(\varepsilon^{(k)}=B\varepsilon^{(k-1)}=\dots=B^k\varepsilon^{(0)}\) 。 Jacobi迭代 通法细节: 将 \(A\) 分裂成 \(A=M-N\) ,其中 \(M\) 为可选择的非奇异矩阵,使 \(Mx=d\) 易解,一般选择为 \(A\) 的某种近似,称 \(M\) 为分裂矩阵。...