数值分析 周维祺
{f1(x1,…,xn)=0⋮fn(x1,…,xn)=0\begin{dcases}f_1(x_1,\ldots,x_n)=0 \\ \quad\quad\quad\vdots \\ f_n(x_1,\ldots,x_n)=0\end{dcases} ⎩⎨⎧f1(x1,…,xn)=0⋮fn(x1,…,xn)=0
x=(x1,…,xn)∈Rn,F=(f1,…,fn):Rn→Rnx=(x_1,\ldots,x_n)\in\mathbb R^n, F=(f_1,\ldots,f_n): \mathbb R^n\to\mathbb R^n x=(x1,…,xn)∈Rn,F=(f1,…,fn):Rn→Rn
F(x)=0⇔{f1(x1,…,xn)=0⋮fn(x1,…,xn)=0F(x)=0 \Leftrightarrow \begin{dcases}f_1(x_1,\ldots,x_n)=0 \\ \quad\quad\quad\vdots \\ f_n(x_1,\ldots,x_n)=0\end{dcases} F(x)=0⇔⎩⎨⎧f1(x1,…,xn)=0⋮fn(x1,…,xn)=0
构造Ω\OmegaΩ上压缩映射Φ:Rn→Rn\Phi:\mathbb R^n\to\mathbb R^nΦ:Rn→Rn，使其不动点x∗x^*x∗是F(x)=0F(x)=0F(x)=0的解，从而有迭代法x(k+1)=Φ(x(k))x^{(k+1)}=\Phi(x^{(k)})x(k+1)=Φ(x(k))
求{x(5+x2+y2)=1x+y=y4\begin{dcases}x(5+x^2+y^2)=1 \\ x+y=y^4\end{dcases}{x(5+x2+y2)=1x+y=y4在x,y∈[0,2]x,y\in[0,2]x,y∈[0,2]上的根
以下用不动点法求解
{x=(5+x2+y2)−1y=(x+y)1/4\begin{dcases}x=(5+x^2+y^2)^{-1} \\ y=(x+y)^{1/4}\end{dcases}{x=(5+x2+y2)−1y=(x+y)1/4, Φ:((5+x2+y2)−1,(x+y)1/4)\Phi:\left((5+x^2+y^2)^{-1}, (x+y)^{1/4}\right)Φ:((5+x2+y2)−1,(x+y)1/4)
设Φ(x)=(Φ1(x),…,Φn(x))\Phi(x)=\left(\Phi_1(x),\ldots, \Phi_n(x)\right)Φ(x)=(Φ1(x),…,Φn(x))，其Jacobi矩阵为
JΦ=(∂Φ1∂x1…∂Φ1∂xn⋮⋱⋮∂Φn∂x1…∂Φn∂xn)J_{\Phi}=\begin{pmatrix} \frac{\partial \Phi_1}{\partial x_1} &\ldots & \frac{\partial \Phi_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial \Phi_n}{\partial x_1} &\ldots & \frac{\partial \Phi_n}{\partial x_n} \end{pmatrix} JΦ=⎝⎛∂x1∂Φ1⋮∂x1∂Φn…⋱…∂xn∂Φ1⋮∂xn∂Φn⎠⎞
则在凸集Ω\OmegaΩ上有∥Φ(x)−Φ(y)∥≤supξ∈Ω∥JΦ(ξ)∥⋅∥x−y∥\|\Phi(x)-\Phi(y)\|\le\sup\limits_{\xi\in\Omega}\|J_{\Phi}(\xi)\|\cdot\|x-y\|∥Φ(x)−Φ(y)∥≤ξ∈Ωsup∥JΦ(ξ)∥⋅∥x−y∥
此处∥⋅∥\|\cdot\|∥⋅∥是任意的向量范数和所对应的矩阵算子范数
称Ω\OmegaΩ是凸集，若其中任意两点连线段上所有的点都在Ω\OmegaΩ中
连线的直线方程：x+t(y−x)x+t(y-x)x+t(y−x)； 连线段：t∈[0,1]t\in[0,1]t∈[0,1]
Ω\OmegaΩ是凸集：∀x,y∈Ω,t∈[0,1]\forall x,y\in\Omega, t\in[0,1]∀x,y∈Ω,t∈[0,1], 都有(1−t)x+ty∈Ω(1-t)x+ty\in\Omega(1−t)x+ty∈Ω
令Ω={(x,y):0≤x≤0.4,0.8≤y≤1.2}\Omega=\{(x,y): 0\le x\le 0.4, 0.8\le y\le 1.2\}Ω={(x,y):0≤x≤0.4,0.8≤y≤1.2},
Φ((xy))=((5+x2+y2)−1(x+y)1/4)\Phi(\begin{pmatrix}x \\ y\end{pmatrix})=\begin{pmatrix}(5+x^2+y^2)^{-1} \\ (x+y)^{1/4} \end{pmatrix} Φ((xy))=((5+x2+y2)−1(x+y)1/4)
验证Φ\PhiΦ是Ω\OmegaΩ上的压缩映射
x(k+1)=x(k)−(JF(x(k)))−1F(x(k))x^{(k+1)}=x^{(k)}-\left(J_F(x^{(k)})\right)^{-1}F(x^{(k)}) x(k+1)=x(k)−(JF(x(k)))−1F(x(k))
先直接或迭代求解
JF(x(k))y(k)=F(x(k))J_F(x^{(k)})y^{(k)}=F(x^{(k)}) JF(x(k))y(k)=F(x(k))
再令
x(k+1)=x(k)−y(k)x^{(k+1)}=x^{(k)}-y^{(k)} x(k+1)=x(k)−y(k)
用牛顿法求{x(5+x2+y2)=1x+y=y4\begin{dcases}x(5+x^2+y^2)=1 \\ x+y=y^4\end{dcases}{x(5+x2+y2)=1x+y=y4的一个根
以(0.2,1)(0.2,1)(0.2,1)为初值，作一步计算
设x∗∈Ω⊂Rnx^*\in\Omega\subset\mathbb R^nx∗∈Ω⊂Rn是FFF的一个根，JFJ_FJF存在且连续，并在Ω\OmegaΩ上可逆，则存在δ>0\delta>0δ>0，使得对满足∥x∗−x(0)∥<δ\|x^*-x^{(0)}\|<\delta∥x∗−x(0)∥<δ的所有初值x(0)x^{(0)}x(0)，牛顿法都超线性收敛；若还存在常树使∥JF(x∗)−JF(x)∥≤L∥x−x∗∥\|J_F(x^*)-J_F(x)\|\le L\|x-x^*\|∥JF(x∗)−JF(x)∥≤L∥x−x∗∥对所有满足∥x∗−x∥<δ\|x^*-x\|<\delta∥x∗−x∥<δ的xxx都成立，则该法平方收敛