数值分析复习整理
数值分析复习整理
点击此处查看复习课整理
秦九韶算法
每次提取一个x出来，这样会减少乘法次数
误差与稳定性分析
误差的定义和来源
误差的定义
人们用误差来描述数值计算中近似解的精确程度
误差的来源
从实际问题中抽象出数学模型——模型误差
通过测量和实验得到模型中的各种数据——观测误差
数学模型的数值求解——截断误差(方法误差)
机器字长有限——舍入误差
数值分析这门课的误差：
总假定数学模型是准确的，因而不考虑模型误差和观测误差
主要研究截断误差和舍入误差对计算结果的影响
举例：
泰勒公式只取前面几项，后面的项不要了，就是截断误差
无限循环小数，后面不要了，算是四舍五入，是舍入误差
绝对误差
\(x\)为精确值，\(x^*\)为近似值，\(e^*\)就是绝对误差 \[ e^*=x^*-x \] 绝对误差 = 近似值 - 精确值
绝对误差，简称误差
说明：
绝对误差可正可负
绝对误差通常是不可知的
绝对误差限
存在一个正数\(\varepsilon^*\)，使得： \[ |e^*|=|x^*-x|\le\varepsilon^* \] 则\(\varepsilon^*\)称为绝对误差限，简称：误差限
精确值\(x=x^*\pm\varepsilon^*\)
误差限，实际上就是绝对误差绝对值最大时的取值
说明
做误差估计时所求的是绝对误差限，越小越好
绝对误差限不能很好地表示近似值的精确程度
相对误差
相对误差\(e_r^*\)比绝对误差多除了一个精确值\(x\)
但是实际计算中，精确值难以求出，则也可以除近似值\(x^*\)
近似值的精确程度，取决于相对误差的大小
相对误差限
实际计算中我们所能得到的是误差限
相对误差限，实际上就是相对误差绝对值最大时的取值
例题
近似值\(x^*=41\)，精确值\(x=40\)
误差为：\(e^*=41-40=1 min\)
相对误差为：\(e^*_r=\dfrac{41-40}{40}=0.025\)
误差最大时，\(x^*=50min\)
此时的相对误差为：\(e^*_r=\dfrac{50-40}{40}=0.25\)
最大的相对误差就是0.25，即\(|e^*_r|\le\varepsilon^*_r=0.25\)
有效数字
有效数字与绝对误差限
定义太麻烦，看描述：
这个描述的意思是：
给定一个数字，判断它的误差限
\(n\)为写成科学计数法以后数字的位数
\(m\)为写成科学计数法以后10的阶数
比如\(385.6\)这个数，写成科学计数法就是\(3.856\times10^2\)，对应的n为4，m为2
就可以通过m和n求出这个数的绝对误差限：\(|x^*-x|\le0.5\times10^{m-n+1}=0.5\times10^{2-4+1}=0.5\times10^{-1}\)
例题
先看给出的两个数，3.1415和3.1416，都是5位
但是这两个数都已知了精确值\(\pi=3.1415926...\)，这个精确值如果四舍五入只剩5个数就是\(3.1416\)
很明显\(3.1415\)这个就是没有四舍五入的数，所以最后一位没用，看成\(3.141\)就行
这样处理之后，有效数字的个数就是数的个数：\(3.141\)有4个数，\(n\)为4；\(3.1416\)有5个数，\(n\)为5
注意：只有给出精确值了才能这样处理，否则都是先写成科学计数法，然后看数字位数
保留有效数字的原则，就是写成科学计数法，然后保留到对应位数
比如第二个数：0.03785551，写成科学计数法就是\(3.785551\times10^{-2}\)，数出5位四舍五入就是\(3.7856\times10^{-2}\)，即0.037856
说明：
按四舍五入原则得到的数字是有效数字
一个数末尾的 0 不可以随意添加或省略
有效数字与相对误差限
有效数字推相对误差限
给定一个数字，判断它的相对误差限
\(a_1\)就是写成科学计数法的第一位，不能是0
例题
\[ \begin{align*} &1234.5678=1.2345678\times10^{3}\\ &n=8,m=3\\ 绝对误差限&: \varepsilon^*\le0.5\times10^{m-n+1}=0.5\times10^{-4}\\ 相对误差限&: \varepsilon^*_r\le\frac{1}{2\times a_1}\times10^{1-n}=\frac{1}{2}\times10^{-7} \end{align*} \]
相对误差限推有效数字
这个公式是给出一个相对误差限，判断有效数字位数
注意，一般都是用有效数字推相对误差限，用上面公式更多\(\varepsilon^*_r\le\dfrac{1}{2\times a_1}\times10^{1-n}\)
注意对比：
有效数字推相对误差限
相对误差限推有效数字
有效数字推绝对误差限
绝对误差限推有效数字（给定一个误差限，我们也得不到这个数字，只能得到有效数字位数）
误差估计
简单算术运算
两个数的加减法的绝对误差限，是这两个数的绝对误差限相加
两个数的乘法的绝对误差限，跟乘法求导公式很像，只不过求导换成了求绝对误差限，并且原数要加绝对值
两个数的除法的绝对误差限，和除法求导公式不完全一致，分子是加法
例题
先把每个数写成科学计数法，求m和n，再求对应的绝对误差限，最后套公式
着重注意一下\(56.430\)这个数，换成科学计数法是\(5.6430\times10^1\)，n为5，m为1，绝对误差为\(0.5\times10^{1-5+1}=0.5\times10^{-3}\)
最后这个0也需要考虑到有效数字里，不能随意增删
一元可微函数
一元可微函数f(x)的误差估计
所谓一元函数的绝对误差限\(\varepsilon[f(x^*)]\)就是\(f(x^*)-f(x)\)，即估计值代入函数求值，减去精确值代入函数求值
所谓一元函数的相对误差限\(\varepsilon_r[f(x^*)]\)就是\(|\dfrac{f(x^*)-f(x)}{f(x)}|\)
公式整合如下： \[ \begin{align*} 绝对误差限&:\varepsilon[f(x^*)]=f(x^*)-f(x)\approx |f'(x)|\varepsilon(x^*)\\\\ 相对误差限&:\varepsilon_r[f(x^*)]=|\dfrac{f(x^*)-f(x)}{f(x)}|\approx C_p\cdot\varepsilon_r(x^*)=|\frac{xf'(x^*)}{f(x)}|\cdot\varepsilon_r(x^*) \end{align*} \]
公式的解释：
第一个式子给出了一元可微函数绝对误差限与自变量绝对误差限的关系
第一个式子给出了一元可微函数相对误差限与自变量相对误差限的关系
比如作业的第三个题，就是问的自变量相对误差限，就要用\(C_p\)，记法：在第一个式子系数\(|f'(x)|\)的基础上，分子乘x，分母除f(x)
多元可微函数
多元可微函数的绝对误差限与一元可微函数类似，只是把每个x的绝对误差限加起来
多元可微函数的相对误差限与一元可微函数类似，在绝对误差限的基础上除以\(|A^*|\)函数值即可
例题
\[ \begin{align*} S&=L\cdot D，其中L和D都是变量\\\\ \varepsilon(S^*)&\approx|(\frac{\partial S}{\partial L})^*|\cdot\varepsilon(L^*)+|(\frac{\partial S}{\partial D})^*|\cdot\varepsilon(D^*)\\ &=D^*\cdot0.2+L^*\cdot0.1\\ &=80*0.2+110*0.1\\ &=27(m^2)\\ \\ \varepsilon_r(S^*)&\approx\frac{\varepsilon(S^*)}{|S^*|}\\ &=\frac{27}{L^*D^*}\\ &=\frac{27}{110*80}\\ &=0.31\% \end{align*} \]
误差分析
在计算过程中，误差会传播、积累、对消
数值算法的稳定性
病态问题：如果输入数据的微小扰动会引起输出数据(即计算结果) 的很大变化(误差)，则称该数值问题是病态的
一元可微函数的稳定性
条件数\(C_p=|\dfrac{xf'(x^*)}{f(x)}|\)
一般认为，条件数大于10就是病态
误差累积
图一乐，看看就好
数值计算注意事项
避免相近的数相减
可能会把有效数字位数减没了
所以如果碰到相近的数相减，做一步处理：
例题
先按求根公式求，发现有效数字位数不够
因为出现了相近的数相减：28 - 27.982
需要处理：
两个相近数相减，就在分子分母同时乘这两个数相加 \[ \begin{align*} \sqrt{x+\varepsilon}-\sqrt{x}&=\frac{(\sqrt{x+\varepsilon}-\sqrt{x})(\sqrt{x+\varepsilon}+\sqrt{x})}{\sqrt{x+\varepsilon}+\sqrt{x}}\\ &=\frac{\varepsilon}{\sqrt{x+\varepsilon}+\sqrt{x}}\\\\ 28-\sqrt{783}&=\frac{(28-\sqrt{783})(28+\sqrt{783})}{28+\sqrt{783}}\\ &=\frac{1}{28+\sqrt{783}}\\ &\approx0.01786 \end{align*} \]
误差总结
\[ \begin{align*} 精确值:&x，近似值:x^*\\ 绝对误差:&e^*=x^*-x\\ 绝对误差限:&|x^*-x|\le\varepsilon^*\\ 相对误差:&e^*_r=\frac{x^*-x}{x}，实际上用\frac{x^*-x}{x^*}\\ 相对误差限:&\frac{|x^*-x|}{x}\le\varepsilon_r^*\\\\ 已知一个数，求绝对误差限&:\\ |x^*-x|&\le0.5\times10^{m-n+1}，先写成科学计数法，m为10的阶数，n为数字位数\\ 求相对误差限&:\\ \varepsilon_r^*&\le\frac{1}{2\cdot a_1}\times10^{1-n}，先写成科学计数法，a_1为第一个数，n为数字位数\\\\ \varepsilon(x_1^*\pm x_2^*)&\le\varepsilon(x_1^*)+\varepsilon(x_2^*)\\ \varepsilon(x_1^* x_2^*)&\le \varepsilon(x_1^*)|x_2^*| + |x_1^*|\varepsilon(x_2^*)\\ \varepsilon(\frac{x_1^*}{x_2^*})&\le \frac{\varepsilon(x_1^*)|x_2^*| + |x_1^*|\varepsilon(x_2^*)}{|x_2^*|^2}\\\\ 一元可微函数绝对误差限:&\varepsilon[f(x^*)]=f(x^*)-f(x)\approx |f'(x)|\varepsilon(x^*)\\ 一元可微函数相对误差限:&\varepsilon_r[f(x^*)]=|\dfrac{f(x^*)-f(x)}{f(x)}|\approx C_p\cdot\varepsilon_r(x^*)=|\frac{xf'(x^*)}{f(x)}|\cdot\varepsilon_r(x^*)\\\\ 多元可微函数绝对误差限:&\varepsilon(A^*)\approx\sum_{k=1}^{n}|(\frac{\partial A}{\partial x_k})^*|\cdot\varepsilon(x_k^*)\\ 多元可微函数相对误差限:&\varepsilon_r(A^*)=\frac{\varepsilon(A^*)}{|A^*|}\approx\frac{\sum_{k=1}^{n}|(\frac{\partial A}{\partial x_k})^*|\cdot\varepsilon(x_k^*)}{|A^*|}\\\\ 相近的数相减:&\\ \sqrt{x+\varepsilon}-\sqrt{x}&=\frac{\varepsilon}{\sqrt{x+\varepsilon}+\sqrt{x}}\\ \ln{(x+\varepsilon)}-\ln{x}&=\ln{(1+\frac{\varepsilon}{x})} \end{align*} \]
误差作业
\[ \begin{align*} \text{已知:}\\ \varepsilon_r(x)&=\delta\\ \frac{x^*-x}{x}&=\delta\\\\ \text{则：}\\ e^*(\ln{x})&\approx|f'(x)|\cdot\varepsilon(x^*)\\ &=\frac{1}{x}\cdot(x^*-x)\\ &=\frac{x^*-x}{x}\\ &=\delta \end{align*} \] 搞清楚相对误差的公式，和一元可微函数绝对误差限的求法即可
先求每一个数对应的绝对误差限： \[
\begin{align*}
x_1^*&=1.1021\times10^0\\
&m=0,n=5\\
\varepsilon(x_1^*)&=0.5\times10^{m-n+1}\\
&=0.5\times10^{-4}\\\\
x_2^*&=3.1\times10^{-2}\\
&m=-2,n=2\\
\varepsilon(x_2^*)&=0.5\times10^{m-n+1}\\
&=0.5\times10^{-3}\\\\
x_3^*&=3.856\times10^2\\
&m=2,n=4\\
\varepsilon(x_3^*)&=0.5\times10^{m-n+1}\\
&=0.5\times10^{-1}\\\\
x_4^*&=5.6430\times10^1\\
&m=1,n=5\\
\varepsilon(x_4^*)&=0.5\times10^{m-n+1}\\
&=0.5\times10^{-3}\\\\
\end{align*}
\] 再开始根据公式求解答案： \[
\begin{align*}
(1):\qquad\qquad\qquad\qquad&\\
\varepsilon(x_1^*+x_2^*+x_4^*)&\le0.5\times10^{-4}+0.5\times10^{-3}+0.5\times10^{-3}\\
&=1.05\times10^{-3}\\\\
(2):\qquad\qquad\qquad\qquad&\\
\varepsilon(x_1^*x_2^*)&\le|x_1^*|\varepsilon(x_2^*)+|x_2^*|\varepsilon(x_1^*)\\
&=5.526\times10^{-4}\\
x_1^*\cdot x_2^*&=3.41651\times10^{-2}\\
\varepsilon(x_1^*x_2^*x_3^*)&\le|x_1^*x_2^*|\varepsilon(x_3^*)+|x_3^*|\varepsilon(x_1^*x_2^*)\\
&=0.214791\\\\
(3):\qquad\qquad\qquad\qquad&\\
\varepsilon(\frac{x_2^*}{x_4^*})&\le\frac{|x_2^*|\varepsilon(x_4^*)+|x_4^*|\varepsilon(x_2^*)}{|x_4^*|^2}\\
&=8.8654\times10^{-6}
\end{align*}
\]
注意题目的要求：
一元函数，给的是相对误差限，求的也是相对误差限，就要用到\(C_p\) \[
\begin{align*}
f(R)&=\frac{4}{3}\pi R^3\\
f'(R)&=4\pi R^2\\\\
C_P&=|\frac{R\cdot f'(R^*)}{f(R)}|\\
&=3
\end{align*}
\] 则： \[
\begin{align*}
\begin{cases}
\varepsilon_r[f(R^*)]&\approx C_P\cdot
\varepsilon_r(R^*)\\\\
\varepsilon_r[f(R^*)]&\le 1\\
\end{cases}
\end{align*}
\] 即： \[
\begin{align*}
3*\varepsilon_r(R^*)&\le1\\
\varepsilon_r(R^*)&\le\frac{1}{3}
\end{align*}
\]
多元函数，两个误差限都要求 \[ \begin{align*} \text{先得到两个变量的误差限：}\\ \varepsilon(a^*)&=0.05\\ \varepsilon(b^*)&=0.15\\ \\ \text{再求面积的绝对误差限：}\\ \varepsilon(\pi ab)&=(\frac{\partial S}{\partial a})^*\cdot\varepsilon(a)+(\frac{\partial S}{\partial b})^*\cdot\varepsilon(b)\\ &=\frac{25}{2}\pi\\\\ \text{最后求面积的相对误差限：}\\ \varepsilon_r(S)&=\frac{\varepsilon(S)}{S}\\ &=0.25\% \end{align*} \]
一看就是会出现两个近似数相减的问题
用求根公式求解：\(x=\dfrac{-b\pm\sqrt{b^2-4ac}}{2a}\) \[ \begin{align*} x&=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\\ &=\frac{16\pm\sqrt{252}}{2}\\\\ x_1&=8+\sqrt{63}\\ &=15.94\\ &=15.9\\\\ x_2&=8-\sqrt{63}\\ &=0.06 \qquad\text{不满足3位有效数字}\\\\ 8-\sqrt{63}&=\frac{8+\sqrt{63}\cdot8-\sqrt{63}}{8+\sqrt{63}}\\ &=\frac{1}{8+\sqrt{63}}\\ x_2&=6.27\times10^{-2} \end{align*} \]
拉格朗日与牛顿插值
多项式插值
插值的基本概念
多项式插值的定义
用\([a,b]\)上\(n+1\)个点插n次多项式
多项式插值唯一性
这个定理还是很重要的，说明了后面遇到的拉格朗日，牛顿前插后插，最后插值的结果是相同的
拉格朗日插值
基函数插值法
基函数的定义
插值基函数，就是插值中用到的函数集合
拉格朗日插值基函数
\[ \begin{align*} l_k(x)&=\frac{(x-x_0)(x-x_1)...(x-x_{k-1})(x-x_{k+1})...(x-x_{n})}{(x_k-x_0)(x_k-x_1)...(x_k-x_{k-1})(x_k-x_{k+1})...(x_k-x_{n})}\\ &=\prod_{i=0,i\ne k}^n\frac{x-x_i}{x_k-x_i} \end{align*} \]
这个还是比较好记的，分子分母形式一致，因为分母不能为0，所以连乘中少一项\(x-x_k\)，然后从0到n，少一项，共n项
拉格朗日基函数与插值节点x有关，与f(x)无关
有了拉格朗日基函数，就能用这个基函数求插值多项式\(P(x)\) \[ P(x)=y_0l_0(x)+y_1l_1(x)+...+y_nl_n(x)=L_n(x) \]
可以看到，插值多项式里，项的个数比n多1，即下标从0到n
每一项中，\(x\)都是\(n\)次方
例题
很基础的计算，我宣布卡西欧计算器嘎嘎乱杀
拉格朗日插值余项
余项的\(\xi\)无法确定，一般算的都是\(f^{(n+1)}(\xi)\)的上界\(M_{n+1}\)，可以根据导数的单调性确定最大值
拉格朗日插值余项 \[ R_n(x)\le\frac{M_{n+1}}{(n+1)!}\omega_{n+1}(x)=\frac{M_{n+1}}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)，M_{n+1}是f^{(n+1)}(\xi)的上界 \] 这个余项的计算公式也很好记，相关项全部跟\(n+1\)有关：
分子\(M_{n+1}\)是是\(f^{(n+1)}(\xi)\)的上界，求的时候要加绝对值
分母是\((n+1)!\)
最右边乘一个连乘，从\((x-x_0)\)到\((x-x_n)\)，共\(n+1\)项
例题
可见，高次插值通常优于低次
但绝对不是次数越高就越好
拉格朗日基函数性质
两条性质
性质1：
注意：\(f(x)\)要是多项式
性质2：同样是因为\(x^k\)求导多次会导致余项为0
\(f(x)\)要是\(x^k\)这种形式
\(k=0\)时，即\(\sum\limits_{j=0}^nl_j(x)=1\)，即拉格朗日插值基函数求和为1
性质1：\(f(x)\)为多项式且次数\(\le n\)
如果次数\(\le n\)，则对应的高阶导数\(f^{(n+1)}(x)=0\)，对应拉格朗日插值的余项\(R_n(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x)\)，分子就是0，所以余项就是0，无误差
性质2：\(f(x)=x^k\)且次数\(\le n\)
同样是因为对应的高阶导数\(f^{(n+1)}(x)=0\)，余项为0，没有误差
特别注意当\(k=0\)时，\(x^k=1\)，所以插值函数\(L_n(x)\)最后等于1
例题
这道题利用了性质
注意：累加的性质一定是用在跟\(i\)有关的项上
牛顿均差插值多项式
拉格朗日插值法，加一个节点很麻烦：全部拉格朗日基函数重新计算
均差
均差又叫“差商”
均差定义
k阶均差： \[ f[x_0,x_1,...,x_k]=\frac{f[x_0,...,x_{k-2},x_k]-f[x_0,...,x_{k-1}]}{x_k-x_{k-1}} \] 注意分子第一项是\(x_{k-2}\)直接跳到了\(x_k\)
分子第一项，方括号里面是\(k\)项
分子第二项，方括号里面也是\(k\)项
均差性质
一般列均差表都是用红框方法算
\(f(x)\in C^k[a,b]\)的意思是：在\([a,b]\)上\(n\)阶可导
均差表
例题
注意均差表的计算：最上面的是我们后面要用的
一阶均差：\(\dfrac{3-5}{-1+2}=-2\)，\(\dfrac{17-3}{1+1}=7\)，\(\dfrac{21-17}{2-1}=4\)
二阶均差：\(\dfrac{7+2}{1+2}=3\)（这个的分母减的是\(x_0\)，即\(x_2-x_0=1-(-2)\)，后面的分母都是隔了一个\(x\)，比如\(x_3-x_1\)，\(x_4-x_2\)）
\(\dfrac{4-7}{2+1}=-1\)
三阶均差：\(\dfrac{-1-3}{2+2}=-1\)（这个的分母减的是\(x_0\)，即\(x_3-x_0=2-(-2)\)
牛顿后插公式
可见，我们需要的均差就是均差表最上面的一系列
牛顿后插公式： \[ \begin{align*} N_n(x)=&f(x_0)+ &\hspace{1cm} 第0项，x次数为0\\ &f[x_0,x_1](x-x_0)+&\hspace{1cm} 第1项，x次数为1\\ &f[x_0,x_1,x_2](x-x_0)(x-x_1)+&\hspace{1cm}第2项，x次数为2\\ &...+\\ &f[x_0,x_1,...x_n](x-x_0)(x-x_1)...(x-x_{n-1})&\hspace{1cm}第n项，x次数为n \end{align*} \]
公式也挺好记，总共\(n+1\)个项，每一项\(x\)的阶数从\(0\)到\(n\)
余项
注意：并不是最后一项多乘一个\((x-x_{n})\)，因为均差的系数不一样，前面是\(f[x,x_0,x_1,...x_n]\)
余项：\(f[x,x_0,x_1,...x_n](x-x_0)(x-x_1)...(x-x_{n-1})(x-x_{n})\)
例题
牛顿后插公式与顺序无关，所以均差表要看情况列
比如这个求的0.54，靠近0.5和0.6，那么线性插值就只用这两个
抛物线插值时，用0.4,0.5,0.6三个点，在后面直接添加0.4这个点就行
差分与牛顿前插公式
向前差分
差分的定义
可见差分的计算非常简单，只用求个差就行
n阶差分表达式
推导一眼麻，图一乐就好
差分与均差与导数
差分表
用两个低阶差分算出高阶差分
后面用到的差分就是第一行计算的结果
牛顿前插公式
牛顿前插公式: \[ N_n(x)=f_0+t\Delta f_0+\frac{t(t-1)}{2!}\Delta^2 f_0+...+\frac{t(t-1)...(t-n+1)}{n!}\Delta^n f_0 \] 误差限： \[ R_n(x)=\frac{t(t-1)...(t-n)}{(n+1)!}h^{n+1}f^{(n+1)}(\xi) \]
\(h\)为间隔
\(t\)为间隔的个数
总共\(n+1\)项，每项\(t\)的阶数从\(0\)到\(n\)
例题
4次，即5个点就够
牛顿前插与前两种的不同在于：必须是等距节点，而且节点排列要有顺序
用\(x_0\)算出偏移\(t\)： \[ \begin{align*} 0+0.1t&=0.048\\ t&=0.48 \end{align*} \] 然后套公式： \[ \begin{align*} N_4(x)&=f_0+t\Delta f_0+\frac{t(t-1)}{2!}\Delta^2 f_0+\frac{t(t-1)(t-2)}{3!}\Delta^3 f_0+\frac{t(t-1)(t-2)(t-3)}{4!}\Delta^4f_0\\ &=0.99884 \end{align*} \]
算误差，这三个插值方法算的误差限必相同
所以让你算误差，你就拿拉格朗日插值的误差算，这个最好算
拉格朗日牛顿插值总结
\[ \begin{align*} 拉格朗日插值基函数：\\ l_k(x)&=\frac{(x-x_0)(x-x_1)...(x-x_{k-1})(x-x_{k+1})...(x-x_{n})}{(x_k-x_0)(x_k-x_1)...(x_k-x_{k-1})(x_k-x_{k+1})...(x_k-x_{n})}\\ &=\prod_{i=0,i\ne k}^n\frac{x-x_i}{x_k-x_i}\\\\ 拉格朗日插值法：\\ L_n(x)&=y_0l_0(x)+y_1l_1(x)+...+y_nl_n(x)\\ 拉格朗日插值法余项：\\ R_n(x)&\le\frac{M_{n+1}}{(n+1)!}\omega_{n+1}(x)\\ &=\frac{M_{n+1}}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)，M_{n+1}是f^{(n+1)}(\xi)的上界\\\\ 牛顿后插公式：\\ N_n(x)=&f(x_0)+ &\hspace{1cm} 第0项，x次数为0\\ &f[x_0,x_1](x-x_0)+&\hspace{1cm} 第1项，x次数为1\\ &f[x_0,x_1,x_2](x-x_0)(x-x_1)+&\hspace{1cm}第2项，x次数为2\\ &...+\\ &f[x_0,x_1,...x_n](x-x_0)(x-x_1)...(x-x_{n-1})&\hspace{1cm}第n项，x次数为n\\ 牛顿后插余项：\\ &f[x,x_0,x_1,...x_n](x-x_0)(x-x_1)...(x-x_{n-1})(x-x_{n})\\\\ 牛顿前插公式：\\ N_n(x)&=f_0+t\Delta f_0+\frac{t(t-1)}{2!}\Delta^2 f_0+...+\frac{t(t-1)...(t-n+1)}{n!}\Delta^n f_0\\ &t为间隔的个数\\ 牛顿前插余项：\\ R_n(x)&=\frac{t(t-1)...(t-n)}{(n+1)!}h^{n+1}f^{(n+1)}(\xi)，可以用M_{n+1}计算f^{(n+1)}(\xi)的上界\\ &h为间隔 \end{align*} \]
拉格朗日牛顿插值作业
\[ \begin{align*} &\text{设三个点为: }(x_0,y_0),(x_1,y_1),(x_2,y_2)\\ &\text{设: } \begin{cases} l_0=a_0x^2+b_0x+c_0\\ l_1=a_1x^2+b_1x+c_1\\ l_2=a_2x^2+b_2x+c_2\\ \end{cases}\\\\ &\text{则: }P(x)=y_0l_0(x)+y_1l_1(x)+y_2l_2(x)\\ &\text{使得: } \begin{pmatrix} l_0(x_0)=1 & l_1(x_0)=0 & l_2(x_0)=0 \\ l_0(x_1)=0 & l_1(x_1)=1 & l_2(x_1)=0 \\ l_0(x_2)=0 & l_1(x_2)=0 & l_2(x_2)=1 \\ \end{pmatrix}\\\\\\ &\text{则}l_0\text{过}(x_0,1),(x_1,0),(x_2,0)\text{三点}\\ &\text{根据: }\begin{cases} 1=a_0x_0^2+b_0x_0+c_0\\ 0=a_0x_1^2+b_0x_1+c_0\\ 0=a_0x_2^2+b_0x_2+c_0\\ \end{cases}\\ &解得\begin{cases} a_0=\frac{1}{(x_0-x_1)\cdot(x_0-x_2)}\\ b_0=-\frac{x_1+x_2}{(x_0-x_1)\cdot(x_0-x_2)}\\ c_0=\frac{x_1\cdot x_2}{(x_0-x_1)\cdot(x_0-x_2)} \end{cases}\\ &\text{故：}&\\ l_0&=\frac{x^2-(x_1+x_2)x+x_1x_2}{(x_0-x_1)\cdot(x_0-x_2)}\\ \text{同理：}&\\ l_1&=\frac{x^2-(x_0+x_2)x+x_0x_2}{(x_1-x_0)\cdot(x_1-x_2)}\\ l_2&=\frac{x^2-(x_0+x_1)x+x_0x_1}{(x_2-x_0)\cdot(x_2-x_1)}\\ \end{align*} \]
\[
\begin{align*}
\text{设:}&f(x)=x^k\qquad k<n\\
\text{构建}L_n(x)&=y_0l_0(x)+y_1l_1(x)+\cdots+y_nl_n(x)\\
&=x_0^kl_0(x)+\cdots+x_n^kl_n(x)\\\\
\text{误差}R_n(x)&=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x)\\
\text{根据}k<n\text{得:}\qquad R_n(x)&=0\\
\text{即}f(x)&=L_n(x)\\
x^k&=\sum_{j=0}^{n}x_j^kl_j(x)\\
\text{得证}
\end{align*}
\]
注意：误差估计时都要加绝对值
拉格朗日插值和牛顿插值的误差估计必须是一样的，因为多项式插值唯一性
埃尔米特插值和分段插值
埃尔米特插值
重节点均差
泰勒插值多项式
三点三次埃尔米特插值
埃尔米特插值，是我们缺点才用的插值
我们可以把牛顿后插公式先写出来：
我们少一个点，就算不了最后一个均差，就设为A
因为插值条件是\(P(x_i)=f(x_i), P'(x_1)=f'(x_1)\)
利用中间这个点导数和插值多项式导数相等，来解出A：
三点三次埃尔米特插值： \[ \begin{align*} P(x)&=f(x_0)+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+A(x-x_0)(x-x_1)(x-x_2)\\\\ A&=\frac{f'(x_1)-f[x_0,x_1]-(x_1-x_0)f[x_0,x_1,x_2]}{(x_1-x_0)(x_1-x_2)}\\\\ 余项：\\ R(x)&=\frac{1}{4!}f^{(4)}(\xi)(x-x_0)(x-x_1)^2(x-x_2) \end{align*} \] 注意余项里面有个平方
例题
可惜卡西欧计算器并不是万能的，多项式化简这一步就不行
顺序化简容易化错，我建议按照项化简
你一个多项式说到底就是\(ax^3+bx^2+cx+d\)，我们直接算出这些系数就行了，不需要一步一步化简，又慢又容易错
卡西欧框框按，算的飞快
考试要是代值那将绝杀
两点三次埃尔米特插值
你现在只有两个点，让你插值一个三次多项式
公式，背！
\[ \begin{align*} 两点三次埃尔米特插值：\\ H_3(x)&=y_0\alpha_0(x)+y_1\alpha_1(x)+m_0\beta_0(x)+m_1\beta_1(x)\\\\ \alpha_0(x)&=(1+2\frac{x-x_0}{x_1-x_0})(\frac{x-x_1}{x_0-x_1})^2\\ \alpha_1(x)&=(1+2\frac{x-x_1}{x_0-x_1})(\frac{x-x_0}{x_1-x_0})^2\\\\ \beta_0(x)&=(x-x_0)(\frac{x-x_1}{x_0-x_1})^2\\ \beta_1(x)&=(x-x_1)(\frac{x-x_0}{x_1-x_0})^2\\\\ 余项：\\ R_3(x)&=\frac{1}{4!}f^{(4)}(\xi)(x-x_0)^2(x-x_1)^2 \end{align*} \]
分段低次插值
分段线性插值
分段两点三次埃尔米特插值
\[ \begin{align*} 分段两点三次埃尔米特插值：\\ 对每个小区间x_k,x_{k+1}有：\\ I_h(x)&=y_k\alpha_k(x)+y_{k+1}\alpha_{k+1}(x)+m_k\beta_k(x)+m_{k+1}\beta_{k+1}(x)\\\\ \alpha_k(x)&=(1+2\frac{x-x_k}{x_{k+1}-x_k})(\frac{x-x_{k+1}}{x_{k}-x_{k+1}})^2\\ \alpha_{k+1}(x)&=(1+2\frac{x-x_{k+1}}{x_{k}-x_{k+1}})(\frac{x-x_{k}}{x_{k+1}-x_{k}})^2\\ \beta_k(x)&=(x-x_k)(\frac{x-x_{k+1}}{x_k-x_{k+1}})^2\\ \beta_{k+1}(x)&=(x-x_{k+1})(\frac{x-x_k}{x_{k+1}-x_k})^2\\\\ 余项：\\ |R(x)|&\le\frac{M_4}{384}h^4\\ M_4&=\max_{a\le x\le b}|f^{(4)}(\xi)|\\ h&=\max_{0\le k\le n-1}(x_{k+1}-x_k) \end{align*} \]
三次样条插值
知道边界条件就好
埃尔米特插值分段插值总结
\[ \begin{align*} 三点三次埃尔米特插值：\\ P(x)&=f(x_0)+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+A(x-x_0)(x-x_1)(x-x_2)\\\\ A&=\frac{f'(x_1)-f[x_0,x_1]-(x_1-x_0)f[x_0,x_1,x_2]}{(x_1-x_0)(x_1-x_2)}\\\\ 余项：\\ R(x)&=\frac{1}{4!}f^{(4)}(\xi)(x-x_0)(x-x_1)^2(x-x_2)\\\\ 两点三次埃尔米特插值：\\ H_3(x)&=y_0\alpha_0(x)+y_1\alpha_1(x)+m_0\beta_0(x)+m_1\beta_1(x)\\\\ \alpha_0(x)&=(1+2\frac{x-x_0}{x_1-x_0})(\frac{x-x_1}{x_0-x_1})^2\\ \alpha_1(x)&=(1+2\frac{x-x_1}{x_0-x_1})(\frac{x-x_0}{x_1-x_0})^2\\\\ \beta_0(x)&=(x-x_0)(\frac{x-x_1}{x_0-x_1})^2\\ \beta_1(x)&=(x-x_1)(\frac{x-x_0}{x_1-x_0})^2\\\\ 余项：\\ R_3(x)&=\frac{1}{4!}f^{(4)}(\xi)(x-x_0)^2(x-x_1)^2\\\\ 分段两点三次埃尔米特插值：\\ 对每个小区间x_k,x_{k+1}有：\\ I_h(x)&=y_k\alpha_k(x)+y_{k+1}\alpha_{k+1}(x)+m_k\beta_k(x)+m_{k+1}\beta_{k+1}(x)\\\\ \alpha_k(x)&=(1+2\frac{x-x_k}{x_{k+1}-x_k})(\frac{x-x_{k+1}}{x_{k}-x_{k+1}})^2\\ \alpha_{k+1}(x)&=(1+2\frac{x-x_{k+1}}{x_{k}-x_{k+1}})(\frac{x-x_{k}}{x_{k+1}-x_{k}})^2\\ \beta_k(x)&=(x-x_k)(\frac{x-x_{k+1}}{x_k-x_{k+1}})^2\\ \beta_{k+1}(x)&=(x-x_{k+1})(\frac{x-x_k}{x_{k+1}-x_k})^2\\\\ 余项：\\ |R(x)|&\le\frac{M_4}{384}h^4\\ M_4&=\max_{a\le x\le b}|f^{(4)}(\xi)|\\ h&=\max_{0\le k\le n-1}(x_{k+1}-x_k)\\\\\\ &注意样条插值边界条件 \end{align*} \]
逼近概念与正交多项式
插值：穿过所有给定点
逼近：不需要穿过所有点
逼近基本概念
范数
范数3个性质：正定性，齐次性，三角不等式
解释：
\(R^n\)为\(n\)阶实数，对向量说的
\(C[a,b]\)为在\([a,b]\)上连续，对函数说的 \[ \begin{align*} 向量的范数：\\ 1-范数:||x||_1&=\sum_{i=1}^n|x_i|=|x_1|+|x_2|+...+|x_n|\\ 2-范数:||x||_2&=(\sum_{i=1}^nx_i^2)^{\frac{1}{2}}=\sqrt{x_1^2+x_2^2+...+x_n^2}\\ p-范数:||x||_p&=(\sum_{i=1}^nx_i^p)^{\frac{1}{p}}\\ \infty-范数:||x||_\infty&=\max_{1\le i\le n}{|x_i|}\\\\ 函数的范数：\\ 1-范数:||f||_1&=\int_a^b|f(x)|dx\\ 2-范数:||f||_2&=(\int_a^b|f(x)|^2dx)^{\frac{1}{2}}\\ p-范数:||f||_p&=(\int_a^b|f(x)|^pdx)^{\frac{1}{p}}\\ \infty-范数:||f||_\infty&=\max_{a\le x\le b}{|f(x)|}\\\\ \end{align*} \]
内积
注意写法：\((x,y)\)表示内积
内积为0，则正交
内积导出范数：\(||u||_2=\sqrt{(u,u)}\)
权函数
权函数一定大于0
记住： \[ \begin{align*} \rho(x)&=1&(-1\le x\le1)\\ \rho(x)&=\frac{1}{\sqrt{1-x^2}}&(-1\le x\le1) \end{align*} \] 这两个权函数
带权内积
\[ \begin{align*} \rho(x)为权函数，带权内积：\\ (f(x),g(x))_\rho&=\int_a^b\rho(x)f(x)g(x)dx\\ 导出范数：\\ ||f(x)||_2&=\sqrt{\int_a^b\rho(x)f^2(x)dx} \end{align*} \]
最佳逼近多项式
就是用一个多项式\(P^*(x)\)逼近一个多项式\(f(x)\)，要让他们差函数的范数最小
正交多项式
带权正交： \[ (f(x),g(x))_\rho=\int_a^b\rho(x)f(x)g(x)dx=0\\ \]
即，仅自己和自己带权内积不为0，在这个函数族内任意两个带权内积都为0
正交多项式定义
正交多项式性质
勒让德多项式
勒让德多项式定义
只用记住勒让德多项式的权函数是\(\rho(x)=1\)，区间是\([-1,1]\)
勒让德多项式性质
注意：勒让德多项式是在\([-1,1]\)上，后面用勒让德多项式求逼近，如果自变量范围不在\([-1,1]\)则需要变换
用勒让德多项式求最佳平方逼近
注：\(H_n\)为\(n\)阶多项式，\(C[-1,1]\)是在\([-1,1]\)连续
n会当做条件给你
规定了\(\rho(x)=1\) \[ \begin{align*} f(x)\in C[-1,1]在H_n中的最佳平方逼近多项式为：\\ P^*(x)&=\sum_{j=0}^na_jP_j(x)\\\\ 其中：\\ a_j&=\frac{2j+1}{2}\int_{-1}^1f(x)P_j(x)dx \end{align*} \]
例题
注意：x的范围并不在[-1,1]，所以要先换元，使定义域在[-1,1]
\(P_i(x)\)考试会给
切比雪夫多项式
切比雪夫多项式定义
切比雪夫多项式性质
用\(n-1\)次多项式最优一致逼近\(n\)次多项式
就是给定一个\(n\)次多项式\(f(x)\)，让你求一个\(n-1\)次多项式\(P_{n-1}(x)\)，逼近\(f(x)\) \[ \begin{align*} f(x)\in H_n且首项系数a_n\ne0\\ 则f(x)在[-1,1]上的n-1次最优一致逼近为：\\ P_{n-1}(x)&=f(x)-a_n\tilde{T}_n(x)\\\\ 其中：\\ \tilde{T}_n(x)&=\frac{T_n(x)}{2^{n-1}}，即首项系数为1(简称首1)，\tilde{H}_n为\le n次的首1多项式集 \end{align*} \]
为什么是\(2^{n-1}\)：
比如\(n=2\)时，\(T_2(x)=2x^2-1\)，\(\tilde{T}_2(x)=\dfrac{T_2(x)}{2^{2-1}}=x^2-\dfrac{1}{2}\)，首项系数就是1了
这样能够保证减法过程中\(f(x)-a_n\tilde{T}_n(x)\)能把\(f(x)\)的最高次减掉，就会从\(n\)次多项式变成\(n-1\)次多项式
例题
考试出题的时候可能会给你多个\(T_n(x)\)，我们的目的是把最高次项减掉，所以只用最高次项对应的\(T_n(x)\)即可
切比雪夫零点插值
这个还是很重要的
切比雪夫多项式零点插值：就是把这些零点当做插值节点进行插值，这肯定不是等距节点，所以不能用牛顿前插公式
注意区分\(n\)的含义：切比雪夫零点公式里的\(n\)是点的个数，比如我现在要求拉格朗日插值\(L_4(x)\)，4阶的拉格朗日插值需要5个点，所以就应该在公式\(x_k=\cos{(\dfrac{2k-1}{2n}\pi)}\qquad k=1,2,...n\)带入\(n=5\)，而不是4
除了用这些零点当插值节点，更重要的是：误差限的算法变了，唯一的变化在于\(\omega_{n+1}(x)\)的求法，最大值就是\(\dfrac{1}{2^n}\) \[ \begin{align*} T_n(x)在(-1,1)上有n个切比雪夫零点：\\ x_k&=\cos{(\frac{2k-1}{2n}\pi)}\qquad k=1,2,...n\\\\ 切比雪夫多项式零点插值对应的误差限：\\ \max{|R_n(x)|}&\le\frac{M_{n+1}}{(n+1)!}\max{|\omega_{n+1}(x)|}\\\\ M_{n+1}&=||f^{(n+1)(x)}||_\infty\\ \max{|\omega_{n+1}(x)|}&=\max{|\tilde{T}_{n+1}|}=\frac{1}{2^n}\\\\ 所以切比雪夫插值对应的误差限：\\ \max{|R_n(x)|}&\le\frac{M_{n+1}}{(n+1)!}\max{|\omega_{n+1}(x)|}\\ &=\frac{||f^{(n+1)}(x)||_\infty}{2^n(n+1)!} \end{align*} \]
变量替换的情况：
误差限会多乘一个\(\dfrac{(b-a)^{n+1}}{2^{n+1}}\)
例题
考试不可能出这么离谱的，这真不可能算出来
只需要知道如果切比雪夫零点插值，则误差限的分析就要重新计算
如果在此基础上又他妈换一个元，把变量换到\([-1,1]\)，误差限分析的时候又要多乘一个\(\dfrac{(b-a)^{n+1}}{2^{n+1}}\)
逼近总结
\[ \begin{align*} 5种线性空间：\\ R^n&:n阶实数\\ C^n&:n阶复数\\ H_n&:n阶多项式\\ C[a,b]&:在[a,b]上连续\\ C^n[a,b]&:在[a,b]上n阶可导\\\\ 范数三个性质：\\ &正定性，齐次性，三角不等式\\\\ 向量的范数：\\ 1-范数:||x||_1&=\sum_{i=1}^n|x_i|=|x_1|+|x_2|+...+|x_n|\\ 2-范数:||x||_2&=(\sum_{i=1}^nx_i^2)^{\frac{1}{2}}=\sqrt{x_1^2+x_2^2+...+x_n^2}\\ p-范数:||x||_p&=(\sum_{i=1}^nx_i^p)^{\frac{1}{p}}\\ \infty-范数:||x||_\infty&=\max_{1\le i\le n}{|x_i|}\\\\ 函数的范数：\\ 1-范数:||f||_1&=\int_a^b|f(x)|dx\\ 2-范数:||f||_2&=(\int_a^b|f(x)|^2dx)^{\frac{1}{2}}\\ p-范数:||f||_p&=(\int_a^b|f(x)|^pdx)^{\frac{1}{p}}\\ \infty-范数:||f||_\infty&=\max_{a\le x\le b}{|f(x)|}\\\\ x=(x_1,x_2,...,x_n)^T\\y=(y_1,y_2,...,y_n)^T\\ 内积：\\ (x,y)&=x_1y_1+x_2y_2+...+x_ny_n\\ 内积导出范数：\\ ||u||_2&=\sqrt{(u,u)}\\\\ 两个要记的权函数：\\ \rho(x)&=1&(-1\le x\le1)\\ \rho(x)&=\frac{1}{\sqrt{1-x^2}}&(-1\le x\le1)\\\\ \rho(x)为权函数，带权内积：\\ (f(x),g(x))_\rho&=\int_a^b\rho(x)f(x)g(x)dx\\ 导出范数：\\ ||f(x)||_2&=\sqrt{\int_a^b\rho(x)f^2(x)dx}\\\\ 带权正交：\\ (f(x),g(x))_\rho&=\int_a^b\rho(x)f(x)g(x)dx=0\\\\ \end{align*} \]
太长了，换一个公式块 \[ \begin{align*} 用勒让德多项式求最佳平方逼近：\\ f(x)\in C[-1,1]在H_n中的最佳平方逼近多项式为：\\ P^*(x)&=\sum_{j=0}^na_jP_j(x)\\\\ 其中：\\ a_j&=\frac{2j+1}{2}\int_{-1}^1f(x)P_j(x)dx\\\\ 用n-1次多项式最优一致逼近n次多项式：\\ f(x)\in H_n且首项系数a_n\ne0\\ 则f(x)在[-1,1]上的n-1次最优一致逼近为：\\ P_{n-1}(x)&=f(x)-a_n\tilde{T}_n(x)\\\\ 其中：\\ \tilde{T}_n(x)&=\frac{T_n(x)}{2^{n-1}}，即首项系数为1(简称首1)，\tilde{H}_n为\le n次的首1多项式集\\\\ T_n(x)在(-1,1)上有n个切比雪夫零点：\\ x_k&=\cos{(\frac{2k-1}{2n}\pi)}\qquad k=1,2,...n\\\\ 切比雪夫多项式零点插值对应的误差限：\\ \max{|R_n(x)|}&\le\frac{M_{n+1}}{(n+1)!}\max{|\omega_{n+1}(x)|}\\ &=\frac{||f^{(n+1)(x)}||_\infty}{2^n(n+1)!}\\ 如果出现变量代换的情况\\ （即从[a,b]变换到[-1,1]）\\ \max{|R_n(x)|}&\le\frac{||f^{(n+1)}(x)||_\infty}{2^n(n+1)!}\cdot\frac{(b-a)^{n+1}}{2^{n+1}}\\ \end{align*} \]
逼近作业
比较基础，卡西欧积分嘎嘎杀
变量不在[-1,1]，先换元，最后再换回来
容易算错，用我之前说到的方法：一个多项式说到底就是\(ax^3+bx^2+cx+d\)，我们直接算出这些系数就行了，不需要一步一步化简，又慢又容易错
刚好计算器支持分数运算，简直嘎嘎乱杀，注意别按错就行
这种题最好一遍算对，毕竟这课考试时间太紧了，可能都写不完
我估计草稿纸都得用2张以上
最小二乘法
曲线拟合方法
残差就是误差
矛盾方程组，就是求残差，然后列到一起
最小二乘法
让所有残差的平方和加和起来最小，就是最小二乘法
直线拟合
正规方程组，是对残差平方和求偏导得来的，两个变量就是两个方程，多个变量就是多个方程
\(m\)为数据点的个数 \[ \begin{align*} 设\phi(x)&=a_0+a_1x\\\\ 则正规方程组为：& \begin{cases} a_0m+a_1\sum\limits_{i=1}^mx_i=\sum\limits_{i=1}^my_i\\ a_0\sum\limits_{i=1}^mx_i+a_1\sum\limits_{i=1}^mx_i^2=\sum\limits_{i=1}^mx_iy_i \end{cases}\\\\ 需要计算的值有：&\begin{cases} \sum\limits_{i=1}^mx_i\\ \sum\limits_{i=1}^my_i\\ \sum\limits_{i=1}^mx_i^2\\ \sum\limits_{i=1}^mx_iy_i \end{cases} \end{align*} \] 可以这样记：第二个式子是在第一个式子的基础上多乘了一个\(\sum\limits_{i=1}^mx_i\)，只是第一项少了一个\(m\)
例题
这个不可能手算，看看就行
手算的例题
最小二乘拟合的时候，先把数据点描在图上，来确定用什么函数拟合
这个就可以用直线拟合
我很倾向于用解方程的方法求解，只是可能会算错，注意计算器别按错就好了
如果你是个蓝狗，也可以试试用矛盾方程组系数矩阵求解的方式：
你要做的工作仅仅只有把系数矩阵A和向量b输入计算器
然后用转置矩阵、求逆这样的方法求解
这种方法仅适用于4个数据点，因为卡西欧计算器最高只支持到4x4的矩阵运算，很可惜
不过一开始的解方程法就不用担心数据点过多，问题不大
多项式拟合
给定\(m\)个数据点，设多项式最高次为\(n\)次，\(n<<m\) \[ \begin{align*} 多项式拟合，设y&=a_0+a_1x+a_2x^2+...+a_nx^n\\\\ 法方程组&\begin{cases} a_0m+a_1\sum\limits_{i=1}^mx_i+...+a_n\sum\limits_{i=1}^mx_i^n=\sum\limits_{i=1}^my_i\\ a_0\sum\limits_{i=1}^mx_i+a_1\sum\limits_{i=1}^mx_i^2+...+a_n\sum\limits_{i=1}^mx_i^{n+1}=\sum\limits_{i=1}^mx_iy_i\\ \qquad\qquad\vdots\\ a_0\sum\limits_{i=1}^mx_i^n+a_1\sum\limits_{i=1}^mx_i^{n+1}+...+a_n\sum\limits_{i=1}^mx_i^{2n}=\sum\limits_{i=1}^mx_i^ny_i\\ \end{cases} \end{align*} \] 这个还是比较好记的，总共\(n+1\)个方程，每次在上一个的基础上多乘一个\(\sum\limits_{i=1}^mx_i\)，只是第一个方程的第一项少了一个\(m\)
最高次为\(x^{2n}\)次
例题
这个如果用矩阵写，卡西欧就不能解决了，所以还是按一开始的方法解
如果告诉你其中一个系数为0，那也挺好算的，列方程的时候少列一个项就好
多项式拟合变体
只要能变化到\(\bar{y}=a_0+a_1\bar{x}\)或者\(\bar{y}=a_0+a_1\bar{x}+a_2\bar{x}^2\)即可
例题
PPT给的答案是：
还是有一定误差的
最小二乘法总结
\[ \begin{align*} 线性拟合：\\ 设\phi(x)&=a_0+a_1x\\\\ 正规方程组：& \begin{cases} a_0m+a_1\sum\limits_{i=1}^mx_i=\sum\limits_{i=1}^my_i\\ a_0\sum\limits_{i=1}^mx_i+a_1\sum\limits_{i=1}^mx_i^2=\sum\limits_{i=1}^mx_iy_i \end{cases}\\\\ 需要计算的值有：&\begin{cases} \sum\limits_{i=1}^mx_i\\ \sum\limits_{i=1}^my_i\\ \sum\limits_{i=1}^mx_i^2\\ \sum\limits_{i=1}^mx_iy_i \end{cases}\\\\\\ 多项式拟合：\\ 设y&=a_0+a_1x+a_2x^2+...+a_nx^n\\\\ 法方程组：&\begin{cases} a_0m+a_1\sum\limits_{i=1}^mx_i+...+a_n\sum\limits_{i=1}^mx_i^n=\sum\limits_{i=1}^my_i\\ a_0\sum\limits_{i=1}^mx_i+a_1\sum\limits_{i=1}^mx_i^2+...+a_n\sum\limits_{i=1}^mx_i^{n+1}=\sum\limits_{i=1}^mx_iy_i\\ \qquad\qquad\vdots\\ a_0\sum\limits_{i=1}^mx_i^n+a_1\sum\limits_{i=1}^mx_i^{n+1}+...+a_n\sum\limits_{i=1}^mx_i^{2n}=\sum\limits_{i=1}^mx_i^ny_i\\ \end{cases}\\\\ 多项式拟合还会有变体：\\ 只要能变化到：&\bar{y}=a_0+a_1\bar{x}\quad或者\quad\bar{y}=a_0+a_1\bar{x}+a_2\bar{x}^2 \end{align*} \]
数值积分
机械求积公式
\[ \begin{align*} 机械求积公式：\\ \int_a^bf(x)dx&\approx\sum_{i=0}^nA_if(x_i)\\ \end{align*} \]
代数精度
代数精度定义
验证代数精度的方法
例题
给定一个机械求积公式，求代数精度：
把\(f(x)=1,x,x^2,x^3...\)往里代
如题，要解出3个未知数\(A_0A_1A_2\)，就需要列3个方程
依次将\(f(x)=1,x,x^2\)代入即可得出三个\(A\)
算出来： \[ \int_{-1}^1f(x)dx\approx\frac{f(-1)+4f(0)+f(1)}{3} \] 把\(f(x)=x^3\)代入，\(0=0\)精确成立
把\(f(x)=x^4\)代入，\(\dfrac{2}{5}\ne\dfrac{2}{3}\)，不精确成立
所以有3次代数精度
求积公式系数的性质
插值型求积
定义
已知f(x)，对其进行拉格朗日插值，然后用拉格朗日插值的结果代替f(x)，可以得到机械求积公式
插值求积公式定理
求积公式收敛性
求积公式稳定性
求积公式稳定性定理
牛柯求积公式
\[ \begin{align*} 牛顿柯特斯求积公式：\\ 积分区间：&[a,b]\\ 求积间距：&h=\frac{b-a}{n}\\ 求积节点：&x_i=a+ih\\ \int_a^bf(x)dx&\approx(b-a)\sum_{i=0}^nC_i^{(n)}f(x_i)\\ &C_i^{(n)}为柯特斯系数 \end{align*} \]
要记住的牛顿柯特斯求积公式
\[ \begin{align*} n=1，梯形公式，代数精度1：\\ \int_a^bf(x)dx&\approx\frac{b-a}{2}[f(a)+f(b)]\\\\ n=2，抛物线公式（辛普森公式），代数精度3：\\ \int_a^bf(x)dx&\approx\frac{(b-a)}{6}[f(a)+4f(\frac{a+b}{2})+f(b)]\\ \end{align*} \]
还是很好理解的，拿\(n=2\)为例：
积分区间\([a,b]\)，求积间隔\(h=\dfrac{b-a}{n}=\dfrac{b-a}{2}\)
所以就用这三个点：\(a,\quad a+1\cdot\dfrac{b-a}{2}=\dfrac{a+b}{2},\quad a+2\cdot\dfrac{b-a}{2}=b\)
每一项的函数值再乘以对应的柯特斯系数，加和，最后乘以间距\((b-a)\)就行了
\(n=3\)同理，间隔\(h=\dfrac{b-a}{n}=\dfrac{b-a}{3}\)
就用四个点：\(a,\quad a+1\cdot\dfrac{b-a}{3}=\dfrac{2a+b}{3},\quad a+2\cdot\dfrac{b-a}{3}=\dfrac{2b+a}{3},\quad a+3\cdot\dfrac{b-a}{3}=b\)
柯特斯系数
可见，\(n\ge8\)以后出现了负数，即求积不稳定
牛柯求积公式代数精度定理
例题
复合求积公式
打错了，抛物线这个公式少一个\(f(x_{i+1})\)
其实不用背公式，说到底就是一个分段积分，在每一小段用牛柯求积公式
搞清楚哪些点用于积分就好
我出的例题
比如指定\(f(x)=\ln(x)\)，规定定义域在\([1,5]\)，分4段，用辛普森公式，求分段积分
这个可以用卡西欧的定义函数功能，毕竟每次都一样
注意搞清楚对哪一段求积分
最后加起来就行了
高斯求积公式
打错了，应该是\(f(x)=x^4\)最后代入
数值积分总结
\[ \begin{align*} 机械求积公式：\\ \int_a^bf(x)dx&\approx\sum_{i=0}^nA_if(x_i)\\\\ 机械求积公式性质：\\ \sum_{i=0}^nA_i&=A_0+...+A_n\\ &=b-a\\\\ 牛顿柯特斯求积公式：\\ 积分区间：&[a,b]\\ 求积间距：&h=\frac{b-a}{n}\\ 求积节点：&x_i=a+ih\\ \int_a^bf(x)dx&\approx(b-a)\sum_{i=0}^nC_i^{(n)}f(x_i)\\ &C_i^{(n)}为柯特斯系数\\\\ n=1，梯形公式，代数精度1：\\ \int_a^bf(x)dx&\approx\frac{b-a}{2}[f(a)+f(b)]\\\\ n=2，抛物线公式（辛普森公式），代数精度3：\\ \int_a^bf(x)dx&\approx\frac{(b-a)}{6}[f(a)+4f(\frac{a+b}{2})+f(b)]\\\\\\ 高斯求积公式&在所有机械求积公式中代数精度最高 \end{align*} \]
数值积分作业
柯特斯系数如下：
\[ \begin{align*} \text{n=3时，步长为}&(12-0)\div3=4\\ \int_{0}^{12}\frac{x}{6+5x^2}dx&=12\times(\frac{1}{8}f(0)+\frac{3}{8}f(4)+\frac{3}{8}f(8)+\frac{1}{8}f(12))\\ &=\frac{12}{8}(0+3\times0.046511627+3\times0.024539877+0.016528925)\\ &=0.344525155\\\\ \text{n=4时，步长为}&(12-0)\div4=3\\ \int_{0}^{12}\frac{x}{6+5x^2}dx&=12\times(\frac{7}{90}f(0)+\frac{32}{90}f(3)+\frac{12}{90}f(6)+\frac{32}{90}f(9)+\frac{7}{90}f(12))\\ &=\frac{12}{90}(7\times0+32\times0.058823529+12\times0.032258064+32\times0.02189781+7\times0.016528925)\\ &=0.411450945 \end{align*} \] \(n=4\)时，代数精度为5
高斯消去法
矩阵的谱：矩阵的所有特征值
矩阵的谱半径：\(\rho(A)\)是矩阵特征值绝对值的最大值
高斯消去法
列主元高斯消去法
定义：\(a_{ii}\)为主元
注意区分列主元：当前列到最低列中最大值
矩阵的三角分解
一般线性方程组
矩阵分解手算：待定系数法
LU分解
也叫杜立特尔（Doolittle）分解
先分解，再回代
\[ \begin{align*} Ax&=b\\ LUx&=b\\\\ 令y&=Ux\\ 先解Ly&=b，得到y\\ 再解Ux&=y，求得x \end{align*} \]
来看L和U的特征：
L矩阵对角线上的元素一定为1
U矩阵第一行元素一定是A的第一行元素
例题
L矩阵对角线上的元素一定为1
U矩阵第一行元素一定是A的第一行元素
PLU分解
列主元高斯消去法
对称正定线性方程组
注意：此处出现的所有A都是对称矩阵
楚列斯基分解法（平方根法）
\[ \begin{align*} 把U的主对角线拿出来变成D：U&=DU_0\\ A&=LU\\ &=LDU_0\\\\ 又因为A为对称矩阵，则A&=A^T\\ A&=U_0^T(DL^T)\\\\ LU分解有唯一性，所以U_0^T&=L\\ 即对称矩阵A&=LDL^T \end{align*} \]
楚列斯基分解法，就是在对称矩阵分解的基础上，把中间的\(D\)矩阵变成\(D^{\frac{1}{2}}D^{\frac{1}{2}}\)，分别乘到\(L\)和\(L^T\)中 \[ \begin{align*} 对称矩阵A&=LDL^T\\\\ 如果A是对称正定矩阵：\\ D&=D^{\frac{1}{2}}D^{\frac{1}{2}}\\\\ A&=LD^{\frac{1}{2}}D^{\frac{1}{2}}L^T\\ &=(LD^{\frac{1}{2}})(D^{\frac{1}{2}}L^T)\\ &=(LD^{\frac{1}{2}})(LD^{\frac{1}{2}})^T\\ &=L_1L_1^T \end{align*} \]
例题
楚列斯基分解不是很好算，头大
我的评价是，手算出L以后，卡西欧按
改进的楚列斯基分解法
改进后的楚列斯基分解，其实就是推导过程中出现的\(A=LDL^T\)
因为考试的计算题现在是10分一个，按老师的说法，处理3个矩阵比处理2个矩阵困难，于是出改进楚列斯基分解的可能性挺高的
找个题练手
书上的例题
处理三个矩阵确实复杂一些
回代按卡西欧就行了
对角占优的三对角线性方程组
本质仍然是LU分解
追赶法
还得是待定系数法
例题
先建立对应的L和U
追赶法的L：主对角线下面一列跟原来的完全一样，只有主对角线是变量
追赶法的U：主对角线全是1，只有主对角线上面一列是变量
容易算错
最后回代也容易错，计算量还是有点大的
给出一种我发现的不错方法：
首先，9个参数还是得解9个方程的，这一步不可能省略
然后写出对应的L和U，我的建议是：维数过多而且有分数的，列成表格的形式：
然后用卡西欧计算器，解前面4阶，得到四维向量的解，与正确答案只差一维
我们只用手算一维，就能得到答案了
向量和矩阵的范数
矩阵范数定义
常见范数
\[ \begin{align*} 矩阵的范数：\\ F-范数：\\ ||A||_F&=(\sum_{i=1}^n\sum_{j=1}^na_{ij}^2)^{\frac{1}{2}}&即矩阵每一项元素平方求和再开根号\\ 1-范数（列范数）：\\ ||A||_1&=\max_{1\le j\le n}\sum_{i=1}^n|a_{ij}|&即矩阵列元素绝对值相加，最大的和\\ 2-范数（谱范数）：\\ ||A||_2&=\sqrt{\rho(A^TA)}&即矩阵转置乘本身，求出谱半径再开根\\ \infty-范数（行范数）：\\ ||A||_\infty&=\max_{1\le i\le n}\sum_{j=1}^n|a_{ij}|&即矩阵行元素绝对值相加，最大的和\\ \end{align*} \]
矩阵的谱半径：\(\rho(A)\)是矩阵特征值绝对值的最大值，注意：是绝对值
1范数是列范数，就是列元素绝对值相加，最大的和
无穷范数是行范数，就是行元素绝对值相加，最大的和
矩阵的范数，除了行列范数，都要开根
矩阵的范数，基本都是绝对值运算（乘方相当于绝对值），仅有2范数不用绝对值
例题
虽然卡西欧不能算特征值，但是我们可以解方程
先用矩阵运算，求出\(A^TA\)，再手算出特征值的方程
卡西欧用的牛顿法解方程，所以我们初始值带一个很大的数，他肯定能够找到最大的特征值，这个就是我们要找的值，开个根就是2范数
矩阵条件数和误差分析
病态矩阵
判断矩阵是不是病态矩阵：条件数
矩阵条件数
2范数太难算了，还是用行范数或者列范数好一些
\[ \begin{align*} 矩阵条件数：\\ Cond(A)_2&=||A^{-1}||\cdot||A|| \end{align*} \]
矩阵三角分解总结
\[ \begin{align*} LU分解：\\ A&=LU\\ &所有方阵都可以LU分解\\ &L矩阵对角线上的元素一定为1\\ &U矩阵第一行元素一定是A的第一行元素\\ &LU分解唯一\\\\ 对称矩阵A&=LDL^T\\ &对称矩阵这个分解，只要是对称矩阵都行\\\\ 如果A是对称正定矩阵：\\ 楚列斯基分解：\\ A&=L_1L_1^T\\ &楚列斯基分解，仅有对称正定矩阵可以\\\\\\ 矩阵的范数：\\ F-范数：\\ ||A||_F&=(\sum_{i=1}^n\sum_{j=1}^na_{ij}^2)^{\frac{1}{2}}&即矩阵每一项元素平方求和再开根号\\ 1-范数（列范数）：\\ ||A||_1&=\max_{1\le j\le n}\sum_{i=1}^n|a_{ij}|&即矩阵列元素绝对值相加，最大的和\\ 2-范数（谱范数）：\\ ||A||_2&=\sqrt{\rho(A^TA)}&即矩阵转置乘本身，求出谱半径再开根\\ \infty-范数（行范数）：\\ ||A||_\infty&=\max_{1\le i\le n}\sum_{j=1}^n|a_{ij}|&即矩阵行元素绝对值相加，最大的和\\\\ 矩阵条件数：\\ Cond(A)_2&=||A^{-1}||\cdot||A|| \end{align*} \]
解线性方程组的迭代法
迭代法定义
雅可比迭代法
迭代形式很容易，把每个变量单独放在等号左边，等号右边全是上一次迭代的值
雅克比迭代法矩阵形式
注意：不要跟矩阵三角分解的LU矩阵弄混了
迭代法的矩阵仅仅是简单的加减法，三角分解里LU是乘法关系
雅克比迭代法： \[ \begin{align*} 把矩阵A分解为：\\ A&=D-L-U\\ &D为主对角线元素，L为下三角矩阵，U为上三角矩阵\\ &因为减法，所以L和U里的元素符号和A是反的\\\\ 对Ax=b：\\ 雅克比迭代法：\\ x^{(k+1)}&=B_Jx^{(k)}+f\\ B_J&=D^{-1}(L+U)\\ f&=D^{-1}b \end{align*} \]
高斯塞德尔迭代法
G-S法
由雅克比迭代法改进而来
高斯塞德尔迭代法矩阵形式
\[ \begin{align*} 把矩阵A分解为：\\ A&=D-L-U\\ &D为主对角线元素，L为下三角矩阵，U为上三角矩阵\\ &因为减法，所以L和U里的元素符号和A是反的\\\\ 对Ax=b：\\ 高斯塞德尔迭代法：\\ x^{(k+1)}&=B_{GS}x^{(k)}+f\\ B_{GS}&=(D-L)^{-1}U\\ f&=(D-L)^{-1}b \end{align*} \]
例题
这个例子可以看出G-S法对雅可比迭代法的改进：把上面算到的最新值代入求解
迭代法收敛条件
判断迭代法收敛条件的充要条件是看迭代矩阵的谱半径是否小于1
例题
通过这个题发现，谱半径太难算了
\(\rho(B)\)是迭代矩阵特征值绝对值的最大值
既然是绝对值，那我是不是只要找到特征值的大致范围就行了？
这就可以通过Gershgorin圆盘定理实现
圆盘定理
说人话，就是一个矩阵的特征值分布在几个圆盘里
圆盘的圆心为矩阵对角线元素
圆盘的半径为矩阵\(A\)的第\(i\)行元素，去掉\(a_{ii}\)以后的绝对值之和
比如：
第一个圆盘，圆心为4，半径为1+0=1
第二个圆盘，圆心为0，半径为1+1=2
第三个圆盘，圆心为-4，半径为1+1=2
如果这个矩阵是一个迭代矩阵，那很明显这个迭代矩阵不收敛
迭代法收敛充分条件
如果任意一个范数小于1，就可以认为是收敛的
如果要判断矩阵是否发散，只能用谱半径
例题
SOR迭代法
矩阵形式
\[ \begin{align*} 对Ax=b：\\ SOR法：\\ x^{(k+1)}&=(D-\omega L)^{-1}[(1-\omega)D+\omega U]x^{(k)}+\omega (D-\omega L)^{-1}b\\ SOR迭代矩阵L_\omega：\\ L_\omega&=(D-\omega L)^{-1}[(1-\omega)D+\omega U]\\\\ f&=\omega (D-\omega L)^{-1}b \end{align*} \]
经验上取\(\omega\)为\(1.4<\omega<1.6\)
例题
SOR收敛性
迭代法总结
\[ \begin{align*} 迭代法：\\ x^{(k+1)}&=Bx^{(k)}+f\\\\ 对Ax=b：\\ 把矩阵A分解为：\\ A&=D-L-U\\ &D为主对角线元素，L为下三角矩阵，U为上三角矩阵\\ &因为减法，所以L和U里的元素符号和A是反的\\\\\\ 对Ax=b：\\ 雅克比迭代法：\\ x^{(k+1)}&=B_Jx^{(k)}+f\\ B_J&=D^{-1}(L+U)\\ f&=D^{-1}b\\\\ 对Ax=b：\\ 高斯塞德尔迭代法：\\ x^{(k+1)}&=B_{GS}x^{(k)}+f\\ B_{GS}&=(D-L)^{-1}U\\ f&=(D-L)^{-1}b\\\\ 迭代法收敛充要条件：\\ \rho(B)&<1\\\\ &但是谱半径太难算了\\ &如果任意一个范数||B||小于1，就可以认为是收敛的\\ &如果要判断收敛法是否发散，只能用\rho(B)\\\\ 对Ax=b：\\ SOR法：\\ x^{(k+1)}&=(D-\omega L)^{-1}[(1-\omega)D+\omega U]x^{(k)}+\omega (D-\omega L)^{-1}b\\ SOR迭代矩阵L_\omega：\\ L_\omega&=(D-\omega L)^{-1}[(1-\omega)D+\omega U]\\ f&=\omega (D-\omega L)^{-1}b\\ \end{align*} \]
复习课习题
有效数字
先看给出的两个数，3.1415和3.1416，都是5位
但是这两个数都已知了精确值\(\pi=3.1415926...\)，这个精确值如果四舍五入只剩5个数就是\(3.1416\)
很明显\(3.1415\)这个就是没有四舍五入的数，所以最后一位没用，看成\(3.141\)就行
这样处理之后，有效数字的个数就是数的个数：\(3.141\)有4个数，\(n\)为4；\(3.1416\)有5个数，\(n\)为5
注意：只有给出精确值了才能这样处理，否则都是先写成科学计数法，然后看数字位数
多元可微函数绝对误差限相对误差限
\[ \begin{align*} S&=L\cdot D，其中L和D都是变量\\\\ \varepsilon(S^*)&\approx|(\frac{\partial S}{\partial L})^*|\cdot\varepsilon(L^*)+|(\frac{\partial S}{\partial D})^*|\cdot\varepsilon(D^*)\\ &=D^*\cdot0.2+L^*\cdot0.1\\ &=80*0.2+110*0.1\\ &=27(m^2)\\ \\ \varepsilon_r(S^*)&\approx\frac{\varepsilon(S^*)}{|S^*|}\\ &=\frac{27}{L^*D^*}\\ &=\frac{27}{110*80}\\ &=0.31\% \end{align*} \]
拉格朗日插值误差限
均差表
一阶均差：\(\dfrac{3-5}{-1+2}=-2\)，\(\dfrac{17-3}{1+1}=7\)，\(\dfrac{21-17}{2-1}=4\)
二阶均差：\(\dfrac{7+2}{1+2}=3\)（这个的分母减的是\(x_0\)，即\(x_2-x_0=1-(-2)\)，后面的分母都是隔了一个\(x\)，比如\(x_3-x_1\)，\(x_4-x_2\)）
\(\dfrac{4-7}{2+1}=-1\)
三阶均差：\(\dfrac{-1-3}{2+2}=-1\)（这个的分母减的是\(x_0\)，即\(x_3-x_0=2-(-2)\)
牛顿前插公式
题目意思：从0开始，间隔0.1，取到0.5
4次插值，只用5个点
注意别把数字抄错了，不然差分表白列了
三点三次埃尔米特插值
可惜卡西欧计算器并不是万能的，多项式化简这一步就不行
顺序化简容易化错，我建议按照项化简
你一个多项式说到底就是\(ax^3+bx^2+cx+d\)，我们直接算出这些系数就行了，不需要一步一步化简，又慢又容易错
卡西欧框框按，算的飞快
考试要是代值那将绝杀
切比雪夫零点插值加换元
考试不可能出这么离谱的，这真不可能算出来
只需要知道如果切比雪夫零点插值，则误差限的分析就要重新计算
如果在此基础上又他妈换一个元，把变量换到\([-1,1]\)，误差限分析的时候又要多乘一个\(\dfrac{(b-a)^{n+1}}{2^{n+1}}\)
切比雪夫多项式性质：\(n-1\)次最优一致逼近\(n\)次
考试出题的时候可能会给你多个\(T_n(x)\)，我们的目的是把最高次项减掉，所以只用最高次项对应的\(T_n(x)\)即可
直线拟合
最小二乘拟合的时候，先把数据点描在图上，来确定用什么函数拟合
这个就可以用直线拟合
我很倾向于用解方程的方法求解，只是可能会算错，注意计算器别按错就好了
如果你是个蓝狗，也可以试试用矛盾方程组系数矩阵求解的方式：
你要做的工作仅仅只有把系数矩阵A和向量b输入计算器
然后用转置矩阵、求逆这样的方法求解
这种方法仅适用于4个数据点，因为卡西欧计算器最高只支持到4x4的矩阵运算，很可惜
不过一开始的解方程法就不用担心数据点过多，问题不大
多项式拟合
变体多项式拟合
PPT给的答案是：
还是有一定误差的
数值积分
牛顿柯特斯求积公式
柯特斯系数如下：
\[ \begin{align*} \text{n=3时，步长为}&(12-0)\div3=4\\ \int_{0}^{12}\frac{x}{6+5x^2}dx&=12\times(\frac{1}{8}f(0)+\frac{3}{8}f(4)+\frac{3}{8}f(8)+\frac{1}{8}f(12))\\ &=\frac{12}{8}(0+3\times0.046511627+3\times0.024539877+0.016528925)\\ &=0.344525155\\\\ \text{n=4时，步长为}&(12-0)\div4=3\\ \int_{0}^{12}\frac{x}{6+5x^2}dx&=12\times(\frac{7}{90}f(0)+\frac{32}{90}f(3)+\frac{12}{90}f(6)+\frac{32}{90}f(9)+\frac{7}{90}f(12))\\ &=\frac{12}{90}(7\times0+32\times0.058823529+12\times0.032258064+32\times0.02189781+7\times0.016528925)\\ &=0.411450945 \end{align*} \] \(n=4\)时，代数精度为5
高斯消去法
列主元高斯消去法
LU分解
L矩阵对角线上的元素一定为1
U矩阵第一行元素一定是A的第一行元素
楚列斯基分解法
楚列斯基分解不是很好算，头大
矩阵范数计算
虽然卡西欧不能算特征值，但是我们可以解方程
先用矩阵运算，求出\(A^TA\)，再手算出特征值的方程
卡西欧用的牛顿法解方程，所以我们初始值带一个很大的数，他肯定能够找到最大的特征值，这个就是我们要找的值，开个根就是2范数
迭代法收敛
SOR迭代法
证明题
函数的范数三条性质：正定性，齐次性，三角不等式
这里仅用到三角不等式
差分的定义
复习课强调
强调内容
SOR的中文：逐次超松弛法
一元可微函数的条件数大于10，认为是病态的
多项式插值存在且唯一
拉格朗日基函数的性质
k阶均差定义（虽然不用定义算均差，但是要知道定义）
均差与节点顺序无关
注意三点三次埃尔米特插值的条件：\(P'(x_1)=f'(x_1)\)
掌握分段插值，如果10分一个题，可能会一个分段值1分
截断误差（方法误差），舍入误差
三次样条插值，不考计算，考的是插值条件和三种边界条件，比如给你三次样条插值的基函数S0, S1, S2，把中间的系数隐去。用S(x)连续且二阶可导：连续就在连接点函数值相等，导数值也相等
范数必考，向量的范数，函数的范数，矩阵的范数，比如证明题，以正定性和齐次性为基础，混合起来考；除了性质，更重点的是范数的计算
用内积的四条性质证明了“柯西施瓦茨不等式”，如果是10分证明题，难度会提高
两个常见的权函数：\(\rho(x)=1\)和\(\rho(x)=\dfrac{1}{\sqrt{1-x^2}}\)
带权内积的计算方法一定得会，比如可能证明一个函数族是正交的，就要算自己跟自己做带权内积不等于0，其他的都等于0
勒让德多项式的4条性质一定要知道，尤其是递推公式和正交性的 \(\dfrac{2}{2n+1}\)
看到切比雪夫多项式就想到三角换元，令\(x=\cos\theta\)，则切比雪夫多项式就可以化为\(T_n(x)=\cos(n\theta)\)
切比雪夫零点：\(x_k=\cos(\dfrac{2k-1}{2n}\pi)\qquad k=1,2,...,n\)，切比雪夫零点公式里的\(n\)是点的个数
切比雪夫多项式正交性的证明要会
切比雪夫插值的误差限：\(\max{|R_n(x)|}\le\dfrac{M_{n+1}}{(n+1)!}\max{|\omega_{n+1}(x)|}\)，注意\(M_{n+1}\)最大值是\(||f^{(n+1)}(x)||_\infty\)，\(\max{|\omega_{n+1}(x)|}\)对应的是\(\dfrac{1}{2^n}\)，所以最终的结果为\(\dfrac{||f^{(n+1)}(x)||_\infty}{2^n(n+1)!}\)
矛盾方程组要会列
考多项式拟合就一定考变体
代数精度要考就考代数精度验证方法，比如给一个机械求积公式，求代数精度，就把\(f(x)=1, x, x^2\)带入先求出这个机械求积公式，再把\(x^3,x^4\)往里带看是否精确成立，直到成立为止
机械求积公式所有系数\(A\)加起来等于\(b-a\)，容易忘
插值型求积公式注意余项，和拉格朗日插值余项是一样的，再多求一个积分就行，即\(R[f]=\int_a^bR_n(x)dx\)
牛顿柯特斯大于等于8以后就不稳定了，因为出现了负数
要熟练掌握n=1，n=2时的牛顿柯特斯求积公式，即梯形公式，辛普森公式（抛物线公式），可能会出填空题
复合求积公式，类似于分段插值，叫做分段求积，比如用辛普森公式对一个从0到1的f(x)，分5段求积，这个还是很容易的，因为积分基本上是让你求一个具体的值，卡西欧可以咣咣按，而分段插值，每一段对应了不同的函数，化简可能有点头大
注意高斯消去法什么时候才能用：消完了以后得到的矩阵，对角线叫做主元；还有一个是没消元之前的矩阵，顺序主子式全都不为0，高斯消去法也能进行到底；这两个对应的矩阵是不一样的
改进的楚列斯基分解法也可能出，处理3个矩阵会比处理2个矩阵麻烦，因为题目分值提高了
矩阵范数的定义多了第四条
矩阵的条件数要会算
三种迭代法对应的收敛条件，所以三种迭代矩阵一定要会
SOR迭代形式必须知道，还有\(w\)跟1对应的三个概念称呼性问题；又强调一遍SOR的中文：逐次超松弛迭代法
可能出一个矩阵，判断某种迭代法是否收敛，预估收敛速度，小的快；可以通过矩阵范数来确定是否收敛，这只是充分条件，算的范数如果都大于等于1，也不能确定发散，发散唯一的判断标准是谱半径大于等于1
圆盘定理可能不能用，不要过多浪费时间
注意，矩阵迭代法，先写迭代形式，再去求解B（迭代形式，就把每个x放在等号左边）
SOR收敛的必要条件和充分条件
对应强调的内容做出的总结
拉格朗日基函数的性质
两条性质
性质1：\(f(x)\)为多项式且次数\(\le n\)
如果次数\(\le n\)，则对应的高阶导数\(f^{(n+1)}(x)=0\)，对应拉格朗日插值的余项\(R_n(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x)\)，分子就是0，所以余项就是0，无误差
性质2：\(f(x)=x^k\)且次数\(\le n\)
同样是因为对应的高阶导数\(f^{(n+1)}(x)=0\)，余项为0，没有误差
特别注意当\(k=0\)时，\(x^k=1\)，所以插值函数\(L_n(x)\)最后等于1
k阶均差的定义
\[ f[x_0,x_1,...,x_k]=\frac{f[x_0,...,x_{k-2},x_k]-f[x_0,...,x_{k-1}]}{x_k-x_{k-1}} \] 注意分子第一项是\(x_{k-2}\)直接跳到了\(x_k\)
分子第一项，方括号里面是\(k\)项
分子第二项，方括号里面也是\(k\)项
三次样条插值条件和边界条件
插值条件：\(S(x_k)=f(x_k)=y_k\)
三类边界条件：
第一类：给定函数在端点处的一阶导数，端点处\(S(x)\)的一阶导数和\(f(x)\)的一阶导数相等
第二类：给定函数在端点处的二阶导数，端点处\(S(x)\)的二阶导数和\(f(x)\)的二阶导数相等
第三类：\(f(x)\)在\(x_0\sim x_n\)是一个周期，即\(S(x_0)=S(x_n)\)
这三类对应了三种不同情况，看题给信息
比如给定三次样条插值的基函数S0, S1, S2，把中间的系数隐去
用S(x)连续且二阶可导：连续就在连接点函数值相等，导数值也相等
范数
向量、函数的范数有三个性质：正定性、齐次性、三角不等式
矩阵的范数多了一个性质：\(||AB||\le||A||\cdot||B||\)
正定性：\(||x||\ge0\)，等号当且仅当\(x=0\)时成立
齐次性：\(||\alpha x||=|\alpha|\cdot||x||,\quad\alpha\in R\)
三角不等式：\(||x+y||\le||x||+||y||\)
\(R^n\)为\(n\)阶实数，向量
\(C[a,b]\)为在\([a,b]\)上连续，函数
\[ \begin{align*} 向量的范数：\\ 1-范数:||x||_1&=\sum_{i=1}^n|x_i|=|x_1|+|x_2|+...+|x_n|&即向量每一维绝对值相加\\ 2-范数:||x||_2&=(\sum_{i=1}^nx_i^2)^{\frac{1}{2}}=\sqrt{x_1^2+x_2^2+...+x_n^2}&即向量每一维平方相加再开根\\ p-范数:||x||_p&=(\sum_{i=1}^nx_i^p)^{\frac{1}{p}}&即向量每一维p次方相加再开p次根\\ \infty-范数:||x||_\infty&=\max_{1\le i\le n}{|x_i|}&绝对值最大的分量\\\\ 函数的范数：\\ 1-范数:||f||_1&=\int_a^b|f(x)|dx&即函数绝对值求积分\\ 2-范数:||f||_2&=(\int_a^b|f(x)|^2dx)^{\frac{1}{2}}&即函数绝对值平方求积再开根\\ p-范数:||f||_p&=(\int_a^b|f(x)|^pdx)^{\frac{1}{p}}&即函数绝对值p次方求积再开p次根\\ \infty-范数:||f||_\infty&=\max_{a\le x\le b}{|f(x)|}&绝对值最大函数值\\\\ 矩阵的范数：\\ F-范数：\\ ||A||_F&=(\sum_{i=1}^n\sum_{j=1}^na_{ij}^2)^{\frac{1}{2}}&即矩阵每一项元素平方求和再开根号\\ 1-范数（列范数）：\\ ||A||_1&=\max_{1\le j\le n}\sum_{i=1}^n|a_{ij}|&即矩阵列元素绝对值相加，最大的和\\ 2-范数（谱范数）：\\ ||A||_2&=\sqrt{\rho(A^TA)}&即矩阵转置乘本身，求出谱半径再开根\\ \infty-范数（行范数）：\\ ||A||_\infty&=\max_{1\le i\le n}\sum_{j=1}^n|a_{ij}|&即矩阵行元素绝对值相加，最大的和\\ \end{align*} \]
内积性质证明柯西施瓦茨不等式
内积：定义\(x=(x_1,x_2,...,x_n)^T,y=(y_1,y_2,...,y_n)^T\)
则内积为：\((x,y)=x_1y_1+x_2y_2+...+x_ny_n\)
内积四条性质： \[ \begin{align*} 1.&(u,v)=\overline{(v,u)}\\ 2.&(\alpha u,v)=\alpha(u,v)\\ 3.&(u+v,w)=(u,w)+(v,w)\\ 4.&(u,u)\ge0,\qquad u=0时取等\\ \end{align*} \]
柯西施瓦茨不等式： \[ |(u,v)|^2\le(u,u)(v,v) \] 证明过程：
勒让德多项式性质
性质1：正交性，这个得知道什么是带权内积，放在下面
性质2：奇偶性，即\(P_{2n}(x)\)只含偶次幂，\(P_{2n+1}(x)\)只含奇次幂
性质3：递推公式：\((n+1)P_{n+1}(x)=(2n+1)xP_n(x)-nP_{n-1}(x)\)
性质4：零点，\(P_n(x)\)在\((-1,1)\)有\(n\)个不同的零点
带权内积 \[ (f(x),g(x))_\rho=\int_a^b\rho(x)f(x)g(x)dx \] 正交性的证明，就是证明自己跟自己带权内积不为0，与其他带权内积都为0
勒让德多项式对应的权函数\(\rho(x)=1\)
因此勒让德公式的正交性就是\(\int_{-1}^1P_n(x)P_m(x)dx\)
当\(m\ne n\)时，值为0
当\(m=n\)时，值为\(\dfrac{2}{2n+1}\)
证明切比雪夫多项式正交性
正交性的证明，就是证明自己跟自己带权内积不为0，与其他带权内积都为0
带权内积： \[
(f(x),g(x))_\rho=\int_a^b\rho(x)f(x)g(x)dx
\]
看到切比雪夫多项式就想到三角换元，令\(x=\cos\theta\)，则切比雪夫多项式就可以化为\(T_n(x)=\cos(n\theta)\)
所以证明过程如下： \[ \begin{align*} 切比雪夫多项式的权函数：\\ \rho(x)&=\frac{1}{\sqrt{1-x^2}}\\ 带权内积为：\\ (T_n,T_m)_\rho&=\int_{-1}^1\frac{T_n(x)T_m(x)}{\sqrt{1-x^2}}dx\\\\ 令x=\cos\theta&，则dx=-\sin\theta d\theta，对应积分上下限同时改变\\\\ 故切比雪夫多项式带权内积转化为：\\ (T_n,T_m)_\rho&=\int_{\pi}^0\frac{\cos(n\theta)\cdot\cos(m\theta)}{\sqrt{1-\cos\theta^2}}\cdot(-sin\theta)d\theta\\ &=\int_{\pi}^0\frac{\cos(n\theta)\cdot\cos(m\theta)}{sin\theta}\cdot(-sin\theta)d\theta\\ 负号放到积分上下限里：&=\int_{0}^\pi\cos(n\theta)\cdot\cos(m\theta)d\theta\\ 利用三角函数加法公式：&=\int_{0}^\pi\frac{\cos(n+m)\theta+\cos(n-m)\theta}{2}d\theta\\\\ 当m\ne n时：\\ (T_n,T_m)_\rho&=\int_{0}^\pi\frac{\cos(n+m)\theta+\cos(n-m)\theta}{2}d\theta\\ \cos k\theta在[0,\pi]积分为0：&=0\\\\ 当m=n\ne0时：\\ (T_n,T_m)_\rho&=\int_{0}^\pi\frac{\cos(n+m)\theta+\cos(n-m)\theta}{2}d\theta\\ &=\int_{0}^\pi\frac{\cos(2n)\theta+\cos(0)\theta}{2}d\theta\\ &=\int_{0}^\pi\frac{\cos(2n)\theta}{2}d\theta+\int_{0}^\pi\frac{1}{2}d\theta\\\\ &=0+\frac{\pi}{2}\\ &=\frac{\pi}{2}\\\\ 当m=n=0时：\\ (T_n,T_m)_\rho&=\int_{0}^\pi\frac{\cos(0)\theta+\cos(0)\theta}{2}d\theta\\ &=\int_{0}^\pi1d\theta\\ &=\pi \end{align*} \]
矩阵条件数
\(Cond(A)_2=||A^{-1}||_2||A||_2\)
其中\(||\cdot||_2\)也可以换为1范数或无穷范数
SOR逐次超松弛迭代法
中文名：逐次超松弛迭代法
迭代形式：多了一个\(\omega\)，比如下图：
\(\omega\)和1对应的3个称呼性问题：
\(\omega=1\)时，SOR就是G-S法
\(\omega>1\)时，称为超松弛法
\(\omega<1\)时，称为低松弛法
经验上取\(\omega\)为\(1.4<\omega<1.6\)
SOR收敛定理
参考资料
课程PPT
最后一节复习课