数值分析-期末考题

非线性求解方程组

• 不动点迭代法、牛顿迭代法：两者之间的关系、收敛性、误差、稳定性
  • 会设计一个不动点
  • 牛顿法推广：和割线法的关系
  • 什么时候收敛
• 方程组的牛顿迭代法：需要知道基本思想
• 二分法：不排除

---

Fixed-point Iteration

• fixed point: the real number $r$ is a fixed point of the function $g$ if $g(r)=r$

def fixed_point_iteration(f, x0, tol=1e-6, maxiter=100):
    x = x0
    for i in range(maxiter):
        x1 = f(x)
        if abs(x1 - x) < tol:
            return x1
        x = x1
    return x

The FPI function can be different.

For equation $x^3+x-1=0$, there exists different FPI functions, along with different convergence speed.

different FPI functions, different convergence speed.

• Linear convergence: Let ${\epsilon }_i=\frac{{\epsilon }_{i-1}}{2}$ denote the error at step $i$ of an iterative method. If

$$\underset{i\to \infty }{\lim }\frac{{\epsilon }_{i+1}}{{\epsilon }_i}=S<1$$

the method is said to obey linear convergence with rate S

Assume that $g$ is continuously differentiable, that $g(r)=r$ , and that $S=|g^{\prime }(r)|<1$ . Then Fixed-Point Iteration converges linearly with rate S to the fixed point $r$ for initial guesses sufficiently close to $r$ .

Convergent Types

• Locally convergent: An iterative method is called locally convergent to $r$ if the method converges to r for initial guesses sufficiently close to $r$

• Globally convergent: For any $x\in I$, the method converges to $r$ for any initial guesses of $x$.

The Bisection Method is guaranteed to converge linearly. Fixed-Point Iteration is only locally convergent, and when it converges it is linearly convergent. Both methods require one function evaluation per step. The bisection cuts uncertainty by $1/2$ for each step, compared with approximately $S=|g^{\prime }(r)|$ for FPI. Therefore, Fixed-Point Iteration may be faster or slower than bisection, depending on whether S is smaller or larger than 1/2. Newton’s Method, a particularly refined version of FPI, where $S$ is designed to be zero

Cases when FPI works

1. Function $f(x)$ is continue in $[a,b]$
   1. $\forall x\in [a,b],a⩽f(x)⩽b$ , then there exists fixed-point.
   2. Based on 1, if $\exists L\in (0,1),s.t.|f(x_1)-f(x_2)⩽L(x_1-x_2)|\forall x_1,x_2\in [a,b]$
      • $f(x)$ exists only one global fixed-point.
      • Error satisfies $|x_k-x^{\ast }|\le \frac{L}{1-L}|x_k-x_{k-1}|\le \cdots \le \frac{L^k}{1-L}|x_1-x_0|$

Local Convergence Theorem: Let $x^{\ast }$ be the fixed-point, if $f^{\prime }(x)$ is continue in $[a,b]$ and $|f^{\prime }(x^{\ast })|<1$ .Then the FPI is locally convergent.

---

Link to original

Newton's Method

x_0 & =\text { initial guess } \ x_{i+1} & =x_i-\frac{f\left(x_i\right)}{f^{\prime}\left(x_i\right)} \text { for } i=0,1,2, \ldots \end{aligned}$$

If $f(x)\in C^2(\mathbb{R})$ is a monotonically increasing convex function, and $f(r)=0$ , then $r$ is the only root and for $\forall x_0\in \mathbb{R}$ , Newton’s method will converges to $r$ .

Convergence Speed

Based on the Rate of convergence - Wikipedia, the order of convergence² and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence $(x_n)$ that converges to $x^{\ast }$ is said to have order of convergence $q\ge 1$ and the rate of convergence $\mu$ if :

$$\underset{n\to \infty }{\lim }\frac{\left|x_{n+1}-x^{\ast }\right|}{{\left|x_n-x^{\ast }\right|}^q}=\mu$$

The rate of convergence $\mu$ is also called the asymptotic error constant.

• $q=1$ is called linear convergence if, and the sequence is said to _converge Q-linearly to $L$.
• $q=2$ is called quadratic convergence.
• $q=3$ is called cubic convergence.
• Etc.

Empirically, if the function $g\in C^p(a,b)$ is convergent to $x^{\ast }$ ，and its $p$ differential $g^{(p)}(x^{\ast })\ne 0$ , while $g^{(q)}(x^{\ast })=0,q=1,2,\cdots ,p-1$ then it’s said that $x_{i+1}=g(x_i)$ has $p$ order convergence speed, and it’s local convergent. For FPI, we have:

$$\underset{i\to \infty }{\lim }\frac{e_{i+1}}{e_i^p}=\frac{|g^{(p)}(x^{\ast })|}{p!}$$

Let $f\in C^2[a,b]$ and $f(r)=0$. If $f^{\prime }(r)\ne 0$, then Newton’s Method is locally and quadratically convergent to $r$. The error $e_i$ at step $i$ satisfies

$$\underset{i\to \infty }{\lim }\frac{e_{i+1}}{e_i^2}=\frac{f^{\prime \prime }(r)}{2f^{\prime }(r)}$$

If $f\in C^{(m+1)}[a,b]$ , which contains a root $r$ of multiplicity $m>1$ , then Newton’s Method’s error $e_i$ satisfies

$$\underset{t\to \infty }{\lim }\frac{e_{i+1}}{e_i}=\frac{m-1}{m}$$

converges locally and linearly to $r$ .

If $f\in C^{(m+1)}[a,b]$ , which contains a root $r$ of multiplicity $m>1$ , and $f^{(m+1)}(r)\ne 0$ , then Modified Newton’s Method

$$x_{i+1}=x_i-\frac{mf(x_i)}{f^{{}^{\prime }}(x_i)}$$

error $e_i$ satisfies

$$\underset{t\to \infty }{\lim }\frac{e_{i+1}}{e_i^2}=\frac{1}{m(m+1)}\left|\frac{f^{(m+1)}(r)}{f^{(m)}(r)}\right|$$

converges locally and quadratically to $r$ .

Examples of error approximation

Link to original

2

如果 $f(x)\in C^m(\mathbb{R})$ , 并满足 $f(r)=0,f^{\prime }(r)\ne 0,$ $f^{(m)}(r)\ne 0(m>2)$ $f^{\prime \prime }(r)=\cdots =f^{(m-1)}(r)=0$ , ，试分析标准牛顿迭代法的收敛性及误差。

$$f(r)=f(x_i)+(r-x_i)f^{\prime }(x_i)+(r-x_i{)}^m\frac{f^{(m)}(\xi )}{m!}$$

化简得到:

$$x_i-\frac{f(x_i)}{f^{\prime }(x_i)}-r=(r-x_i{)}^m\frac{f^{(m)}(\xi )}{m!f^{\prime }(x_i)}$$

即：

$$\frac{e_{i+1}}{e_i^m}=\frac{f^{(m)}(\xi )}{m!f^{\prime }(x_i)}$$

牛顿法求解非线性方程组

线性方程组的直接解法

• 高斯消元法
  • 与 LU 分解的联系与用途
• LU 三角分解
  • 使用高斯消元求解 LU 分解
  • LU 分解的用途：行列式
  • 部分主元概念
• 范数：某一个题包含，不是重点

( ${\Vert A\Vert }_{\infty }={\max }_{1\le i\le n}\left(\left|a_{i1}\right|+\cdots +\left|a_{in}\right|\right)$ )

Transclude of Chapter3--System-of-Equation#^g0ff5n

Transclude of Chapter3--System-of-Equation#pa--lu-factorization

线性方程组的迭代法

• 分析性质：是否收敛
• 设计+收敛性
• 每一种迭代方法都很重要，随机出一个考察

The generative form of iterative methods:

$$Q{x}_{k+1}=(Q-A)x_k+b$$

Where $Q$ is the Split Matrix. Rewrite it at fixed-point formula:

$$\begin{array}{rl}form:x_{k+1}& =(I-Q^{-1}A)x_k+Q^{-1}b\\ IterativeMatrix:G& =(I-Q^{-1}A)\end{array}$$

• Richardson: $Q=I$ : 单位严格行/列对角占优矩阵
• Jacobi: $Q=D$ ：严格行对角占优
• Gauss-Seidel: $Q=D+L$ ：严格行对角占优
• SOR： $Q=\frac{1}{\omega }(D+\omega L)$ ： $0<\omega <2$

以上判断收敛为充分条件；充要条件使用迭代矩阵 $G$ 的谱半径小于 1 判断。

对称正定线性方程组的解法

• 对称正定矩阵的定义和性质
• Cholesky 分解
• 对称正定矩阵的 SOR 迭代

Transclude of Chapter3--System-of-Equation#methods-for-symmetric-positive-definite-matrices

Cholesky 另外一种分解

矩阵特征值的数值解法

• 特征值估计：了解即可，理论部分不过多考察
• 幂法：一定要掌握，+各种变形
• QR 算法：必须，

Repeat step above until it stops. Finally the maximum eigenvalue is $\lambda =5$ ，its corresponding eigenvector $\mathbf{x}=\left[\begin{array}{c}\frac{3}{\sqrt{15}}\\ \frac{1}{\sqrt{15}}\\ \frac{2}{\sqrt{15}}\end{array}\right]$

Link to original

Other Kinds of Power Iteration

Other Kinds of Power Iteration

example of 位移逆幂法

假设我们要求解矩阵

$$A=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right]$$

的最大特征值和对应的特征向量。

具体步骤如下：

1. 初始化一个初始向量 $x^{(0)}$，可以是任意非零向量。

2. 对于每一次迭代 $k$，计算位移矩阵 $B=A-\mu I$，其中 $\mu$ 是一个位移量，通常选择接近所求特征值的值。

3. 解线性方程组 $B{x}^{(k+1)}=x^{(k)}$，得到新的迭代向量 $x^{(k+1)}$。

4. 归一化迭代向量 $x^{(k+1)}$，即 $x^{(k+1)}=\frac{x^{(k+1)}}{\Vert x^{(k+1)}\Vert }$。

5. 判断迭代是否收敛，如果满足收敛条件（如 $|x^{(k+1)}-x^{(k)}|<ϵ$），则停止迭代，否则返回步骤 2。

下面我们以 $\mu =10$ 为例，进行迭代计算。

首先，选择一个初始向量 $x^{(0)}=[1,1,1{]}^T$。

迭代计算如下：

$$\begin{array}{rl}k=0:& B=A-\mu I=\left[\begin{array}{ccc}-9& 2& 3\\ 4& -5& 6\\ 7& 8& -1\end{array}\right],x^{(1)}=B^{-1}{x}^{(0)}={\left[\begin{array}{ccc}-0.081& -0.027& 0.108\end{array}\right]}^T\\ k=1:& B=A-\mu I=\left[\begin{array}{ccc}-9& 2& 3\\ 4& -5& 6\\ 7& 8& -1\end{array}\right],x^{(2)}=B^{-1}{x}^{(1)}={\left[\begin{array}{ccc}-0.058& -0.086& 0.142\end{array}\right]}^T\\ k=2:& B=A-\mu I=\left[\begin{array}{ccc}-9& 2& 3\\ 4& -5& 6\\ 7& 8& -1\end{array}\right],x^{(3)}=B^{-1}{x}^{(2)}={\left[\begin{array}{ccc}-0.039& -0.112& 0.187\end{array}\right]}^T\\ & ⋮\end{array}$$

请注意，迭代过程中需要对迭代向量进行归一化，以保证迭代结果的正确性。

Link to original

![[Chapter7-Eigenvalues and singular values#|#^j17wmv]]

Example of Full QR Factorization.

Full QR Factorization

Householder Transformation

Since the transformation matrix $H$ in Householder transformation is symmetric orthogonal matrix, then we can replace $Q$ with $H$ . See the example below.

Householder transformation in QR factorization.

Use Householder transformation to apply QR factorization.

Householder Transformation

Link to original

QR Algorithm

The way the QR algorithm finds eigenvalues of a matrix A is to locate a similar matrix whose eigenvalues are obvious. An example of the latter is real Schur form.

Real Schur form: A matrix $T$ has real Schur form if it is upper triangular, except possibly for $2\times 2$ blocks on the main diagonal. For example, a matrix of the form

$$\left[\begin{array}{ccccc}x& x& x& x& x\\ & x& x& x& x\\ & & x& x& x\\ & & & & x\end{array}\right]$$

Has real Schur form.

Theorems about QR algorithm

Let’s consider the matrix A:

$$A=\left[\begin{array}{ccc}2& 1& 0\\ 1& 3& 1\\ 0& 1& 2\end{array}\right]$$

To find the eigenvalues of $A$ using the QR algorithm, we follow these steps:

1. Start by initializing $A_0$ as the given matrix $A$.

2. Compute the QR decomposition of $A_0$. Let $Q_0$ and $R_0$ be the resulting orthogonal and upper triangular matrices, respectively.

3. Update $A_1=R_0\cdot Q_0$ .

4. Repeat steps 2 and 3 until convergence or a desired number of iterations. Let $A_k$ be the matrix at the k-th iteration.

5. The eigenvalues of A are the diagonal elements of the final upper triangular matrix $A_k$.

Let’s go through the steps for our example:

Step 1:

$$A_0=\left[\begin{array}{ccc}2& 1& 0\\ 1& 3& 1\\ 0& 1& 2\end{array}\right]$$

Step 2: Compute the QR decomposition of $A_0$: $A_0=Q_0\cdot R_0$

Step 3: Update $A_1=R_0\cdot Q_0$

Step 4 : Repeat steps 2 and 3 until convergence or a desired number of iterations.

After a few iterations, we obtain the following matrices:

$$A_1=\left[\begin{array}{ccc}3.317& 2.317& 1.317\\ 0& 1.317& 0.317\\ 0& 0& -0.634\end{array}\right]$$ $$A_2=\left[\begin{array}{ccc}2.585& 1.585& 0.585\\ 0& 1.585& 0.585\\ 0& 0& -0.17\end{array}\right]$$ $$A_3=\left[\begin{array}{ccc}2.414& 1.414& 0.414\\ 0& 1.414& 0.414\\ 0& 0& -0.17\end{array}\right]$$

Step 5: The eigenvalues of A are the diagonal elements of the final upper triangular matrix $A_k$. In this case, the eigenvalues are:

$${\lambda }_1=2.414,{\lambda }_2=1.414,{\lambda }_3=-0.17$$

So, these are the eigenvalues of the given matrix $A$ using the QR algorithm.

Link to original

插值

• Language 插值，Newton 插值
• 利用插值插其它函数
• 基本的多项式插值与 Hermite 插值的区别与联系
• 分段插值：自然三次样条插值

example of Newton's Interpolation

Transclude of Chapter4--Polynomial-Interpolation#chebyshev-interpolation

example of Hermite interpolation with Newton's differences

example of Hermite interpolation with Newton's differences

Transclude of Chapter4--Polynomial-Interpolation#example

最小二乘法

• 最小二乘法，可能与作业结合起来：数值分析作业-拟合和最小二乘法
• 跟 QR 分解联系起来。

Least squares and QR decompostion

微分

• 数值积分精度外推：给定一个近似，要求你把它的精度提高
• 如何设计一个数值微分，达到给定精度给定解
• 分析给定数值微分的误差

text title here...

积分

• 设计外推数值积分
• 分析给定的数值积分
• GUASS积分的区间变换

梯形法则

积分公式：

$$I\left(f\right)={\int }_a^{b}f\left(x\right)dx\approx I\left(P_1\right)=\frac{h}{2}\left[f\left(a\right)+f\left(b\right)\right],h=b-a$$

误差：

$$E\left(f\right)=I\left(f\right)-I\left(P_1\right)={\int }_a^{b}E\left(x\right)dx=-\frac{h^3}{12}{f}^{\prime \prime }\left(\xi \right),\xi \in \left(a,b\right)$$

代数精度：1

开 -梯形法则：

$$I\left(f\right)={\int }_a^{b}f\left(x\right)dx\approx I\left(P_0\right)=hf\left(\frac{a+b}{2}\right),h=b-a$$

误差：

$$E\left(f\right)=I\left(f\right)-I\left(P_0\right)=\frac{h^3}{24}{f}^{\prime \prime }\left(\xi \right),\xi \in \left(a,b\right)$$

复合梯形法则

积分公式：

$$I(f)=\frac{\Delta h}{2}\left[f\left(a\right)+f\left(b\right)+2\sum _{i=1}^{m-1}f\left(x_i\right)\right]$$

误差：

$$E(f)=-\frac{\left(b-a\right)\Delta h^2}{12}{f}^{\prime \prime }\left(\xi \right),{\xi }_i\in \left(x_i,x_{i+1}\right),\xi \in \left(a,b\right)$$

Simpson 法则

积分公式：

$$I\left(f\right)={\int }_a^{b}f\left(x\right)dx\approx I\left(P_2\right)=\frac{h}{6}\left[f\left(a\right)+4f\left(\frac{a+b}{2}\right)+f\left(b\right)\right],h=b-a$$

误差：

$$E\left(f\right)=-\frac{h^5}{2880}{f}^{\prime \prime \prime \prime }\left(\xi \right),\xi \in \left(a,b\right)$$

代数精度：3

三点开 -Newton-Cote’s 积分

$$I\left(f\right)={\int }_a^{b}f\left(x\right)dx\approx I\left(P_2\right)=\frac{2h}{3}f\left(\frac{3a+b}{4}\right)-\frac{h}{3}f\left(\frac{a+b}{2}\right)+\frac{2h}{3}f\left(\frac{a+3b}{4}\right),h=b-a$$

误差：

$$E\left(f\right)=\frac{7h^5}{23040}{f}^{\prime \prime \prime \prime }\left(\xi \right),\xi \in \left(a,b\right)$$

复合 Simpson 法则

积分公式：

$$I(f)=\frac{\Delta h}{6}\left[f\left(a\right)+f\left(b\right)+2\sum _{i=1}^{m-1}f\left(x_i\right)+4\sum _{i=0}^{m-1}f\left(\frac{x_i+x_{i+1}}{2}\right)\right]$$

误差：

$$E(f)=-\frac{\left(b-a\right)\Delta h^4}{2880}{f}^{\prime \prime \prime \prime \prime }\left(\xi \right),{\xi }_i\in \left(x_i,x_{i+1}\right),\xi \in \left(a,b\right)$$

代数精度

代数精度求法

Romberg Integration

Romberg Integration

The main idea of Romberg integration is using Richardson Extrapolation to increase the accuracy of the integration.

text title here...

pseudocode of Romberg

Link to original

待定系数法

Undetermined Coefficients Method

高斯积分

Gauss Integration

Are the Newton–Cotes formulas optimal for their degree of precision, or can more powerful formulas be developed? In particular, if the requirement that evaluation points be evenly spaced is relaxed, are there better methods?

We pick out the most famous one to discuss in this section. Gaussian Quadrature has degree of precision $2n+1$ when $n+1$ points are used, double that of Newton–Cotes.

text title here...

Integration error:

$${\int }_a^{b}f\left(x\right)dx-\sum _{i=0}^n{A}_{i}f\left(x_i\right)=\frac{f^{(2n+2)}\left(\xi \right)}{\left(2n+2\right)!}{\int }_a^b\prod _{i=0}^n{\left(x-x_i\right)}^{2}dx,\xi \in \left(a,b\right)$$

There are mainly three ways to find $Q(x)$ :

1. Let $Q_{n+1}(x)=x^{n+1}+a_n{x}^n+\cdots +a_{1}x+a_0$ , $s.t.{\int }_a^b{Q}_{n+1}(x)x^{k}dx=0,k=0,1,\cdots ,n$
2. Given linearly independent functions $\{{\phi }_0(x),{\phi }_1(x),\cdots ,{\phi }_n(x)\}$ in interval $[a,b]$ , build orthogonality function using Gram-Schmidt
3. Legendre polynomials $L_n(x)=\frac{1}{2^n\cdot n!}\frac{d^n}{d{x}^n}(x^2-1{)}^n$

We usually use Legendre polynomials to compute numerical integration.

Gaussian Quadrature coefficients

approximate integrals on a general interval

approximate integrals on a general interval

Link to original