Say I am dealing with $f(x) = x^3+2x+1$ and I need to come up a fixed point iteration to find its root, that has a second order convergence. How should one approach this question? Should I just compute a couple formulae and see which one converge quadratically? Is there a better method than that?
Asked
Active
Viewed 313 times
1
-
Why can't you just use the Newton-Raphson method since it is of order two? – Moo Jun 17 '19 at 21:43
-
@Moo Had to use fixed point iteration from a past paper I was doing :( – UnsinkableSam Jun 17 '19 at 21:52
2 Answers
2
Okay, the question has been changed, so I'm going to edit my answer:
First, why can't you just use something like Newton's method (applied to the function $x^3+2x+1$)? Note this is a fixed point method for the function $g(x)=x-\frac{f(x)}{f'(x)}.$ It will converge quadratically because your zero is simple.
If you don't like that, then the most naive thing that you could do is define an iteration $$x_{n+1}=x_n^3+3x_n+1,$$ then use Aitken extrapolation, which will be second order. This will converge to some real $x$ with $x=x^3+3x+1,$ so it will satisfy $x^3+2x+1=0.$ Thus, it will be a root.
Generally, Aitken extrapolation is a good way to take a first-order fixed point method and extend it to one which is second order (to answer the title's question).
cmk
- 12,303
-
Wait, correct me if I am wrong, a fixed point iteration is when a function $g(x)=x$ so wouldn't your example not be an example of fixed-point iteration (Sorry I should've said it's to find the root of f(x)) – UnsinkableSam Jun 17 '19 at 21:51
-
Yes, so when the above iteration converges to some $x$, then we'll have $x=x^3+2x+1,$ which is what it means for $f(x)=x^3+2x+1$ to have a fixed point. Are you saying that you, instead, want to find when $x^3+2x+1=0?$ And if you want to find zeros, then why can't you just use Newton's method? – cmk Jun 17 '19 at 21:59
-
@JustWandering I've edited my answer according to your edit. Changing it to wanting a root instead of a fixed point doesn't change the answer too much. – cmk Jun 17 '19 at 22:23
-
0
To find the root of a function $f$, Newton's method should come to mind first: $$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} . $$
From you comment, it seems you are not aware that it is a fixed point iteration also, because if $x_\star$ is a fixed point, and $f'(x_\star) \neq 0$, then $f(x_\star) = 0$.
user66081
- 3,987
- 17
- 29