研一课程笔记-数值分析4-6

非线性方程迭代解法

n次方程根的个数与次数相同（实根或者复根）

设有非线性方程

$f(x)=0\tag{4.1}$

其中 $f(x)$ 是一元非线性函数。若常数 $s$ 使 $f(s)=0$ ,则称 $s$ 是方程(4.1)的根，又称 $s$ 是函数 $f(x)$ 的零点。若 $f( x)$ 能分解为

$f(x)=(x-s)^m\varphi(x)$

其中 $m$ 是正整数， $\varphi(s)\neq0$ ，则称 $s$ 是方程(4.1)的 $m$ 重根和 $f(x)$ 的 $m$ 重零点。当 $m=1$ 时， $s$ 称为方程(4.1)的单根和 $f(x)$ 的单零点。

二分法

用 $C[a,b]$ 和 $C(a,b)$ 分别表示在闭区间 $[a,b]$ 和开区间 $(a,b)$ 上连续的函数集合。

设 $f(x)\in C[a,b]$ 且 $f(a)f(b)<0$ ，根据连续函数的介值定理，在区间 $(a,b)$ 内至少有一实数 $s$ ，使 $f(s)=0$ 。现假定在 $(a,b)$ 内只有一个实数 $s$ 使 $f(s)=0$ ,并要把 $s$ 求出来。用对分法求这个 s 的算法如下：

令 $a_0=a,b_0=b$ 。

对于 $k=0,1,\cdotp\cdotp\cdotp,M$ 执行

(1)计算 $x_k=\frac {a_k+b_k}2$

(2) 若 $b_k-a_k\leqslant\varepsilon$ 或 $|f(x_k)|\leqslant\eta$ ,则停止计算，取 $s\approx x_k$ 否则转(3)。

(3)若 $f(a_k)f(x_k)<0$ ,则令 $a_k+1=a_k,b_{k+1}=x_k$ 若 $f(a_k)f(x_k)>0$ ，则令 $a_k+1=x_k,b_{k+1}=b_k$ 。

(4)若 $k=M$ ，则输出 $M$ 次迭代不成功的信息；否则继续。

迭代终止条件

一般通过 $\begin{vmatrix}x_{k+1}-x_k\end{vmatrix}<\varepsilon_1$ 或者 $\begin{vmatrix}f(x)\end{vmatrix}<\varepsilon_2$ 来作为迭代的终止条件，一般我们选择前者，因为后者可能会有梯度非常小的情况

简单迭代法及其收敛性

把 $f(x)=0$ 转化为等价的方程

$x=\varphi(x) \tag{4.2}$

从而 $f( s) = 0$ 等价于 $s= \varphi ( s)$ 。 $s$ 叫 $\varphi(x)$ 的不动点。

选定 $s$ 的初始近似值 $x_0$ ，用递推公式

$x_{k+1}=\varphi(x_k)\quad(k=0,1,\cdotp\cdotp\cdotp)\tag{4.3}$

产生序列 $\left\{x_k\right\}$ ，在一定条件下，序列 $\left\{x_k\right\}$ 收敛于 $s$ 。在 $\left\{x_k\right\}$ 收敛的情况下，当 $k$ 足够大时就可取 $x_k$ 作为方程(4.1)的近似根。迭代公式(4.3)被称为求解方程(4.1)的简单迭代法，其中 $\varphi(x)$ 称为迭代函数。

对于任意的式(4.1)可构成多种简单选代法，它们的迭代函数各不相同。为求同一个根，它们所产生的序列 $\left\{x_k\right\}$ ，有的可能收敛，有的可能不收敛；有的会收敛得快，有的会收敛得慢。这一切都取决于送代函数 $\varphi(x)$ 在有根区间内的性态。

大范围收敛性定理

设函数 $\varphi(x)\in C[a,b]$ ，在( $a,b)$ 内可导，且满足两个条件：

当 $x\in[a,b]$ 时， $\varphi(x)\in[a,b];$
当 $x\in(a,b)$ 时， $|\varphi^\prime(x)|\leqslant L<1$ ，其中 $L$ 为一常数。

则有如下结论：

方程(4.2)在区间[a,b]上有唯一的根 $s$ ;
对任取的 $x_0\in[a,b]$ ，简单迭代法(4. 3)产生的序列 $\{x_k\}\subset[a,b]$ 且收敛于 $s$ ;
成立误差估计式

$\mid s-x_k\mid\leqslant\frac{L^k}{1-L}\mid x_1-x_0\mid \tag{4.4}$

$\mid s-x_k\mid\leqslant\frac L{1-L}\mid x_k-x_{k-1}\mid \tag{4.5}$

1）令 $F(x)=x-\varphi(x)$ ，则 $F(x)\in C[a,b]$ ，并由条件(1)可知
$F(a)=a-\varphi(a)\leqslant0,\quad F(b)=b-\varphi(b)\geqslant0$
若上面两个不等式中有一个等号成立，则方程(4.2)有根 $s=a$ 或 $s=b$ 。若两个都是严格不等式，则根据连续函数的介值定理，必存在 $s\in(a,b)$ ，使 $F(s)=s-\varphi(s)=0$ ，即方程(4.2)有根 $s\in(a,b)$ 。今设有两个不同的 $s_1,s_2\in[a,b]$ 使 $s_1=\varphi(s_1),s_2=\varphi(s_2)$ ，则由微分中值定理以及条件(2)，有
$\mid s_1-s_2\mid=\mid\varphi(s_1)-\varphi(s_2)\mid=\mid\varphi^{\prime}(\xi)\mid\mid s_1-s_2\mid\leqslant L\mid s_1-s_2\mid<\mid s_1-s_2\mid$
其中 $\xi$ 在 $s_1$ 与 $s_2$ 之间，因而 $\xi\in(a,b)$ 。上式出现的矛盾证实 $s_1=s_2$ 。
2）因 $x_0\in[a,b]$ ，由条件(1)可知， $\{x_k\}\subset[a,b]$ 。又由条件(2)，得
$\mid x_k-s\mid=\mid\varphi(x_{k-1})-\varphi(s)\mid=\mid\varphi^{\prime}(\xi_k)\mid\cdot\mid x_{k-1}-s\mid\leqslant L\mid x_{k-1}-s\mid\leqslant\cdotp\cdotp\cdotp\leqslant L^k\mid x_0-s\mid$
其中 $\xi_k$ 在 $x_k-1$ 与 $s$ 之间，因而 $\xi_k\in(a,b)$ 。因 0 $\leqslant L<1$ ，故有 $\lim_{k\to\infty} x_k=s$ 。
3）设 $m>k$ ，则有
$x_m-x_k=\sum_{i=k}^{m-1}(x_{i+1}-x_i)$
而
$\begin{aligned}\mid x_{i+1}-x_i\mid&=\mid\varphi(x_i)-\varphi(x_{i-1})\mid\leqslant\\&L\mid x_i-x_{i-1}\mid\leqslant\ldots\leqslant L^i\mid x_1-x_0\mid\end{aligned}$
于是有：
$\mid x_m-x_k\mid\leqslant\sum_{i=k}^{m-1}\mid x_{i+1}-x_i\mid\leqslant\sum_{i=k}^{m-1}L^i\mid x_1-x_0\mid=L^k\frac{1-L^{m-k}}{1-L}\mid x_1-x_0\mid$
$x_m-x_k=x_m-x_{m-1}+x_{m-1}\cdots-x_k$
然后使用绝对值不等式
令 $m\to\infty$ ,由于 0 $\leqslant L<1$ ，故由上式得到式(4.4)。
又由
$\mid x_{i+1}-x_i\mid\leqslant L\mid x_i-x_{i-1}\mid\leqslant\cdots\leqslant L^{i-k+1}\mid x_k-x_{k-1}\mid$
得
$\mid x_m-x_k\mid\leqslant\sum_{i=k}^{m-1}\mid x_{i+1}-x_i\mid\leqslant\sum_{i=k}^{m-1}L^{i-k+1}\mid x_k-x_{k-1}\mid=L\frac{1-L^{m-k}}{1-L}\mid x_k-x_{k-1}\mid$
令 $m\to\infty$ ，由上式得到式(4.5)。证毕。

局部收敛性定理

注：定理4.2并没有给出邻域 $\delta$ 具体是什么，怎么计算，仅仅要求该邻域存在，也即迭代的起始点 $x_0$ 足够接近 $s$ 时。总能得到收敛于 $s$ 的迭代序列。

简单迭代法收敛速度

这里 $\theta$ 相当于一个仿射变换，此外证明得到的 $\lim_{k\to\infty}\mid\varphi^{\prime}(s-\theta e_{k})\mid=\mid\varphi^{\prime}(s)\mid$ ，也就是说常数 $c=\mid\varphi^{\prime}(s)\mid$

证明中一个非常关键的点是连续性

牛顿法

用简单送代法求方程(4.1)的根 $s$ ，十分重要的问题是构造迭代函数 $\varphi(x)$ 。为了使收敛速度的阶高一些，应尽可能使 $\varphi(x)$ 在 $x=s$ 处有更多阶导数等于零。

现在令 $\varphi(x)=x+h(x)f(x)$ ， $h(x)$ 为待定函数，但 $h(s)\neq0$ ，代入简单迭代法 $\varphi(x)=x$ ，则方程(4.1)与方程

$x=x+h(x)f(x)$

有共同的根 $s$ 。现用条件 $\varphi^{\prime}(s)=0$ 确定 $h(x)$ 。由 $f(s)=0$ ，则：

$\varphi^\prime(s)=1+h^\prime(s)f(s)+h(s)f^\prime(s)=1+h(s)f^\prime(s)=0$

知 $h(x)$ 必须满足 $h(s)=\frac{-1}{f^{\prime}(s)}$ 。显然，取 $h(x)=-\frac1{f^{\prime}(x)}$ 就具备这个条件，并且也满反 $h(s)\neq0$ 。于是， $\varphi(x)$ 被确定为

$\varphi(x)=x-\frac{f(x)}{f^{\prime}(x)}$

它满足 $\varphi^\prime(s)=0$ 。由此得出下面的特殊的简单迭代法

$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime}(x_k)}\quad(k=0,1,\cdotp\cdotp\cdotp)\tag{4.7}$

式(4.7)所表示的迭代法称为 Newton(牛顿)法。

Newton 法可求方程(4.1)的实数根和复数根。当求实数根时，Newton 法有明显的几何意义。当获得 $x_k$ 之后，过曲线 y $=f(x)$ 上的点 $(x_k,f(x_k))$ 作该曲线的切线，此切线与 $x$ 轴相交的交点横坐标就是 Newton 法迭代序列的第 $k+1$ 个元素 $x_{k-1}$ 。因此 Newton 法(4.7)又称为切线法。

局部收敛性

定理 4.6 设 $s$ 是方程(4.1)的根，在包含 s 的某个开区间内 $f^\prime(x)$ 连续且 $f^{\prime}(x)\neq0$ ，则存在 $\delta{>}0$ ，当 $x_0\in[s-\delta,s+\delta]$ 时，由 Newton 法(4.7)产生的序列 $\{x_k\}$ 收敛于 $s$ ；若 $f^\prime(s)\neq0$ 且 $x_0\neq s$ ，则序列 $\left\{x_k\right\}$ 是平方收敛的。

Newton 法(4.7)的迭代函数 $\varphi(x)$ 为
$\varphi(x)=x-\frac{f(x)}{f^{'}(x)},\quad\varphi^{'}(x)=\frac{f(x)f^{''}(x)}{[f^{'}(x)]^2}$
因 $f^\prime(x)$ 连续且 $f^\prime(x)\neq0$ ，故 $\varphi^{\prime}(x)$ 在包含 $s$ 的某个开区间内连续，并且有
$\varphi(s)=s,\varphi^\prime(s)=0$
根据定理 4.2，必存在 $\delta>0$ ，当 $x_0\in[s-\delta,s+\delta]$ 时，由送代法(4.7)产生的序列 $\{x_k\}\subset[s-\delta,s+\delta]$ ，且收敛于 $s$ 。
由 Taylor 公式以及 $f(s)=0$ ，有
$f(s)=f(x_k)+f^{\prime}(x_k)(s-x_k)+\frac{f^{\prime\prime}(\xi_k)}{2!}(s-x_k)^2=0$
$x_{k+1}-s=x_k-\frac{f(x_k)}{f^{\prime}(x_k)}-s=\frac{f^{\prime\prime}(\xi_k)}{2f^{\prime}(x_k)}(s-x_k)^2$
其中 $\xi_k$ 在 $x_k$ 与 $s$ 之间。因 $f^\prime(s)\neq0$ 以及 $f^{\prime}(x)$ 的连续性，故可设当 $x\in[s-\delta,s+\delta]$ 时 $f^{\prime\prime}(x)\neq0$ 。因而当 $x_0\in[s-\delta,s+\delta]$ 且 $x_0\neq s$ 时 $,x_k\neq s(k=1,2,...)$ 。于是有
$\lim_{k\to\infty}\frac{\mid x_{k+1}-s\mid}{\mid x_k-s\mid^2}=\left|\frac{f^{\prime\prime}(s)}{2f^{\prime}(s)}\right|>0$
故序列 $\left\{x_k\right\}$ 是平方收敛的。
证毕。

定理 4.6 是 Newton 法的局部收敛性定理。如果 $f(x)$ 只满足此定理的条件，则在一般情况下，初值 $x_{0}$ 要比较靠近所要求的根 $s$ ，Newton 法才能收敛，也就是定理结论中的 $\delta$ 要比较小。

大范围收敛性（收敛的充分条件

定理 4.7 设函数 $f(x)$ 在区间 $[a,b]$ 上存在二阶连续导数，且满足条件：

$f( a) f( b) {< }0$ ;（根存在）
$f^{\prime\prime}(x)$ 在区间 $[a,b]$ 上不变号；（根唯一）
当 $x\in[a,b]$ 时， $f^\prime(x)\neq0;$ （ $f^\prime(x)\neq0$ ，根唯一）
$x_{0}\in [ a, b] , f( x_{0}) f^{\prime \prime }( x_{0}) > 0$ 。

则由 Newton 法(4.7)产生的序列 $\{ x_k \}$ 单调收敛于方程(4.1) 在 $[a, b]$ 内唯一的根 $s$ ，并且至少是平方收敛的。

插值与逼近

代数插值

给定 $n+1$ 个互异的实数 $x_0, x_1, \cdots , x_n$ ，实值函数 $f( x)$ 在包含 $x_0,x_1,\cdots,x_n$ 的某个区间 $[a,b]$ 内有定义。设函数组

$\{\varphi_k(x)(k=0,1,\cdots,n)\}$

是次数不高于 $n$ 的多项式组，且在点集 $\left\{x_0,x_1,\cdots,x_n\right\}$ 上线性无关。

现在提出如下的问题：在次数不高于 $n$ 的多项式集合

$\mathscr{D}_n=\mathrm{Span}\{\varphi_0,\varphi_1,\cdots,\varphi_n\}$

中寻求多项式

$p_n(x)=\sum_{k=0}^nc_k\varphi_k(x)\tag{5.1}$

使其满足条件

$p_n(x_i)=f(x_i)\quad(i=0,1,\cdots,n)\tag{5.2}$

此问题称为一元函数的代数插值问题。 $x_0,x_1,\cdotp\cdotp\cdotp,x_n$ 称为插值节点； $f(x)$ 称为被插值函数； $\varphi_k(x)(k=0,1,\cdots,n)$ 称为插值基函数；条件(5.2)称为插值条件；满足插值条件(5.2)的多项式(5.1)称为 n 次插值多项式。

由于插值基函数组 $\{\varphi_k(x)(k=0,1,\cdots,n)\}$ 在点集 $\left\{x_0,x_1,\cdots,x_n\right\}$ 上线性无关，所以满足插值条件(5.2)的 $n$ 次插值多项式 $p_n(x)$ 是存在且唯一的。

又由于插值基函数组限定为次数不高于 $n$ 的多项式组，所以对于不同的插值基函数组，只要满足同一插值条件(5.2)，则所得的 $n$ 次插值多项式也是唯一的。

对于 $n+1$ 个插值点， $p_n(x_i)=f(x_i)$ 有 $n+1$ 个方程： $p(x_i)=\sum^n_{j=0}a_jx_i^j=f(x_i)$
最后可以化为矩阵 $X\cdot A=F$ （分别是列向量 $x_i$ ，值 $a_i,f(x_i)$ 构成的矩阵）

拉格朗日插值

取插值基函数

$l_k(x)=\prod_{j=0}^n\frac{x-x_j}{x_k-x_j}\quad(k=0,1,\cdotp\cdotp\cdotp,n) \tag{5.3}$

显然， $l_k(x)(k=0,1,...,n)$ 都是 $n$ 次多项式，且具有下列性质

$l_k(x_i)=\begin{cases}1,&i=k\\0,&i\neq k\end{cases}$

显然，通过这种方式得到的 $l_k(x_i)$ 仅第 $i$ 个分量为1，所以彼此一定会线性无关

因此，函数组 $\left\{l_k(x)(k=0,1,\cdotp\cdotp\cdotp,n)\right\}$ 必在点集 $\left\{x_0,x_1,\cdotp\cdotp\cdotp,x_n\right\}$ 上线性无关，并且

$p_n(x)=\sum_{k=0}^nl_k(x)f(x_k)\tag{5.4}$

由 $c_kl(x_k)=0,k\neq j$
$p_n(x_j)=\sum c_i l(x_i)=c_jl(x_j)=c_j=f(x_j)$

或

$p_n(x)=\sum_{k=0}^n\Big(\prod_{j=0}^n\frac{x-x_j}{x_k-x_j}\Big)f(x_k)\tag{5.5}$

就是满足插值条件(5.2)的 $n$ 次插值多项式。

牛顿插值

拉格朗日插值在计算过程中若需要改变节点或增加节点时，全部基函数 $l_k(x)$ 都需要重新计算，这在实际计算中很不方便

目标是寻找新的基函数，使得每加一个节点时，只附加一项上去，而不必重新计算全部基函数

Newton 插值多项式的构造

基函数如下：

$\{\varphi_k(x)\}=\{1,x-x_0,(x-x_0)(x-x_1),\ldots,(x-x_0)(x-x_1)\ldots(x-x_{n-1})\}$

$\begin{pmatrix}\varphi_0(x_0),\varphi_1(x_0),\ldots,\varphi_n(x_0)\\\varphi_0(x_1),\varphi_1(x_1),\ldots,\varphi_n(x_1)\\\vdots&\vdots&\vdots\\\varphi_0(x_n),\varphi_1(x_n),\ldots,\varphi_n(x_n)\end{pmatrix}=\begin{pmatrix}1&0&0&0\\1&x_1-x_0&0&0\\1&x_2-x_0&(x_2-x_0)(x_2-x_1)&\vdots\\\vdots&\vdots&\vdots&0\\\\1&x_n-x_0&(x_n-x_0)(x_n-x_1)&\prod_{j=0}^{n-1}(x_n-x_j)\end{pmatrix}$

所以这组函数线性无关，故插值函数为：

$\begin{aligned}p_{n}(x)&=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)\\&+\cdots+c_n(x-x_0)(x-x_1)\cdots(x-x_{n-1})\end{aligned}$

由 $p_n(x_i)=f(x_i)\quad(i=0,1,\cdots,n)$ ：

$\begin{cases}&f(x_0)=p_n(x_0)=c_0\\&f(x_1)=p_n(x_1)=c_0+c_1(x_1-x_0)\\&f(x_2)=p_n(x_2)=c_0+c_1(x_2-x_0)+c_2(x_2-x_0)(x_2-x_1)\\&f(x_3)=p_n(x_3)=c_0+c_1(x_3-x_0)+c_2(x_3-x_0)(x_3-x_1)\\&f(x_n)=p_n(x_n)=c_0+c_1(x_n-x_0)+c_2(x_n-x_0)(x_n-x_1)+\cdots+c_n(x_n-x_0)\cdots(x_n-x_{n-1})\end{cases}$

可得 $c_k=f[x_0,x_1,\cdots,x_k]$

k 阶差商

一阶差商： $f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}$

二阶差商： $f[x_0,x_1,x_2]=\frac{f[x_0,x_2]-f[x_0,x_1]}{x_2-x_1}$

k阶插商：

$f[x_0,x_1,\cdots,x_k]=\frac{f[x_0,x_1,\cdots,x_{k-2},x_k]-f[x_0,x_1,\cdots,x_{k-1}]}{x_k-x_{k-1}}$

牛顿插值公式利用差商可简单地表为

$\begin{aligned} &N_0(x)=f(x_0) \\ &N_1(x)=f(x_0)+f[x_0,x_1](x-x_0) \\ & \quad \quad \quad =N_0(x)+f[x_0,x_1](x-x_0) \\ &N_2(x)=N_1(x)+f[x_0,x_1,x_2](x-x_0)(x-x_1) \\ &...... \\ &N_{k+1}(x)=N_k(x)+\underbrace{f[x_0,\cdots,x_{k+1}](x-x_0)(x-x_1)\cdots(x-x_k)} \end{aligned}$

因此, 每增加一个结点， Newton 插值多项式只增加一项（即括号标注的一项）

插值余项

设 $x_0, x_1, \cdots , x_n$ 是互异实数，对给定的实数 $x$ ，实值函数 $f( x)$ 在区间 $I_x$ 上有 $n+ 1$ 阶导数，则拉格朗日插值多项式与牛顿插值多项式有相同的插值余项：

$R_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i).$

罗尔定理的推论：若 $\varphi ( x)$ 充分光滑，且 $\phi ( x_1) = \cdots = \phi ( x_n) = 0\Rightarrow$ 存在 $n-l$ 个 $\xi \in \tilde{I}$ 使得 $\varphi ^{( l) }( \xi ) = 0$
此外，过 $n +1$ 个点的 $n$ 次多项式是唯一的： $N_n(x)\equiv L_n(x)$
$R_n(x)$ 有 $n+1$ 个根 $x_0$ ~ $x_n$

证明：

由于 $R_n( x_i) = 0$ , $\boldsymbol{i}= 0, 1, . . . , n$ $\Rightarrow$ $R_{n}(x)=u(x)\prod_{i=0}(x-x_{i})=f(x)-p_{n}(x)$

任意固定 $x\neq x_i$ $( i= 0, . . . , n)$ ，构造辅助函数

$g(t)=R_n(t)-u(x)\prod_{i=0}^n(t-x_i)=f(t)-p_n(t)-u(x)\prod_{i=0}^n(t-x_i)\tag{1}$

则 $g( t)$ 有 $n+ 2$ 个不同的根 $x, x_0, \ldots , x_n$ 反复使用Rolle定理，可得存在 $\xi\in\tilde{I}_x$ ，使得：

$g^{(n+1)}(\xi)=0,\xi\in\tilde{I}_{x}$

$\Rightarrow u(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\Rightarrow R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i).\tag{2}$

显然 $\xi$ 和 $x$ 有关

对 (1) 式求导，由于 $p_n(t)$ 为 $n$ 次多项式，所以 $p_n^{(n+1)}(t)=0$ ， $[u(x)\prod_{i=0}^n(t-x_i)]^{(n+1)}=u(x)(n+1)!$ ，所以：

$g^{(n+1)}(t)=f^{(n+1)}(t)-u(x)(n+1)!$

即可得到 (2) 式

正交多项式

权函数

定义权函数在区间( $a,b)$ 上，若非负函数 $\rho ( x)$ 满足

对一切整数 $n\geq0,\int_a^bx^n\rho(x)dx$ 存在；
对 $( a, b)$ 上的非负连续函数 $f( x)$ ，若 $\int _{a}^{b}\rho ( x) f( x) dx= 0$ ，则在区间 $( a, b)$ 上 $f( x) \equiv 0.$

那么，称 $\rho(x)$ 为 $(a,b)$ 上的权函数。

常见的权函数： $\rho ( x) \equiv 1, a\leq x\leq b;$

内积

给定 $f( x) , g( x) \in C[ a, b] , \rho ( x)$ 是 $(a,b)$ 上的权函数，称

$(f,g)=\int_a^b\rho(x)f(x)g(x)dx$

为 $f$ , $g$ 在 $[a,b]$ 上的内积.

内积的性质

$\left(f,\:g\right)=\left(\:g,\:f\right);$
$(kf,g)=(f,kg)=k(f,g),k$ 为常数， $k\in R;$
$\left(f_{1}+f_{2},\:g\right)=\left(f_{1},g\:\right)+\left(f_{2},g\:\right);$
若在 $[a,b]$ 上 $f(x)\not\equiv0$ ，则 $(f,f)>0.$

正交与正交函数系

若内积

$(f,g)=\int_a^b\rho(x)f(x)g(x)dx=0$

则称 $f$ , g 在 $[a,b]$ 上带权 $\rho(x)$ 正交.

正交函数系

定义若函数系 $\{\varphi_0(x),\varphi_1(x),...,\varphi_n(x),...\}$ 满足

$(\varphi_i,\varphi_j)=\int\limits_a^b\rho(x)\varphi_i(x)\varphi_j(x)dx=\begin{cases}0, i\neq j\\a_i>0,i=j\end{cases}$

则称 $\{\varphi_n(x)\}$ 是 $[a,b]$ 上带权 $\rho(x)$ 的正交函数系.

$[a,b]$ 上带权 $\rho(x)$ 的正交函数系必是线性无关的函数系，而不论 $\rho(x)$ 是什么函数.
- 这里函数系线性无关与前面插值里的线性无关不是一个概念
设 $\varphi_k(x)$ 是最高项系数不为零的 $k$ 次多项式， $k=0,1,2,\ldots;$ 则 $\{\boldsymbol{\varphi}_k(x)\}$ 是 $[a,b]$ 上带权 $\rho(x)$ 的正交多项式系
$\Leftrightarrow$ (充分必要条件)
对任何次数不高于 $k-1$ 的多项式 $q(x)$ ，总有
$(q,\varphi_k)=\int_a\rho(x)q(x)\varphi_k(x)dx=0,k=1,2,\cdots.$

性质

(结构)设 $\{\varphi_k(x)\}$ 是 $[a,b]$ 上带权 $\rho(x)$ 的正交多项式系，则 $\left\{c_k\varphi_k(x)\right\}$ 也是 $[a,b]$ 上带权 $\rho(x)$ 的正交多项式系。其中， $c_k$ 是非零常数.
(唯一性){ $\varphi_k(x)\}$ 是区间 $[a,b]$ 上带权 $\rho(x)$ 的正交多项式系，若各个 $\varphi_k(x)$ 的最高次项系数是1，则这样的 $\{\varphi_k(x)\}$ 是唯一的.
证设 $\{\varphi_k(x)\},\{g_k(x)\}$ 为性质2中要求正交多项式系，
$k=0$ 时， $\varphi_0(x)\equiv1\equiv g_0(x).$
$k\geq 1$ 时， $g_k- \varphi _k$ 是次数不高于 $k- 1$ 的多项式，由定理5.6知，
$\begin{aligned}&(\:g_k-\varphi_k,\:\varphi_k\:)=(\:g_k-\varphi_k,\:g_k\:)=0\\&\Leftrightarrow(g_k-\varphi_k,g_k-\varphi_k)=0,\\&\Leftrightarrow g_k-\varphi_k\equiv0,\quad g_k(x)\equiv\varphi_k(x)_,a\leq x\leq b\end{aligned}$
(正交多项式的根)若 ${\varphi_k(x)}$ 是 $[a,b]$ 上带权 $\rho(x)$ 的正交多项式系，则 $k\geq1$ 时， $k$ 次正交多项式 $\varphi_k(x)$ 在 $(a,b)$ 内有 $k$ 个互异的实根.
事实上，可以证明 $k$ 次正交多项式有 $k$ 个单根.
设{ $\varphi_k(x)\}$ 是区间 $[a,b]$ 上带权 $\rho(x)$ 的正交多项式系，则 $k\geq1$ 时，有如下的递推关系式：

$\phi_{k+1}(x)=\frac{a_{k+1}}{a_k}(x-\beta_k)\phi_k(x)-\frac{a_{k+1}a_{k-1}}{a_k^2}\lambda_{k-1}\phi_{k-1}(x)$

其中， $a_k$ 是 $\varphi_k(x)$ 的最高次项系数，且

$\beta_{k}=\frac{(x\varphi_{k},\varphi_{k})}{(\varphi_{k},\varphi_{k})},\quad\lambda_{k-1}=\frac{(\varphi_{k},\varphi_{k})}{(\varphi_{k-1},\varphi_{k-1})}.$

函数的最佳平方逼近

函数的最佳逼近问题：对函数类 $A$ 中给定的函数 $f( x)$ ，需要在另一类较简单的便于计算的函数类 $B$ $( B\in A)$ 中，找一个函数 $P( x)$ ，使 $P(x)$ 与 $f (x)$ 之差在某种度量意义下达到最小。

函数 $f(x)$ 称为被逼近函数； $P( x)$ 称为逼近函数，两者之差称为逼近误差。

函数类 $A$ 通常是区间 $[a,b]$ 上的连续函数，记作 $C[a,b]$ ；函数类 $B$ 通常是代数多项式，有理多项式，三角多项式，分段多项式等容易计算的函数。

常用度量标准

一致逼近(均匀逼近)以 $\max _a\leq x\leq b| f( x) - p( x) |$ 作为度量误差 $f(x)-P( x)$ 的“大小” 标准
平方逼近(均方逼近)以以 $\int_a^b[f(x)-p(x)]^2dx$ 作为度量误差 $f(x)-P( x)$ 的“大小” 标准

最佳平方逼近的概念与解法

$H_n= \operatorname { Span} \{ \varphi _0( x) , \varphi _1( x) , . . . , \varphi _n( x) \}$ 是 $\varphi_i(x)$ 张成的线性空间

定理5.7 设 $f(x)\in C[a,b],p^*(x)\in H_n$ ，在 $H_n$ 中， $p^* ( x)$ 是 $f( x)$ 最佳平方逼近的函数 $\Leftrightarrow(f-p^*,\varphi_j)=0,j=0,1,...,n$ 其中， $\{ \varphi _0( x) , \varphi _1( x) , . . . , \varphi _n( x) \}$ 为子空间 $H_n$ 的一组基

$( \Rightarrow )$ $p^*(x)=\sum c_i^*\varphi _i(x)$ 代入 $(f-p^*,\varphi_j)=0$ 得 $(f-\sum c_i^*\varphi _i,\varphi_j)=0$
则 $(f,\varphi_j)=(\sum c_i^*\varphi _i,\varphi_j)=\sum c_i^*(\varphi_i,\varphi_j)$
即：
$\begin{bmatrix}(\varphi_0,\varphi_0)&(\varphi_0,\varphi_1)&\cdots&(\varphi_0,\varphi_n)\\(\varphi_1,\varphi_0)&(\varphi_1,\varphi_1)&\cdots&(\varphi_1,\varphi_n)\\\vdots&\vdots&\cdots&\vdots\\(\varphi_n,\varphi_0)&(\varphi_n,\varphi_1)&\cdots&(\varphi_n,\varphi_n)\end{bmatrix}\begin{bmatrix}c_0^*\\c_1^*\\\vdots\\c_n^*\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix}$
从而求解系数 $c_i^*$
$( \Leftarrow )$ 若 $( f- p^*, \varphi _j) = 0, j= 0, 1, . . . , n$ 成立，对任意的 $p( x) \in H_n$ ，有
$\begin{aligned}(f-p,f-p)&=(f-p^*+p^*-p,f-p^*+p^*-p)\\&=(f-p^*,f-p^*)+2(f-p^*,p^*-p)+(p^*-p,p^*-p)\end{aligned}$
由于 $\left ( f- p^* , p^* - p\right ) = \sum _{j= 0}^n\left ( c_j^* - c_j\right ) \left ( f- p^* , \varphi _j\right ) = 0$ 及 $( p^* - p, p^* - p) \geq 0$ ，故 $(f-p,f-p)\geq(f-p^*,f-p^*).$
$p^*$ 在 $H_n$ 中是对 $f$ 的最佳平方逼近函数

即设 $f(x)\in C[a,b],p^*(x)\in H_n$ ，在 $H_n$ 中， $p^* ( x)$ 是对 $f( x)$ 最佳平方逼近的函数 $\Leftrightarrow$ 对任意的 $p( x) \in H_n$ 均有

$(f-p^*,p)=0$

定理5.8 设 $f( x) \in C[ a, b]$ 在子空间 $H_n$ 中，对 $f( x)$ 最佳平方逼近的函数是唯一的

正交函数系在最佳平方逼近中的应用

对于正交函数系， $(\varphi_{k},\varphi_{j})=\int\rho(x)\varphi_{k}(x)\varphi_{j}(x)dx=0,k\neq j$

$\begin{bmatrix}(\varphi_0,\varphi_0)&(\varphi_0,\varphi_1)&\cdots&(\varphi_0,\varphi_n)\\(\varphi_1,\varphi_0)&(\varphi_1,\varphi_1)&\cdots&(\varphi_1,\varphi_n)\\\vdots&\vdots&\cdots&\vdots\\(\varphi_n,\varphi_0)&(\varphi_n,\varphi_1)&\cdots&(\varphi_n,\varphi_n)\end{bmatrix}\begin{bmatrix}c_0\\c_1\\\vdots\\c_n\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix}$

$\Rightarrow\begin{bmatrix}(\varphi_0,\varphi_0)\\&(\varphi_1,\varphi_1)\\&&\ddots\\&&&(\varphi_n,\varphi_n)\end{bmatrix}\begin{bmatrix}c_0\\c_1\\\vdots\\c_n\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix}$

$\Rightarrow c_k=\frac{(f,\varphi_k)}{(\varphi_k,\varphi_k)},\quad k=0,1,2,...,n$

曲线拟合

与插值的一个非常大的区别就是曲线拟合的函数 $y^*(x)$ 不要求经过所有数据点。

最小二乘问题

最小二乘问题的矩阵表示

最小二乘解的特征

最小二乘法的精度

正交多项式用于曲线拟合

数值积分

目的是求一些牛顿-莱布尼茨积分公式无法求解的积分函数

求积公式及其代数精度

一求积公式的一般形式：

$\int_a^bf(x)dx\approx\sum_{k=0}^n\lambda_kf(x_k)\tag{6.1}$

式中 $x_k( k= 0, 1, \cdots , n)$ 称为求积节点，它们满足 :

$a\leq x_0<x_1<\ldots<x_n\leq b$

$\lambda _{k}( k= 0, 1, \cdots , n)$ 称为求积系数，与被积函数无关。

当求积节点与求积系数确定了以后，求积公式就确定了，因此任务是确定求积节点和求积系数。

截断误差或余项：

$R_n=\int_a^bf(x)dx-\sum_{k=0}^n\lambda_kf(x_k)$

代数精度

对求积公式(6.1)，当 $f(x)$ 为任何次数不高于 $m$ 的多项式时都成立，而当 $f(x)$ 为某个 $m+1$ 次多项式时不成立，则称它具有 $m$ 次代

数精度。

如何求解代数精度：对求积公式(6.1)，当 $f(x)$ 为 $1,x,x^2,\cdots,x^n$ 时，求积公式均成立，则对于任何次数不高于 $m$ 的多项式求积公式也必然成立。

差值型求积公式

利用插值多项式 $p_n(x)$ 逼近代替 $f(x)$ 计算积分

在 $\left [ a, b\right ]$ 上取 $a\leq x_0< x_1< \ldots < x_m\leq b$ 。构造 $f$ 的 $n$ 次Lagrange插值基函数

$p_n(x)=\sum_{k=0}^nl_k(x)f(x_k),l_k(x)=\prod_{i=0}^n\frac{x-x_i}{x_k-x_i},k=0,1,\cdots,n$

$\int_a^bf(x)dx\approx\sum_{k=0}^n\left(\int_a^bl_k(x)\mathrm{d}x\right)f(x_k)\tag{6.1.1}$

$\lambda_k^{(n)}=\int_a^bl_k(x)\mathrm{d}x=\int_a^b\prod_{i=0\atop i\neq k}^n\frac{x-x_i}{x_k-x_i}\mathrm{d}x,k=0,1,\cdots,n\tag{6.2}$

其中， $\lambda_k^{(n)}$ 由节点决定与 $f(x)$ 无关。

设函数 $f(x)$ 在区间 $[a,b]$ 上足够光滑,则由定理5.1得

$f(x)=\sum_{k=0}^nl_k\left(x\right)f(x_k)+\frac{f^{(n+1)}\left(\xi\right)}{\left(n+1\right)!}\prod_{j=0}^n\left(x-x_j\right)$

其中 $x\in[a,b],\xi=\xi(x)\in(a,b)$ 因此，可得

$R_n=\int_a^bf(x)\mathrm{d}x-\sum_{k=0}^n\lambda_k^{(n)}f(x_k)=\int_a^b[f(x)-L_n(x)]\mathrm{d}x\\=\sum_{k=0}^n\left(\int_a^bl_k\left(x\right)dx\right)f(x_k)+\int_a^b\frac{f^{(n+1)}\left(\xi\right)}{\left(n+1\right)!}\prod_{j=0}^n\left(x-x_j\right)dx-\sum_{k=0}^n\left(\int_a^bl_k^{\prime}(x)\mathrm{d}x\right)f(x_k)\\=\int_a^b \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{j=0}^n\left(x-x_j\right)dx$