Fixed-point iteration
Introduced| English | Meaning |
|---|---|
| fixed-point iteration | A numerical method that rearranges f(x) = 0 as x = g(x) and repeats x_(n+1) = g(x_n). |
| continuous/kənˈtɪnjuːəs/ | Changing without a break or jump, or taking every value within an interval. |
| iteration/ˌɪtəˈreɪʃn/ | Repeating a sequence of instructions or calculations. |
| staircase | An iteration diagram whose steps approach the root from one side. |
| cobweb | An iteration diagram that spirals in, with values falling either side of the root. |
| diverges/daɪˈvɜːdʒɪz/ | Fails to approach a finite limit, in the context of a sequence or the partial sums of a series. |
Newton's cubic in Wallis's Algebra, 1685
- In 1685, John Wallis printed an example from Isaac Newton in his book A Treatise of Algebra: the cubic $x^3 - 2x - 5 = 0$. It has no neat solution, yet Newton found its root to many decimal places by improving a guess again and again.
- Today, calculators do the same thing. In P3 you learn the simplest version: fixed-point iteration 不动点迭代.
Locating the root first
- If $f$ is continuous 连续的 on $[a, b]$ and $f(a)$ and $f(b)$ have opposite signs, then $f(x) = 0$ has a root between $a$ and $b$.
- For $f(x) = x^3 - 2x - 5$: $f(2) = -1 < 0$ and $f(3) = 16 > 0$, so a root lies in $(2, 3)$.
$f(x) = x^3 - 3x + 1$ has a root between 0 and 1.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$f(0) = 1$ and $f(1) = -1$; $f$ is continuous, so the sign change shows a root.
Rearrange, then iterate
- Rearrange $f(x) = 0$ into the form $x = g(x)$, then use the iteration 迭代 $x_{n+1} = g(x_n)$ from a starting value $x_0$.
- $x^2 - x - 2 = 0$ becomes $x = \sqrt{x + 2}$. From $x_0 = 1$: $1.7321, 1.9319, 1.9829, 1.9957, \dots \to 2$, where $y = x$ meets $y = \sqrt{x + 2}$.
Fixed-point iteration
Rearrange the equation as x=g(x), choose a starting value and iterate
Compare the model with the worked case and explain one change.
Use $x_{n+1} = \sqrt{x_n + 3}$ with $x_0 = 2$. Find $x_1$ to 4 d.p.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$x_1 = \sqrt{5} = 2.23607$.
Which is a correct rearrangement of $x^3 + 4x - 7 = 0$?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$4x = 7 - x^3$. The others change a sign or move a term wrongly.
Worked example: Newton's cubic
Show that $x^3 - 2x - 5 = 0$ can be written as $x = \sqrt[3]{2x + 5}$. Use $x_0 = 2$ to find $x_1$, $x_2$, $x_3$ to 4 d.p., then show the root is $2.0946$ to 4 d.p.
- Rearrange: $x^3 = 2x + 5$, so $x = \sqrt[3]{2x + 5}$.
- Iterate: $x_1 = \sqrt[3]{9} = 2.0801$, $x_2 = 2.0924$, $x_3 = 2.0942$.
- Prove the 4 d.p. value: $f(2.09455) = -0.00002 < 0$ and $f(2.09465) = 0.0011 > 0$. There is a sign change and $f$ is continuous, so the root lies in $(2.09455, 2.09465)$ and is $2.0946$ to 4 d.p.
To show that a root is $1.732$ to 3 d.p., which values of $x$ do you test?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The bounds of 1.732 to 3 d.p. are $1.732 \pm 0.0005$.
Staircase or cobweb?
- On a graph, draw $y = x$ and $y = g(x)$ and move between them. If $g$ is increasing, the path is a staircase 阶梯图; if $g$ is decreasing, it spirals in a cobweb 蛛网图.
- $x_{n+1} = e^{-x_n}$ from $x_0 = 1$ gives $0.3679, 0.6922, 0.5005, 0.6062, \dots$ — values jump either side of the root, a cobweb.
Iterates $0.37, 0.69, 0.50, 0.61, 0.55$ approach a root. What does the diagram look like?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Values alternating above and below the root give a cobweb; $g$ is decreasing.
When iteration fails
- Not every rearrangement works. From the same cubic, $x = \dfrac{x^3 - 5}{2}$ with $x_0 = 2.1$ gives $2.131, 2.335, 3.867, \dots$ — it diverges 发散.
- An iteration converges when $g(x)$ is not too steep near the root: the gradient must lie between $-1$ and $1$. Here $g'(x) = 1.5x^2$, which is about 6.6 near the root, so the values run away.
Every rearrangement $x = g(x)$ of an equation converges if $x_0$ is close to the root.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
If $g$ is steep near the root ($|g'(x)| > 1$), the iterates move away.
Stopping when two iterates agree is not a proof. $x_3 = 2.0942$ and $x_4 = 2.0945$ do not show that the root is $2.0945$. For "show that the root is … to 4 d.p.", test the interval bounds $\pm 0.00005$ for a sign change, and state that the function is continuous.
Locate a root with a sign change of a continuous function, rearrange $f(x) = 0$ as $x = g(x)$ and iterate $x_{n+1} = g(x_n)$. A gentle $g$ converges in a staircase or cobweb; a steep one diverges. Prove a rounded root by a sign change across its bounds.
Show that $x^3 + x - 3 = 0$ has a root in $(1, 2)$. Use $x_{n+1} = \sqrt[3]{3 - x_n}$ with $x_0 = 1$ to find $x_1$, $x_2$, $x_3$ to 4 d.p.
Locate, then iterate.