Numerical solution of equations
| English | Chinese | Pinyin |
|---|---|---|
| root | 根 | gēn |
| numerical method | 数值方法 | shù zhí fāng fǎ |
| accuracy | 精度 | jīng dù |
| sign change | 变号 | biàn hào |
| iteration | 迭代 | dié dài |
| converge | 收敛 | shōu liǎn |
| iterative formula | 迭代公式 | dié dài gōng shì |
| rearrangement | 重新排列 | chóng xīn pái liè |
| diverge | 发散 | fā sàn |
The root 根 you can't see
- Some equations have no neat algebraic solution. $x^3 + x - 1 = 0$ can't be factorised.
- But you know a root exists between $0$ and $1$ because the function changes sign. Numerical methods 数值方法 let you find it to any accuracy 精度.
Locating a root
- Many equations can't be solved exactly. A root is a solution.
- Sign change 变号: if $f(a)$ and $f(b)$ have opposite signs (and no break between them), a root lies between $a$ and $b$.
Worked example. $f(x) = x^3 + x - 1$. $f(0) = -1$ (negative), $f(1) = 1$ (positive). Sign change → root between $0$ and $1$.
Sign change doesn't guarantee exactly one root. There could be 3 roots (or any odd number) between $a$ and $b$. The sign change only tells you there's at least one.
Iteration 迭代: step up to the curve and across to y = x; the steps converge 收敛 to a root
Where is the root?
y = ax³ + bx² + cx + d
A root is where the curve crosses zero. A sign change in f(x) traps a root between two x-values.
If f(a) and f(b) have opposite signs (and f is continuous between them), then between a and b there is:
A sign change of a continuous function guarantees a root between a and b.
f(x) = x³ + x − 1. f(0) = −1 and f(1) = 1. Between which two integers is the root?
Sign change between 0 and 1 (f(0) < 0, f(1) > 0), so root is between 0 and 1.
Iteration
- Rearrange the equation into the form $x = F(x)$.
- Use the iterative formula 迭代公式 $x_{n+1} = F(x_n)$ from a first guess $x_0$.
- If the values settle, they converge to a root. Keep going until steady to the asked accuracy.
Iteration: starting from $x_0$, each step applies $F$ and reflects in $y = x$. The cobweb spirals into the fixed point — the root.
An iterative formula has the form:
Iteration repeatedly applies x_{n+1} = F(x_n) from a first guess.
If the iteration values settle down to a steady number, they have converged to a root.
Convergence means the sequence approaches a fixed value — a root of the equation.
Using x_{n+1} = ∛(1 − x_n) with x₀ = 0, what is x₁ (2 dp)?
x₁ = ∛(1 − 0) = ∛1 = 1.
Worked example — iteration
- Solve $x^3 + x - 1 = 0$ using $x_{n+1} = \sqrt[3]{1 - x_n}$, starting from $x_0 = 0.5$.
- $x_1 = \sqrt[3]{0.5} = 0.794$, $x_2 = \sqrt[3]{0.206} = 0.591$, $x_3 = \sqrt[3]{0.409} = 0.742$, ...
- The values converge to $x \approx 0.682$.
An iteration x_{n+1} = F(x_n) always converges regardless of the starting value.
Convergence requires |F′(x)| < 1 near the root. Poor rearrangements or starting values can diverge.
Choosing a rearrangement 重新排列
- Not all rearrangements converge. The iteration $x_{n+1} = F(x_n)$ converges when $|F'(x)| < 1$ near the root.
- If it diverges 发散 (values move away), try a different rearrangement.
You've got it
- a sign change of $f$ between $a$ and $b$ traps a root in between
- iteration: $x_{n+1} = F(x_n)$ from a starting guess
- if the values converge (settle), they approach a root
- convergence requires $|F'(x)| < 1$ near the root