解一元方程组

约 401 个字 预计阅读时间 1 分钟

二分法

介值定理

终止条件

• \(|p_N-p_{N-1}|<\epsilon\)
  • 数列可能发散
  • 没有一个绝对的标准来判断误差
• \(\frac{|p_N-p_{N-1}|}{|p_N|}<\epsilon\)

二分法精度：\(|p_N-p_{N-1}|<\frac{b-1}{2^n}\)

优点：

• 较简单，只需要是连续函数就行
• 总是能收敛

缺点：

• 收敛慢，
• 没法找重根
• 找到最初范围较难

p54 13，15

不动点迭代法

将\(f(x)=0\)转化为\(x=g(x)\)，然后从\(p_0\)开始，令\(p_n=g(p_{n-1})\)，进行迭代

收敛条件

Let \(g\in C[a,b]\) be such that \(g(x) \in [a, b]\), for all \(x\) in \([a, b]\). Suppose, in addition, that \(g’\) exists on \((a, b)\) and that a constant \(0 < k < 1\) exists with \(|g’(x)| \leq k\) for all \(x \in (a, b)\). Then, for any number \(p_0\) in \([a, b]\), the sequence defined by \(p_n = g( p_n – 1 ), n \geq 1\), converges to the unique fixed point \(p\) in \([a, b]\).

若\(g\)满足不动点迭代的条件，则可以通过 \(|p_n-p|\leq \frac{1}{1-k}|p_{n+1}-p_n|\ and\ |p_n-p|\leq \frac{k^n}{1-k}|p_{1}-p_0|\) 来判断精度

牛顿法

利用切线逼近零点

\(0=f(p)\approx f(p_0)+f'(p_0)(p-p_0) \rightarrow p\approx p_0-\frac{f(p_0)}{f'(p_0)}\)

由此进行迭代，有\(p_n=p_{n-1}-\frac{f(p_{n-1})}{f'(p_{n-1})}\)

迭代法误差分析

误差分析

如果\(\{p_n\}\)收敛于\(p\)，若存在\(\alpha,\lambda\)使\(\lim_{n\rightarrow \infty}\frac{|p_{n+1}-p|}{|p_n-p|^{\alpha}}=\lambda\)，则

1. \(\alpha=1\)，线性收敛
2. \(\alpha=2\)，二次收敛

what if the root is not simple

If \(p\) is a root of \(f\) of multiplicity \(m\), then \(f(x) = (x – p)^mq(x)\ and\ q(p)\neq 0\),then \(f'(x)=m(x-p)^{m-1}q(x)+(x-p)^mq'(x)\)