Numerical solution of equations
Introduced| English | Meaning |
|---|---|
| root/ruːt/ | Values of a variable that make an equation or polynomial expression equal to zero. |
| numerical method/njuːˈmerɪkl ˈmeθəd/ | numerical method |
| accuracy/ˈækjʊrəsi/ | How close a measurement is to the true value. |
| sign change/saɪn tʃeɪndʒ/ | A change from a positive value to a negative value or from a negative value to a positive value. |
| iteration/ˌɪtəˈreɪʃn/ | Repeating a sequence of instructions or calculations. |
| converge/kənˈvɜːdʒ/ | To approach a definite limiting value or object as a sequence, process or series progresses. |
| iterative formula/ˈɪtərətɪv ˈfɔːmjʊlə/ | A rule that calculates a new approximation or term from one or more preceding values. |
| rearrangement/ˌriːəˈreɪndʒmənt/ | rearrangement |
| diverge/daɪˈvɜːdʒ/ | Fails to approach a finite limit, in the context of a sequence or the partial sums of a series. |
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:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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)?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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